A023142 -id:A023142 - cp's OEIS frontend

A000374 Number of cycles (mod n) under doubling map.

1, 1, 2, 1, 2, 2, 3, 1, 3, 2, 2, 2, 2, 3, 5, 1, 3, 3, 2, 2, 6, 2, 3, 2, 3, 2, 4, 3, 2, 5, 7, 1, 5, 3, 6, 3, 2, 2, 5, 2, 3, 6, 4, 2, 8, 3, 3, 2, 5, 3, 8, 2, 2, 4, 5, 3, 5, 2, 2, 5, 2, 7, 13, 1, 7, 5, 2, 3, 6, 6, 3, 3, 9, 2, 8, 2, 6, 5, 3, 2, 5, 3, 2, 6, 12, 4, 5, 2, 9, 8, 10, 3, 14, 3, 5, 2, 3, 5, 8, 3

Offset: 1

Shel Kaphan

nonn

Number of cycles of the function f(x) = 2x mod n. Number of irreducible factors in the factorization of the polynomial x^n-1 over GF(2). - T. D. Noe, Apr 16 2003

			a(14) = 3 because (1) the function 2x mod 14 has the three cycles (0),(2,4,8),(6,12,10) and (2) the factorization of x^14-1 over integers mod 2 is (1+x)^2 (1+x+x^3)^2 (1+x^2+x^3)^2, which has three unique factors. Note that the length of the cycles is the same as the degree of the factors.

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

T. D. Noe, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
Jarkko Peltomäki and Aleksi Saarela, Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also arXiv:2004.14657 [cs.FL], 2020.

Cf. A000005, A023135-A023142.
Cf. A081844 (number of irreducible factors of x^(2n+1) - 1 over GF(2)).
Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2).

Table[Length[FactorList[x^n - 1, Modulus -> 2]] - 1, {n, 100}]
CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i}, While[Mod[m, p]==0, m/=p]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[2, n], {n, 100}]

a(n)={sumdiv(n >> valuation(n,2), d, eulerphi(d)/znorder(Mod(2,d)));}
vector(100,n,a(n)) \\ Andrew Howroyd, Nov 12 2018

from sympy import totient, n_order, divisors
def A000374(n): return sum(totient(d)//n_order(2,d) for d in divisors(n>>(~n & n-1).bit_length(),generator=True) if d>1)+1 # Chai Wah Wu, Apr 09 2024

a(n) = Sum_{d|m} phi(d)/ord(2, d), where m is n with all factors of 2 removed. - T. D. Noe, Apr 19 2003

a(n) = (1/ord(2,m))*Sum_{j = 0..ord(2,m)-1} gcd(2^j - 1, m), where m is n with all factors of 2 removed. - Nihar Prakash Gargava, Nov 12 2018

A023136 Number of cycles of function f(x) = 4x mod n.

Original entry on oeis.org

1, 1, 3, 1, 3, 3, 3, 1, 5, 3, 3, 3, 3, 3, 9, 1, 5, 5, 3, 3, 9, 3, 3, 3, 5, 3, 7, 3, 3, 9, 7, 1, 9, 5, 9, 5, 3, 3, 9, 3, 5, 9, 7, 3, 15, 3, 3, 3, 5, 5, 15, 3, 3, 7, 9, 3, 9, 3, 3, 9, 3, 7, 23, 1, 13, 9, 3, 5, 9, 9, 3, 5, 9, 3, 15, 3, 9, 9, 3, 3, 9, 5, 3, 9, 23, 7, 9, 3, 9, 15, 17, 3, 21, 3, 9, 3, 5, 5, 15, 5, 3, 15

Offset: 1

David W. Wilson

nonn

			a(9) = 5 because the function 4x mod 9 has the five cycles (0),(3),(6),(1,4,7),(2,8,5).

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000374, A133703, A133702.

Cf. A023135, A023137, A023138, A023139, A023140, A023141, A023142.

CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i, ps, j}, ps=Transpose[FactorInteger[p]][[1]]; Do[While[Mod[m, ps[[j]]]==0, m/=ps[[j]]], {j, Length[ps]}]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[4, n], {n, 100}]

a(n)=sumdiv(n>>valuation(n,2), d, eulerphi(d)/znorder(Mod(4,d))) \\ Charles R Greathouse IV, Aug 05 2016

from sympy import totient, n_order, divisors
def A023136(n): return sum(totient(d)//n_order(4,d) for d in divisors(n>>(~n & n-1).bit_length(),generator=True) if d>1)+1 # Chai Wah Wu, Apr 09 2024

a(n) = Sum_{d|m} phi(d)/ord(4, d), where m is n with all factors of 2 removed. The formula was developed by extending the ideas in A000374 to composite multipliers. - T. D. Noe, Apr 21 2003
Mobius transform of A133702: (1, 2, 4, 3, 4, 8, 4, 4, 9, 8, ...). = Row sums of triangle A133703. - Gary W. Adamson, Sep 21 2007
a(n) = (1/ord(4, m))*Sum_{j = 0..ord(4, m) - 1} gcd(4^j - 1, m), where m is the odd part of n (A000265). - Nihar Prakash Gargava, Nov 14 2018

A023135 Number of cycles of function f(x) = 3x mod n.

Original entry on oeis.org

1, 2, 1, 3, 2, 2, 2, 5, 1, 4, 3, 3, 5, 4, 2, 7, 2, 2, 2, 7, 2, 6, 3, 5, 3, 10, 1, 7, 2, 4, 2, 9, 3, 4, 5, 3, 3, 4, 5, 13, 6, 4, 2, 9, 2, 6, 3, 7, 3, 6, 2, 15, 2, 2, 6, 13, 2, 4, 3, 7, 7, 4, 2, 11, 10, 6, 4, 7, 3, 10, 3, 5, 7, 6, 3, 7, 6, 10, 2, 23, 1, 12, 3, 7, 7, 4, 2, 15, 2, 4, 18, 9, 2, 6, 5, 9, 3, 6, 3, 11

Offset: 1

David W. Wilson

nonn

Number of factors in the factorization of the polynomial x^n-1 over GF(3). - T. D. Noe, Apr 16 2003

			a(15) = 2 because (1) the function 3x mod 15 has the two cycles (0),(3,9,12,6) and (2) the factorization of x^15-1 over integers mod 3 is (2+x)^3 (1+x+x^2+x^3+x^4)^3, which has two unique factors. Note that the length of the cycles is the same as the degree of the factors.

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000005, A000374.

Cf. A023136, A023137, A023138, A023139, A023140, A023141, A023142.

Table[Length[FactorList[x^n - 1, Modulus -> 3]] - 1, {n, 100}]
CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i}, While[Mod[m, p]==0, m/=p]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[3, n], {n, 100}]

a(n)={sumdiv(n/3^valuation(n, 3), d, eulerphi(d)/znorder(Mod(3, d)));}
vector(100,n,a(n)) \\ Joerg Arndt, Jan 22 2024

a(n) = Sum_{d|m} phi(d)/ord(3, d), where m is n with all factors of 3 removed. - T. D. Noe, Apr 19 2003

a(n) = (1/ord(3,m))*Sum_{j = 0..ord(3,m)-1} gcd(3^j - 1, m), where m is n with all factors of 3 removed. - Nihar Prakash Gargava, Nov 14 2018

A023137 Number of cycles of function f(x) = 5x mod n.

Original entry on oeis.org

1, 2, 2, 4, 1, 4, 2, 6, 3, 2, 3, 8, 4, 4, 2, 8, 2, 6, 3, 4, 5, 6, 2, 14, 1, 8, 4, 8, 3, 4, 11, 10, 6, 4, 2, 12, 2, 6, 11, 6, 3, 10, 2, 12, 3, 4, 2, 20, 3, 2, 5, 16, 2, 8, 3, 14, 6, 6, 3, 8, 3, 22, 12, 12, 4, 12, 4, 8, 5, 4, 15, 22, 2, 4, 2, 12, 6, 22, 3, 8, 5, 6, 2, 20, 2, 4, 8, 18, 3, 6, 11, 8, 22, 4, 3, 26

Offset: 1

David W. Wilson

nonn

Number of factors in the factorization of the polynomial x^n-1 over GF(5). - T. D. Noe, Apr 16 2003

			a(15) = 2 because (1) the function 5x mod 15 has the two cycles (0),(5,10) and (2) the factorization of x^15-1 over integers mod 5 is (4+x)^5 (1+x+x^2)^5, which has two unique factors. Note that the length of the cycles is the same as the degree of the factors.

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000005, A000374.

Cf. A023135, A023136, A023138, A023139, A023140, A023141, A023142.

Table[Length[FactorList[x^n - 1, Modulus -> 5]] - 1, {n, 100}]
CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i}, While[Mod[m, p]==0, m/=p]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[5, n], {n, 100}]

a(n)={sumdiv(n/5^valuation(n, 5), d, eulerphi(d)/znorder(Mod(5, d)));}
vector(100,n,a(n)) \\ Joerg Arndt, Jan 22 2024

from sympy import totient, n_order, divisors
def A023137(n):
    a, b = divmod(n,5)
    while not b:
        n = a
        a, b = divmod(n,5)
    return sum(totient(d)//n_order(5,d) for d in divisors(n,generator=True) if d>1)+1 # Chai Wah Wu, Apr 09 2024

a(n) = Sum_{d|m} phi(d)/ord(5, d), where m is n with all factors of 5 removed. - T. D. Noe, Apr 19 2003

a(n) = (1/ord(5,m))*Sum_{j = 0..ord(5,m)-1} gcd(5^j - 1, m), where m is n with all factors of 5 removed. - Nihar Prakash Gargava, Nov 14 2018

A023138 Number of cycles of function f(x) = 6x mod n.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 4, 1, 1, 5, 2, 1, 2, 4, 5, 1, 2, 1, 3, 5, 4, 2, 3, 1, 9, 2, 1, 4, 3, 5, 6, 1, 2, 2, 20, 1, 10, 3, 2, 5, 2, 4, 15, 2, 5, 3, 3, 1, 7, 9, 2, 2, 3, 1, 10, 4, 3, 3, 2, 5, 2, 6, 4, 1, 10, 2, 3, 2, 3, 20, 3, 1, 3, 10, 9, 3, 11, 2, 2, 5, 1, 2, 2, 4, 10, 15, 3, 2, 2, 5, 11, 3, 6, 3, 15, 1, 9, 7, 2, 9, 11

Offset: 1

David W. Wilson

nonn

			a(11) = 2 because the function 6x mod 11 has the two cycles (0),(1,6,3,7,9,10,5,8,4,2).

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000374.

Cf. A023135, A023136, A023137, A023139, A023140, A023141, A023142.

CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i, ps, j}, ps=Transpose[FactorInteger[p]][[1]]; Do[While[Mod[m, ps[[j]]]==0, m/=ps[[j]]], {j, Length[ps]}]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[6, n], {n, 100}]

from sympy import totient, n_order, divisors
def A023138(n):
    m = n>>(~n & n-1).bit_length()
    a, b = divmod(m,3)
    while not b:
        m = a
        a, b = divmod(m,3)
    return sum(totient(d)//n_order(6,d) for d in divisors(m,generator=True) if d>1)+1 # Chai Wah Wu, Apr 09 2024

a(n) = Sum_{d|m} phi(d)/ord(6, d), where m is n with all factors of 2 and 3 removed. - T. D. Noe, Apr 21 2003

a(n) = (1/ord(6,m))*Sum_{j = 0..ord(6,m)-1} gcd(6^j - 1, m), where m is n with all factors of 2 and 3 removed. - Nihar Prakash Gargava, Nov 14 2018

A023139 Number of cycles of function f(x) = 7x mod n.

Original entry on oeis.org

1, 2, 3, 3, 2, 6, 1, 5, 5, 4, 2, 9, 2, 2, 6, 9, 2, 10, 7, 7, 3, 4, 2, 15, 7, 4, 7, 3, 5, 12, 3, 13, 6, 4, 2, 15, 5, 14, 6, 13, 2, 6, 8, 7, 10, 4, 3, 27, 1, 14, 6, 7, 3, 14, 5, 5, 21, 10, 3, 21, 2, 6, 5, 17, 7, 12, 2, 7, 6, 4, 2, 25, 4, 10, 21, 21, 2, 12, 2, 25, 9, 4, 3, 9, 7, 16, 15, 13, 2, 20, 2, 7, 9, 6

Offset: 1

David W. Wilson

nonn

Number of factors in the factorization of the polynomial x^n-1 over GF(7). - T. D. Noe, Apr 16 2003

			a(8) = 5 because (1) the function 7x mod 8 has the five cycles (0),(4),(1,7),(2,6),(3,5) and (2) the factorization of x^8-1 over integers mod 7 is (1+x) (6+x) (1+x^2) (1+3x+x^2) (1+4x+x^2), which has five unique factors. Note that the length of the cycles is the same as the degree of the factors.
a(10) = 2 because the function 8x mod 10 has the two cycles (0),(2,6,8,4).

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000005, A000374.

Cf. A023135, A023136, A023137, A023138, A023140, A023141, A023142.

Table[Length[FactorList[x^n - 1, Modulus -> 7]] - 1, {n, 100}]
CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i}, While[Mod[m, p]==0, m/=p]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[7, n], {n, 100}]

a(n)={sumdiv(n/7^valuation(n, 7), d, eulerphi(d)/znorder(Mod(7, d)));}
vector(100,n,a(n)) \\ Joerg Arndt, Jan 22 2024

from sympy import totient, n_order, divisors
def A023139(n):
    a, b = divmod(n,7)
    while not b:
        n = a
        a, b = divmod(n,7)
    return sum(totient(d)//n_order(7,d) for d in divisors(n,generator=True) if d>1)+1 # Chai Wah Wu, Apr 09 2024

a(n) = Sum_{d|m} phi(d)/ord(7, d), where m is n with all factors of 7 removed. - T. D. Noe, Apr 19 2003

a(n) = (1/ord(7,m))*Sum_{j = 0..ord(7,m)-1} gcd(7^j - 1, m), where m is n with all factors of 7 removed. - Nihar Prakash Gargava, Nov 14 2018

A023140 Number of cycles of function f(x) = 8x mod n.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 7, 1, 5, 2, 2, 2, 4, 7, 5, 1, 3, 5, 4, 2, 14, 2, 3, 2, 3, 4, 8, 7, 2, 5, 7, 1, 5, 3, 14, 5, 4, 4, 11, 2, 3, 14, 4, 2, 14, 3, 3, 2, 13, 3, 8, 4, 2, 8, 5, 7, 11, 2, 2, 5, 4, 7, 35, 1, 17, 5, 4, 3, 6, 14, 3, 5, 25, 4, 8, 4, 14, 11, 7, 2, 11, 3, 2, 14, 12, 4, 5, 2, 9, 14, 28, 3, 14, 3, 11, 2, 7

Offset: 1

David W. Wilson

nonn

			a(10) = 2 because the function 8x mod 10 has the two cycles (0),(2,6,8,4).

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000374.

Cf. A023135, A023136, A023137, A023138, A023139, A023141, A023142.

CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i, ps, j}, ps=Transpose[FactorInteger[p]][[1]]; Do[While[Mod[m, ps[[j]]]==0, m/=ps[[j]]], {j, Length[ps]}]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[8, n], {n, 100}]

a(n) = Sum_{d|m} phi(d)/ord(8, d), where m is n with all factors of 2 removed. - T. D. Noe, Apr 21 2003

a(n) = (1/ord(8,m))*Sum_{j = 0..ord(8,m)-1} gcd(8^j - 1, m), where m is n with all factors of 2 removed. - Nihar Prakash Gargava, Nov 14 2018

A023141 Number of cycles of function f(x) = 9x mod n.

Original entry on oeis.org

1, 2, 1, 4, 3, 2, 3, 8, 1, 6, 3, 4, 5, 6, 3, 12, 3, 2, 3, 12, 3, 6, 3, 8, 5, 10, 1, 12, 3, 6, 3, 16, 3, 6, 9, 4, 5, 6, 5, 24, 11, 6, 3, 12, 3, 6, 3, 12, 5, 10, 3, 20, 3, 2, 9, 24, 3, 6, 3, 12, 13, 6, 3, 20, 15, 6, 7, 12, 3, 18, 3, 8, 13, 10, 5, 12, 9, 10, 3, 44, 1, 22, 3, 12, 13, 6, 3, 24, 3, 6, 31, 12, 3

Offset: 1

David W. Wilson

nonn

			a(12) = 4 because the function 9x mod 12 has the four cycles (0),(3),(1,9),(2,6).

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000374.

Cf. A023135, A023136, A023137, A023138, A023139, A023140, A023142.

CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i, ps, j}, ps=Transpose[FactorInteger[p]][[1]]; Do[While[Mod[m, ps[[j]]]==0, m/=ps[[j]]], {j, Length[ps]}]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[9, n], {n, 100}]

from sympy import totient, n_order, divisors
def A023141(n):
    a, b = divmod(n,3)
    while not b:
        n = a
        a, b = divmod(n,3)
    return sum(totient(d)//n_order(9,d) for d in divisors(n,generator=True) if d>1)+1 # Chai Wah Wu, Apr 09 2024

a(n) = Sum_{d|m} phi(d)/ord(9, d), where m is n with all factors of 3 removed. - T. D. Noe, Apr 21 2003

a(n) = (1/ord(9,m))*Sum_{j = 0..ord(9,m)-1} gcd(9^j - 1, m), where m is n with all factors of 3 removed. - Nihar Prakash Gargava, Nov 14 2018

A175198 a(n) is the smallest integer k such that the polynomial x^k + 1 over the integers mod 2 has exactly n distinct irreducible factors.

Original entry on oeis.org

1, 3, 7, 27, 15, 21, 31, 45, 73, 91, 129, 85, 63, 93, 105, 275, 257, 219, 127, 189, 217, 453, 441, 357, 601, 741, 273, 837, 1191, 981, 513, 645, 903, 949, 255, 315, 1649, 341, 1103, 1235, 455, 651, 657, 1443, 775, 2795, 825, 1925, 1911, 771

Offset: 1

Michel Lagneau, Mar 02 2010

nonn

Example: the polynomial x^1649 + 1 over GF(2) is the product of 37 irreducible factors.

Records: 1, 3, 7, 27, 31, 45, 73, 91, 129, 275, 453, 601, 741, 837, 1191, 1649, 2795, 3045, 3913, 3955, 10719, 18875, 48631, 73143, 76373, 126191, 189061, 210105, 216481, 249891, 303021, 896041, 961185, 1063997, 1759603, 2555521, 3492783, 3923381, 5276409, 5529727, 6663515, 7234645, 8761553, 10488401, 11636993, 12290949, 20936365, 25099273, 25821285, 28081875, 28623469, 32848947, 48539883, 58885551, ..., . - Robert G. Wilson v, Feb 07 2018

			For n=1, x+1 is irreducible hence a(1) = 1.
For n=2, x^3 + 1 = (x+1)(x^2+x+1) mod 2 hence a(2) = 3.
For n=3, x^7 + 1 = (x+1)(x^3 + x^2 + 1)(x^3 + x + 1) mod 2 hence a(3) = 7.
For n=4, x^27 + 1 = (x+1)(x^2 + x + 1)(x^18 + x^9 + 1)(x^6 + x^3 + 1) mod 2 hence a(4) = 27.
For n=5, x^15 + 1 = (x+1)(x^4 + x^3 + x^2 + x + 1)(x^2 + x + 1)(x^4 + x^3 + 1)(x^4 + x + 1) mod 2 hence a(5) = 15.

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

Robert G. Wilson v, Table of n, a(n) for n = 1..10000 (first 300 terms from Charles R Greathouse IV)
Eric Weisstein's World on Math, Irreducible Polynomial

Cf. A023135, A000005, A000374, A023136-A023142.

with(numtheory):T:=array(0..50000000):U=array(0..50000000 ):nn:=3000: for k from 1 to nn do:liste:=Factors(x^k+ 1) mod 2;t1 := liste[2]:t2:=(liste[2][i], i=1..nops(t1)):a :=nops(t1):T[k]:=a:U[k]:=k:od:mini:=T[1]:ii:=1: print(mini):for p from 1 to nn-1 do:for n from 1 to nn-1 do:if T[n] < mini then mini:= T[n]:ii:=n: indice:=U[n]: else fi:od:print(indice):print(mini):T[ii]:= 99999999: ii:=1:mini:=T[1] :od:

With[{s = Array[Length@ FactorList[#, Modulus -> 2] &[x^# + 1] &, 500]}, Array[FirstPosition[s, #][[1]] &, 1 + LengthWhile[Differences@ #, # == 1 &], 2] &@ Union@ s] (* Michael De Vlieger, Feb 05 2018 *)
CountFactors[p_, n_] := CountFactors[p, n] = Module[{sum = 0, m = n, d, f, i}, While[ Mod[m, p] == 0, m /= p]; d = Divisors[m]; Do[f = d[[i]]; sum += EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum](*after Shel Kaphan from A000374*); f[n_] := Block[{k = 1}, While[CountFactors[2, k] != n, k++]; k]; Array[f, 60] (* Robert G. Wilson v, Feb 07 2018 *)

first(n)=my(v=vector(n),left=n,k,t); while(left, t=#factor(Mod('x^k+++1,2))~; if(t<=n && v[t]==0, v[t]=k; left--)); v \\ Charles R Greathouse IV, Jan 28 2018

A000005(a(n)) <= n <= a(n). - Robert Israel, Feb 07 2018

Name corrected by Charles R Greathouse IV, Jan 28 2018

A366494 a(n) is the number of cycles of the map f(x) = 10x mod (10n - 1).

Original entry on oeis.org

8, 1, 1, 8, 2, 1, 5, 6, 2, 53, 1, 4, 8, 3, 1, 14, 4, 1, 41, 2, 16, 29, 1, 34, 8, 49, 1, 26, 2, 7, 11, 16, 4, 5, 3, 2, 80, 1, 1, 26, 2, 1, 83, 2, 14, 29, 9, 2, 8, 1, 1, 14, 2, 27, 17, 16, 2, 5, 9, 2, 14, 1, 25, 26, 16, 1, 5, 8, 14, 5, 1, 2, 32, 3, 5, 50, 4, 17, 5, 4, 4, 143

Offset: 1

Hillel Wayne, Oct 10 2023

nonn

Taking the length of each orbit that starts from f(0)=1 gives the sequence A128858.
Equivalently, the number of cyclotomic cosets of 10 mod (10*n - 1). See A006694.
Map is the Multiply-with-carry algorithm with a=n, b=10, and c=1.

			For a(4) the 8 cycles are:
  (1 10 22 25 16 4)
  (2 20 5 11 32 8)
  (3 30 27 36 9 12)
  (6 21 15 33 18 24)
  (7 31 37 19 34 28)
  (13)
  (14 23 35 38 29 17)
  (26)

Hillel Wayne, Table of n, a(n) for n = 1..1002
George Marsaglia, Random Number Generators, Journal of Modern Applied Statistical Methods, Volume 2, Issue 1 (2003).
Kenneth Shum, Cyclotomic cosets.

Cf. A006694, A023142, A128858, A128857.

a(n)=sumdiv(10*n-1, d, eulerphi(d)/znorder(Mod(10, d)))-1;
vector(100, n, a(n-1)) \\ Joerg Arndt, Jan 22 2024

def get_num_orbits(n: int) -> int:
    orbits = 0
    mod = 10*n - 1
    seen = set()
    for i in range(1, mod):
        if i not in seen:
            seen.add(i)
            orbits += 1
        x = 10*i % mod
        while x != i:
            seen.add(x)
            x = 10*x % mod
    return orbits

from sympy import totient, n_order, divisors
def A366494(n): return sum(totient(d)//n_order(10,d) for d in divisors(10*n-1,generator=True) if d>1) # Chai Wah Wu, Apr 09 2024

cp's OEIS Frontend

A000374 Number of cycles (mod n) under doubling map.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A023136 Number of cycles of function f(x) = 4x mod n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A023135 Number of cycles of function f(x) = 3x mod n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A023137 Number of cycles of function f(x) = 5x mod n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A023138 Number of cycles of function f(x) = 6x mod n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A023139 Number of cycles of function f(x) = 7x mod n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A023140 Number of cycles of function f(x) = 8x mod n.

A366494 a(n) is the number of cycles of the map f(x) = 10x mod (10n - 1).