A089587 - OEIS

%I #10 Jun 20 2022 04:17:40

%S 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,

%T 16,23,9,6,16,31,26,11,20,23,16,11,36,27,34,12,6,29,43,41,26,35,16,37,

%U 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

%N 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.

%C The values at a(2^n+1), n>=0, are given by A089588: {1,2,2,7,2,9,38,79,2,220,..} and it is conjectured that a(n)=2 only when n is a Fermat number 2^(2^j)+1.

%F a(2^(2^n)+1)=2; a(2^n-1)=2^(n-1); a(4^n-2)=4^(n-1) (conjectures).

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

%e n=7: k=1..6, m=1..7

%e k^m (mod 7).. #>'s

%e 1=1=1=1=1=1=1:0

%e 2<4>1<2<4>1<2:2

%e 3>2<6>4<5>1<3:3

%e 4>2>1<4>2>1<4:4 <- max of 4 >'s first occurs at k=4

%e 5>4<6>2<3>1<5:3

%e 6>1<6>1<6>1<6:3

%o (PARI) a(n) = local(high, lowK, count); high = 0; for (k = 1, n - 1, count = 0; for (m = 1, n - 1, if (k^m%n > k^(m+1)%n, count++)); if (count > high, high = count; lowK = k)); if(n==2, 1, lowK) \\ _David Wasserman_, Sep 20 2005 [a(2) corrected by _Georg Fischer_, Jun 20 2022]

%Y Cf. A089588, A000215.

%K nonn

%O 1,3

%A _Paul D. Hanna_, Nov 09 2003