A033949 Positive integers that do not have a primitive root.

8, 12, 15, 16, 20, 21, 24, 28, 30, 32, 33, 35, 36, 39, 40, 42, 44, 45, 48, 51, 52, 55, 56, 57, 60, 63, 64, 65, 66, 68, 69, 70, 72, 75, 76, 77, 78, 80, 84, 85, 87, 88, 90, 91, 92, 93, 95, 96, 99, 100, 102, 104, 105, 108, 110, 111, 112, 114, 115, 116, 117, 119, 120, 123

Offset: 1

Author

Calculated by Jud McCranie

Keywords

• nonn

Comments

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

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

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

Also, numbers k for which A000010(k) > A002322(k), or equivalently A034380(k) > 1. - Ivan Neretin, Mar 28 2015

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

Seems to be A050275 without the duplicates. - Charles R Greathouse IV, Feb 09 2025

References

• I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers, 4th edition, page 62, Theorem 2.25.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Brett A. Harrison, On the reducibility of cyclotomic polynomials over finite fields, Amer. Math. Monthly, Vol 114, No. 9 (2007), 813-818.
• Eldar Sultanow, Christian Koch, and Sean Cox, Collatz Sequences in the Light of Graph Theory, Universität Potsdam (Germany, 2020).
• Wikipedia, Primitive root modulo n

Crossrefs

Cf. A000010, A002322, A033948 (complement), A193305 (composites with primitive root).

Column k=1 of A277915, A281854.

Programs

Haskell

a033949 n = a033949_list !! (n-1)
a033949_list = filter
               (\x -> any ((== 1) . (`mod` x) . (^ 2)) [2 .. x-2]) [1..]
-- Reinhard Zumkeller, Dec 10 2014

Maple

m := proc(n) local k, r; r := 1; if n = 2 then return false fi;
for k from 1 to n do if igcd(n,k) = 1 then r := modp(r*k,n) fi od; r end:
select(n -> m(n) = 1, [$1..123]); # Peter Luschny, May 25 2017

Mathematica

Select[Range[2,130],!IntegerQ[PrimitiveRoot[#]]&] (* Harvey P. Dale, Oct 25 2011 *)
a[n_] := Module[{j, l = {}}, While[Length[l] 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 *)

PARI

is(n)=n>7 && (!isprimepower(if(n%2,n,n/2)) || n>>valuation(n,2)==1) \\ Charles R Greathouse IV, Oct 08 2016

Python

from itertools import count, islice
from sympy.ntheory import sqrt_mod_iter
def A033949_gen(): # generator of terms
    return filter(lambda n:max(filter(lambda k:k 1,count(3))
A033949_list = list(islice(A033949_gen(),30)) # Chai Wah Wu, Oct 26 2022

Python

from sympy import primepi, integer_nthroot
def A033949(n):
    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)))
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Feb 24 2025

Sage

[n for n in range(1,100) if not Integers(n).multiplicative_group_is_cyclic()]
# Ralf Stephan, Mar 30 2014

Formula

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.