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

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,1

Comments

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

Links

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

Formula

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).

Maple

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

Mathematica

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 *)

Prog

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

Crossrefs

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.

Sequence in context: A247456 A266383 A217948 * A020213 A011979 A058219

Adjacent sequences: A059888 A059889 A059890 * A059892 A059893 A059894

Keyword

nonn

Author

Vladeta Jovovic, Feb 06 2001

Status

approved