A372403 Number of k < 2^n that are neither squarefree nor prime powers.

1, 5, 16, 37, 83, 178, 374, 772, 1565, 3160, 6361, 12770, 25599, 51265, 102634, 205374, 410873, 821924, 1644070, 3288433, 6577231, 13154868, 26310347, 52621521, 105244142, 210489792, 420981295, 841964929, 1683933254, 3367871086, 6735748322, 13471504796, 26943020642

Offset

4,2

Comments

Analogous to A143658 (number of squarefree k <= 2^n) and A182908 (position of 2^n among prime powers A246655).

Links

Chai Wah Wu, Table of n, a(n) for n = 4..57

Example

Let quality Q represent a number k that is neither squarefree nor prime power. For instance, Q(k) is true if and only if Omega(k) > omega(k) > 1, i.e., A001222(k) > A001221(k) > 1.
a(4) = 1 since there is one number k = 12 such that Q(k) is true; 12 < 2^4.
a(5) = 5 since there are 5 numbers k such that Q(k) is true; {12, 18, 20, 24, 28} are less than 2^5.
a(6) = 16 since A126706(16) < 2^6 < A126706(17), etc.

Maple

filter:= proc(n) local F;
  F:= ifactors(n)[2];
  nops(F) > 1 and max(F[.., 2]) > 1
end proc:
R:= NULL: v:= 0:
for i from 4 to 20 do
  v:= v + nops(select(filter, [$2^(i-1)+1 .. 2^i-1]));
  R:= R, v;
od:
R; # Robert Israel, Jun 09 2024

Mathematica

nn = 2^20; m = 2; c = 0;
Reap[Do[If[Nor[PrimePowerQ[n], SquareFreeQ[n]], c++];
  If[n >= m, m *= 2; Sow[c]], {n, nn}] ][[-1, 1]]

Prog

(Python)
from math import isqrt
from sympy import mobius, nextprime, integer_log
def A372403(n):
    m, p = (1<<n)-1, 2
    q = isqrt(m)
    r = m-sum(mobius(k)*(m//k**2) for k in range(1, q+1))
    while p<=q:
        r -= integer_log(m, p)[0]-1
        p = nextprime(p)
    return r # Chai Wah Wu, Jun 10 2024

Crossrefs

Cf. A007053, A126706, A143658, A182908.

Sequence in context: A274248 A188427 A022496 * A296536 A041044 A042645

Adjacent sequences: A372400 A372401 A372402 * A372404 A372405 A372406

Keyword

nonn,hard

Author

Michael De Vlieger, Jun 09 2024

Extensions

a(30) onwards from Chai Wah Wu, Jun 10 2024

Status

approved