A394337 - OEIS

%I #23 Apr 01 2026 06:54:43

%S 3,7,0,23,17,41,59,0,97,109,139,167,151,199,0,283,317,359,397,431,421,

%T 521,569,0,659,701,773,839,887,941,1019,1069,1153,1223,0,1367,1433,

%U 1489,1583,1669,1753,1847,1913,1997,2113,2179,2297,0,2477,2579,2699,2801,2897

%N The largest prime p which is less than n^2 and n is a primitive root modulo p, or 0 if n is a square.

%C These primes are natural choices for the modulus in a two-digit check digit system in base n, because the check digits are computed modulo p and range from 0 to n^2-1 (i.e., they fit in two base-n digits). The condition that n is a primitive root modulo p ensures that the multiplicative order of n modulo p is maximal (equal to p-1). This maximal order allows the check digit algorithm to detect a wide variety of errors (such as single-digit errors, transpositions, and cyclic shifts) for data strings of length up to p-1 digits. For n = 10, a(10) = 97, and the fact that 10 is a primitive root modulo 97 is exactly what underlies the ISO 7064 MOD 97-10 standard (used e.g. for IBAN numbers), which can handle strings of up to 96 digits.

%t Table[If[IntegerQ[Sqrt[b]], 0,

%t   Prime[NestWhile[# - 1 &, PrimePi[b^2],

%t     MultiplicativeOrder[b, Prime[#]] < Prime[#] - 1 &]]], {b, 2, 54}]

%o (PARI) row(n) = my(p=prime(n), r=vector(eulerphi(p-1)), pr=znprimroot(p), j=0); for(i=1, p-1, if(gcd(i, p-1)==1, r[j++]=lift(pr^i))); vecsort(r); \\ A060749

%o a(n) = if (issquare(n), 0, my(p=precprime(n^2), ip = primepi(p)); while (!vecsearch(row(ip), n), ip--); prime(ip)); \\ _Michel Marcus_, Mar 17 2026

%Y Cf. A060749.

%K nonn

%O 2,1

%A _Steven Lu_, Mar 17 2026