I am implementing A064604 - OEIS for positive integers up to 10 billion.

I am finding the divisors in \$O(\sqrt N)\$. So, the overall time complexity of running the formula right now is \$O(N\sqrt N)\$. How do I improve on this?


import math

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def sigma_4(n):
    l = factors(n)
    for factor in l:
        ans += (pow(factor,4))
    return ans

for i in xrange(1,n+1):
print ans
  • \$\begingroup\$ What are you going to use these numbers for? Is this for a programming challenge? \$\endgroup\$ Sep 6, 2014 at 15:13
  • \$\begingroup\$ It is a sort of a subproblem of a programming challenge \$\endgroup\$
    – rayu
    Sep 6, 2014 at 15:56
  • 1
    \$\begingroup\$ Can you point us at the challenge? I had a quick look but the closest match I found was Project Euler problem 401, which is based on sums of sigma2. \$\endgroup\$ Sep 6, 2014 at 18:18

2 Answers 2


That's a very naive bruteforce algorithm. To optimize this sort of calculation you can usually "turn it around" by doing something like: for each possible divisor, computing the number of times it'll feature as a contributor and adding them up. And if you can get it to work by just iterating over primes, it'll be even better/faster.


Use List Comprehensions for sigma_4

def sigma_4(n):
    return sum([i**4 for i in factors(n)])

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.