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

0, 0, 0, 0, 0, 0, 1, 4, 9, 17, 28, 48, 75, 115, 178, 266, 403, 590, 865, 1263, 1830, 2644, 3810, 5466, 7838, 11210, 16011, 22841, 32530, 46315, 65886, 93658, 133060, 188952, 268204, 380564, 539823, 765481, 1085224, 1538194, 2179816, 3088481, 4375308, 6197420, 8777222

Offset: 0

Author

Michael De Vlieger, Jan 24 2025

Keywords

• nonn
• hard

Examples

			Let s = A286708 = A001694 \ A246547 \ {1}.
a(0..5) = 0 since the smallest number in s is 36.
a(6) = 1 since only s(1) = 36 is smaller than 2^6 = 64.
a(7) = 4 since s(1..4) = {36, 72, 100, 108} are smaller than 2^7 = 128.
a(8) = 9 since s(1..9) = {36, 72, 100, 108, 144, 196, 200, 216, 225} are smaller than 2^8 = 256, etc.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 0..90

Crossrefs

Cf. A001694, A036386, A062762, A246547, A286708, A372403.

Programs

Mathematica

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} ]

Python

from math import isqrt
from sympy import mobius, integer_nthroot, primepi
def A380431(n):
    def squarefreepi(n): return int(sum(mobius(k)*(n//k**2) for k in range(1, isqrt(n)+1)))
    l, m = 0, 1<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, Jan 30 2025

Formula

a(n) = A062762(n) - A036386(n) - 1.

a(n) <= A372403(n), since A286708 is a proper subset of A126706.