Project Euler Forum

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.

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

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

Thank you, Rowan.

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..

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.

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.

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

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.

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.

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

Than you.

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.

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!