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

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, 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, 0, 0, 0, 5, 0, 3, 0, 1, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 1

Offset

1,32

Comments

Given n, T(n,k) only depends on gcd(k,psi(n)). For the truncated version see A354061.

Each column is multiplicative.

The n-th rows contains entirely 0's if and only if n == 2 (mod 4).

For n !== 2 (mod 4), T(n,psi(n)) > T(n,k) if k is not divisible by psi(n).

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

Links

Jianing Song, Table of n, a(n) for n = 1..5050 (the first 100 ascending diagonals)

Formula

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.

T(n,psi(n)) = A007431(n). - Jianing Song, May 24 2022

Example

  n/k  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
   1   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   2   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   3   0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1
   4   0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1
   5   0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3
   6   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   7   0  1  2  1  0  5  0  1  2  1  0  5  0  1  2  1  0  5  0  1
   8   0  2  0  2  0  2  0  2  0  2  0  2  0  2  0  2  0  2  0  2
   9   0  0  2  0  0  4  0  0  2  0  0  4  0  0  2  0  0  4  0  0
  10   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  11   0  1  0  1  4  1  0  1  0  9  0  1  0  1  4  1  0  1  0  9
  12   0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  1
  13   0  1  2  3  0  5  0  3  2  1  0 11  0  1  2  3  0  5  0  3
  14   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  15   0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3
  16   0  0  0  4  0  0  0  4  0  0  0  4  0  0  0  4  0  0  0  4
  17   0  1  0  3  0  1  0  7  0  1  0  3  0  1  0 15  0  1  0  3
  18   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  19   0  1  2  1  0  5  0  1  8  1  0  5  0  1  2  1  0 17  0  1
  20   0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3  0  1  0  3

Prog

(PARI) b(n, k)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(k, Z[i]));
T(n, k) = sumdiv(n, d, moebius(n/d)*b(d, k))

Crossrefs

k-th column: A114643 (k=2), A160498 (k=3), A160499 (k=4), A307380 (k=5), A307381 (k=6), A307382 (k=7), A329272 (k=8).

Moebius transform of A354057 applied to each column.

A354257 gives the smallest index for the nonzero terms in each row.

Cf. A007431.

Sequence in context: A091959 A318659 A318513 * A323878 A046094 A055976

Adjacent sequences: A354055 A354056 A354057 * A354059 A354060 A354061

Keyword

nonn,tabl

Author

Jianing Song, May 16 2022

Status

approved