How to speed up my code about Divisors?

In[21]:= ParallelSum[n*Count[Divisors[n^2], a_ /; n < a < 2 n], {n, 1, 10^5}] // AbsoluteTiming
Out[21]= {5.987342,10724527832}


I need the sum from n=1 to n=10^9, but this code is too slow to get the result. I have tried to use Compile, but it works very little.

How can I speed up it? Thanks a lot.

Edit

Thanks for Pickett's help, I really learned a lot about how to use Compile from your answer. But some error occurs on my computer, like this What's wrong? My computer's memory is 2G, and the mathematica version is 10.0.1.

• oeis.org/A005279 – Dr. belisarius Jan 8 '15 at 13:48
• Regarding your error message in your edit, I can't reproduce it for n=10^5, but I can get it for n=10^10 and greater. – dr.blochwave Jan 9 '15 at 12:20

belisarius left a hint in a comment on how to solve this problem more efficiently, but I'm going to take it at face value and try to optimize your code.

The pattern matcher is slow, so you don't want to use the pattern matcher in any kind of loop generally. On my computer your code takes 3.87 seconds to execute, whereas

ParallelSum[
n Length@Select[Divisors[n^2], n < # < 2 n &],
{n, 1, 10^5}
] // AbsoluteTiming


takes only 2.55 seconds to execute. You did this when you compiled your function, you should always do this whether you plan to compile it or not.

Secondly, compilation doesn't help as much as you'd expect because Divisors is not compilable. This doesn't mean that it's not fast, because it's probably already written in C. But if you compile the function in its entirety you get a MainEvaluate call which slows it down. You can see whether you have any MainEvaluate calls by using

Needs["CompiledFunctionTools"]
CompilePrint[compiledFunction]


For this reason the code

compiled0 = Compile[{{n, _Integer}},
n Length@Select[Divisors[n^2], n < # < 2 n &]
];
ParallelSum[
compiled0[n],
{n, 1, 10^5}
] // AbsoluteTiming


takes 2.36 seconds to evaluate whereas

compiled = Compile[{{list, _Integer, 1}, {n, _Integer}},
n Length@Select[list, n < # < 2 n &]
];
ParallelSum[
compiled[Divisors[n^2], n],
{n, 1, 10^5}
] // AbsoluteTiming


takes just 1.18 seconds to evaluate. The effect of adding runtime attributes and changing the compilation target to C is negligible, I get 1.10. But overall this is a pretty good improvement, with 1.10 instead of 3.87.

• +1 for both a great solution and the insight into what goes on with Compile and the MainEvaluate` call. This clears up lots of mysteries I've encountered over the years. Thx! – Jagra Jan 8 '15 at 16:58
• Thanks for your help, but there is some error on my computer. I have edited it to the question. – wuyingddg Jan 9 '15 at 4:50
• @wuyingddg I asked about it in the chat. For others the limit is much higher, for example $10^10$, but no one seems to know why it occurs unfortunately. I will update if I find a solution. – C. E. Jan 9 '15 at 19:09