Divisor game cheating aid

Question

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.

Answer 1

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]

Answer 2

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.