Project Euler Forum

NB: The first posts in this topic refer to an earlier version of problem #238, which unfortunately had an error.
To fix it, the problem statement was modified. As a result, the (partial) answers posted below are no longer valid.
-Edited by harryh


I think this is a broken problem. My semi brute force code gives the same answers for N=10^8 and N=2*10^8 that my fast code. (for brute force obviously it is not so that easy if you have not got enough RAM, but if you replace the starting value(s) of the sequence then testing is easy).

//so I mean: sum(k=0,10^8,p(k)) and sum(k=0,2*10^8,p(k))

I'm still working through this one (looked crazy challenging, so I couldn't resist). Once I've got my fast code developed a bit more, I'll see if I can't corroborate this.

Can you confirm: sum(k=0,10^8,p(k)) = 49...33, sum(0,2*10^8,p(k)) = 99...00?

I am inclined to agree there is something wrong.

Yes, I've gotten the same results.

Well, it seems that at least one user got it right
To be sure, I've double-checked the answer entered in the database and it is the same as the one we found while developing the problem, so...

I've got the same values for 10^8 and 2.10^8... strange !

And 49...89 for 10^14

harryh wrote:Well, it seems that at least one user got it right
To be sure, I've double-checked the answer entered in the database and it is the same as the one we found while developing the problem, so...

Or he/she found the same wrong way. Could you confirm the leading/trailing two digits for N=10^8 and for N=2*10^8 (posted above), if you have got a program... I've checked that my slow brute force and fast code gives the answers for N=k*10^6, where k=100..300, yes 201 big values, and there was no difference.

I think Robert is right. And by the way, choosing n>10^8 is a good idea. Actually, chosing n>=80...91 is meaningful, hu ?

Considering that there is only one solution so far, it is possible that we overlooked something.
So, we are temporarily putting it on hold and a new e-mail notification will be sent a few hours before it becomes available again.
Our sincere apologies for the inconvenience.

I'm the one who solved the problem. I hope the problem (and my solution) is correct...

I get the same results for 1e8, 2e8 and 1e14 as the previous posters.

harryh wrote:So, we are temporarily putting it on hold and a new e-mail notification will be sent a few hours before it becomes available again.

Now that we all have our code ready, there's going to quite a rush of submissions when it comes back

Robert_Gerbicz wrote:My semi brute force code gives the same answers for N=10^8 and N=2*10^8

As I said, I'm the one that first "solved" the problem and if I apply my fast algorithm to 10^8 and 2*10^8 i get two different values. The only way to get the same number is if all p(k) in that range are zero, which seems impossible given that w is a string of infinite length!

mastro wrote:

Robert_Gerbicz wrote:My semi brute force code gives the same answers for N=10^8 and N=2*10^8

As I said, I'm the one that first "solved" the problem and if I apply my fast algorithm to 10^8 and 2*10^8 i get two different values. The only way to get the same number is if all p(k) in that range are zero, which seems impossible given that w is a string of infinite length!

Interpreting what he said, he meant that the brute force & fast solutions agree for both k's. Not that they're the same value.

I also get the same results for 10E8, 2* 10E8, 10E14,.

I too confirm, 10^8, 2x10^8 and 10^14.

quilan wrote:Interpreting what he said, he meant that the brute force & fast solutions agree for both k's. Not that they're the same value.

Oops, sorry. You're right of course. Still my result for 10^8 is not the 49...33 mentioned by Eigenray and the one for 2*10^8 is not 99...00.

I'm either a genius or an extremely lucky idiot!

mastro wrote:As I said, I'm the one that first "solved" the problem and if I apply my fast algorithm to 10^8 and 2*10^8 i get two different values.

Out of curiosity (and to check a wild surmise), what does your algorithm give for the first and last two digits for these?

Thumbo wrote:Out of curiosity (and to check a wild surmise), what does your algorithm give for the first and last two digits for these?

I get 49...36 and 99...06. I'll try a brute force and see what I get.

mastro wrote:

Thumbo wrote:Out of curiosity (and to check a wild surmise), what does your algorithm give for the first and last two digits for these?

I get 49...36 and 99...06. I'll try a brute force and see what I get.

Aha! Those match my surmise - I get those answers by including one easy to make error in my code. I'll pm harryh.