cp's OEIS Frontend

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

%I A372403 #35 Jan 25 2025 02:17:07
%S A372403 1,5,16,37,83,178,374,772,1565,3160,6361,12770,25599,51265,102634,
%T A372403 205374,410873,821924,1644070,3288433,6577231,13154868,26310347,
%U A372403 52621521,105244142,210489792,420981295,841964929,1683933254,3367871086,6735748322,13471504796,26943020642
%N A372403 Number of k < 2^n that are neither squarefree nor prime powers.
%C A372403 Analogous to A143658 (number of squarefree k <= 2^n) and A182908 (position of 2^n among prime powers A246655).
%H A372403 Chai Wah Wu, <a href="/A372403/b372403.txt">Table of n, a(n) for n = 4..70</a>
%F A372403 a(n) = 2^n - A036386(n) - A143658(n). - _Michael De Vlieger_, Jan 24 2025
%e A372403 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.
%e A372403 a(4) = 1 since there is one number k = 12 such that Q(k) is true; 12 < 2^4.
%e A372403 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.
%e A372403 a(6) = 16 since A126706(16) < 2^6 < A126706(17), etc.
%p A372403 filter:= proc(n) local F;
%p A372403   F:= ifactors(n)[2];
%p A372403   nops(F) > 1 and max(F[..,2]) > 1
%p A372403 end proc:
%p A372403 R:= NULL: v:= 0:
%p A372403 for i from 4 to 20 do
%p A372403   v:= v + nops(select(filter, [$2^(i-1)+1 .. 2^i-1]));
%p A372403   R:= R,v;
%p A372403 od:
%p A372403 R; # _Robert Israel_, Jun 09 2024
%t A372403 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 *)
%o A372403 (Python)
%o A372403 from math import isqrt
%o A372403 from sympy import mobius, nextprime, integer_log
%o A372403 def A372403(n):
%o A372403     m, p = (1<<n)-1, 2
%o A372403     q = isqrt(m)
%o A372403     r = m-sum(mobius(k)*(m//k**2) for k in range(1,q+1))
%o A372403     while p<=q:
%o A372403         r -= integer_log(m,p)[0]-1
%o A372403         p = nextprime(p)
%o A372403     return r # _Chai Wah Wu_, Jun 10 2024
%Y A372403 Cf. A007053, A036386, A126706, A143658, A182908.
%K A372403 nonn,hard
%O A372403 4,2
%A A372403 _Michael De Vlieger_, Jun 09 2024
%E A372403 a(30) onwards from _Chai Wah Wu_, Jun 10 2024