A000374 -id:A000374 - cp's OEIS frontend

A006694 Number of cyclotomic cosets of 2 mod 2n+1.

0, 1, 1, 2, 2, 1, 1, 4, 2, 1, 5, 2, 2, 3, 1, 6, 4, 5, 1, 4, 2, 3, 7, 2, 4, 7, 1, 4, 4, 1, 1, 12, 6, 1, 5, 2, 8, 7, 5, 2, 4, 1, 11, 4, 8, 9, 13, 4, 2, 7, 1, 2, 14, 1, 3, 4, 4, 5, 11, 8, 2, 7, 3, 18, 10, 1, 9, 10, 2, 1, 5, 4, 6, 9, 1, 10, 12, 13, 3, 4, 8, 1, 13, 2, 2, 11, 1, 8, 4, 1, 1, 4, 6, 7, 19, 2, 2, 19, 1, 2

Offset: 0

N. J. A. Sloane, Sep 25 2001

a(0) = 0 by convention.
The number of cycles in permutations constructed from siteswap juggling patterns 1, 123, 12345, 1234567, etc., i.e., the number of ball orbits in such patterns minus one.
Also the number of irreducible polynomial factors of the polynomial (x^(2n+1) - 1) / (x - 1) over GF(2). - V. Raman, Oct 04 2012
Also, a(n) is the number of cycles of the Josephus permutation for n elements and a count of 2. For n >= 1, the Josephus permutation is given by the n-th row of A321298. See Knuth 1997 (exercise 1.3.3-29). - Pontus von Brömssen, Sep 18 2022

			Mod 15 there are 4 cosets: {1, 2, 4, 8}, {3, 6, 12, 9}, {5, 10}, {7, 14, 13, 11}, so a(7) = 4. Mod 13 there is only one coset: {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7}, so a(6) = 1.

Donald E. Knuth, The Art of Computer Programming, Vol. 1, 3rd edition, Addison-Wesley, 1997.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier/North Holland, 1977, pp. 104-105.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ray Chandler, Table of n, a(n) for n = 0..10000
Christopher Adler and Jean-Paul Allouche, Finite self-similar sequences, permutation cycles, and music composition, Journal of Mathematics and the Arts, 16:3, 244-261, (2022).
J.-P. Allouche, Suites infinies à répétitions bornées, Séminaire de Théorie des Nombres de Bordeaux, 20 (13 April, 1984), 1-11.
J.-P. Allouche, Suites infinies à répétitions bornées, Séminaire de Théorie des Nombres de Bordeaux, 20 (13 April, 1984), 1-11.
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
Michael Assis, Folding Pi, arXiv:2403.09277 [math.NT], 2024.

Cf. A000010, A000374 (number of factors of x^n - 1 over GF(2)), A002326 (order of 2 mod 2n+1), A037226, A064286, A064287, A081844, A139767, A321298.
A001917 gives cycle counts of such permutations constructed only for odd primes.
Second column of A357217.

with(group); with(numtheory); gen_rss_perm := proc(n) local a, i; a := []; for i from 1 to n do a := [op(a), ((2*i) mod (n+1))]; od; RETURN(a); end; count_of_disjcyc_seq := [seq(nops(convert(gen_rss_perm(2*j),'disjcyc')),j=0..)];

Needs["Combinatorica`"]; f[n_] := Length[ToCycles[Mod[2Range[2n], 2n + 1]]]; Table[f[n], {n, 0, 100}] (* Ray Chandler, Apr 25 2008 *)
f[n_] := Length[FactorList[x^(2n + 1) - 1, Modulus -> 2]] - 2; Table[f[n], {n, 0, 100}] (* Ray Chandler, Apr 25 2008 *)
a[n_] := Sum[ EulerPhi[d] / MultiplicativeOrder[2, d], {d, Divisors[2n + 1]}] - 1; Table[a[n], {n, 0, 99}] (* Jean-François Alcover, Dec 14 2011, after Joerg Arndt *)

a(n)=sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1; /* cf. A081844 */
vector(122, n, a(n-1)) \\ Joerg Arndt, Jan 18 2011

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

Conjecture: a((3^n-1)/2) = n. - Vladimir Shevelev, May 26 2008 [This is correct. 2*((3^n-1)/2) + 1 = 3^n and the polynomial (x^(3^n) - 1) / (x - 1) factors over GF(2) into Product_{k=0..n-1} x^(2*3^k) + x^(3^k) + 1. - Joerg Arndt, Apr 01 2019]
a(n) = A081844(n) - 1.
a(n) = A064286(n) + 2*A064287(n).
From Vladimir Shevelev, Jan 19 2011: (Start)
1) a(n)=A037226(n) iff 2n+1 is prime;
2) The only case when a(n) < A037226(n) is n=0;
3) If {C_i}, i=1..a(n), is the set of all cyclotomic cosets of 2 mod (2n+1), then lcm(|C_1|, ..., |C_{a(n)}|) = A002326(n). (End)
a(n) = A000374(2*n + 1) - 1. - Joerg Arndt, Apr 01 2019
a(n) = (Sum_{d|(2n+1)} phi(d)/ord(2,d)) - 1, where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d. - Jianing Song, Nov 13 2021

Additional comments from Antti Karttunen, Jan 05 2000
Extended by Ray Chandler, Apr 25 2008
Edited by N. J. A. Sloane, Apr 27 2008 at the suggestion of Ray Chandler

A091221 Number of distinct irreducible polynomials dividing n-th GF(2)[X]-polynomial.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 3, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 1, 2, 2, 2, 1, 2, 2, 3, 1, 2, 2, 3, 1, 2, 1, 2, 2, 1, 2, 3, 1, 2, 1, 3, 2, 3, 1, 2, 2, 2, 2, 3, 2, 2, 1, 2, 3, 2, 1, 3, 1, 2, 2, 3, 1, 3, 2, 2, 2, 2, 1, 3, 2, 2, 3, 2

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
A. Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials

a(n) = A001221(A091203(n)) = A001221(A091205(n)). A000374(n) = a(A000051(n)).

f:= proc(n) local L,P,R,i;
  L:= convert(n,base,2);
  P:= add(L[i]*X^(i-1),i=1..nops(L));
  R:= Factors(P) mod 2;
  nops(R[2]);
end proc:
map(f, [$1.200]); # Robert Israel, Oct 11 2024

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

A023142 Number of cycles of function f(x) = 10x mod n.

Original entry on oeis.org

1, 1, 3, 1, 1, 3, 2, 1, 9, 1, 6, 3, 3, 2, 3, 1, 2, 9, 2, 1, 6, 6, 2, 3, 1, 3, 15, 2, 2, 3, 3, 1, 18, 2, 2, 9, 13, 2, 9, 1, 9, 6, 3, 6, 9, 2, 2, 3, 3, 1, 6, 3, 5, 15, 6, 2, 6, 2, 2, 3, 2, 3, 18, 1, 3, 18, 3, 2, 6, 2, 3, 9, 10, 13, 3, 2, 17, 9, 7, 1, 21, 9, 3, 6, 2, 3, 6, 6, 3, 9, 16, 2, 9, 2, 2, 3, 2, 3, 54, 1, 26

Offset: 1

David W. Wilson

nonn

			a(12) = 3 because the function 10x mod 12 has the three cycles (0),(1,10,4),(2,8).

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

Cf. A000374, A023135-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[10, n], {n, 100}]

a(n)=n/=2^valuation(n,2)*5^valuation(n,5);sumdiv(n,d,eulerphi(d)/znorder(Mod(10,d))) \\ Charles R Greathouse IV, Apr 24 2013

from sympy import totient, n_order, divisors
def A023142(n):
    m = n>>(~n & n-1).bit_length()
    a, b = divmod(m,5)
    while not b:
        m = a
        a, b = divmod(m,5)
    return sum(totient(d)//n_order(10,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(10, d), where m is n with all factors of 2 and 5 removed. - T. D. Noe, Apr 21 2003

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

cp's OEIS Frontend

A006694 Number of cyclotomic cosets of 2 mod 2n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A091221 Number of distinct irreducible polynomials dividing n-th GF(2)[X]-polynomial.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

A023142 Number of cycles of function f(x) = 10x mod n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

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