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,2

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

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

Mathematica

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

Prog

(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

Crossrefs

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

Sequence in context: A348538 A185075 A342693 * A074399 A090302 A093074

Adjacent sequences: A349335 A349336 A349337 * A349339 A349340 A349341

Keyword

nonn

Author

Antti Karttunen, Nov 17 2021

Status

approved