A114810 Number of complex, weakly primitive Dirichlet characters modulo n.

1, 1, 2, 1, 4, 2, 6, 2, 4, 4, 10, 2, 12, 6, 8, 4, 16, 4, 18, 4, 12, 10, 22, 4, 16, 12, 12, 6, 28, 8, 30, 8, 20, 16, 24, 4, 36, 18, 24, 8, 40, 12, 42, 10, 16, 22, 46, 8, 36, 16, 32, 12, 52, 12, 40, 12, 36, 28, 58, 8, 60, 30, 24, 16, 48, 20, 66, 16, 44, 24, 70, 8, 72, 36, 32, 18, 60, 24, 78

Offset: 1

Author

Steven Finch, Feb 19 2006

Keywords

• nonn
• mult

Comments

Any primitive Dirichlet character is weakly primitive (not conversely). Jager uses the phrase "proper character", but this conflicts with other authors (e.g., W. Ellison and F. Ellison, Prime Numbers, Wiley, 1985, p. 224) who use the word "proper" to mean the same as "primitive".

Equals Mobius transform of A055653. - Gary W. Adamson, Feb 28 2009

Examples

			The function chi defined on the integers by chi(1)=1, chi(5)=-1 and chi(2)=chi(3)=chi(4)=chi(6)=0 [and extended periodically] is a weakly primitive character mod 6, but not mod 12 or mod 18. In this sense, we eliminate the "overcounting" of complex Dirichlet characters in A000010.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• H. Jager, On the number of Dirichlet characters with modulus not exceeding x, Nederl. Akad. Wetensch. Proc. Ser. A 76=Indag. Math. 35 (1973) 452-455.

Crossrefs

Cf. A000010, A007431, A055231, A330523.

Cf. A055653. [Gary W. Adamson, Feb 28 2009]

Programs

Mathematica

b[n_] := Sum[EulerPhi[d]*MoebiusMu[n/d], {d, Divisors[n]}]; squareFreeKernel[n_] := Times @@ First /@ FactorInteger[n]; a[n_] := Sum[b[n/d], {d, Divisors[Denominator[n/squareFreeKernel[n]^2]]}]; Table[a[n], {n, 1, 80}] (* Jean-François Alcover, Sep 07 2015 *)
f[p_, e_] := If[e == 1, p - 1, (p - 1)^2*p^(e - 2)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 04 2022 *)

Formula

a(n) is multiplicative with a(p) = phi(p), a(p^k) = phi(p^k)-phi(p^(k-1)) and phi(n) = A000010(n).

a(n) = Sum_{d} A007431(n/d), where the sum is over all divisors 1<=d<=n of A055231(n).

Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} (1 - 1/p^2 - 1/p^3 + 1/p^4) = A330523 / 2 = 0.2679480769... . - Amiram Eldar, Nov 04 2022