# Lists highly divisible numbers, oeis squence: A002182

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))

• So many factorials in that sequence... Just a coincidence? – Caridorc Aug 13 '15 at 21:59
• Some code of mine generates this numbers upto 10 ** 231 in a pair of seconds, what is the performance of your code? – Caridorc Aug 16 '15 at 8:35
• My code was wrong, it generated only some of those numbers. – Caridorc Aug 16 '15 at 11:13
• Hi! Would you be able to provide the code for gen_prime as well ? Kind of hard to test your code at the moment. – Josay Aug 21 '15 at 14:29
• @Josay I didn't provide it because it would've made my code 3 times longer as it is highly optimized. You can just replace that line with for p in [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:. – Dan Aug 21 '15 at 15:52

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.

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.