A081063 Number of numbers <= n that are 3-smooth or prime powers.

1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 11, 12, 12, 12, 13, 14, 15, 16, 16, 16, 16, 17, 18, 19, 19, 20, 20, 21, 21, 22, 23, 23, 23, 23, 24, 25, 25, 25, 25, 26, 26, 27, 27, 27, 27, 28, 29, 30, 30, 30, 30, 31, 32, 32, 32, 32, 32, 33, 33, 34, 34, 34, 35, 35, 35, 36, 36, 36, 36, 37, 38, 39

Offset: 1

Author

Reinhard Zumkeller, Mar 04 2003

Keywords

• nonn

Comments

a(n) = #{A081061(k): 1<=k<=n}.

Links

• Harvey P. Dale, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A003586, A000961.

Programs

Mathematica

Accumulate[Table[If[PrimePowerQ[n]||Max[FactorInteger[n][[All,1]]]<5,1,0],{n,80}]] (* Harvey P. Dale, Nov 29 2020 *)

Python

from sympy import integer_log, primepi, integer_nthroot
def A081063(n): return int(1-(a:=n.bit_length())-(b:=integer_log(n,3)[0])+sum((n//3**i).bit_length() for i in range(b+1))+sum(primepi(integer_nthroot(n, k)[0]) for k in range(1, a))) # Chai Wah Wu, Sep 16 2024

Formula

a(n)=A071521(n)+A065515(n)-A000523(n)-A062153(n)+1.