cp's OEIS Frontend

A373943 a(n) is the cardinality of the set containing all rational numbers of the form 2 <= m/2^(bigomega(m) - 1) <= n.

%I A373943 #27 Dec 04 2024 05:49:38
%S A373943 0,1,2,2,4,4,6,7,7,7,10,11,13,13,13,15,18,19,21,22,22,22,24,25,27,29,
%T A373943 30,31,34,35,36,37,38,38,40,41,43,45,47,48,49,50,54,57,57,58,61,62,63,
%U A373943 63,63,65,66,67,67,70,71,74,75,77,79,82,82,84,86,89,91
%N A373943 a(n) is the cardinality of the set containing all rational numbers of the form 2 <= m/2^(bigomega(m) - 1) <= n.
%H A373943 Chai Wah Wu, <a href="/A373943/b373943.txt">Table of n, a(n) for n = 1..10000</a>
%F A373943 a(n) = card{x | x = m/2^(bigomega(m)-1), x<=n}.
%F A373943 a(n) = pi_k(n * 2^(k - 1)), with pi_k(n) as the counting function for k-almost primes and k sufficiently large.
%F A373943 k needs to be at least max(1, floor(log(n/2)/(log(3)-log(2)))) and m = n * 2^(k - 1).
%F A373943 a(n) = A374022(n) + A000720(n).
%F A373943 a(2^n) = A052130(n-1).
%e A373943 a(10) = 7 = card{2, 3, 9/2, 5, 27/4, 7, 15/2}.
%t A373943 z = 100;
%t A373943 k[n_] := Max[1, Floor[Log[3/2, n/2]]];
%t A373943 m[n_] := n 2^(k[n] - 1);
%t A373943 PrimePiK = Table[0, Floor[Log[2, m[z]]], m[z]];
%t A373943 For[i = 2, i <= m[z], i++, PrimePiK[[PrimeOmega[i], i]] = 1]
%t A373943 PrimePiK = Accumulate /@ PrimePiK;
%t A373943 a = Table[PrimePiK[[k[n], m[n]]], {n, z}] (*sequence*)
%t A373943 x = Union@Select[Table[i/2^(PrimeOmega[i] - 1), {i, 1, m[z], 2}], # <= z &] (*set*)
%o A373943 (PARI) nap(n, k) = sum(i=1, n, bigomega(i)==k);
%o A373943 a(n) = my(k=max(1, floor(log(n/2)/(log(3)-log(2))))); nap(n*2^(k-1), k); \\ _Michel Marcus_, Jun 27 2024
%o A373943 (Python)
%o A373943 from math import isqrt, prod
%o A373943 from sympy import primepi, primerange, integer_nthroot
%o A373943 def A373943(n):
%o A373943     if n<=4: return primepi(n)
%o A373943     def g(x,a,b,c,m): yield from (((d,) for d in enumerate(primerange(b,isqrt(x//c)+1),a)) if m==2 else (((a2,b2),)+d for a2,b2 in enumerate(primerange(b,integer_nthroot(x//c,m)[0]+1),a) for d in g(x,a2,b2,c*b2,m-1)))
%o A373943     k = 1
%o A373943     while 3**k<(r:=n<<k-1): k+=1
%o A373943     return int(sum(primepi(r//prod(c[1] for c in a))-a[-1][0] for a in g(r,0,1,1,k))) # _Chai Wah Wu_, Dec 03 2024
%Y A373943 Cf. A000720, A001222, A052130, A374022.
%K A373943 nonn
%O A373943 1,3
%A A373943 _Friedjof Tellkamp_, Jun 23 2024