Problem 153

[rowanparker]

Hello,
I have an issue regarding problem 153, I have made a script (in PHP) that works out all [complex] divisors of the real integer. Then it adds them up. And I can get 35 for n<5 in under a second. But when I try and run it for n<10⁸ (I know the 1 minute rule, but I was ignoring that for now) and it ran over night and ended up on about n=60000. I gave up as this would take forever (as that is only 0.006% of the way through).

I had previously written some functions to deal with complex numbers (such as add, subtract, multiply, divide). And after dividing Array(5,0) [meaning: Re(5), Im(0) or 5] by Array(1,2) [meaning: Re(1), Im(2) or 1+2i] I get the desired result of Array(1,-2) [or 1-2i]. Now I wrote a function to find the complex divisors. For 5, the results are as follows (in no particular order):

1-2i, 1, 1+2i, 2-i, 2+i, 5

This shows my script is working fine. It even works on much larger numbers too. It is just extremely slow.

Please can anyone give me any pointers?
Thanks, Rowan.

[hk]

Can you predict from what kind of numbers 3+4i will be a divisor? And 3-4i?
Don't answer my question here.

[rowanparker]

I don't understand your question. Could you rephrase it please?
Where should I answer then? PM?

Thank you, Rowan.

[stijn263]

Since your algorithm is too slow, hk is trying to help you think of a faster one.

You should note though that problem 153 is a very difficult problem..

[rowanparker]

Yeah, I'm aware it is challenging. Sounds like its past me.
I just didn't understand what hk was saying, but I guess now I do, I just don't know the answer.
I'll have a think. Thanks.

[btilly]

Could some admin please verify that the solution to problem 153 in the database is correct?

I have a program which produces the right answers for 5 and 100,000, whose logic looks correct to me, but the system won't accept my answer for 100,000,000. The last 4 digits of the answer it is rejecting are 0627.

If the database is correct, I would appreciate being told what the first incorrect value is in this sequence:

10: 161
100: 16749
1000: 1752541
10000: 178231226
100000: 17924657155
1000000: xxxxx
10000000: xxxxx

Thanks.

[TripleM]

All of your smaller answers are correct, as is the answer in the database which doesn't match your last 4 digits.

[hk]

Please don't start a new topic for a problem if there exists one already.
Skipped some answers that exceed the example given in the problem.

[btilly]

I rewrote my code in a different language and got the right answer.

I clearly encountered a bug in Perl's Math::BigInt, which I'll have to track down. Thanks.

[GenePeer]

Can someone respond to my recent post on this problem's forum?

Than you.

[oleglyamin]

In the closed forum of this problem there is a formula in the post made by Eigenray (third post) for function sq(n). Could someone pm me please with a quick explanation for optimization behind this formula? Can't get my head around it. Thank you.

[maujjy]

I am having trouble with this one. Currently, I can confirm all the values btilly gives except for 10**5, the example given in the problem. I am unsure if my problem is with my divisor function or with another part of the algorithm. Can anyone confirm that the sum of all divisors of n, n ranging from 1 to 10**5 inclusive, is 8224740835? And for 1 up to 10**6 inclusive is 822468118437?

The incorrect figure I'm getting for the problem for 10**5 is 12201795741

EDIT: I have realised my mistake!