A023136 -id:A023136 - cp's OEIS frontend

A133702 A051731 * A023136.

1, 2, 4, 3, 4, 8, 4, 4, 9, 8, 4, 12, 4, 8, 16, 5, 6, 18, 4, 12, 16, 8, 4, 16, 9, 8, 16, 12, 4, 32, 8, 6, 16, 12, 16, 27, 4, 8, 16, 16, 6, 32, 8, 12, 36, 8, 4, 20, 9, 18, 24, 12, 4, 32, 16, 16, 16, 8, 4, 48, 4, 16, 44, 7, 20, 32, 4, 18, 16, 32, 4, 36, 10, 8, 36, 12, 16, 32, 4, 20, 25, 12, 4, 48

Offset: 1

Gary W. Adamson, Sep 21 2007

nonn

A023136 = (1, 1, 3, 1, 3, 3, 3, 1, 5, 3, ...).

			a(4) = 3 = (1, 1, 0, 1) * (1, 1, 3, 1) = (1, 1, 0, 1), row 4 of triangle A133701.

Cf. A051731, A133698, A023136.

Inverse Mobius transform of A023136.

More terms from R. J. Mathar, Jan 19 2009

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

A133701 A133698 * A051731.

Original entry on oeis.org

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

Offset: 1

Gary W. Adamson, Sep 21 2007

Left and right borders = A001227: (1, 1, 2, 1, 2, 2, 2, ...), the number of odd divisors of n.

Row sums = A133702, the inverse Mobius transform of A023136.

			First few rows of the triangle:
  1;
  1, 1;
  2, 0, 2;
  1, 1, 0, 1;
  2, 0, 0, 0, 2;
  2, 2, 2, 0, 0, 2;
  2, 0, 0, 0, 0, 0, 2;
  1, 1, 0, 1, 0, 0, 0, 1;
  ...

Cf. A051731, A133698, A001227, A133702, A023136.

A133698 * A051731 as infinite lower triangular matrices.

A275367 Number of odd divisors of n^2.

Original entry on oeis.org

1, 1, 3, 1, 3, 3, 3, 1, 5, 3, 3, 3, 3, 3, 9, 1, 3, 5, 3, 3, 9, 3, 3, 3, 5, 3, 7, 3, 3, 9, 3, 1, 9, 3, 9, 5, 3, 3, 9, 3, 3, 9, 3, 3, 15, 3, 3, 3, 5, 5, 9, 3, 3, 7, 9, 3, 9, 3, 3, 9, 3, 3, 15, 1, 9, 9, 3, 3, 9, 9, 3, 5, 3, 3, 15, 3, 9, 9, 3, 3, 9, 3, 3, 9, 9, 3, 9, 3, 3, 15, 9, 3, 9

Offset: 1

Juri-Stepan Gerasimov, Jul 24 2016

All terms are odd.

First differs from A023136 at a(17).

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Vaclav Kotesovec, Graph - the asymptotic ratio (100000 terms)

Cf. A000005, A001227, A023136, A048691.

A275367 := proc(n) local a, d;
    a := 1 ;
    for d in ifactors(n)[2] do
        if op(1, d) > 2 then
            a := a*(2*op(2, d)+1) ;
        end if;
    end do:
    a ;
end proc:
seq(A275367(n),n=1..40) ; # R. J. Mathar, Mar 20 2023

Table[Count[Divisors[n^2], ?OddQ], {n, 120}] (* _Michael De Vlieger, Jul 25 2016 *)
f[2, e_] := 1; f[p_, e_] := 2*e + 1; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 11 2020 *)

a(n) = sumdiv(n^2, d, d%2); \\ Michel Marcus, Jul 25 2016

a(n)=my(f=factor(n>>valuation(n,2))[,2]); prod(i=1,#f,2*f[i]+1) \\ Charles R Greathouse IV, Jul 28 2016

a(n) = A001227(n^2).
a(2n + 1) = A048691(2n + 1).
a(n) = A000005(n^2) if n is odd, else A000005(2*n^2) - A000005(n^2).
Multiplicative with a(2^e) = 1, a(p^e) = 2*e + 1 for odd prime p. - Andrew Howroyd, Jul 20 2018
Dirichlet g.f.: (zeta(s)^3/zeta(2*s))*(2^s-1)/(2^s+1). - Amiram Eldar, Dec 08 2022
Sum_{k=1..n} a(k) ~ n*log(n)^2/Pi^2 + 2*n*log(n)*((3*gamma + 4*log(2)/3 - 1)/Pi^2 - 12*zeta'(2)/Pi^4) + 2*n*((1 + 3*gamma^2 - 4*log(2)/3 - 2*log(2)^2/9 + gamma*(4*log(2) - 3) - 3*sg1)/Pi^2 - 4*((9*gamma*zeta'(2) + (4*log(2) - 3)*zeta'(2) + 3*zeta''(2))/Pi^4) + 144*zeta'(2)^2/Pi^6), where gamma is the Euler-Mascheroni constant A001620 and sg1 is the first Stieltjes constant (see A082633). - Vaclav Kotesovec, Dec 08 2022

A133703 A054525 * A133701.

Original entry on oeis.org

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

Offset: 1

Gary W. Adamson, Sep 21 2007

Right border = A001227: (1, 1, 2, 1, 2, 2, 2, 1, 3, ...), the number of odd divisors of n.

Row sums = A023136: (1, 1, 3, 1, 3, 3, 3, 1, 5, 3, ...).

			First few rows of the triangle:
  1;
  0, 1;
  1, 0, 2;
  0, 0, 0, 1;
  1, 0, 0, 0, 2;
  0, 1, 0, 0, 0, 2;
  1, 0, 0, 0, 0, 0, 2;
  ...

Cf. A054525, A133701, A001227, A023136.

Mobius transform of triangle A133701.

cp's OEIS Frontend

A133702 A051731 * A023136.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs