A349338 Dirichlet convolution of A000010 (Euler totient phi) with A080339 (characteristic function of noncomposite numbers).

1, 2, 3, 3, 5, 5, 7, 6, 8, 9, 11, 8, 13, 13, 14, 12, 17, 14, 19, 14, 20, 21, 23, 16, 24, 25, 24, 20, 29, 22, 31, 24, 32, 33, 34, 22, 37, 37, 38, 28, 41, 32, 43, 32, 38, 45, 47, 32, 48, 44, 50, 38, 53, 42, 54, 40, 56, 57, 59, 36, 61, 61, 54, 48, 64, 52, 67, 50, 68, 58, 71, 44, 73, 73, 68, 56, 76, 62, 79, 56, 72, 81

Offset: 1

Author

Antti Karttunen, Nov 17 2021

Keywords

• nonn

Comments

Möbius transform of A230593.

The number of integers k from 1 to n such that gcd(n, k) is a noncomposite number. - Amiram Eldar, Jun 21 2025

Links

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

Crossrefs

Cf. A000010, A005117, A008683, A069359, A080339, A085548, A117494, A230593, A348976, A349435.

Programs

Mathematica

a[n_] := DivisorSum[n, Boole[!CompositeQ[#]] * EulerPhi[n/#] &]; Array[a, 100] (* Amiram Eldar, Nov 17 2021 *)

PARI

A349338(n) = sumdiv(n, d, eulerphi(n/d)*((1==d)||isprime(d)));

PARI

a(n) = {my(f = factor(n), p = f[,1], e = f[,2]); n * vecprod(apply(x -> 1-1/x, p)) * (1 + vecsum(apply(x -> 1/x, p - vector(#e, i, e[i] == 1)~)));} \\ Amiram Eldar, Jun 21 2025

Formula

a(n) = Sum_{d|n} A000010(n/d) * A080339(d).

a(n) = Sum_{d|n} A008683(n/d) * A230593(d).

a(n) = Sum_{d|n} A349435(n/d) * A348976(d).

a(n) = A000010(n) + A117494(n). [Because A117494 is the Möbius transform of A069359]

For all n >= 1, a(A005117(n)) = A348976(A005117(n)).

Sum_{k=1..n} a(k) ~ 3 * (1 + A085548) * n^2 / Pi^2. - Vaclav Kotesovec, Nov 20 2021