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,8

Links

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

Formula

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

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

Example

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.

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

Prog

(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<<n
    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)
    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, Jan 30 2025

Crossrefs

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

Sequence in context: A137441 A005744 A027367 * A348238 A009879 A219841

Adjacent sequences: A380428 A380429 A380430 * A380432 A380433 A380434

Keyword

nonn,hard

Author

Michael De Vlieger, Jan 24 2025

Status

approved