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