Project Euler Forum

I think I understood the problem, yet I'm only able to verify 9 fibonacci primitive roots for primes <10000:
2,3,5,7,11,13,17,19,29.

Did I understand it correctly, that for p to have a primitive root n,
- (n^x % p) has to be cyclic
- cycling with period (p-1)
- and the cycle having all numbers [1..p-1]?

tomboy wrote:I think I understood the problem, yet I'm only able to verify 9 fibonacci primitive roots for primes <10000:
2,3,5,7,11,13,17,19,29.

Did I understand it correctly, that for p to have a primitive root n,
- (n^x % p) has to be cyclic
- cycling with period (p-1)
- and the cycle having all numbers [1..p-1]?

You're criteria for n being a primitive root of p is correct.
However, your test for the Fibonacci behavior must be wrong.

Lets take p=2. The only primitive root of 2 is 1, and {1^k} = {1, 1, 1, 1, 1, ... }. Now 1 + 1 &ne; 1 modulo 2, so p=2 has no Fibonacci primitive root.

Let take p=3. The only primitive root is 2, and {2^k}={1,2,1,2,1,2...}. Now 1 + 2 &ne; 1 modulo 3, so p=3 has no Fibonacci primitive root.

Similarly 7, 13, 17 and 29 have no Fibonacci primitive root. 5, 11 and 19 do, as well as 320 others less than 10000.

Just making sure I understand this.

Must fpr<p?

If so, for p<10000, the only solution I get is the one shown as the example, where p=11 and fpr=8.

If I however allow fpr<100000, I find 2 solutions, and if fpr<1000000, I find 3.

I am confused.

Thanks.

KING-OLE wrote: Mon Apr 16, 2018 2:49 pm Must fpr<p?

Yes, you may assume that a primitive root modulo $p$ is less than $p$.

KING-OLE wrote: Mon Apr 16, 2018 2:49 pm If so, for p<10000, the only solution I get is the one shown as the example, where p=11 and fpr=8.

You should be able to find many examples with an exhaustive brute force search.

traxex wrote: Mon Apr 16, 2018 4:30 pm You should be able to find many examples with an exhaustive brute force search.

Thanks.

Hmm, then obviously I am doing something wrong somewhere.

I have a brute force test looping through all p's < 10,000 and all fpr's < p, and the example (11,8) is the only result I get.

Back to the drawing board.