A085972 Number of numbers <= n that are primes or not prime powers.

0, 1, 2, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9, 10, 11, 11, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 20, 21, 22, 23, 24, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 54, 55, 56, 57, 58, 59, 60, 61

Offset

1,3

Comments

a(n) = Max{k: A085971(k)<=n};

a(n) = n-A085501(n) = A000720(n)+n-A065515(n) = A085970(n)+A000720(n).

Links

Table of n, a(n) for n=1..71.

Mathematica

Accumulate[Table[If[PrimeQ[n]||(!PrimePowerQ[n]), 1, 0], {n, 80}]]-1 (* Harvey P. Dale, Oct 13 2022 *)

Prog

(Python)
from sympy import primepi, integer_nthroot
def A085972(n): return n-1-sum(primepi(integer_nthroot(n, k)[0]) for k in range(2, n.bit_length())) # Chai Wah Wu, Aug 20 2024

Crossrefs

Sequence in context: A242493 A261345 A243285 * A136378 A344374 A305557

Adjacent sequences: A085969 A085970 A085971 * A085973 A085974 A085975

Keyword

nonn

Author

Reinhard Zumkeller, Jul 06 2003

Status

approved