VOOZH about

URL: https://oeis.org/A062762

⇱ A062762 - OEIS

login
A062762
Number of powerful numbers not exceeding 2^n.
5
1, 1, 2, 3, 5, 8, 11, 18, 26, 38, 55, 80, 116, 166, 240, 345, 497, 710, 1016, 1453, 2073, 2955, 4211, 5992, 8523, 12111, 17202, 24423, 34648, 49152, 69694, 98795, 140009, 198378, 281016, 398002, 563612, 797999, 1129737, 1599166, 2263457, 3203381
OFFSET
0,3
COMMENTS
Number of terms x from A001694 for which x <= 2^n.
LINKS
Chai Wah Wu, Table of n, a(n) for n = 0..127 (terms 0..90 from Daniel Suteu)
FORMULA
a(n) = Sum_{k=0..n} A062761(k). - Daniel Suteu, Feb 18 2020
EXAMPLE
Below 128, the 18 powerful numbers {1,4,8,9,16,25,...,100,108,121,125,128} can be found, so a(7)=18.
MATHEMATICA
nn = 41; s = Union@ Flatten@ Table[a^2*b^3, {b, (2^nn)^(1/3)}, {a, Sqrt[(2^nn)/b^3]}]; Table[FirstPosition[s, 2^k][[1]], {k, 2, nn}] (* Michael De Vlieger, Oct 29 2023 *)
PROG
(PARI) a(n) = my(s=0, N=2^n); forsquarefree(k=1, sqrtnint(N, 3), s += sqrtint(N\k[1]^3)); s; \\ Daniel Suteu, Feb 18 2020
(Python)
from math import isqrt
from sympy import mobius, integer_nthroot
def A062762(n):
def squarefreepi(n): return int(sum(mobius(k)*(n//k**2) for k in range(1, isqrt(n)+1)))
m = 1<<n
c, l, j = squarefreepi(integer_nthroot(m, 3)[0]), 0, isqrt(m)
while j>1:
k2 = integer_nthroot(m//j**2, 3)[0]+1
w = squarefreepi(k2-1)
c += j*(w-l)
l, j = w, isqrt(m//k2**3)
return c-l # Chai Wah Wu, Sep 13 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Labos Elemer, Jul 16 2001
EXTENSIONS
a(19)-a(41) from Donovan Johnson, Oct 01 2009
STATUS
approved