[seqfan] Fermat Numbers: A089587

[Paul D Hanna]

A conjecture regarding FERMAT NUMBERS 2^(2^n)+1 has emerged from 
the newly submitted sequence A089587: 

a(n) is the smallest integer k, 0<k<n, that most often satisfies 
the condition: k^m > k^(m+1) (modulo n) as m varies from 1 to n-1, 
for n>2, with a(1)=0 and a(2)=1.

CONJECTURE:
The number of integers m that satisfy the condition: 
   k^m > k^(m+1) (modulo n) and 0<m<n
is the same for all integer k in the interval 1<k<n
iff n is a Fermat number n=2^(2^j)+1 for all j>=0.

This conjecture implies that a(n)=2 only at n=2^(2^j)+1.
I have computed a(2^i+1) for i=0 to i=12:
{1,2,2,7,2,9,38,79,2,220,821,1780,2168}
and you can see that a(n)=2 at n=3,5,17,257.

Would someone like to comment, or test this conjecture further? 
Perhaps it is true and already known?

Outline of this message:
* PROBLEM
* EXAMPLE
* SEQUENCE
* TRIANGLE  
* OCCURRENCES
* OBSERVATIONS

Thanks,
     Paul
-----------------------------------------------------------

PROBLEM.
========
Determine the following sequence:

a(n) is the smallest integer k, 0<k<n, that most often satisfies 
the condition: k^m > k^(m+1) (modulo n) as m varies from 1 to n-1, 
for n>2, with a(1)=0 and a(2)=1.

Procedure.
For each integer k, 0<k<n, list the residues of k^m modulo n 
as m varies from 1 to n-1, and count the number of m that 
satisfy the condition: k^m > k^(m+1) (mod n);
then let a(n) be the smallest k that has the maximum count.

EXAMPLE. 
=========
a(7)=4 since 4 is the smallest number between 1 and 6
that has the maximum number of decreasing power residues mod 7.

n=7: k=1..6, m=1..7
k^m (mod 7).. #>'s
------------- ----
1=1=1=1=1=1=1:0
2<4>1<2<4>1<2:2
3>2<6>4<5>1<3:3
4>2>1<4>2>1<4:4 <--max of 4 >'s first occurs at k=4
5>4<6>2<3>1<5:3
6>1<6>1<6>1<6:3

SEQUENCE.
=========
PARI CODE:
{a(n)=local(A);n>=0;M=0;A=1;
for(k=1,n-1,S=sum(j=1,n-1,if(k^j%n>k^(j+1)%n,1,0));
if(S>M,M=S;A=k));A}

The sequence (OEIS A089587) begins:

0,1,2,3,2,5,4,3,7,8,3,5,9,4,8,11,2,13,11,3,16,5,6,5,
21,9,19,18,16,8,16,23,9,6,16,31,26,11,20,23,16,11,36,
27,34,12,6,29,43,41,26,35,16,37,43,25,49,49,3,53,47,
16,32,57,38,4,37,39,12,16,57,61,37,26,61,49,67,47,55,
27,73,16,3,37,43,36,41,53,67,53,83,52,70,14,8,77,61,
85,67,91,87,26,56,68,27,36,3,91,63,49,80,69,49,49,68,...

Values for a(2^n+1), n>=0 (OEIS A089588):
1,2,2,7,2,9,38,79,2,220,821,1780,2168,..

Values for a(2^n), n>=0:
1,1,3,3,11,23,57,113,241,481,993,1985,..

TRIANGLE.
=========
Perhaps we can understand the problem better by examining 
the following triangle.

Let the n-th row of a triangle T(n,k) list the 
number of decreasing power residues modulo n 
for each number k between 1 and n-1, for n>1.

PARI CODE:
{T(n,k)=local(t);t=0;if(n>0&k>0&k<n,if(n<=2,t=1,
t=sum(m=1,n-1,if(k^m%n>k^(m+1)%n,1,0))));t}

{for(n=2,23,print1(n,": ");for(k=1,n-1,
print1(T(n,k),","));print(" "))}

The triangle begins:
2: 1,
3: 0,1,   
4: 0,1,2,
5: 0,2,2,2,   
6: 0,2,0,0,3,
7: 0,2,3,4,3,3,
8: 0,1,4,1,4,2,4,
9: 0,3,1,3,3,1,6,4,
10: 0,4,4,4,0,0,4,5,5,
11: 0,5,6,4,4,5,5,5,6,5,
12: 0,5,5,0,6,1,6,6,0,1,6,
13: 0,6,4,6,6,6,6,6,8,6,6,6,
14: 0,4,6,9,6,6,0,0,4,7,9,7,7,
15: 0,3,6,7,7,0,7,11,7,0,7,8,7,7,
16: 0,1,4,1,4,2,8,1,8,2,12,1,12,2,8,
17: 0,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,   
18: 0,8,0,11,9,1,6,8,0,0,9,1,12,9,1,6,9,
19: 0,9,9,10,8,8,6,9,10,9,12,9,9,9,9,10,8,9,
20: 0,8,10,9,0,0,10,9,10,1,10,9,10,9,10,0,10,9,10,

OCCURRENCES.
============
Listing where numbers occur in the sequence, we get:
1: 2
2: 3,5,17,257,..
3: 4,8,11,20,59,83,107,179,227,347,467,563,587,1019,..
4: 7,14,66,1049,..
5: 6,12,22,24,149,269,389,..
6: 23,34,47,167,263,383,503,557,653,797,863,887,983,..
7: 9,..
8: 10,15,30,95,359,..
9: 13,26,33,..
10: ?
11: 16,19,38,42,136,154,418,..
12: 46,69,184,719,839,..
13: 18,419,..
14: 94,188,479,922,..
15: 317,..
16: 21,29,31,35,41,53,62,70,82,266,293,509,1013,..

Also, a(n) = powers of 2 at these n:
2: 3,5,17,257,..
4: 7,14,66,1049,..
8: 10,15,30,95,359,..
16: 21,29,31,35,41,53,62,70,82,266,293,509,1013,..
32: 63,1006,.
64: 127,146,170,254,508,1016,..
128: 204,255,339,340,430,510,678,703,1020,..
256: 267,292,351,511,527,682,953,1022,.
512: 631,1023,..

OBSERVATIONS.
=============
 From the above, we see that
a(n)=2 at n=3,5,17,257,...
It is conjectured that a(2^(2^k)+1)=2 for all k>=0.

It also appears that
a(2^n-1) = 2^(n-1); 
a(4^n-2) = 4^(n-1).