A307382 -id:A307382 - cp's OEIS frontend

A319101 Number of solutions to x^7 == 1 (mod n).

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 7

Offset: 1

Jianing Song, Sep 10 2018

All terms are powers of 7. Those n such that a(n) > 1 are in A066502.

			Solutions to x^7 == 1 (mod 29): x == 1, 7, 16, 20, 23, 24, 25 (mod 29).
Solutions to x^7 == 1 (mod 43): x == 1, 4, 11, 16, 21, 35, 41 (mod 43).
Solutions to x^7 == 1 (mod 49): x == 1, 8, 15, 22, 29, 36, 43 (mod 49) (x == 1 (mod 7)).

Jianing Song, Table of n, a(n) for n = 1..10000

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), this sequence (k=7), A247257 (k=8).
Cf. A066502, A140444, A293484, A000010.
Mobius transform gives A307382.

f[p_, e_] := If[Mod[p, 7] == 1, 7, 1]; f[7, 1] = 1; f[7, e_] := 7; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

a(n)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(7, Z[i]))

Multiplicative with a(7) = 1, a(7^e) = 7 if e >= 2; for other primes p, a(p^e) = 7 if p == 1 (mod 7), a(p^e) = 1 otherwise.
If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(7, k_i).
a(n) = A000010(n)/A293484(n). - Jianing Song, Nov 10 2019

A307380 Number of quintic primitive Dirichlet characters modulo n.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0

Offset: 1

Jianing Song, Apr 06 2019

a(n) is the number of primitive Dirichlet characters modulo n such that all entries are 0 or a fifth-power root of unity.

Mobius transform of A319099. Every term is 0 or a power of 4.

			Let w = exp(2*Pi/5). For n = 11, the 4 quintic primitive Dirichlet characters modulo n are:
  Chi_1 = [0, 1, w, w^3, w^2, w^4, w^4, w^2, w^3, w, 1];
  Chi_2 = [0, 1, w^2, w, w^4, w^3, w^3, w^4, w, w^2, 1];
  Chi_3 = [0, 1, w^3, w^4, w, w^2, w^2, w, w^4, w^3, 1];
  Chi_4 = [0, 1, w^4, w^2, w^3, w, w, w^3, w^2, w^4, 1],
so a(11) = 4.

Antti Karttunen, Table of n, a(n) for n = 1..65539

Number of k-th power primitive Dirichlet characters modulo n: A114643 (k=2), A160498 (k=3), A160499 (k=4), this sequence (k=5), A307381 (k=6), A307382 (k=7), A329272 (k=8).

Cf. A319099 (number of solutions to x^5 == 1 (mod n)).

f[5, 2] = 4; f[p_, e_] := If[Mod[p, 5] == 1 && e == 1, 4, 0]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 16 2020 *)

a(n)=sum(d=1, n, if(n%d==0, moebius(n/d)*sum(i=1, d, if((i^5-1)%d, 0, 1)), 0))

A307380(n) = sumdiv(n, d, moebius(n/d)*sum(i=1, d, if((i^5-1)%d, 0, 1))); \\ (Slightly speeding the program above) - Antti Karttunen, Aug 22 2019

A307380(n) = { my(f=factor(n)); prod(i=1, #f~, if(((5==f[i,1])&&(2==f[i,2]))||((1==(f[i,1]%5))&&(1==f[i,2])),4,0)); }; \\ (After the multiplicative formula, much faster) - Antti Karttunen, Aug 22 2019

Multiplicative with a(p^e) = 4 if p^e = 25 or p == 1 (mod 5) and e = 1, otherwise 0.

More terms from Antti Karttunen, Aug 22 2019

A307381 Number of sextic primitive Dirichlet characters modulo n.

Original entry on oeis.org

1, 0, 1, 1, 1, 0, 5, 2, 4, 0, 1, 1, 5, 0, 1, 0, 1, 0, 5, 1, 5, 0, 1, 2, 0, 0, 0, 5, 1, 0, 5, 0, 1, 0, 5, 4, 5, 0, 5, 2, 1, 0, 5, 1, 4, 0, 1, 0, 0, 0, 1, 5, 1, 0, 1, 10, 5, 0, 1, 1, 5, 0, 20, 0, 5, 0, 5, 1, 1, 0, 1, 8, 5, 0, 0, 5, 5, 0, 5, 0, 0, 0, 1, 5, 1, 0, 1

Offset: 1

Jianing Song, Apr 06 2019

a(n) is the number of primitive Dirichlet characters modulo n such that all entries are 0 or a six-power root of unity (1, (1 + sqrt(3)*i)/2, (-1 + sqrt(3)*i)/2, -1, (-1 - sqrt(3)*i)/2, (1 - sqrt(3)*i)/2).

Mobius transform of A319100.

			Let w = exp(2*Pi/6) = (1 + sqrt(3)*i)/2. For n = 19, the 5 sextic primitive Dirichlet characters modulo n are:
  Chi_1 = [0, 1, w, w, w - 1, -w, w - 1, 1, -1, w - 1, -w + 1, 1, -1, -w + 1, w, -w + 1, -w, -w, -1];
  Chi_2 = [0, 1, w - 1, w - 1, -w, w - 1, -w, 1, 1, -w, -w, 1, 1, -w, w - 1, -w, w - 1, w - 1, 1];
  Chi_3 = [0, 1, -1, -1, 1, 1, 1, 1, -1, 1, -1, 1, -1, -1, -1, -1, 1, 1, -1];
  Chi_4 = [0, 1, -w, -w, w - 1, -w, w - 1, 1, 1, w - 1, w - 1, 1, 1, w - 1, -w, w - 1, -w, -w, 1];
  Chi_5 = [0, 1, -w + 1, -w + 1, -w, w - 1, -w, 1, -1, -w, w, 1, -1, w, -w + 1, w, w - 1, w - 1, -1],
so a(19) = 5.

Jianing Song, Table of n, a(n) for n = 1..65539

Number of k-th power primitive Dirichlet characters modulo n: A114643 (k=2), A160498 (k=3), A160499 (k=4), A307380 (k=5), this sequence (k=6), A307382 (k=7), A329272 (k=8).

Cf. A319100 (number of solutions to x^6 == 1 (mod n)).

f[2, e_] := Which[e == 1, 0, e == 2, 1, e == 3, 2, e >= 4, 0]; f[3, e_] := Which[e == 1, 1, e == 2, 4, e >= 3, 0]; f[p_, 1] := If[Mod[p, 6] == 1, 5, 1]; f[p_, e_] := 0; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 16 2020 *)

a(n)={
    my(r=1, f=factor(n));
    for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]);
        if(p==2, if(e==3, r*=2, if(e!=2, r=0; return(r))));
        if(p==3, if(e==2, r*=4, if(e!=1, r=0; return(r))));
        if(p>3, if(p%6==1&&e==1, r*=5, if(e!=1, r=0; return(r))));
    );
    return(r);
} \\ Jianing Song, Nov 10 2019

Multiplicative with a(4) = 1, a(8) = 2, a(2^e) = 0 for e = 1 or e >= 4; a(3) = 1, a(9) = 4, a(3^e) = 0 for e >= 3; a(p) = 5 if p == 1 (mod 6) and 1 if p == 5 (mod 6), a(p^e) = 0 if p > 3 and e >= 2.

A329272 Number of octic primitive Dirichlet characters modulo n.

Original entry on oeis.org

1, 0, 1, 1, 3, 0, 1, 2, 0, 0, 1, 1, 3, 0, 3, 4, 7, 0, 1, 3, 1, 0, 1, 2, 0, 0, 0, 1, 3, 0, 1, 8, 1, 0, 3, 0, 3, 0, 3, 6, 7, 0, 1, 1, 0, 0, 1, 4, 0, 0, 7, 3, 3, 0, 3, 2, 1, 0, 1, 3, 3, 0, 0, 0, 9, 0, 1, 7, 1, 0, 1, 0, 7, 0, 0, 1, 1, 0, 1, 12, 0, 0, 1, 1, 21, 0, 3, 2, 7, 0, 3

Offset: 1

Jianing Song, Nov 10 2019

a(n) is the number of primitive Dirichlet characters modulo n such that all entries are 0 or a eighth-power root of unity (+-1, +-i, +-sqrt(2)/2 +- sqrt(2)/2*i, i = sqrt(-1)).

Mobius transform of A247257.

			Let w = exp(2*Pi*i/8) = sqrt(2)/2 + i*sqrt(2)/2. For n = 17, the 7 octic primitive Dirichlet characters modulo n are:
  Chi_1 = [0, 1, -i, w, -1, -w, -w^3, w^3, i, i, w^3, -w^3, -w, -1, w, -i, 1];
  Chi_2 = [0, 1, -1, i, 1, i, -i, -i, -1, -1, -i, -i, i, 1, i, -1, 1];
  Chi_3 = [0, 1, i, w^3, -1, -w^3, -w, w, -i, -i, w, -w, -w^3, -1, w^3, i, 1];
  Chi_4 = [0, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, -1, -1, 1, -1, 1, 1];
  Chi_5 = [0, 1, -i, -w, -1, w, w^3, -w^3, i, i, -w^3, w^3, w, -1, -w, -i, 1];
  Chi_6 = [0, 1, -1, -i, 1, -i, i, i, -1, -1, i, i, -i, 1, -i, -1, 1];
  Chi_7 = [0, 1, i, -w^3, -1, w^3, w, -w, -i, -i, -w, w, w^3, -1, -w^3, i, 1],
so a(17) = 7.

Jianing Song, Table of n, a(n) for n = 1..65539

Number of k-th power primitive Dirichlet characters modulo n: A114643 (k=2), A160498 (k=3), A160499 (k=4), A307380 (k=5), A307381 (k=6), A307382 (k=7), this sequence (k=8).

Cf. A247257 (number of solutions to x^8 == 1 (mod n)).

f[2, e_] := If[2 <= e <= 5, 2^(e-2), 0]; f[p_, e_] := If[e == 1, GCD[p-1, 8] - 1, 0];  a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 16 2020 *)

a(n)={
    my(r=1, f=factor(n));
    for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]);
        if(p==2, if(e>=2&&e<=5, r*=2^(e-2), r=0; return(r)));
        if(p>2, if(e==1, r*=gcd(p-1,8)-1, r=0; return(r)));
    );
    return(r);
}

Multiplicative with a(2^e) = 2^(e-2) for 2 <= e <= 5, a(2^e) = 0 for e = 1 or e >= 6; a(p^e) = gcd(p-1, 8)-1 if p > 2 and e = 1, a(p^e) = 0 if p > 2 and e >= 2.

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

Original entry on oeis.org

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

Jianing Song, May 16 2022

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

			  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

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

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.

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

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

cp's OEIS Frontend

A319101 Number of solutions to x^7 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A307380 Number of quintic primitive Dirichlet characters modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions

A307381 Number of sextic primitive Dirichlet characters modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A329272 Number of octic primitive Dirichlet characters modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula