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

Author

Labos Elemer, Feb 29 2000

Keywords

• nonn
• easy

Comments

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

Examples

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

Links

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

Crossrefs

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

Programs

Magma

[2*n - EulerPhi(n): n in [1..100]]; // G. C. Greubel, Feb 12 2024

Mathematica

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

PARI

a(n) = 2*n - eulerphi(n); \\ Michel Marcus, Dec 19 2013

SageMath

[2*n - euler_phi(n) for n in range(1,101)] # G. C. Greubel, Feb 12 2024

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

Extensions

Name amended with formula by Antti Karttunen, Nov 15 2021