I'm working on problem 401 in project euler, I coded up my solution in python but it's going to take a few days to run, obviously I'll need to speed it up or use a different approach. I came across a solution in Haskell that looks almost identical to my python solution but completes almost instantaneously.
Can someone explain how it is so fast? (I AM NOT ASKING FOR HELP OR SOLUTIONS TO PROBLEM 401)
divisors n = filter (\x -> n `mod` x == 0) [1..(n`div`2)] ++ [n]
sigma2 n = sum $ map (\x -> x * x) (divisors n)
sigma2big n = sum $ map (sigma2)[1..n]
let s2b = sigma2big 10^15
putStrLn ("SIGMA2(10^15) mod 10^9 is " ++ (show (mod s2b 10^9)))
From my understanding it is just using trial division to generate a list of divisors, squaring and summing them, and then summing the results from 1 to n.
EDIT: forgot my python code
from time import clock
def timer(function):
def wrapper(*args, **kwargs):
start = clock()
print(function(*args, **kwargs))
runtime = clock() - start
print("Runtime: %f seconds." % runtime)
return wrapper
@timer
def find_answer():
return big_sigma2(10**15) % 10**9
def get_divisors(n):
divs = set()
for i in range(1, int(sqrt(n)) + 1):
if n % i == 0:
divs.add(i)
divs.add(n // i)
return divs
def sigma2(n):
return sum(map(lambda x: x**2, get_divisors(n)))
def big_sigma2(n):
total = 0
for i in range(1, n + 1):
total += sigma2(i)
return total
if __name__ == "__main__":
find_answer()
Prelude> sigma2big 1000
401382971
(0.48 secs, 28491864 bytes)
Prelude> sigma2big 10^3
103161709
(0.02 secs, 1035252 bytes)
Prelude> (sigma2big 10)^3
103161709
function precedence (shh...)
Make sure you are using Integer
for your calculations and not Int
since 10^15
will overflow an Int
value.
If you change:
let s2b = sigma2big 10^15
to:
let s2b = sigma2big (10^15 :: Integer)
the Haskell code runs out of memory in ghci
and I didn't bother to wait for it to complete when running the compiled version.
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