Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1)

[T.Rex]

Hello,

One more conjecture. Again based on Shallit&Vasiga paper, and checked up to n=16.
The DiGraph under x^2-2 modulo a Fermat prime is made of a Tree and of Cycles of length dividing 2^n-1.

Conjecture:
Let n be an integer and F = 2^2^n+1 .

S(0) = (F-3)/2 and
S(i+1) = S(i)^2 - 2 (mod F) ;

F is prime iff S(2^n-1) == S(0) (mod F).

Tony

[T.Rex]

The number of Cycles for n=2,3,4 are:

n    2^n-1     L      #Cycles
-----------------------------
2      3       3       1
3      7       7       9
4     15       3       1
               5       3
              15    1091
...
34   3.43691.131071

About F4, under llt2(x)=x^3-3x, 2 of the 3 Cycles of Length 5 are connected to the third, which is connected to itself. That means that 2 starting values are required for going through the 3 Cycles of Length 5, thus doing the 3*5 required iterations.

F34 is the first Fermat number we do not know if it is prime or not. Under x^2-2, there are probably Cycles of length 3, 43691, 131071, 3*43691, 3*131071, 43691*131071, and 2^34-1.

With the same kind of hypothesis than the ones I've used for the "idea" I've explained in a previous thread about Mersenne numbers, one could imagine to run the llt (x^2-2) on several Cycles smaller than the big one (L=2^34-1), jumping from one Cycle to another by means of llt2 (x^3-3*x). If one Cycle does not exist, then it would mean F34 is not prime. Once proved (!) ... this test would be faster than Pépin's test for proving a Fermat number is composite.
But this requires to build several properties before ... Shallit&Vasiga's paper say nothing about a formula for building numbers belonging to Cycles of the DiGrapht under x^2-2 modulo a Fermat prime.

Since the same kind of Conjecture appears for Mersenne, Fermat, and Wagstaff numbers, I think it is worth Number Theory experts look at this and see if the work of Shallit&Vasiga can be extended.

Your opinion ?

Tony

[T.Rex]

About the 4 Lengths we have the number of Cycles:

 L    #Cycles
-----------
 3       1
 5       3
 7       9
15    1091

these values are exactly half of those of the A001037 sequence, which represents the number N of cycles of length L in a digraph under x^2 seen modulo a Mersenne prime M_q=2^q-1.
I guess it is related to: A000048.

Who can provide a proof ?

Rony

[philmoore]

Originally Posted by T.Rex

F34 is the first Fermat number we do not know if it is prime or not.

Actually, F33:
http://www.prothsearch.net/fermat.html

[T.Rex]

Originally Posted by philmoore

Actually, F33:

OoopS. Sorry. Too much red wine at lunch ! Always check ! Don't rely on your memory.
Factors of 2^33-1 : 7*23*89*599479 . Less interesting than F34 !

Thanks Phil !
Tony

[AntonVrba]

We have three threads, lets put them together for a common primality test for Mersenne, Wagstaff and Fermat numbers.

Mersenne:
refer Another (candidate) test of primality of Mersenne number
But the conjecture can be simplified to:

Conjecture:
Let p be a prime integer and M = (2^p-1).

S(0) = (M-10)/3 and
S(i+1) = S(i)^2 - 2 (mod M) ;

M is prime iff S(p-1) == S(0) .

Wagstaff:
refer Conjectured primality test for (2^p+1)/3

Conjecture:
Let p be a prime integer and W = (2^p+1)/3 .

S(0) = (W+3)/2 and
S(i+1) = S(i)^2 - 2 (mod W) ;

W is prime iff S(p-1) == S(0) .

Fermat:
refer Conjectured primality test for Fermat numbers

Conjecture:
Let n be an integer and F = 2^2^n+1 .

S(0) = (F-3)/2 and
S(i+1) = S(i)^2 - 2 (mod F) ;

F is prime iff S(2^n-1) == S(0) (mod F).

The similarities are striking - should not be ignored

Originally Posted by T.Rex

Since the same kind of Conjecture appears for Mersenne, Fermat, and Wagstaff numbers, I think it is worth Number Theory experts look at this and see if the work of Shallit&Vasiga can be extended.

Your opinion ?

Tony

I fully agree.

[AntonVrba]

Lets continue under a common thread
Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1)

[T.Rex]

Originally Posted by AntonVrba

Lets continue under a common thread ...

Good idea !
Tony

[AntonVrba]

Oh if you were wondering about

S(0) = (M-10)/3 that is (2^p+1)/3-4

The common number in the DiGraphs of length (p-1) for Mersenne numbers.

[T.Rex]

With: W(q) = (2^q+1)/3 , S(0) = (W(q)+3)/2 .
Since S(1) = S(0)^2-2 ~= W(q-2) (mod W(q)), you could also use: S(0) = W(q-2) = (2^(q-2)+1)/3 as a starting value (seed).
Not really useful, buf funny.
T.

[AntonVrba]

Conjecture:
Let p be a prime integer and
Q = (2^p-1) or Q=(2^p+1)/3

Let x=(Q-1)/p and y be an odd integer

y^x = r (mod Q)

if r is odd then r=Q-r

Q is prime iff r==2^z , z a integer.

I have found no exceptions