cp's OEIS Frontend

A380431 Number of powerful numbers that are not powers of primes (i.e. are in A286708) that do not exceed 2^n.

%I A380431 #16 Jul 25 2025 04:34:30
%S A380431 0,0,0,0,0,0,1,4,9,17,28,48,75,115,178,266,403,590,865,1263,1830,2644,
%T A380431 3810,5466,7838,11210,16011,22841,32530,46315,65886,93658,133060,
%U A380431 188952,268204,380564,539823,765481,1085224,1538194,2179816,3088481,4375308,6197420,8777222
%N A380431 Number of powerful numbers that are not powers of primes (i.e. are in A286708) that do not exceed 2^n.
%H A380431 Amiram Eldar, <a href="/A380431/b380431.txt">Table of n, a(n) for n = 0..90</a>
%F A380431 a(n) = A062762(n) - A036386(n) - 1.
%F A380431 a(n) <= A372403(n), since A286708 is a proper subset of A126706.
%e A380431 Let s = A286708 = A001694 \ A246547 \ {1}.
%e A380431 a(0..5) = 0 since the smallest number in s is 36.
%e A380431 a(6) = 1 since only s(1) = 36 is smaller than 2^6 = 64.
%e A380431 a(7) = 4 since s(1..4) = {36, 72, 100, 108} are smaller than 2^7 = 128.
%e A380431 a(8) = 9 since s(1..9) = {36, 72, 100, 108, 144, 196, 200, 216, 225} are smaller than 2^8 = 256, etc.
%t A380431 Table[-1 + Sum[If[MoebiusMu[j] != 0, Floor[Sqrt[(2^n)/j^3]], 0], {j, 2^(n/3)}] - Sum[PrimePi@ Floor[2^(n/k)], {k, 2, n}], {n, 0, 45} ]
%o A380431 (Python)
%o A380431 from math import isqrt
%o A380431 from sympy import mobius, integer_nthroot, primepi
%o A380431 def A380431(n):
%o A380431     def squarefreepi(n): return int(sum(mobius(k)*(n//k**2) for k in range(1, isqrt(n)+1)))
%o A380431     l, m = 0, 1<<n
%o A380431     c, j = -1-sum(primepi(integer_nthroot(m, k)[0]) for k in range(2, m.bit_length()))+squarefreepi(integer_nthroot(m,3)[0]), isqrt(m)
%o A380431     while j>1:
%o A380431         k2 = integer_nthroot(m//j**2,3)[0]+1
%o A380431         w = squarefreepi(k2-1)
%o A380431         c += j*(w-l)
%o A380431         l, j = w, isqrt(m//k2**3)
%o A380431     return c-l # _Chai Wah Wu_, Jan 30 2025
%Y A380431 Cf. A001694, A036386, A062762, A246547, A286708, A372403.
%K A380431 nonn,hard
%O A380431 0,8
%A A380431 _Michael De Vlieger_, Jan 24 2025