Problem 451

[francisco_lolo12]

Hi,

Problem 451 asks for the sum of the largest coprime number (lets say A) of N for which (A*A)%N=1, looping N between 3 and 20 million.
Also, A has to be smaller than N-1 otherwise it would be trivial.

My initial approach has been:
- get an optimized function f1 to compute (i*i)%N
- get an optimized function f2 to check whether A and B are coprime
- for every N between 3 and 20M, loop down starting at i=N-2 and if f1 and f2 (by this order), exit the loop

A believe that each individual function is fairly optimized, but I still can't get beyond 1M in 10 minutes, so 20M will not be feasible.

Also, I tried to check in other places (mostly stack overflow) whether I could get some information at all about N+1 given the result on N, and the answers were negative.

So, can anyone help steer me in the right direction please?
Thanks

Edit:
New here, just to be sure: does this count as "posting code fragment"? If yes then sorry, I'll remove it

[hk]

The problem builds on several lower numbered problems.
If you want to be steered into the right direction: solve some relevant lower numbered problems first.
Project Euler problems often tend to be built upon lower numbered ones.

[Bobail]

My algorithm does not give me the good answer on 2.10^7
Could someone give me some data in order to check my program (without waiting 40 min each time)

I have the following result:
* 3 -> 100: 1932
* 3 -> 1000: 272840
* 3 -> 10000: 31829433

[TripleM]

* 3 -> 100: 1932

This is too low.

[Bobail]

* 3 -> 100: 1932

This is too low.

Well if you have the data, could you provide it please.

[hk]

Come on Bobail.
It shouldn't be too difficult to write a bruteforcer that gives you the correct answer for 3[le]n[le]100.

[Bobail]

Come on Bobail.
It shouldn't be too difficult to write a bruteforcer that gives you the correct answer for 3[le]n[le]100.

Sorry, you are totally right.
I figured out my problem.