A394337 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.

3, 7, 0, 23, 17, 41, 59, 0, 97, 109, 139, 167, 151, 199, 0, 283, 317, 359, 397, 431, 421, 521, 569, 0, 659, 701, 773, 839, 887, 941, 1019, 1069, 1153, 1223, 0, 1367, 1433, 1489, 1583, 1669, 1753, 1847, 1913, 1997, 2113, 2179, 2297, 0, 2477, 2579, 2699, 2801, 2897

Offset

2,1

Comments

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.

Links

Table of n, a(n) for n=2..54.

Mathematica

Table[If[IntegerQ[Sqrt[b]], 0,
  Prime[NestWhile[# - 1 &, PrimePi[b^2],
    MultiplicativeOrder[b, Prime[#]] < Prime[#] - 1 &]]], {b, 2, 54}]

Prog

(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
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

Crossrefs

Cf. A060749.

Sequence in context: A198490 A354797 A247956 * A295043 A074051 A335918

Adjacent sequences: A394334 A394335 A394336 * A394338 A394339 A394340

Keyword

nonn

Author

Steven Lu, Mar 17 2026

Status

approved