|
| |
|
|
A354058
|
|
Square array read by ascending diagonals: T(n,k) is the number of degree-k primitive Dirichlet characters modulo n.
|
|
5
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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.
|
|
|
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
|
Moebius transform of A354057 applied to each column.
A354257 gives the smallest index for the nonzero terms in each row.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
