A394767 Number of numbers k <= 2^n such that k is neither squareful nor squarefree.

0, 0, 0, 0, 1, 5, 15, 33, 74, 161, 346, 724, 1490, 3045, 6183, 12504, 25196, 50675, 101769, 204111, 409043, 819280, 1640260, 3282967, 6569393, 13143658, 26294336, 52598680, 105211612, 210443477, 420915409, 841871271, 1683800194, 3367682134, 6735480118, 13471124232

Offset

0,6

Links

Michael De Vlieger, Table of n, a(n) for n = 0..100

Formula

a(n) = A000079(n) - A062762(n) - A143658(n) + 1.

a(n) = A372403(n) - A380431(n).

a(n) = 1 + 2^n - (Sum_{j=1..2^(n/3)} |mu(j)| * floor(sqrt(2^n/j^3))) - Sum_{k=1..2^(n/2)} mu(k) * floor((2^n)/k^2), where mu = A008683.

Example

a(0)..a(3) = 0 since 12 is the smallest number in A332785.
a(4) = 1 since only 12 is no larger than 2^4 = 16.
a(5) = 5 since a(4) = 1, and additionally, 4 more numbers in A332785 are no larger than 2^5 = 32, these are {18, 20, 24, 28}.
a(6) = 15 since a(5) = 5, and additionally, 10 more are no larger than 2^6 = 64, i.e., {40, 44, 45, 48, 50, 52, 54, 56, 60, 63}, etc.

Mathematica

Table[1 + 2^n - Sum[Abs[MoebiusMu[j]]*Floor[Sqrt[(2^n)/j^3]], {j, 2^(n/3)}] - Sum[MoebiusMu[k]*Floor[(2^n)/k^2], {k, 2^(n/2)}], {n, 0, 30}]

Prog

(Python)
from math import isqrt
from sympy import integer_nthroot
from oeis_sequences.OEISsequences import squarefreepi
def A394767(n):
    m = 1<<n
    c, l, j = m+1-squarefreepi(integer_nthroot(m, 3)[0])-squarefreepi(m), 0, isqrt(m)
    while j>1:
        k2 = integer_nthroot(m//j**2, 3)[0]+1
        w = squarefreepi(k2-1)
        c += j*(l-w)
        l, j = w, isqrt(m//k2**3)
    return c+l # Chai Wah Wu, Apr 11 2026

Crossrefs

Cf. A000079, A001694, A005117, A062762, A143658, A332785, A372403, A380431.

Sequence in context: A212983 A055004 A332355 * A147264 A147150 A393616

Adjacent sequences: A394764 A394765 A394766 * A394768 A394769 A394770

Keyword

nonn

Author

Michael De Vlieger, Apr 03 2026

Status

approved