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.