A259484 Smallest nonprime number having least positive primitive root n, or 0 if no such root exists.

1, 0, 9, 4, 0, 6, 1681, 22, 0, 0, 97969, 118, 16900321, 914, 1062961, 542, 0, 262, 2827367929, 382

Offset: 0

Author

Robert G. Wilson v, Jun 28 2015

Keywords

• nonn
• hard
• more

Comments

The value 0 at indices 4, 8, 9, 16, ..., says 0 has no primitive roots (A001597), but the 0 at index 1 says 1 has a primitive root of 0, the only real 0 in the sequence.

a(n) cannot be 2, 4, the odd power of a prime or twice the odd power of a prime.

Conjecture: each odd-indexed value will be populated before either of its even-indexed neighbors.

Examples

			a(2) = 9 because the least primitive root of the nonprime number 9 is 2 and no nonprime less than 9 meets this criterion.
		

References

• A. E. Western and J. C. P. Miller, Tables of Indices and Primitive Roots. Royal Society Mathematical Tables, Vol. 9, Cambridge Univ. Press, 1968, p. XLIV.

Links

• Eric Weisstein's World of Mathematics, Primitive Root.

Crossrefs

Cf. A001597, A023048, A046145, A214158.

Programs

Mathematica

smallestPrimitiveRoot[n_ /; n <= 1] = 0; smallestPrimitiveRoot[n_] := Block[{pr = PrimitiveRoot[n], g}, If[ !NumericQ[pr], g = 0, g = 1; While[g <= pr, If[ CoprimeQ[g, n] && MultiplicativeOrder[g, n] == EulerPhi[n], Break[]]; g++]]; g]; (* This part of the code is from Jean-François Alcover as found in A046145, Feb 15 2012 *)
t = Table[-1, {1000}];  ppQ[n_] := GCD @@ Last /@ FactorInteger@ n > 1; ppQ[1] = True; k = 1; While[ k < 1001, If[ ppQ@ k, t[[k]] = 0]; k++]; k = 1; While[k < 200000001, If[ !PrimeQ[k], a = smallestPrimitiveRoot[k]; If[ t[[a]] == -1, t[[a]] = k]]; k++]; t

Formula

a(n) = 0 if n is a perfect power (A001597).

Extensions

a(18)-a(19) from Robert G. Wilson v, Sep 26 2015