login
Smallest prime p such that the multiplicative order of 8 modulo p is n, or 0 if no such prime exists.
4

%I #16 Nov 26 2024 02:14:51

%S 3,17,13,113,251,7,1163,89,109,431,1013,577,4421,953,571,257,4523,127,

%T 15467,3761,3109,7151,18539,73,25301,14327,2971,42953,72269,151,683,

%U 12641,331,2687,42701,5113,18797,1103,8581,13121,172283,631,221021,120737,3061,5153,217517

%N Smallest prime p such that the multiplicative order of 8 modulo p is n, or 0 if no such prime exists.

%C First prime p such that the expansion of 1/p has period (p-1)/n in base 8. Also the first prime p such that {k/p : 1 <= k <= p-1} has n different cycles when written out in base 8.

%H Jean-François Alcover, <a href="/A372798/b372798.txt">Table of n, a(n) for n = 1..1000</a>

%e In the following examples let () denote the reptend. The prime numbers themselves and the fractions are written out in decimal.

%e The base-8 expansion of 1/3 is 0.(25), so the reptend has length 2 = (3-1)/1. Also, the base-8 expansions of 1/3 = 0.(25) and 2/3 = 0.(52) have only one cycle 25. 3 is the smallest such prime, so a(1) = 3.

%e The base-8 expansion of 1/17 is 0.(03607417), so the reptend has length 8 = (17-1)/2. Also, the base-8 expansions of 1/17, 2/17, ..., 16/17 have two cycles 03607417 and 13226455. 17 is the smallest such prime, so a(2) = 17.

%e The base-8 expansion of 1/13 is 0.(0473), so the reptend has length 4 = (13-1)/3. Also, the base-8 expansions of 1/13, 2/13, ..., 12/13 have three cycles 0473, 1166 and 2354. 13 is the smallest such prime, so a(3) = 13.

%t a[n_] := a[n] = For[p = 2, True, p = NextPrime[p], If[MultiplicativeOrder[8, p] == (p-1)/n, Return[p]]];

%t Table[Print[n, " ", a[n]]; a[n], {n, 1, 100}] (* _Jean-François Alcover_, Nov 24 2024 *)

%o (PARI) a(n,{base=8}) = forprime(p=2, oo, if((base%p) && znorder(Mod(base,p)) == (p-1)/(n * if(issquare(base), 2, 1)), return(p)))

%Y Cf. A211244.

%Y In other bases: A101208, A101209, A372797, A372798, A372799, A054471, A372800.

%K nonn

%O 1,1

%A _Jianing Song_, May 13 2024