A176095 a(n) = n - phi(2*n), where phi() is the Euler totient A000010().

0, 0, 1, 0, 1, 2, 1, 0, 3, 2, 1, 4, 1, 2, 7, 0, 1, 6, 1, 4, 9, 2, 1, 8, 5, 2, 9, 4, 1, 14, 1, 0, 13, 2, 11, 12, 1, 2, 15, 8, 1, 18, 1, 4, 21, 2, 1, 16, 7, 10, 19, 4, 1, 18, 15, 8, 21, 2, 1, 28, 1, 2, 27, 0, 17, 26, 1, 4, 25, 22, 1, 24, 1, 2, 35, 4, 17, 30, 1, 16, 27, 2, 1, 36, 21, 2, 31, 8, 1, 42, 19

Offset: 1

Author

Michel Lagneau, Apr 08 2010

Keywords

• nonn
• easy

Examples

			a(1) = 1 - phi(2) = 0;
a(2) = 2 - phi(2*2) = 2 - 2 = 0;
a(3) = 3 - phi(2*3) = 3 - 2 = 1;
If n = (2^m)*p, with m = 3 and p = 7, then n = 2^3 * 7 = 56, and a(56) = 2^3 = 8.
		

References

• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
• Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 24.

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Crossrefs

Cf. A000010, A000040, A051953, A062570.

Programs

Maple

A176095 := proc(n)
    n-numtheory[phi](2*n) ;
end proc:
seq(A176095(n),n=1..60) ;

Mathematica

Table[n-EulerPhi[2n],{n,0,100}] (* Harvey P. Dale, Jul 24 2011 *)

PARI

A176095(n) = (n-eulerphi(n+n)); \\ Antti Karttunen, May 19 2021

Formula

a(n) = n - A062570(n).

a(2^k) = 0, k >= 0. - Michel Lagneau, Dec 17 2010

a(A000040(k)) = 1, k >= 2. - Michel Lagneau, Dec 17 2010, corrected by Antti Karttunen, May 19 2021

a(2^m*A000040(k)) = 2^m, m >= 1, k >= 2. - Michel Lagneau, Dec 17 2010

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 1 - 8/Pi^2 = 0.1894305... . - Amiram Eldar, Dec 21 2023

Extensions

Offset corrected; entry corrected and edited by Michel Lagneau, Apr 25 2010