Lists highly divisible numbers, oeis squence: A002182

Question

My code works (as far as I can tell), so I'm looking mostly for readability and efficiency tips.

Goal of my code: Generate a list of all numbers that have more divisors than any lower number up to a certain limit. In other words this sequence: https://oeis.org/A002182

Background: The number of divisors of \$n=p_1^{k1} \times p_2^{k2} \times p_3^{k3}\$ is just \$(k_1+1)\times(k_2+1)\times(k_3+1)\$... so the primes themselves don't matter, just the set of exponents. Thus to be the smallest possible number with that number of divisors, the exponents are required be in order from largest (on the smallest primes) to smallest (on the largest primes).

My code breaks into 3 sections, the first figures out the largest prime needed. The second generates a list of candidate numbers which is a list of all numbers that fit the descending exponent requirement. Finally, the third part puts them in order and checks which of the candidates actually have more divisors than any previous numbers.

Final Random question: Is there a name for the middle algorithm? An algorithm that finds a list of all lists that are under a certain threshold? A more generic version would probably set pows[:marker] = [0] * marker instead, but in my case I only want descending lists.

from numpy import prod

def highlydiv(n):
    """ Returns a list of all numbers with more divisors than any lower numbers, up to a limit n """
    primeprod = 1
    plist =  []
    for p in gen_prime(50): #gen_prime: generates primes up to n, can just use [ 2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
        primeprod *= p
        if primeprod <= n:
            plist.append(p)
        else:
            break

    pows = [0 for x in plist]
    breakout = False
    candidate_list = []
    calcsum = 1
    while True:
        marker = 0
        pows[marker] += 1
        calcsum *= 2
        while calcsum > n:
            marker += 1
            if marker == len(pows):
                breakout = True
                break
            pows[marker] += 1
            pows[:marker] = [pows[marker]] * marker
            calcsum = prod([p**k for p, k in zip(plist, pows)])
        if breakout:
            break
        ndivs = prod([x+1 for x in pows])
        candidate_list.append((calcsum,ndivs))

    candidate_list.sort()
    maxdivs = 0
    final_list = []
    for candidate, ndivs in candidate_list:
        if ndivs > maxdivs:
            maxdivs = ndivs
            final_list.append(candidate)
    return final_list

print(highlydiv(1000000))

Answer 1

Consider writing your middle while loop as a separate function - it'll make breaking out of the inner loop easier.

For example, your code could look like this:

def highlydiv(n):
    plist = ...set up plist...
    candidates = divisor_candidates(n, plist)
    ...

def divisor_candidates(n, plist):
    ...set up calcSum, mark, pows, candidates...
    while True:
        ...
        while calcSum > n:
            marker += 1
            if marker > len(pows):
                return candidates
            pows[marker] += 1
            ...
        candidates.append(...)

and you get rid of the breakout flag.

Additionally, this makes the middle part of your program testable.

Answer 2

I'll be using PEP0008 the Python style guide as the bible for these suggestions and I suggest you give a thorough read because it offers a lot of good readability suggestions.

Line lengths should ideally be limited to 79 characters and it's suggested that you only have short comments after code. This line foes against both these points:

    for p in gen_prime(50): #gen_prime: generates primes up to n, can just use [ 2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Separate onto three lines, the comment is long and makes two separate (though related) points.

    #gen_prime: generates primes up to n
    #Can just use [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
    for p in gen_prime(50): 

Also I removed the double spacing around the numbers. I assume you did it to pad out the single digit numbers but it's not necessary.

    pows = [0 for x in plist]

This list comprehension isn't needed since the value is always just zero. It's slower, and will probably confuse people unfamiliar with them. You can just use list multiplication.

    pows = [0] * len(plist)

---

In general across your script you need more comments. You don't have any comments after the one about what gen_prime does even though it's a complicated algorithm. Comments will give context and allow a reader to understand why your code does what it does. This is valuable even for yourself, when reading scripts later.

Another big readability issue is whitespace. You only separate with blank whitespace lines for loops and functions, but separating distinct blocks of the process helps readability a lot. This is how I would arrange it:

def highlydiv(n):
    """ Returns a list of all numbers with more divisors than any lower numbers, up to a limit n """

    primeprod = 1
    plist =  []

    for p in gen_prime(50): #gen_prime: generates primes up to n, can just use [ 2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
        primeprod *= p
        if primeprod <= n:
            plist.append(p)
        else:
            break

    pows = [0 for x in plist]
    breakout = False
    candidate_list = []
    calcsum = 1

    while True:
        marker = 0
        pows[marker] += 1
        calcsum *= 2

        while calcsum > n:
            marker += 1
            if marker == len(pows):
                breakout = True
                break

            pows[marker] += 1
            pows[:marker] = [pows[marker]] * marker
            calcsum = prod([p**k for p, k in zip(plist, pows)])

        if breakout:
            break
        ndivs = prod([x+1 for x in pows])
        candidate_list.append((calcsum,ndivs))

    candidate_list.sort()
    maxdivs = 0
    final_list = []

    for candidate, ndivs in candidate_list:
        if ndivs > maxdivs:
            maxdivs = ndivs
            final_list.append(candidate)

    return final_list

Without adding any text, it's now easier to just focus on it one piece at a time rather than feeling like a wall of text.