A212957 - OEIS

%I #29 Jan 26 2025 02:17:33

%S 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,

%T 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,

%U 4,5,0,2,12,5,14,6,42,2,28,26,16,3,0

%N 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.

%H Alois P. Heinz, <a href="/A212957/b212957.txt">Antidiagonals n = 1..60</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multiplicative_order">Multiplicative order</a>.

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

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

%e A(4,3) = 6: 3^4 = 81 == 1 (mod m) for m in {5,10,16,20,40,80}.

%e Square array A(n,k) begins:

%e   0,  1,  2,  2,  3,  2,  4,  2, ...

%e   0,  1,  2,  2,  5,  2,  6,  4, ...

%e   0,  1,  2,  4,  3,  2,  8,  2, ...

%e   0,  2,  6,  4, 12,  4, 26, 18, ...

%e   0,  1,  4,  6,  9,  4,  4,  6, ...

%e   0,  3, 10, 16, 37, 10, 42, 24, ...

%e   0,  1,  2,  6,  3,  2, 12, 10, ...

%e   0,  4, 14,  8, 28,  8, 48, 72, ...

%p with(numtheory):

%p A:= (n, k)-> add(mobius(n/d)*tau(k^d-1), d=divisors(n)):

%p seq(seq(A(n, 1+d-n), n=1..d), d=1..15);

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

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

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

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

%Y Main diagonal gives A252760.

%Y Cf. A000005, A008683.

%K nonn,tabl

%O 1,4

%A _Alois P. Heinz_, Jun 01 2012