login
Square array read by ascending antidiagonals: T(n,k) is the number of degree-k primitive Dirichlet characters modulo n.
5

%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