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

Author

Michael De Vlieger, Jun 09 2024

Keywords

• nonn
• hard

Comments

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A007053, A036386, A126706, A143658, A182908.

Programs

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

Table[2^n - Sum[PrimePi@Floor[2^(n/k)], {k, 2, n}] - Sum[MoebiusMu[k]*Floor[#/(k^2)], {k, Floor[Sqrt[#]]}] &[2^n], {n, 4, 36} ] (* Michael De Vlieger, Jan 24 2025 *)

Python

from math import isqrt
from sympy import mobius, nextprime, integer_log
def A372403(n):
    m, p = (1<Chai Wah Wu, Jun 10 2024

Formula

a(n) = 2^n - A036386(n) - A143658(n). - Michael De Vlieger, Jan 24 2025

Extensions

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