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

Author

Reinhard Zumkeller, Jul 06 2003

Keywords

• nonn

Comments

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

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

Programs

Mathematica

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

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