A281854 -id:A281854 - cp's OEIS frontend

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

Calculated by Jud McCranie

nonn

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

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

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

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

Column k=1 of A277915, A281854.

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

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

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 *)

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

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

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

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

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.

A282625 Number of cyclic groups in the total direct product factorization of the multiplicative group of integers modulo n, for n >= 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 3, 2, 2, 3, 2, 3, 1, 3, 3, 2, 2, 3, 3, 2, 3, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 2, 2, 3, 4, 3, 2, 2, 3, 3, 3, 4, 2, 3, 3, 3, 2, 3, 3, 3, 4, 2, 2, 3, 3, 4, 3, 3, 3, 2, 2, 2, 4, 2, 3, 3, 4, 2, 3, 4, 3, 4, 2, 3, 3, 2, 3, 4, 3

Offset: 1

Wolfdieter Lang, Mar 02 2017

nonn

The multiplicative group of integers modulo n, (Z/n*Z)^x, also the cyclotomic group, the Galois group Gal(Q(zeta(n))/Q) with zeta(n) = exp(2*Pi*I/n), is cyclic for n from A033948 and non-cyclic for n from A033949. Each of these groups is the direct product of cyclic factors (one factor is included).
In the total factorization for n >= 3 only cyclic factors whose orders are prime powers appear, and because the direct product is associative, and for these abelian groups also commutative, one can order the factors with nonincreasing orders.
For n=1 and n=2 the group is C_1 = {1} (for n=1 one has 1 == 0 (mod 1)).
Cyclic groups may also have a factorization into more than one factor. E.g., C_6 = C_3 x C_2.
The number of factors in this total factorization is for a cyclic group C_m, for m >= 2, given by A001221(m). For m=1 this number is 1 (not A001221(1)).
For non-cyclic groups the number of factors in this total factorization is given by A281855(m) if n = A033949(m), m >= 1.
For the non-cyclic group case see also the W. Lang links under A281854.
Compare this sequence with A046072 where another factorization of these groups is used, the one with the least cyclic factors. E.g., A046072(7) = 1 for the group C_6, and a(7) = 2 here (see the example above).

			n = 35, a non-cyclic case because A033949(12) = 35. The group can be written as <19_6, 13_4 > where the orders modulo 35 of the generators are given as subscript. Therefore the group is C_6 x C4 = C_4 x C_3 x C_2 and a(35) = 3, whereas A046072(35) = 2.

Cf. A001221, A033948, A033949, A046072, A281854, A281855, A282624.

A281856 One fourth of the order of the abelian non-cyclic groups (Z/A033949(n)*Z)^x.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 2, 3, 2, 4, 5, 6, 3, 6, 4, 3, 5, 6, 4, 8, 6, 10, 6, 9, 4, 9, 8, 12, 5, 8, 11, 6, 6, 10, 9, 15, 6, 8, 6, 16, 14, 10, 6, 18, 11, 15, 18, 8, 15, 10, 8, 12, 12, 9, 10, 18, 12, 9, 22, 14, 18, 24, 8, 20, 15, 9, 16, 21, 12, 10, 27, 18, 16, 11, 12, 23

Offset: 1

Wolfdieter Lang, Feb 02 2017

nonn

a(n) is one fourth of the row product of the irregular triangle A281854.

Cf. A000010, A033949, A060679, A281854.

EulerPhi@ Select[Range[2, 130], ! IntegerQ@ PrimitiveRoot@ # &]/4 (* Michael De Vlieger, Feb 02 2017 *)

from sympy import primepi, integer_nthroot, totient
def A281856(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 totient(m)>>2 # Chai Wah Wu, Feb 25 2025

a(n) = A000010(A033949(n))/4, n >= 1.

cp's OEIS Frontend

A281855 Number of cyclic group factors in the total decomposition of the abelian non-cyclic group (Z/A033949(n) Z)^x. Row lengths of A281854.

Views

Author

Keywords

Comments

Crossrefs

A033949 Positive integers that do not have a primitive root.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Sage

Formula

A282625 Number of cyclic groups in the total direct product factorization of the multiplicative group of integers modulo n, for n >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A281856 One fourth of the order of the abelian non-cyclic groups (Z/A033949(n)*Z)^x.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Python

Formula