A053158 Sum of n and its cototient function value (A051953): a(n) = 2*n - phi(n), where phi is Euler phi.

1, 3, 4, 6, 6, 10, 8, 12, 12, 16, 12, 20, 14, 22, 22, 24, 18, 30, 20, 32, 30, 34, 24, 40, 30, 40, 36, 44, 30, 52, 32, 48, 46, 52, 46, 60, 38, 58, 54, 64, 42, 72, 44, 68, 66, 70, 48, 80, 56, 80, 70, 80, 54, 90, 70, 88, 78, 88, 60, 104, 62, 94, 90, 96, 82, 112, 68, 104, 94, 116

Offset

1,2

Comments

For Mersenne primes and also for certain composites the values of this function are powers of 2.

Links

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

Formula

a(n) = n + A051953(n) = 2n - phi(n), where phi is A000010.

a(2^k) = 3*2^(k-1).

Sum_{k=1..n} a(k) = c * n^2 + O(n*log(n)), where c = 1 - 3/Pi^2 = 0.696036... . - Amiram Eldar, Dec 16 2023

Example

a(127) = 254 - 126 = 128.
a(80) = 160 - 32 = 128.

Mathematica

a[n_] := 2*n - EulerPhi[n]; Array[a, 60] (* Amiram Eldar, Dec 16 2023 *)

Prog

(PARI) a(n) = 2*n - eulerphi(n); \\ Michel Marcus, Dec 19 2013
(Magma) [2*n - EulerPhi(n): n in [1..100]]; // G. C. Greubel, Feb 12 2024
(SageMath) [2*n - euler_phi(n) for n in range(1, 101)] # G. C. Greubel, Feb 12 2024

Crossrefs

Cf. A000010, A000043, A000668, A001368, A051953, A104141.

Sequence in context: A175708 A023830 A063649 * A206924 A185443 A275258

Adjacent sequences: A053155 A053156 A053157 * A053159 A053160 A053161

Keyword

nonn,easy

Author

Labos Elemer, Feb 29 2000

Extensions

Name amended with formula by Antti Karttunen, Nov 15 2021

Status

approved