# Divisor game cheating aid

This code outputs the smallest number with more divisors than the input:

from operator import mul
from math import sqrt, ceil

def next_prime_factor(n):
if n % 2 == 0:
return 2
for x in range(3, int(ceil(sqrt(n)) + 1), 2):
if n % x == 0:
return x
return int(n)

def factor(n):
factors=[]
number=int(n)
while number > 1:
f=next_prime_factor(number)
factors.append(f)
number /= float(f)
number=int(number)
if number==1:break

return list(factors)

def sundaram(max_n):
numbers = range(3, max_n+1, 2)
half = (max_n)/2
initial = 4
for step in xrange(3, max_n+1, 2):
for i in xrange(initial, half, step):
numbers[i-1] = 0
initial += 2*(step+1)

if initial > half:
x=filter(None, numbers) + [2] if filter(None, numbers) != None else [2]
return sorted(x)

def factor_count(n):
factors=factor(n)
primecounts=[]
primes_list=sundaram(int(sqrt(n)))
primes_list = primes_list if primes_list != None else [2]
for i in primes_list:
primecounts.append(factors.count(i))
return primecounts

def div_exps(pcount):
return [i+1 for i in pcount if i!=0]

def div_count(n):
pcount=factor_count(n)
div_count=reduce(mul,div_exps(pcount),1)
return div_count

def next_num(last_num):
if last_num == 1:
return 2
if last_num in sundaram(last_num+1):
return 4

plist=sundaram(int(sqrt(last_num))+1)

div_count_factors=factor(div_count(last_num))
num=1
for i in enumerate(div_count_factors):
num*=plist[i[0]]**(i[1]-1)

end_num=num
while 1:
if div_count(end_num)<=div_count(last_num):
end_num*=min(div_count_factors)
else:
break
return end_num

ans=next_num(input('Input the last number chosen: '))
print 'The smallest number with more divisors than the inputted number is',ans,'.'


It was written to help win aid a number game. The game is simple: somebody says a number, you say a number with more divisors than that number.

You get a point if your number is smaller. So if Bob says "5", you can say "4" and get a point. The winner is first to 3 points.

This code outputs the next best number given the previous number as input.

# Style guide

You should code your Python to follow PEP (Python Enhancement Proposal) documents, and in particular, PEP8.

# PEP8

Comparing your code to PEP8's standards shows quite a few violations.

• You should have whitespace between your binary operators.

factors=[]
number=int(n)

• Two blank lines after a declaration

from operator import mul
from math import sqrt, ceil

def next_prime_factor(n):

• Comparison to None: instead of != None it should be is not None

x=filter(None, numbers) + [2] if filter(None, numbers) != None else [2]

• Line too long: PEP8 has a maximum character count of 79 characters per line, this line has 82:
print 'The smallest number with more divisors than the inputted number is',ans,'.'

• while 1 should be denoted as while True instead:
while 1:


# Whitespace and naming

You have double indentation here:

while number > 1:
f=next_prime_factor(number)
factors.append(f)
number /= float(f)
number=int(number)
if number==1:break


You should avoid names like this:

numbers = range(3, max_n+1, 2)
half = (max_n)/2


Their purpose is a little confusing. Try to use more descriptive names that better describe what they are.

You should name your variables like snake_case:

primecounts


# Unnecessary logic

div_count=reduce(mul,div_exps(pcount),1)
return div_count


You're defining a variable right before returning it, just return it directly.

for i in primes_list:
primecounts.append(factors.count(i))
return v


You can use the list comprehension notation instead:

primecounts = [factors.count(i) for i in primes_list]

if div_count(end_num)<=div_count(last_num):
end_num*=min(div_count_factors)
else:
break


When you have a block that looks like this:

if condition == true/false:
doSomething()
else:
endBlock #return, break, continue


When the block terminates in the else loop, you can reverse the conditions and reduce a layer of logic:

if condition != true/false:
endBlock

doSomething()


So, you can simplify that above block down:

if div_count(end_num) > div_count(last_num):
break

end_num *= min(div_count_factors)


The code after the if is not needed: filter always returns a list, which is empty, if no elements remain. This results in identical behavior to the current code.

x=filter(None, numbers) + [2] if filter(None, numbers) != None else [2]

• This helped the most so far, and is really what I wanted to get reviewed. Thanks a lot. – user95591 Apr 1 '16 at 17:54
• And are list comphresions really good form? I thought they were only useful in golfing. – user95591 Apr 1 '16 at 17:56
• @EasterlyIrk yeah, I use them in my non golfing code – Quill Apr 1 '16 at 22:27
• @ Quill okay, cool. – user95591 Apr 1 '16 at 22:28

# You’ve got a bug

Well, I guess. Your lack of comments and/or docstrings make understanding sundaram and thus factor_count pretty hard. So I went for the description and the factor / next_prime_factor functions.

Anyway:

$python2 code.py Input the last number chosen: 9 The smallest number with more divisors than the inputted number is 12 .  I thought 8 had as much divisors than 12 and was smaller. $ python2 code.py
Input the last number chosen: 12
The smallest number with more divisors than the inputted number is 36 .


Same here, 16 is 2×2×2×2, same lenght but smaller than 2×2×3×3.

So, either I didn’t understand things well and there is some special handling of redundant factors; or you need to take into account that $2^n$ is the smallest number with $n$ divisors.

With that in mind, you can remove almost anything except factor and next_prime_factor.

# Count factors, don't list them

Knowing that, in order to generate the smallest number with more than $n$ factors, you only need to compute $2^{n+1}$, there is no need in listing the factors of the input number. Just counting them should be enough:

def factors(n):
number = int(n)
count = 1

while number > 1:
number /= next_prime_factor(number)
count += 1

return count


Several things to note here:

• if number==1:break is useless since this case is already handled by while number > 1;
• factors.append(f) is not needed anymore since we just want to count factors;
• number /= float(f): why do you want to perform floating-point division when you know for sure that number % f is 0 (you wrote next_prime_factor for that purpose);
• number = int(number) is thus not needed anymore.

I also renamed factor (which suggest an action) into factors (which suggest a query).

# range

Since you’re using Python 2, the range builtin will return a list. And since you’re calling next_prime_factor several times, it will build several lists while, often, only using the first few items from them.

As an example, lets assume the user entered 729 (aka $3^6$). next_prime_factor will thus be called 6 times returning 3 at each call. In the meantime, it will build 6 (useless) lists:

[3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27]
[3, 5, 7, 9, 11, 13, 15]
[3, 5, 7, 9]
[3, 5]
[3]
[]


Instead, you should use xrange which will generate numbers when needed.

I can also advise you to look into the yield keyword to turn this function into a generator and avoid computing ceil and sqrt at each call.

# input

This function let Python interpret the user input for you. Meaning that if the user enters 86524 the returned value is an int; if 3.14 is entered the returned value is a float; and if hello is entered, the returned value is a str. So technicaly you do not need the various int(n) calls in your code.

However, input is deemed insecure for the exact same reason: Python interpret the user input. You should instead use the raw_input function which will always return strings and perform the desired convertion yourself, as you did using int. Note that, in Python 3, raw_input has been renamed input and the original input has been dropped.

# Proposed improvements

from math import sqrt, ceil

def next_prime_factor(number):
if number % 2 == 0:
return 2
for divisor in xrange(3, int(ceil(sqrt(number)) + 1), 2):
if number % divisor == 0:
return divisor
return number

def factors(number):
count = 1

while number > 1:
number /= next_prime_factor(number)
count += 1

return count

def next_number(n):
number = int(n)
return 2**factors(number)

if __name__ == '__main__':
ans = next_number(raw_input('Input the last number chosen: '))
print 'The smallest number with more divisors than the inputted number is', ans, '.'


You can read more about the last if in this answer.

• Actually, 16 has less divisors than 36. So that isn't a bug. But good answer! – user95591 Apr 1 '16 at 17:05
• @EasterlyIrk As said, I didn't quite get the code, so I assumed divisors was a shorthand for prime factors. Anyway, the first comment still apply: you need better description of what your code does. – 301_Moved_Permanently Apr 1 '16 at 17:10
• Okay, I'll try. Probably post a follow up question. – user95591 Apr 1 '16 at 17:54
• @EasterlyIrk 24 has more divisors than 12... – vnp Apr 1 '16 at 18:24