login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033949 Positive integers that do not have a primitive root. 37
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
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. See 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
REFERENCES
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers, 4th edition, page 62, Theorem 2.25.
LINKS
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).
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.
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]<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 *)
PROG
(Sage)
[n for n in range(1, 100) if not Integers(n).multiplicative_group_is_cyclic()]
# Ralf Stephan, Mar 30 2014
(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
(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<n-1, sqrt_mod_iter(1, n))) > 1, count(3))
A033949_list = list(islice(A033949_gen(), 30)) # Chai Wah Wu, Oct 26 2022
CROSSREFS
Cf. A000010, A002322, A033948, A193305 (composites with primitive root).
Column k=1 of A277915, A281854.
Sequence in context: A279963 A050275 A363863 * A175594 A272592 A062373
KEYWORD
nonn
AUTHOR
Calculated by Jud McCranie
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 15 15:53 EDT 2024. Contains 374333 sequences. (Running on oeis4.)