Project Euler Forum

Hi,

This seems pretty straightforward, and I can verify the value given by the problem for 10**9 (7037) in less than a second.

However, my answer to the question for 10**10 (obtained in a second too) is wrong, whereas I use exactly the same computation. Anyone confirms this? Is there a problem in the value of the expected solution?

thanks

No.

In the problem, P_n is the nth prime, so P₁ = 2
Your program probably says that P₀ = 2

At least that's what my problem was. The problem isn't worded in the most programmer-friendly way.

you are right! but with 10**9 I get the 7037 something result. So the problem wording is wrong BTW
And adding 1 to my result still is not accepted

Adding 2 works

thanks

jotd wrote:you are right! but with 10**9 I get the 7037 something result. So the problem wording is wrong BTW
And adding 1 to my result still is not accepted

Adding 2 works

thanks

I think the problem is your program. Maybe it's exiting the loop before updating the value of n. Since n is always odd, the "margin of error" is 2 instead of the usual 1. My program gave the right answer without modifications.

GenePeer wrote:

jotd wrote:you are right! but with 10**9 I get the 7037 something result. So the problem wording is wrong BTW
And adding 1 to my result still is not accepted

Adding 2 works

thanks

I think the problem is your program. Maybe it's exiting the loop before updating the value of n. Since n is always odd, the "margin of error" is 2 instead of the usual 1. My program gave the right answer without modifications.

The more likely explanation is that, because of the off-by-one index, he used the correct exponent n but the incorrect prime p_n+1 in the equation. That mixed equation happens to give a "good" result for 10**9, but only by accident. By the way, a careful reading of the problem makes the indexing unambiguous.

So, to straighten things out... if n=1 then p_n=2, if n=2 then p_n=3 et cetera and finally if n=7037 then p_n=71059.
Right?

leghorn wrote:So, to straighten things out... if n=1 then p_n=2, if n=2 then p_n=3 et cetera and finally if n=7037 then p_n=71059.
Right?

Since p_n is your own notation, it might be of help, if you define its meaning.

It appears that p_n means the nth prime and the 1st prime is 2, the 2nd prime is 3 and the 7037th prime is 71059.

Tom

Thanks, dawg. That's what I meant, like in the problem's description: p_n denotes the nth prime.

[edit]

Could anybody check out n = 6544 (pn = 65539)? Using the formula ((pn-1)^n + (pn+1)^n) mod pn^2 gives a remainder of 3,780,539,272. Using the test case I never get to 7037

[another edit]

Could it be that this is overflowing on 64 bit already?

It does overflow. Solved anyway.

original message Sorry. The first prime is 2. It's just me. I'm an idiot tonight. 🤪