A212957 -id:A212957 - cp's OEIS frontend

A059892 a(n) = |{m : multiplicative order of 10 mod m is equal to n}|.

3, 3, 5, 6, 9, 53, 9, 36, 12, 33, 9, 186, 21, 33, 111, 144, 9, 564, 3, 330, 239, 273, 3, 1756, 84, 165, 76, 714, 93, 16167, 21, 5952, 111, 177, 363, 4288, 21, 15, 99, 5724, 45, 48807, 45, 4314, 1140, 183, 9, 14192, 36, 2940, 495, 1338, 45, 11572, 747, 11484

Offset: 1

Vladeta Jovovic, Feb 06 2001

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).
The number of unit fractions 1/k having a decimal expansion of period n and with k coprime to 10. - T. D. Noe, May 18 2007
Also, number of primitive factors of 10^n - 1 (cf. A003060). - Max Alekseyev, May 03 2022
a(n) is odd if and only if n is squarefree. Proof: Note that 10^d - 1 == 3 (mod 4) for d >= 2, so 10^d - 1 is a square if and only if d = 1. From the formula we can see that a(n) is odd if and only if mu(n) is nonzero, or n is squarefree. - Jianing Song, Jun 15 2021

Table of n, a(n) for n = 1..352

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), this sequence (b=10).
Cf. A000005, A008683, A002329, A007138, A005422, A057951, A058946, A070528.
Column k=10 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(10^d-1), d=divisors(n)):
seq(a(n), n=1..30);  # Alois P. Heinz, Oct 12 2012

f[n_, d_] := MoebiusMu[n/d]*Length[Divisors[10^d - 1]]; a[n_] := Total[(f[n, #] & ) /@ Divisors[n]]; Table[a[n], {n, 1, 56}] (* Jean-François Alcover, Mar 21 2011 *)

j=[]; for(n=1,10,j=concat(j,sumdiv(n,d,moebius(n/d)*numdiv(10^d-1)))); j

from sympy import divisors, mobius, divisor_count
def a(n): return sum(mobius(n//d)*divisor_count(10**d - 1) for d in divisors(n)) # Indranil Ghosh, Apr 23 2017

a(n) = Sum_{d|n} mu(n/d)*tau(10^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

More terms from Jason Earls, Aug 06 2001.
Terms to a(280) in b-file from T. D. Noe, Oct 01 2013
a(281)-a(322) in b-file from Ray Chandler, May 03 2017
a(323)-a(352) in b-file from Max Alekseyev, May 03 2022

A059499 a(n) = |{m : multiplicative order of 2 mod m = n}|.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 2, 5, 3, 16, 1, 5, 5, 8, 1, 24, 1, 38, 9, 11, 3, 68, 6, 5, 4, 54, 7, 79, 1, 16, 11, 5, 13, 462, 3, 5, 13, 140, 3, 123, 7, 110, 54, 11, 7, 664, 2, 114, 29, 118, 7, 124, 59, 188, 13, 55, 3, 4456, 1, 5, 82, 96, 5, 353, 3, 118, 11, 485, 7

Offset: 1

Vladeta Jovovic, Feb 04 2001

nonn

Also, number of primitive factors of 2^n - 1 (cf. A212953). - Max Alekseyev, May 03 2022
The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). See A002326.
a(n) is odd iff n is squarefree, A005117. - Thomas Ordowski, Jan 18 2014
The set S for which a(n) = |S| contains an odd number of prime powers p^k, where k > 0 and p == 3 (mod 4), iff n is squarefree and greater than one. - Isaac Saffold, Dec 28 2019

			a(3) = |{7}| = 1, a(4) = |{5,15}| = 2, a(6) = |{9,21,63}| = 3.

Max Alekseyev, Table of n, a(n) for n = 1..1206 (first 200 terms from Alois P. Heinz)

Column k=2 of A212957.
Primitive factors of b^n - 1: this sequence (b=2), A059885 (b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A001037, A046801, A058943, A059912, A112927, A212953.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(2^d-1), d=divisors(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, May 31 2012

a[n_] := Sum[ MoebiusMu[n/d] * DivisorSigma[0, 2^d - 1], {d, Divisors[n]}]; Table[a[n], {n, 1, 71} ] (* Jean-François Alcover, Dec 12 2012 *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(2^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{d|n} A008683(n/d) * A046801(d) = Sum_{d|A007947(n)} A008683(d) * A046801(n/d). - Max Alekseyev, May 03 2022

a(n) = 1 iff 2^n-1 is noncomposite. a(prime(n)) = 2^A088863(n)-1. - Thomas Ordowski, Jan 16 2014

More terms from John W. Layman, Mar 22 2002

More terms from Alois P. Heinz, May 31 2012

A059885 a(n) = |{m : multiplicative order of 3 mod m = n}|.

Original entry on oeis.org

2, 2, 2, 6, 4, 10, 2, 14, 4, 16, 6, 58, 2, 10, 16, 88, 6, 108, 6, 150, 10, 54, 6, 290, 18, 10, 56, 138, 14, 716, 14, 144, 22, 118, 40, 1088, 6, 54, 90, 670, 14, 730, 6, 570, 356, 22, 30, 13864, 124, 342, 54, 138, 14, 3912, 116, 1362, 118, 238, 6, 22058, 6, 110

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, GCD(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). a(n) = number of orders of degree-n monic irreducible polynomials over GF(3).

Also, number of primitive factors of 3^n - 1 (cf. A218356). - Max Alekseyev, May 03 2022

			a(2) = |{4,8}| = 2, a(4) = |{5,10,16,20,40,80}| = 6, a(6) = |{7,14,28,52,56,91,104,182,364,728}| = 10.

Max Alekseyev, Table of n, a(n) for n = 1..690 (first 100 terms from Alois P. Heinz)

Primitive factors of b^n - 1: A059499 (b=2), this sequence (b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A027376, A057958, A058944, A074477, A143663, A212906, A218356.
Column k=3 of A212957.

with(numtheory); A059885 := proc(n) local d,s; s := 0; for d in divisors(n) do s := s+mobius(n/d)*tau(3^d-1); od; RETURN(s); end;

a[n_] := Sum[ MoebiusMu[n/d] * DivisorSigma[0, 3^d - 1], {d, Divisors[n]}]; Table[a[n], {n, 1, 62} ] (* Jean-François Alcover, Dec 12 2012 *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(3^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{ d divides n } mu(n/d)*tau(3^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059887 a(n) = |{m : multiplicative order of 5 mod m=n}|.

Original entry on oeis.org

3, 5, 3, 12, 9, 37, 3, 28, 18, 47, 3, 180, 3, 53, 81, 176, 9, 446, 21, 564, 39, 117, 9, 884, 180, 53, 360, 244, 21, 5959, 9, 800, 39, 111, 369, 9536, 21, 483, 39, 5476, 9, 18289, 9, 1140, 2958, 111, 3, 9424, 6, 3852, 177, 884, 21, 81048, 561, 1188, 69, 227, 9

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). a(n) = number of orders of degree-n monic irreducible polynomials over GF(5).

Also, number of primitive factors of 5^n - 1 (cf. A218357). - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..502

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), this sequence (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A001692, A053447, A057956, A058945, A074479, A143665, A212485, A218357
Column k=5 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(5^d-1), d=divisors(n)):
seq(a(n), n=1..50);  # Alois P. Heinz, Oct 12 2012

a[n_] := Sum[MoebiusMu[n/d]*DivisorSigma[0, 5^d-1], {d, Divisors[n]}];
Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Dec 13 2024, after Alois P. Heinz *)

a(n) = sumdiv(n, d, moebius(n/d)*numdiv(5^d-1)); \\ Michel Marcus, Dec 13 2024

a(n) = Sum_{d|n} mu(n/d)*tau(5^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059889 a(n) = |{m : multiplicative order of 7 mod m=n}|.

Original entry on oeis.org

4, 6, 8, 26, 4, 42, 12, 48, 52, 66, 12, 778, 4, 138, 80, 300, 12, 528, 12, 1430, 72, 138, 28, 15216, 24, 66, 1216, 966, 28, 3630, 28, 1344, 360, 58, 108, 16988, 28, 138, 176, 12752, 28, 7398, 12, 4422, 1900, 122, 12, 131028, 240, 536, 744, 1046, 28, 23744, 44

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).
a(n) = number of orders of degree n monic irreducible polynomials over GF(7).
Also, number of primitive factors of 7^n - 1 (cf. A218358). - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..388

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), this sequence (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A058946, A053450, A057954, A058946, A074249, A212486, A218358
Column k=7 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(7^d-1), d=divisors(n)):
seq(a(n), n=1..40);  # Alois P. Heinz, Oct 12 2012

a[n_] := DivisorSum[n, MoebiusMu[n/#] * DivisorSigma[0, 7^#-1] &]; Array[a, 60] (* Amiram Eldar, Jan 25 2025 *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(7^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{d|n} mu(n/d)*tau(7^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059886 a(n) = |{m : multiplicative order of 4 mod m=n}|.

Original entry on oeis.org

2, 2, 4, 4, 6, 16, 6, 8, 26, 38, 14, 68, 6, 54, 84, 16, 6, 462, 6, 140, 132, 110, 14, 664, 120, 118, 128, 188, 62, 4456, 6, 96, 364, 118, 498, 7608, 30, 118, 180, 568, 30, 9000, 30, 892, 3974, 494, 62, 5360, 24, 8024, 1524, 892, 62, 9600, 3050, 1784, 372, 446

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, GCD(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).
a(n) is the number of orders of degree-n monic irreducible polynomials over GF(4).
Also, number of primitive factors of 4^n - 1. - Max Alekseyev, May 03 2022

			a(1) = |{1,3}| = 2, a(2) = |{5,15}| =2, a(3) = |{7,9,21,63}| =4, a(4) = |{17,51,85,255}| = 4.

Max Alekseyev, Table of n, a(n) for n = 1..1128 (first 160 terms from Alois P. Heinz)

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), this sequence (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A027377, A053447, A057957, A058948, A112092, A274906.
Column k=4 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(4^d-1), d=divisors(n)):
seq(a(n), n=1..60);  # Alois P. Heinz, Oct 12 2012

a[n_] := DivisorSum[n, MoebiusMu[n/#]*DivisorSigma[0, 4^# - 1]&]; Array[a, 100] (* Jean-François Alcover, Nov 11 2015 *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(4^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{ d divides n } mu(n/d)*tau(4^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059888 a(n) = |{m : multiplicative order of 6 mod m=n}|.

Original entry on oeis.org

2, 2, 2, 4, 4, 10, 2, 8, 12, 40, 6, 108, 6, 42, 40, 48, 30, 100, 6, 332, 10, 22, 30, 376, 26, 118, 48, 332, 2, 1436, 6, 448, 54, 222, 88, 7952, 62, 54, 54, 2680, 6, 698, 30, 476, 1476, 222, 14, 7632, 28, 438, 478, 1916, 14, 1872, 84, 11896, 118, 58, 14, 784452

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, GCD(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).

Also, number of primitive factors of 6^n - 1. - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..430

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), A059887 (b=5), this sequence (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Column k=6 of A212957.
Cf. A000005, A008683, A053449, A057955, A274907.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(6^d-1), d=divisors(n)):
seq(a(n), n=1..50);  # Alois P. Heinz, Oct 12 2012

a[n_] := DivisorSum[n, MoebiusMu[n/#] * DivisorSigma[0, 6^#-1] &]; Array[a, 60] (* Amiram Eldar, Jan 25 2025 *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(6^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{ d divides n } mu(n/d)*tau(6^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059890 a(n) = |{m : multiplicative order of 8 mod m = n}|.

Original entry on oeis.org

2, 4, 2, 18, 6, 24, 10, 72, 4, 84, 14, 462, 14, 128, 54, 672, 30, 124, 14, 4494, 82, 364, 14, 7608, 120, 172, 56, 9054, 62, 3920, 6, 5376, 238, 1500, 1518, 9600, 62, 364, 494, 69048, 30, 5892, 30, 24174, 956, 364, 62, 253280, 52, 12072, 222, 147246, 254, 12072

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). a(n) = number of orders of degree-n monic irreducible polynomials over GF(8).

Also, number of primitive factors of 8^n - 1. - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..500

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), this sequence (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A027380, A053451, A057953, A058946, A274908.
Column k=8 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(8^d-1), d=divisors(n)):
seq(a(n), n=1..40);  # Alois P. Heinz, Oct 12 2012

a[n_] := Sum[MoebiusMu[n/d]*DivisorSigma[0, 8^d-1], {d, Divisors[n]}];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Jan 13 2025, after Alois P. Heinz *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(8^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{ d divides n } mu(n/d)*tau(8^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059891 a(n) = |{m : multiplicative order of 9 mod m = n}|.

Original entry on oeis.org

4, 6, 12, 14, 20, 58, 12, 88, 112, 150, 60, 290, 12, 138, 732, 144, 124, 1088, 60, 670, 740, 570, 28, 13864, 360, 138, 3968, 1362, 252, 22058, 124, 320, 1972, 1146, 732, 10704, 124, 570, 12260, 15176, 124, 60470, 28, 11634, 195728, 282, 508, 116592, 2032

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).
a(n) = number of orders of degree-n monic irreducible polynomials over GF(9).
Also, number of primitive factors of 9^n - 1. - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..690

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), this sequence (b=9), A059892 (b=10).
Cf. A000005, A008683, A027381, A053452, A057952, A058946, A274909.
Column k=9 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(9^d-1), d=divisors(n)):
seq(a(n), n=1..40);  # Alois P. Heinz, Oct 12 2012

a[n_] := Sum[MoebiusMu[n/d]*DivisorSigma[0, 9^d-1], {d, Divisors[n]}];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Jan 13 2025, after Alois P. Heinz *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(9^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{d|n} mu(n/d)*tau(9^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A059907 a(n) = |{m : multiplicative order of n mod m = 2}|.

Original entry on oeis.org

0, 1, 2, 2, 5, 2, 6, 4, 6, 3, 12, 2, 10, 6, 8, 4, 13, 2, 18, 6, 10, 4, 16, 4, 12, 9, 12, 4, 26, 2, 20, 6, 8, 12, 20, 4, 15, 6, 16, 4, 32, 2, 24, 10, 10, 6, 20, 4, 26, 9, 18, 4, 26, 6, 32, 12, 12, 4, 28, 2, 20, 10, 12, 18, 25, 4, 24, 6, 26, 4, 52, 2, 18, 10, 12, 18, 26, 4, 40, 8, 14, 5, 28

Offset: 1

Vladeta Jovovic, Feb 08 2001

The multiplicative order of a mod m, GCD(a,m) = 1, is the smallest natural number d for which a^d = 1 (mod m).

			a(2) = |{3}| = 1, a(3) = |{4,8}| = 2, a(4) = |{5,15}| = 2, a(5) = |{3,6,8,12,24}| = 5, a(6) = |{7,35}| = 2, a(7) = |{4,8,12,16,24,48}| = 6,...

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

Cf. A002329, A059908-A059911, A059499, A059885-A059892, A002326, A053446-A053452, A055205, A048691, A048785, A347191.

Row n=2 of A212957. - Alois P. Heinz, Oct 24 2012

with(numtheory):f := n->tau(n^2-1)-tau(n-1):for n from 1 to 100 do printf(`%d,`,f(n)) od:

a[n_] := Subtract @@ DivisorSigma[0, {n^2-1, n-1}]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jan 25 2025 *)

a(n) = if(n == 1, 0, numdiv(n^2-1) - numdiv(n-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^2-1)-tau(n-1), where tau(n) = number of divisors of n A000005. Generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

cp's OEIS Frontend

A059892 a(n) = |{m : multiplicative order of 10 mod m is equal to n}|.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A059499 a(n) = |{m : multiplicative order of 2 mod m = n}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A059885 a(n) = |{m : multiplicative order of 3 mod m = n}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059887 a(n) = |{m : multiplicative order of 5 mod m=n}|.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059889 a(n) = |{m : multiplicative order of 7 mod m=n}|.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059886 a(n) = |{m : multiplicative order of 4 mod m=n}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059888 a(n) = |{m : multiplicative order of 6 mod m=n}|.