|
%I #92 Oct 02 2023 11:44:53
%S 8,12,15,16,20,21,24,28,30,32,33,35,36,39,40,42,44,45,48,51,52,55,56,
%T 57,60,63,64,65,66,68,69,70,72,75,76,77,78,80,84,85,87,88,90,91,92,93,
%U 95,96,99,100,102,104,105,108,110,111,112,114,115,116,117,119,120,123
%N Positive integers that do not have a primitive root.
%C Numbers k such that the cyclotomic polynomial Phi(k,x) is reducible over Zp for all primes p. Harrison shows that this is equivalent to k > 2 and the discriminant of Phi(k,x), A004124(k), being a square. - _T. D. Noe_, Nov 06 2007
%C The multiplicative group modulo k is non-cyclic. See the complement A033948. - _Wolfdieter Lang_, Mar 14 2012. See A281854 for the groups. - _Wolfdieter Lang_, Feb 04 2017
%C Numbers k with the property that there exists a positive integer m with 1 < m < k-1 and m^2 == 1 (mod k). - _Reinhard Muehlfeld_, May 27 2014
%C Also, numbers k for which A000010(k) > A002322(k), or equivalently A034380(k) > 1. - _Ivan Neretin_, Mar 28 2015
%C Numbers k of the form a + b + 2*sqrt(a*b + 1) for positive integers a,b such that a*b + 1 is a square. Proof: If 1 < m < k - 1 and m^2 == 1 (mod k), take a = (m^2 - 1)/k and b = ((k - m)^2 - 1)/k. Conversely, if k = a + b + 2*sqrt(a*b + 1), take m = a + sqrt(a*b + 1). - _Tor Gunston_, Apr 24 2021
%D I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers, 4th edition, page 62, Theorem 2.25.
%H T. D. Noe, <a href="/A033949/b033949.txt">Table of n, a(n) for n = 1..10000</a>
%H Brett A. Harrison, <a href="http://www.jstor.org/stable/27642336">On the reducibility of cyclotomic polynomials over finite fields</a>, Amer. Math. Monthly, Vol 114, No. 9 (2007), 813-818.
%H Eldar Sultanow, Christian Koch, and Sean Cox, <a href="https://doi.org/10.25932/publishup-48214">Collatz Sequences in the Light of Graph Theory</a>, Universität Potsdam (Germany, 2020).
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Primitive_root_modulo_n">Primitive root modulo n</a>
%F Positive integers except 1, 2, 4 and numbers of the form p^i and 2p^i, where p is an odd prime and i >= 1.
%p m := proc(n) local k, r; r := 1; if n = 2 then return false fi;
%p for k from 1 to n do if igcd(n,k) = 1 then r := modp(r*k,n) fi od; r end:
%p select(n -> m(n) = 1, [$1..123]); # _Peter Luschny_, May 25 2017
%t Select[Range[2,130],!IntegerQ[PrimitiveRoot[#]]&] (* _Harvey P. Dale_, Oct 25 2011 *)
%t a[n_] := Module[{j, l = {}}, While[Length[l]<n, For[j = 1+If[l=={}, 0, l // Last], True, j++, If[EulerPhi[j] > CarmichaelLambda[j], AppendTo[l, j]; Break[]]]]; l[[n]]]; Array[a, 100] (* _Jean-François Alcover_, May 29 2018, after _Alois P. Heinz_'s Maple code for A277915 *)
%o (Sage)
%o [n for n in range(1,100) if not Integers(n).multiplicative_group_is_cyclic()]
%o # _Ralf Stephan_, Mar 30 2014
%o (Haskell)
%o a033949 n = a033949_list !! (n-1)
%o a033949_list = filter
%o (\x -> any ((== 1) . (`mod` x) . (^ 2)) [2 .. x-2]) [1..]
%o -- _Reinhard Zumkeller_, Dec 10 2014
%o (PARI) is(n)=n>7 && (!isprimepower(if(n%2,n,n/2)) || n>>valuation(n,2)==1) \\ _Charles R Greathouse IV_, Oct 08 2016
%o (Python)
%o from itertools import count, islice
%o from sympy.ntheory import sqrt_mod_iter
%o def A033949_gen(): # generator of terms
%o return filter(lambda n:max(filter(lambda k:k<n-1,sqrt_mod_iter(1,n))) > 1,count(3))
%o A033949_list = list(islice(A033949_gen(),30)) # _Chai Wah Wu_, Oct 26 2022
%Y Cf. A000010, A002322, A033948, A193305 (composites with primitive root).
%Y Column k=1 of A277915, A281854.
%K nonn
%O 1,1
%A Calculated by _Jud McCranie_
|
