A259484 - OEIS

%I #22 Apr 02 2020 10:32:41

%S 1,0,9,4,0,6,1681,22,0,0,97969,118,16900321,914,1062961,542,0,262,

%T 2827367929,382

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

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

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

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

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimitiveRoot.html"> Primitive Root.</a>

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

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

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

%Y Cf. A001597, A023048, A046145, A214158.

%K nonn,hard,more

%O 0,3

%A _Robert G. Wilson v_, Jun 28 2015

%E a(18)-a(19) from _Robert G. Wilson v_, Sep 26 2015