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

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: A287528 A328312 A289281 * A035393 A068913 A128306

Adjacent sequences: A212954 A212955 A212956 * A212958 A212959 A212960

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 01 2012

Status

approved