cp's OEIS Frontend

A033949 Positive integers that do not have a primitive root.

%I A033949 #103 Feb 25 2025 07:16:55
%S A033949 8,12,15,16,20,21,24,28,30,32,33,35,36,39,40,42,44,45,48,51,52,55,56,
%T A033949 57,60,63,64,65,66,68,69,70,72,75,76,77,78,80,84,85,87,88,90,91,92,93,
%U A033949 95,96,99,100,102,104,105,108,110,111,112,114,115,116,117,119,120,123
%N A033949 Positive integers that do not have a primitive root.
%C A033949 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 A033949 The multiplicative group modulo k is non-cyclic; the complement A033948. - _Wolfdieter Lang_, Mar 14 2012. See A281854 for the groups. - _Wolfdieter Lang_, Feb 04 2017
%C A033949 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 A033949 Also, numbers k for which A000010(k) > A002322(k), or equivalently A034380(k) > 1. - _Ivan Neretin_, Mar 28 2015
%C A033949 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
%C A033949 Seems to be A050275 without the duplicates. - _Charles R Greathouse IV_, Feb 09 2025
%D A033949 I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers, 4th edition, page 62, Theorem 2.25.
%H A033949 T. D. Noe, <a href="/A033949/b033949.txt">Table of n, a(n) for n = 1..10000</a>
%H A033949 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 A033949 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 A033949 Wikipedia, <a href="https://en.wikipedia.org/wiki/Primitive_root_modulo_n">Primitive root modulo n</a>
%F A033949 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 A033949 m := proc(n) local k, r; r := 1; if n = 2 then return false fi;
%p A033949 for k from 1 to n do if igcd(n,k) = 1 then r := modp(r*k,n) fi od; r end:
%p A033949 select(n -> m(n) = 1, [$1..123]); # _Peter Luschny_, May 25 2017
%t A033949 Select[Range[2,130],!IntegerQ[PrimitiveRoot[#]]&] (* _Harvey P. Dale_, Oct 25 2011 *)
%t A033949 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 A033949 (Sage)
%o A033949 [n for n in range(1,100) if not Integers(n).multiplicative_group_is_cyclic()]
%o A033949 # _Ralf Stephan_, Mar 30 2014
%o A033949 (Haskell)
%o A033949 a033949 n = a033949_list !! (n-1)
%o A033949 a033949_list = filter
%o A033949                (\x -> any ((== 1) . (`mod` x) . (^ 2)) [2 .. x-2]) [1..]
%o A033949 -- _Reinhard Zumkeller_, Dec 10 2014
%o A033949 (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 A033949 (Python)
%o A033949 from itertools import count, islice
%o A033949 from sympy.ntheory import sqrt_mod_iter
%o A033949 def A033949_gen(): # generator of terms
%o A033949     return filter(lambda n:max(filter(lambda k:k<n-1,sqrt_mod_iter(1,n))) > 1,count(3))
%o A033949 A033949_list = list(islice(A033949_gen(),30)) # _Chai Wah Wu_, Oct 26 2022
%o A033949 (Python)
%o A033949 from sympy import primepi, integer_nthroot
%o A033949 def A033949(n):
%o A033949     def f(x): return int(n+1+(x>=2)+(x>=4)+sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length()))+sum(primepi(integer_nthroot(x>>1,k)[0])-1 for k in range(1,x.bit_length()-1)))
%o A033949     m, k = n, f(n)
%o A033949     while m != k: m, k = k, f(k)
%o A033949     return m # _Chai Wah Wu_, Feb 24 2025
%Y A033949 Cf. A000010, A002322, A033948 (complement), A193305 (composites with primitive root).
%Y A033949 Column k=1 of A277915, A281854.
%K A033949 nonn
%O A033949 1,1
%A A033949 Calculated by _Jud McCranie_