Re: [julia-users] Re: performance compared to mathematica

[Jason Merrill]

On Sunday, March 16, 2014 6:37:45 PM UTC-7, Laszlo Hars wrote:
>
> You could try this function to compute the sum of divisors faster, and 
> using very little memory:
> ~~~
> function sumFactors(n)
>     f = 1
>     for (p,e) in factor(n)
>         f *= div(p^(e+1)-1,p-1)
>     end
>     return f
> end
> ~~~
>

Nice. This gives very fast code for me:

julia> function is_amicable(n)
         sf = sumFactors(n) - n
         return sf != n && sumFactors(sf) - sf == n
       end
is_amicable (generic function with 1 method)

julia> function amicable_sum(bound)
         s = 0
         for n = 2:bound
           if is_amicable(n)
             s += n
           end
         end
         return s
       end
amicable_sum (generic function with 1 method)

julia> amicable_sum(9999)
31626

julia> @time amicable_sum(9999)
elapsed time: 0.026057094 seconds (10235968 bytes allocated)
31626

Compared to OP's Mathematica code, this is better by about a factor of 10:

In[6]:= DivSum[n_] := DivisorSigma[1, n] - n
AmicableQ[n_Integer] := DivSum[n] != n && DivSum[DivSum[n]] == n
Plus @@ Select[Range[9999], AmicableQ] // Timing

Out[8]= {0.277874, 31626}