cp's OEIS Frontend

A118896 Number of powerful numbers <= 10^n.

%I A118896 #68 Feb 16 2025 08:33:01
%S A118896 1,4,14,54,185,619,2027,6553,21044,67231,214122,680330,2158391,
%T A118896 6840384,21663503,68575557,217004842,686552743,2171766332,6869227848,
%U A118896 21725636644,68709456167,217293374285,687174291753,2173105517385,6872112993377,21731852479862,68722847672629,217322225558934,687236449779456,2173239433013146
%N A118896 Number of powerful numbers <= 10^n.
%C A118896 These numbers agree with the asymptotic formula c*sqrt(x), with c=2.1732...(A090699). - _T. D. Noe_, May 09 2006
%C A118896 Bateman & Grosswald proved that the number of powerful numbers up to x is zeta(3/2)/zeta(3) * x^1/2 + zeta(2/3)/zeta(2) * x^1/3 + o(x^1/6). This approximates the series very closely: up to a(24), all absolute errors are less than 75. - _Charles R Greathouse IV_, Sep 23 2008
%H A118896 Charles R Greathouse IV and Hiroaki Yamanouchi, <a href="/A118896/b118896.txt">Table of n, a(n) for n = 0..45</a> (terms a(0)-a(32) from Charles R Greathouse IV)
%H A118896 Michael Filaseta and Ognian Trifonov, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa67/aa6743.pdf">The distribution of squarefull numbers in short intervals</a>, Acta Arithmetica 67 (1994), pp. 323-333.
%H A118896 Paul T. Bateman and Emil Grosswald, <a href="http://projecteuclid.org/euclid.ijm/1255380836">On a theorem of Erdős and Szekeres</a>, Illinois J. Math. 2:1 (1958), p. 88-98.
%H A118896 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PowerfulNumber.html">Powerful Number</a>
%F A118896 Pi(x) = Sum_{i=1..x^(1/3)} floor(sqrt(x/i^3)) only if i is squarefree. - _Robert G. Wilson v_, Aug 12 2014
%p A118896 f:= m -> nops({seq(seq(a^2*b^3, b=1..floor((m/a^2)^(1/3))),a=1..floor(sqrt(m)))}):
%p A118896 seq(f(10^n),n=0..10); # _Robert Israel_, Aug 12 2014
%t A118896 f[n_] := Block[{max = 10^n}, Length@ Union@ Flatten@ Table[ a^2*b^3, {b, max^(1/3)}, {a, Sqrt[ max/b^3]}]]; Array[f, 13, 0] (* _Robert G. Wilson v_, Aug 11 2014 *)
%t A118896 powerfulNumberPi[n_] := Sum[ If[ SquareFreeQ@ i, Floor[ Sqrt[ n/i^3]], 0], {i, n^(1/3)}]; Array[ powerfulNumberPi[10^#] &, 27, 0] (* _Robert G. Wilson v_, Aug 12 2014 *)
%o A118896 (PARI) a(n)=n=10^n;sum(k=1, floor((n+.5)^(1/3)), if(issquarefree(k), sqrtint(n\k^3))) \\ _Charles R Greathouse IV_, Sep 23 2008
%o A118896 (Python)
%o A118896 from math import isqrt
%o A118896 from sympy import integer_nthroot, factorint
%o A118896 def A118896(n):
%o A118896     m = 10**n
%o A118896     return sum(isqrt(m//x**3) for x in range(1,integer_nthroot(m,3)[0]+1) if max(factorint(x).values(),default=0)<=1) # _Chai Wah Wu_, May 13 2023
%o A118896 (Python)
%o A118896 # faster program
%o A118896 def A118896(n):
%o A118896     def squarefreepi(n): return int(sum(mobius(k)*(n//k**2) for k in range(1, isqrt(n)+1)))
%o A118896     m, c, l = 10**n, 0, 0
%o A118896     j = isqrt(m)
%o A118896     while j>1:
%o A118896         k2 = integer_nthroot(m//j**2,3)[0]+1
%o A118896         w = squarefreepi(k2-1)
%o A118896         c += j*(w-l)
%o A118896         l, j = w, isqrt(m//k2**3)
%o A118896     c += squarefreepi(integer_nthroot(m,3)[0])-l
%o A118896     return c # _Chai Wah Wu_, Sep 09 2024
%Y A118896 Cf. A001694, A090699.
%K A118896 nonn
%O A118896 0,2
%A A118896 _Eric W. Weisstein_, May 05 2006
%E A118896 More terms from _T. D. Noe_, May 09 2006
%E A118896 a(13)-a(24) from _Charles R Greathouse IV_, Sep 23 2008
%E A118896 a(25)-a(29) from _Charles R Greathouse IV_, May 30 2011
%E A118896 a(30) from _Charles R Greathouse IV_, May 31 2011