Problem 123

[jotd]

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

[hk]

No.

[dgriff]

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.

[jotd]

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

[GenePeer]

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.

[rblackadar]

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.

[Oliver1978]

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?

[dawghaus4]

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

[Oliver1978]

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?

[Oliver1978]

It does overflow. Solved anyway.

[kkm000]

original message

Expand

Just out of curiosity, what is the first prime? 1? This convention has been extremely rarely used in 20-21cc.

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