Why sigma(n) seems not so performant for small n?
When I try to timeit sigma(n):
sage: %timeit
sage: for n in xsrange(1,10000): c=sigma(n)
5 loops, best of 3: 181 ms per loop
but it seems much quicker when you directly sum the divisors
sage: %timeit
sage: def s(n): return sum(divisors(n))
sage: for n in xsrange(1,10000): c=s(n)
5 loops, best of 3: 44.8 ms per loop
The same with sigma(n,k). Why that happens (for relatively small n)?
Finding divisors uses
pari
, and maybepari
has gotten faster recently, making your version faster. Or more specifically, maybepari
has gotten faster at listing divisors than at factoring --sigma
uses thefactor
function. That's just a guess, though.By the way, as far as I can tell, the code for
sigma
was last changed in 2007 or so. So it may be time to revisit it.Thank you for your hint