I did a lot of research online before starting this problem. I knew there’d be no other way to do it without that. I really didn’t want to do it brute force for sure.
Wikipedia lead me to some really old book that I had to dig through. It gave me a really really nice formula for finding the number of distinct solutions to this equation. The next problem was finding the correct answer. That part took forever!
from time import time
start = time()
def isprime(n):
if n == 2:
return True
elif n < 2 or n%2 == 0:
return False
else:
for i in range(3, int(n**0.5 + 1), 2):
if n%i == 0: return False
return True
primes = []
for n in xrange(10**6):
if isprime(n) == True:
primes.append(n)
primes = tuple(primes)
def nextprime_new(p):
i = primes.index(p)
return primes[i+1]
def nextprime(p):
if p == 2:
return 3
else:
while True:
p += 2
if isprime(p) == True:
return p
def powerlist(n):
ans = []
p = 2
while n > 1:
i = 1
while n%(p**i) == 0:
i += 1
if i > 1:
n /= p**(i-1)
ans.append(i-1)
p = nextprime(p)
return ans
n = 1
largest = 0
while True:
n += 1
alist = powerlist(n)
ans = 1
for a in alist:
ans *= (1 + 2*a)
ans = (ans + 1)/2
if ans > 1000:
print n, ans
break
elif ans > largest:
largest = ans
else:
end, start = time() - start, time()
print n, largest, end