I'm trying to solve the 12th problem on Project Euler. I can calculate the number that has over 500 divisors in almost 4 minutes. How can i make it faster? Here's the attempt;
import time
def main():
memo={0:0,1:1}
i=2
n=200
while(1):
if len(getD(getT(i)))>n:
break
i+=1
print(getT(i))
#returns the nth triangle number
def getT(n):
if not n in memo:
memo[n]=n+getT(n-1)
return memo[n]
#returns the list of the divisors
def getD(n):
divisors=[n]
for i in xrange(1,int((n/2)+1)):
if (n/float(i))%1==0:
divisors.append(i)
return divisors
startTime=time.time()
main()
print(time.time()-startTime)
And the number, 76,576,500 (the 12375th triangular number) is indeed the first triangular number with more than 500 divisors.
The first ten terms would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, … We can see that 28 is the first triangle number to have over five divisors.
List Of Triangular Numbers. 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120,136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431, and so on.
You don't need an array to store the triangle numbers. You can use a single int because you are checking only one value. Also, it might help to use the triangle number formula:n*(n+1)/2
where you find the n
th triangle number.
getD
also only needs to return a single number, as you are just looking for 500 divisors, not the values of the divisors.
However, your real problem lies in the n/2
in the for loop. By checking factor pairs, you can use sqrt(n)
. So only check values up to sqrt(n)
. If you check up to n/2
, you get a very large number of wasted tests (in the millions).
So you want to do the following (n
is the integer to find number of divisors of, d
is possible divisor):
n/d
has no remainder.Using a decorator (courtesy of activestate recipes) to save previously calculated values, and using a list comprehension to generate the devisors:
def memodict(f):
""" Memoization decorator for a function taking a single argument """
class memodict(dict):
def __missing__(self, key):
ret = self[key] = f(key)
return ret
return memodict().__getitem__
@memodict
def trinumdiv(n):
'''Return the number of divisors of the n-th triangle number'''
numbers = range(1,n+1)
total = sum(numbers)
return len([j for j in range(1,total+1) if total % j == 0])
def main():
nums = range(100000)
for n in nums:
if trinumdiv(n) > 200:
print n
break
Results:
In [1]: %cpaste
Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:def main():
: nums = range(10000)
: for n in nums:
: if trinumdiv(n) > 100:
: print 'Found:', n
: break
:
:startTime=time.time()
:main()
:print(time.time()-startTime)
:--
Found: 384
1.34229898453
and
In [2]: %cpaste
Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:def main():
: nums = range(10000)
: for n in nums:
: if trinumdiv(n) > 200:
: print 'Found:', n
: break
:
:startTime=time.time()
:main()
:print(time.time()-startTime)
:--
Found: 2015
220.681169033
A few comments.
As Quincunx writes, you only need to check the integer range from 1..sqrt(n) which would translate into something like this for i in xrange(1, sqrt(n) + 1): ...
. This optimization alone vastly speeds up things.
You can use the triangle number formula (which I didn't know until just now, thank you Quincunx), or you can use another approach for finding the triangle numbers than recursion and dictionary lookups. You only need the next number in the sequence, so there is no point in saving it. Function calls involves significant overhead in Python, so recursion is usually not recommended for number crunching. Also, why the cast to float
, I didn't quite get that ?
I see that you are already using xrange
instead of range
to build the int
stream. I assume you know that xrange
is faster because it is implemented as a generator function. You can do that too. This makes things a lot smoother as well.
I've tried to do just that, use generators, and the code below finds the 500th triangle number in ~16sec on my machine (YMMV). But I've also used a neat trick to find the divisors, which is the quadratic sieve.
Here is my code:
def triangle_num_generator():
""" return the next triangle number on each call
Nth triangle number is defined as SUM([1...N]) """
n = 1
s = 0
while 1:
s += n
n += 1
yield s
def triangle_num_naive(n):
""" return the nth triangle number using the triangle generator """
tgen = triangle_num_generator()
ret = 0
for i in range(n):
ret = tgen.next()
return ret
def divisor_gen(n):
""" finds divisors by using a quadrativ sieve """
divisors = []
# search from 1..sqrt(n)
for i in xrange(1, int(n**0.5) + 1):
if n % i is 0:
yield i
if i is not n / i:
divisors.insert(0, n / i)
for div in divisors:
yield div
def divisors(n):
return [d for d in divisor_gen(n)]
num_divs = 0
i = 1
while num_divs < 500:
i += 1
tnum = triangle_num_naive(i)
divs = divisors(tnum)
num_divs = len(divs)
print tnum # 76576500
Running it produces the following output on my humble machine:
morten@laptop:~/documents/project_euler$ time python pr012.py
76576500
real 0m16.584s
user 0m16.521s
sys 0m0.016s
Using the triangle formula instead of the naive approach:
real 0m3.437s
user 0m3.424s
sys 0m0.000s
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With