Problem 437

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
tomboy
Posts: 5
Joined: Sun Sep 01, 2013 8:24 am

Problem 437

Post by tomboy » Sat Oct 11, 2014 12:14 pm

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]?
Image

User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 4:40 pm
Location: Montréal, Canada

Re: Problem 437

Post by mpiotte » Sat Oct 11, 2014 12:53 pm

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.
Image

KING-OLE
Posts: 10
Joined: Mon Dec 22, 2014 9:33 pm

Re: Problem 437

Post by KING-OLE » Mon Apr 16, 2018 1:49 pm

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.
Image

traxex
Posts: 77
Joined: Thu Oct 19, 2017 12:30 pm

Re: Problem 437

Post by traxex » Mon Apr 16, 2018 3:30 pm

KING-OLE wrote:
Mon Apr 16, 2018 1: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 1: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.
Technically, everyone is full of himself.

KING-OLE
Posts: 10
Joined: Mon Dec 22, 2014 9:33 pm

Re: Problem 437

Post by KING-OLE » Mon Apr 16, 2018 3:40 pm

traxex wrote:
Mon Apr 16, 2018 3: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.
Image

Post Reply