A033949 -id:A033949 - cp's OEIS frontend

A082568 First nontrivial square root of unity mod A033949(n), i.e., smallest x > 1 such that x^2 == 1 mod A033949(n).

3, 5, 4, 7, 9, 8, 5, 13, 11, 15, 10, 6, 17, 14, 9, 13, 21, 19, 7, 16, 25, 21, 13, 20, 11, 8, 31, 14, 23, 33, 22, 29, 17, 26, 37, 34, 25, 9, 13, 16, 28, 21, 19, 27, 45, 32, 39, 17, 10, 49, 35, 25, 29, 53, 21, 38, 15, 37, 24, 57, 53, 50, 11, 40, 61, 55, 63, 44

Offset: 1

Jon Perry, May 06 2003

nonn

			a(3) = 4 because A033949(3) = 15 and 4^2 = 16 == 1 mod 15 is the first integer to do so.

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Cf. A033949.

Column k=1 of A277776.

for (n=3,100, for (j=2,n-2,if (j^2%n==1,print1(j","); break)))

from itertools import chain, count, islice
from sympy.ntheory import sqrt_mod_iter
def A082568_gen(): # generator of terms
    return chain.from_iterable((sorted(filter(lambda m:1A082568_list = list(islice(A082568_gen(),30)) # Chai Wah Wu, Oct 26 2022

Offset corrected, name clarified and more terms from Alois P. Heinz, Oct 30 2016

A282624 Irregular triangle read by rows: row n gives a certain choice of generators of the multiplicative group of integers modulo A033949(n).

Original entry on oeis.org

3, 5, 5, 7, 2, 11, 3, 7, 3, 11, 2, 13, 5, 7, 13, 3, 13, 7, 11, 3, 31, 2, 23, 19, 13, 5, 19, 17, 5, 3, 11, 29, 5, 13, 3, 43, 11, 17, 5, 7, 17, 5, 35, 3, 5, 19, 23, 3, 13, 29, 2, 37, 7, 11, 19, 2, 5, 3, 31, 2, 31, 5, 43, 3, 67, 2, 68, 19, 13, 5, 17, 19, 11, 7

Offset: 1

Wolfdieter Lang, Mar 03 2017

The length of row n is given by A046072(A033949(n)), n >= 1.
The generators are chosen minimally in the sense that the product of their orders (cycle lengths) is phi(N(n)) = A000010(N(n)) with N(n) = A033949(n). In addition, the generators are sorted with nonincreasing orders, and the smallest numbers with these orders are listed.
Note that the first instance where a composite generator is needed is N = 51 = A033949(20) with a generator 35. The next such number is N = 69 = A033949(31) with a generator 68. Such numbers N will be called exceptional.
For a table with n = 1..69, N = 8, 12, ..., 130, see the W. Lang link. Compare this with the Wikipedia table (where some generator errors will be corrected). There non-minimal generators are also used, i.e., the product of the orders of the generators is larger than phi(N). The Wikipedia table often uses composite generators when primes would do the job. E.g., N = 16 with generators 2, 14 instead of 2, 11; or N = 16 with 3, 15 instead of 3, 7, etc.

			The irregular triangle T(n, k) begins (here N = A033949(n), and the respective primitive cycle lengths and phi(N) are also given)
n,   N \k 1   2   3 ... cycle lengths, phi(N)
1,   8:   3   5           2  2          4
2,  12:   5   7           2  2          4
3,  15:   2  11           4  2          8
4,  16:   3   7           4  2          8
5,  20:   3  11           4  2          8
6,  21:   2  13           6  2         12
7,  24:   5   7  13       2  2  2       8
8,  28:   3  13           6  2         12
9,  30:   7  11           4  2          8
10, 32:   3  31           8  2         16
11, 33:   2  23          10  2         20
12, 35:  19  13           6  4         24
13, 36:   5  19           6  2         12
14, 39:  17   5           6  4         24
15, 40:   3  11  29       4  2  2      16
16: 42:   5  13           6  2         12
17, 44:   3  43          10  2         20
18, 45:  11  17           6  4         24
19, 48:   5   7  17       4  2  2      16
20, 51:   5  35          16  2         32
... See the link for more.

Wolfdieter Lang, Table for the multiplicative non-cyclic groups of integers modulo A033949.
Eldar Sultanow, Christian Koch, and Sean Cox, Collatz Sequences in the Light of Graph Theory, Universität Potsdam (Germany, 2020).

Cf. A033949, A046072, A279399, A281855, A281856, A282623, A282625.

A281854 Irregular triangle read by rows. Row n gives the orders of the cyclic groups appearing as factors in the direct product decomposition of the abelian non-cyclic multiplicative groups of integers modulo A033949(n).

Original entry on oeis.org

2, 2, 2, 2, 4, 2, 4, 2, 4, 2, 3, 2, 2, 2, 2, 2, 3, 2, 2, 4, 2, 8, 2, 5, 2, 2, 4, 3, 2, 3, 2, 2, 4, 3, 2, 4, 2, 2, 3, 2, 2, 5, 2, 2, 4, 3, 2, 4, 2, 2, 16, 2, 4, 3, 2, 5, 4, 2, 3, 2, 2, 2, 9, 2, 2, 4, 2, 2

Offset: 1

Wolfdieter Lang, Feb 02 2017

The length of row n is given in A281855.
The multiplicative group of integers modulo n is written as (Z/(n Z))^x (in ring notation, group of units) isomorphic to Gal(Q(zeta(n))/Q) with zeta(n) = exp(2*Pi*I/n). The present table gives in row n the factors of the direct product decomposition of the non-cyclic group of integers modulo A033949(n) (in nonincreasing order). The cyclic group of order n is C_n. Note that only C-factors of prime power orders are used; for example C_6 has the decomposition C_3 x C_2, etc. C_n is decomposed whenever n has relatively prime factors like in C_30 = C_15 x C_2 = C_5 x C_3 x C_2. In the Wikipedia table partial decompositions appear.
The row products phi(A033949(n)) are given as 4*A281856(n), n >= 1, with phi(n) = A000010(n).
See also the W. Lang links for these groups.

			The triangle T(n, k) begins (N = A033949(n)):
n,   N, phi(N)\ k  1  2  3  4 ...
1,   8,   4:       2  2
2,  12,   4:       2  2
3,  15,   8:       4  2
4,  16,   8:       4  2
5,  20,   8:       4  2
6,  21,  12:       3  2  2
7,  24,   8:       2  2  2
8,  28,  12:       3  2  2
9,  30,   8:       4  2
10, 32,  16:       8  2
11, 33,  20:       5  2  2
12, 35,  24:       4  3  2
13, 36,  12:       3  2  2
14, 39,  24:       4  3  2
15, 40,  16:       4  2  2
16, 42,  12:       3  2  2
17, 44,  20:       5  2  2
18, 45,  24:       4  3  2
19, 48,  16:       4  2  2
20, 51,  32:      16  2
21, 52,  24:       4  3  2
22, 55,  40:       5  4  2
23, 56,  24:       3  2  2  2
24, 57,  36:       9  2  2
25, 60,  16:       4  2  2
...
n = 6, A033949(6) = N = 21, phi(21) = 12, group (Z/21 n)^x decomposition C_3 x C_2 x C_2 (in the Wikipedia Table C_2 x C_6). The smallest positive reduced system modulo 21 has the primes {2, 5, 11, 13, 17, 19} with cycle lengths {6, 6, 6, 2, 6, 6}, respectively. As generators of the group one can take <2, 13>.
  (In the Wikipedia Table <2, 20> is used).
----------------------------------------------
From _Wolfdieter Lang_, Feb 04 2017: (Start)
n = 32, A033949(32) = N = 70, phi(70) = 24.
Cycle types (multiplicity as subscript): 12_7, 6_4, 4_2, 3_1, 2_2 (a total of 16 cycles). Cycle structure: 12_2, 6_2 (all other cycles are sub-cycles).
The first 12-cycle obtained from the powers of, say 3, contains also the 12-cycles from 17 and 47. It also contains the 4-cycle from 13, the 3-cycle from 11 and the 2-cycle from 29.
The second 12-cycle from the powers of, say, 23 contains also the 12-cycles from 37, 53 and 67, as well as the 4-cycle from 43.
The first 6-cycle from the powers of, say, 19 contains also the 6-cycle of 59 as well as the 2-cycle from 41.
The second 6-cycle from the powers of, say, 31 contains also the 6-cycle from 61.
The group is C_6 x C_4 = (C_2 x C_3) x C_4 = C_4 X C_3 x C_2 (see the W. Lang link, Table 7)
The cycle graph of C_4 X C_3 x C_2 is the 7th entry of Figure 4 of this link.
(End)

Wolfdieter Lang, The field Q(2cos(pi/n)), its Galois group and length ratios in the regular n-gon, Table 7 (in row n = 80 it should read Z_4^2 x Z_2), arXiv:1210.1018 [math.GR], 2012.
Wolfdieter Lang, Table for the multiplicative non-cyclic groups of integers modulo A033949.
Wikipedia, Multiplicative group of integers modulo n . Compare with the Table at the end.

Cf. A033949, A192005, A281855, A282624.

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.

Original entry on oeis.org

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

Offset: 1

Wolfdieter Lang, Mar 03 2017

See A281854.

Compare this with A046072(A033949(n)). In A046072 the decompositions used are not total, e.g., n = 6 with A033949(6) = 1 uses C_6, but C_6 = C_2 x C_3. Or, 21 = A033949(6), A046072(21) = 2 not 3 = a(6).

Cf. A033949, A046072, A281854, A282623, A282624, A282625.

A277777 Largest nontrivial square root of unity modulo the n-th positive integer that does not have a primitive root (A033949).

Original entry on oeis.org

5, 7, 11, 9, 11, 13, 19, 15, 19, 17, 23, 29, 19, 25, 31, 29, 23, 26, 41, 35, 27, 34, 43, 37, 49, 55, 33, 51, 43, 35, 47, 41, 55, 49, 39, 43, 53, 71, 71, 69, 59, 67, 71, 64, 47, 61, 56, 79, 89, 51, 67, 79, 76, 55, 89, 73, 97, 77, 91, 59, 64, 69, 109, 83, 63, 71

Offset: 1

Alois P. Heinz, Oct 30 2016

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Wikipedia, Root of unity modulo n

Last elements of nonempty rows of A277776.

Cf. A033948, A033949, A082568.

from gmpy2 import *
def f(n):
  for k in range(n - 2, 0, -1):
    if pow(k, 2, n) == 1:
      return k
def A277777(L):
  return [j for j in [f(k) for k in range(3, L + 1)] if j > 1] # Darío Clavijo, Oct 15 2022

from itertools import count, islice
from sympy.ntheory import sqrt_mod_iter
def A277777_gen(): # generator of terms
    for n in count(3):
        if (m:=max(filter(lambda k:k 1:
            yield m
A277777_list = list(islice(A277777_gen(),30)) # Chai Wah Wu, Oct 26 2022

a(n) = A033949(n) - A082568(n).

A279399 Irregular triangle read by rows. Row n gives the primes of the smallest positive restricted residue system modulo A033949(n).

Original entry on oeis.org

3, 5, 7, 5, 7, 11, 2, 7, 11, 13, 3, 5, 7, 11, 13, 3, 7, 11, 13, 17, 19, 2, 5, 11, 13, 17, 19, 5, 7, 11, 13, 17, 19, 23, 3, 5, 11, 13, 17, 19, 23, 7, 11, 13, 17, 19, 23, 29, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 2, 5, 7, 13, 17, 19, 23, 29, 31, 2, 3, 11, 13, 17, 19, 23, 29, 31, 5, 7, 11, 13, 17, 19, 23, 29, 31, 2, 5, 7, 11, 17, 19, 23, 29, 31, 37, 3, 7, 11, 13, 17, 19, 23, 29, 31, 37

Offset: 1

Wolfdieter Lang, Jan 25 2017

The length of row n is given by A279400(n)
For the restricted residue systems modulo n see A038566. For the primes of A038566 (for n >= 3) see A112484.
The primes of the restricted residue system modulo the (composite) positive numbers without a primitive root, given in A033949, are of interest for the determination of the Dirichlet characters modulo the A033949 numbers. For prime numbers (A000040) or for composite positive numbers that have prime primitive roots (A279398) the Dirichlet characters are determined from those of the prime primitive root.

			The triangle T(n, k) begins (here N = A033949(n)):
n,   N \ k 1  2  3  4  5  6  7  8  9 10 ...
1,   8:    3  5  7
2,  12:    5  7 11
3,  15:    2  7 11 13
4,  16:    3  5  7 11 13
5,  20:    3  7 11 13 17 19
6,  21:    2  5 11 13 17 19
7,  24:    5  7 11 13 17 19 23
8,  28:    3  5 11 13 17 19 23
9,  30:    7 11 13 17 19 23 29
10, 32:    3  5  7 11 13 17 19 23 29 31
11, 33:    2  5  7 13 17 19 23 29 31
12, 35:    2  3 11 13 17 19 23 29 31
13, 36:    5  7 11 13 17 19 23 29 31
14, 39:    2  5  7 11 17 19 23 29 31 37
15, 40:    3  7 11 13 17 19 23 29 31 37
...

Cf. A000040, A033949, A038566, A112484, A279398, A279400, A279401.

Row n of T is given by the primes of row A033949(n) of A038566, for n >= 1.

T(n, k) = A112484(A033949(n), k), n >= 1, k = 1..A279400(n).

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.

A282623 Number of independent cycles of the multiplicative group of integers modulo A033949(n).

Original entry on oeis.org

3, 3, 4, 4, 4, 3, 7, 3, 4, 5, 3, 4, 3, 4, 10, 3, 3, 4, 10, 6, 4, 4, 7, 3, 10, 12, 6, 6, 3, 6, 3, 4, 7, 4, 3, 3, 4, 16, 7, 10, 4, 7, 4, 16, 3, 3, 4, 13, 3, 4

Offset: 1

Wolfdieter Lang, Mar 03 2017

A cycle starting with number a of the restricted residue system modulo m (namely the one with the smallest positive numbers RRS(m)) is independent of a cycle starting with number b != a if the set of numbers of the a-cycle is not a (not necessarily proper) subset of the numbers of the b-cycle.
See Table 7, column 4 of the W. Lang link for these numbers.
See also the Table in the W. Lang link given in A282624 for these independent cycles.

			a(1) = 3 because A033949(1) = 8 with RRS(8) = {1, 3, 5, 7} and the three 2-cycles [3,1],[5,1] and [7,1], which are independent.
a(4) = 4 because A033949(4) = 16 with RRS(16) = {1, 3, 5, 7, 9, 11, 13, 15} and only, e.g., the cycles from 3, 5, 7 and 15 are independent. The cycles [1], [9, 1], [11, 9, 3, 1] and [13, 9, 5, 1] are not independent. One could replace 5 with 13 but we always take the smallest numbers.

Wolfdieter Lang, The field Q(2cos(pi/n)), its Galois group and length ratios in the regular n-gon, arXiv:1210.1018 [math.GR], 2012-2017.

Cf. A033949, A282624.

A357099 Second nontrivial square root of unity mod A033949(n), i.e., second smallest x > 1 such that x^2 == 1 mod the n-th positive integer that does not have a primitive root.

Original entry on oeis.org

5, 7, 11, 9, 11, 13, 7, 15, 19, 17, 23, 29, 19, 25, 11, 29, 23, 26, 17, 35, 27, 34, 15, 37, 19, 55, 33, 51, 43, 35, 47, 41, 19, 49, 39, 43, 53, 31, 29, 69, 59, 23, 71, 64, 47, 61, 56, 31, 89, 51, 67, 27, 34, 55, 89, 73, 41, 77, 91, 59, 64, 69, 19, 83, 63, 71

Offset: 1

Alois P. Heinz, Oct 25 2022

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Column k=2 of A277776.

Cf. A033949, A082568.

from itertools import count, chain, islice
from sympy.ntheory import sqrt_mod_iter
def A357099_gen(): # generator of terms
    return chain.from_iterable((sorted(filter(lambda m:1A357099_list = list(islice(A357099_gen(),30)) # Chai Wah Wu, Oct 26 2022

A255979 a(n) = smallest nonnegative integer solution z to the system of congruences: z == 0 (mod n), z == 1 (mod A038610(n)) if n is in A033948; or z == 0 (mod n), z == -1 (mod A038610(n)) if n is in A033949.

Original entry on oeis.org

0, 0, 1, 1, 5, 1, 43, 13, 249, 19, 2291, 32, 6397, 1379, 3737, 36599, 423953, 4727, 2579419, 436486, 1935539, 1262563, 30364247, 1549256, 1028011945, 94055426, 2754232963, 230491358, 77544004469, 7188548, 1277242663471, 4089553744057, 235736847903

Offset: 1

Bruno Berselli, Mar 12 2015 - proposed by Umberto Cerruti (Department of Mathematics "Giuseppe Peano", University of Turin, Italy)

Umberto Cerruti, Il Teorema Cinese dei Resti (in Italian), 2015. The sequence is on page 26.

Cf. A033948, A033949, A038610.

v[n_] := Module[{s}, s = Select[Range[n], CoprimeQ[n, #] == True &]; LCM @@ s]; g1[n_] := If[n == 1, 0, If[IntegerQ[PrimitiveRoot[n]], PowerMod[n, -1, v[n]], PowerMod[-n, -1, v[n]]]]; Table[g1[k], {k, 1, 40}]

cp's OEIS Frontend

A082568 First nontrivial square root of unity mod A033949(n), i.e., smallest x > 1 such that x^2 == 1 mod A033949(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Extensions

A282624 Irregular triangle read by rows: row n gives a certain choice of generators of the multiplicative group of integers modulo A033949(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A281854 Irregular triangle read by rows. Row n gives the orders of the cyclic groups appearing as factors in the direct product decomposition of the abelian non-cyclic multiplicative groups of integers modulo A033949(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A277777 Largest nontrivial square root of unity modulo the n-th positive integer that does not have a primitive root (A033949).

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Python

Formula

A279399 Irregular triangle read by rows. Row n gives the primes of the smallest positive restricted residue system modulo A033949(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

A282623 Number of independent cycles of the multiplicative group of integers modulo A033949(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A357099 Second nontrivial square root of unity mod A033949(n), i.e., second smallest x > 1 such that x^2 == 1 mod the n-th positive integer that does not have a primitive root.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A255979 a(n) = smallest nonnegative integer solution z to the system of congruences: z == 0 (mod n), z == 1 (mod A038610(n)) if n is in A033948; or z == 0 (mod n), z == -1 (mod A038610(n)) if n is in A033949.

Views