login
A079715
a(n) = pi(n) - pi(sqrt(n)) + 1.
1
1, 2, 3, 2, 3, 3, 4, 4, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 7, 7, 7, 7, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19
OFFSET
1,2
COMMENTS
A well-known application of the principle of inclusion-exclusion used in sieve methods.
Number of numbers less than or equal to n and coprime to the product of the primes less than sqrt(n), i.e., to A104588(n). - Lekraj Beedassy, Mar 17 2005
LINKS
FORMULA
a(n) = pi(n) - pi(sqrt(n)) + 1 = A000720(n) - A056811(n) + 1 = A056812(n) + 1.
a(n) = Sum_{k=1..n} mu(k)*floor(n/k) where each prime factor of k is <= sqrt(n). [Corrected by Steven Foster Clark, May 03 2023]
MATHEMATICA
Table[PrimePi[n] - PrimePi[Sqrt[n]] + 1, {n, 1, 100}] (* G. C. Greubel, May 13 2017 *)
PROG
(PARI) for(n=1, 100, print1(primepi(n) - primepi(sqrt(n)) + 1, ", ")) \\ G. C. Greubel, May 13 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Benoit Cloitre, Feb 16 2003
EXTENSIONS
Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 12 2007
STATUS
approved