A212957 A(n,k) is the number of moduli m such that the multiplicative order of k mod m equals n; square array A(n,k), n>=1, k>=1, read by antidiagonals.

0, 1, 0, 2, 1, 0, 2, 2, 1, 0, 3, 2, 2, 2, 0, 2, 5, 4, 6, 1, 0, 4, 2, 3, 4, 4, 3, 0, 2, 6, 2, 12, 6, 10, 1, 0, 4, 4, 8, 4, 9, 16, 2, 4, 0, 3, 6, 2, 26, 4, 37, 6, 14, 2, 0, 4, 3, 12, 18, 4, 10, 3, 8, 4, 5, 0, 2, 12, 5, 14, 6, 42, 2, 28, 26, 16, 3, 0

Offset

1,4

Links

Alois P. Heinz, Antidiagonals n = 1..60

Wikipedia, Multiplicative order.

Formula

A(n,k) = |{m : multiplicative order of k mod m = n}|.

A(n,k) = Sum_{d|n} mu(n/d)*tau(k^d-1), mu = A008683, tau = A000005.

Example

A(4,3) = 6: 3^4 = 81 == 1 (mod m) for m in {5,10,16,20,40,80}.
Square array A(n,k) begins:
  0,  1,  2,  2,  3,  2,  4,  2, ...
  0,  1,  2,  2,  5,  2,  6,  4, ...
  0,  1,  2,  4,  3,  2,  8,  2, ...
  0,  2,  6,  4, 12,  4, 26, 18, ...
  0,  1,  4,  6,  9,  4,  4,  6, ...
  0,  3, 10, 16, 37, 10, 42, 24, ...
  0,  1,  2,  6,  3,  2, 12, 10, ...
  0,  4, 14,  8, 28,  8, 48, 72, ...

Maple

with(numtheory):
A:= (n, k)-> add(mobius(n/d)*tau(k^d-1), d=divisors(n)):
seq(seq(A(n, 1+d-n), n=1..d), d=1..15);

Mathematica

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

Prog

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

Crossrefs

Columns k=1-10 give: A000004, A059499, A059885, A059886, A059887, A059888, A059889, A059890, A059891, A059892.

Rows n=1-10 give: A000005, A059907, A059908, A059909, A059910, A059911, A218256, A218257, A218258, A218259.

Main diagonal gives A252760.

Cf. A000005, A008683.

Sequence in context: A328312 A289281 A374996 * A035393 A068913 A128306

Adjacent sequences: A212954 A212955 A212956 * A212958 A212959 A212960

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 01 2012

Status

approved