Problem 261

[zwuupeape]

Apparently someone has already managed to solve it but for some reason I get wrong answer even though I am 100 % confident about the solution.

For 10^8 I get: 242816464261
For 10^13 I get: 7482405209124158762

Perhaps my fault is with the word 'distinct' ? What is meant by distinct? For some k, there may be more than one pair of (m,n) such that (k-m)^2 + ... k^2 = (n+1)^2 + ... (n+m)^2, so there is only need to count those values of k once - right?

Thanks.

[stijn263]

For some k, there may be more than one pair of (m,n) such that (k-m)^2 + ... k^2 = (n+1)^2 + ... (n+m)^2, so there is only need to count those values of k once - right?

Exactly. Your result for 10⁸ is slightly off. I didn't check the other one. Good luck!

Problem 261 (View Problem)

[daniel.is.fischer]

'distinct' == 'different', so you've interpreted that correctly.
However, your values are wrong. For 10⁸, it's 243xxxxxxxxx, for 10¹³: 74828xxxxxxxxxxxxxx.

[Robert_Gerbicz]

That is very interesting. My code gives the same number for n=10^8 (still no answer for n=10^10, my code is a little slow, it would take about 2 days for one core):

is it also bad:
// f(999)=8347
// f(9999)=276416
// f(99999)=8340384
// f(999999)=253131726

[zwuupeape]

I get exactly that, too.

[Robert_Gerbicz]

I found a bug, my new guess: f(10^6)=255978835

[daniel.is.fischer]

I found a bug, my new guess: f(10^6)=255978835

Yup.

[zwuupeape]

I now tried a completely different approach. Scales much, much worse than the other but apparently finds some that the other misses - I cannot, for the life of mine, understand why. And it still doesn't match f(10^6) ...

Who can confirm 8446625 for 10^5?
277236 for 10^4 ?

[daniel.is.fischer]

I now tried a completely different approach. Scales much, much worse than the other but apparently finds some that the other misses - I cannot, for the life of mine, understand why. And it still doesn't match f(10^6) ...

Who can confirm 8446625 for 10^5?

Not I. You're still missing some.

277236 for 10^4 ?

That, yes.

[Rodinio]

OK,

first post...

I really like this problem, and am sure to finish it quickly if it were not for the special special cases that I keep finding.
Can anyone confirm 10^8 as 243xxx202099 ? First three digits are ok thanks to a previous post, I get 10^6 just fine, and the runtime for this case is well under a minute in python, so I do believe I must be on to something. But I still get the red cross, so there must be another (probably stupid) bug...

(I'm perhaps obfuscating too much here, don't want to get on the wrong side of the etiquette here...)

Cheers
Rodinio

[daniel.is.fischer]

No, the sum for 10⁸ ends in 7.

[MrDrake]

This is really annoying... I have an algorithm that will solve it but would take too long, and I can't see how to really re-work it. 10^6 is taking a minute to get the correct answer (as opposed to a few seconds for the wrong one).

[quilan]

Finally got my missing part written so that my algorithm can work!

But curses, my algorithm runs in <1 second for 10⁵, but I'm just shy of the correct amount (my result was juuuust lower than zwuupeape's result)... and brute force takes way too long. Time for a very lengthy debug time. *grumble*

[zwuupeape]

My incorrect algorithm is approximately O(sqrt(n)) time, I think. Well below one minute for 10^13 in unoptimized Python. Wonder how different that could be from everyone else's. Anyway, I hate that problem because I felt my 100% was near and it now seems further than ever

[quintana]

finally! 10^6 in 15ms. beyond that c++ is helpless, due to overflow. back to java...

[quilan]

If it makes you feel any better, my 'O(sqrt(n))' algorithm took 3h42m to calculate in Python. Massively inefficient. It turns out there are a few odd side-cases one wouldn't normally expect (as everyone here seems to have noticed with their values being slightly low).

[zwuupeape]

Got it !!

Tricky and hard. A possible candidate, I think, for the hardest problem ever on PE, at least judging by the number of solvers so far ..

[quilan]

Got it !!

Tricky and hard. A possible candidate, I think, for the hardest problem ever on PE, at least judging by the number of solvers so far ..

I'm pretty sure 245 had lower by around this length... but it's pretty close.

[Rodinio]

OK, I found one more (sparse) class of solutions so one more try:

Can someone confirm 10^7 -> 7835865568 ?
I'm stuck until I find a pattern to those special cases.

PS: I would really not mind seeing a correct solution for 10^8 either, Iknow I'm off (243296863635), but probably only one short... which would open the door to the next special case, I reckon.

Cheers
Rodinio

[daniel.is.fischer]

Both numbers are too low.