%I #35 Jul 06 2024 19:04:13
%S 1,0,1,0,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,0,0,1,0,0,1,0,1,0,3,0,1,
%T 0,1,0,2,2,0,0,1,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,2,2,0,0,0,1,0,0,1,0,1,
%U 0,0,0,5,0,3,0,1,0,1,0,1,0,0,0,2,0,0,0,1,0,0,1
%N Square array read by ascending antidiagonals: T(n,k) is the number of degree-k primitive Dirichlet characters modulo n.
%C Given n, T(n,k) only depends on gcd(k,psi(n)). For the truncated version see A354061.
%C Each column is multiplicative.
%C The n-th rows contains entirely 0's if and only if n == 2 (mod 4).
%C For n !== 2 (mod 4), T(n,psi(n)) > T(n,k) if k is not divisible by psi(n).
%C Proof: this is true if n is a prime power (see the formula below). Now suppose that n = Product_{i=1..r} (p_i)^(e_i). Since n !== 2 (mod 4), (p_i)^(e_i) != 2, so T((p_i)^(e_i),psi((p_i)^(e_i))) > 0 for each i. If k is not divisible by psi(n), then it is not divisible by some psi((p_{i_0})^(e_{i_0})), so T(n,psi(n)) = Product_{i=1..r} T((p_i)^(e_i),psi(n)) = Product_{i=1..r} T((p_i)^(e_i),psi((p_i)^(e_i))) > T((p_{i_0})^(e_{i_0}),k) * Product_{i!=i_0} T((p_i)^(e_i),psi((p_i)^(e_i))) >= Product_{i=1..r} T((p_i)^(e_i),k) = T(n,k).
%H Jianing Song, <a href="/A354058/b354058.txt">Table of n, a(n) for n = 1..5050</a> (the first 100 ascending diagonals)
%F For odd primes p: T(p,k) = gcd(p-1,k)-1, T(p^e,k*p^(e-1)) = p^(e-2)*(p-1)*gcd(k,p-1), T(p^e,k) = 0 if k is not divisible by p^(e-1). T(2,k) = 0, T(4,k) = 1 for even k and 0 for odd k, T(2^e,k) = 2^(e-2) if k is divisible by 2^(e-2) and 0 otherwise.
%F T(n,psi(n)) = A007431(n). - _Jianing Song_, May 24 2022
%e n/k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
%e 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
%e 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
%e 3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
%e 4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
%e 5 0 1 0 3 0 1 0 3 0 1 0 3 0 1 0 3 0 1 0 3
%e 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
%e 7 0 1 2 1 0 5 0 1 2 1 0 5 0 1 2 1 0 5 0 1
%e 8 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2
%e 9 0 0 2 0 0 4 0 0 2 0 0 4 0 0 2 0 0 4 0 0
%e 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
%e 11 0 1 0 1 4 1 0 1 0 9 0 1 0 1 4 1 0 1 0 9
%e 12 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
%e 13 0 1 2 3 0 5 0 3 2 1 0 11 0 1 2 3 0 5 0 3
%e 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
%e 15 0 1 0 3 0 1 0 3 0 1 0 3 0 1 0 3 0 1 0 3
%e 16 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0 4
%e 17 0 1 0 3 0 1 0 7 0 1 0 3 0 1 0 15 0 1 0 3
%e 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
%e 19 0 1 2 1 0 5 0 1 8 1 0 5 0 1 2 1 0 17 0 1
%e 20 0 1 0 3 0 1 0 3 0 1 0 3 0 1 0 3 0 1 0 3
%o (PARI) b(n,k)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(k, Z[i]));
%o T(n,k) = sumdiv(n, d, moebius(n/d)*b(d,k))
%Y k-th column: A114643 (k=2), A160498 (k=3), A160499 (k=4), A307380 (k=5), A307381 (k=6), A307382 (k=7), A329272 (k=8).
%Y Moebius transform of A354057 applied to each column.
%Y A354257 gives the smallest index for the nonzero terms in each row.
%Y Cf. A007431.
%K nonn,tabl
%O 1,32
%A _Jianing Song_, May 16 2022