cp's OEIS Frontend

A374022 a(n) is the cardinality of the set containing all noninteger rationals of the form m/2^(bigomega(m) - 1) <= n.

%I A374022 #36 Dec 04 2024 05:49:46
%S A374022 0,0,0,0,1,1,2,3,3,3,5,6,7,7,7,9,11,12,13,14,14,14,15,16,18,20,21,22,
%T A374022 24,25,25,26,27,27,29,30,31,33,35,36,36,37,40,43,43,44,46,47,48,48,48,
%U A374022 50,50,51,51,54,55,58,58,60,61,64,64,66,68,71,72,72,74
%N A374022 a(n) is the cardinality of the set containing all noninteger rationals of the form m/2^(bigomega(m) - 1) <= n.
%H A374022 Chai Wah Wu, <a href="/A374022/b374022.txt">Table of n, a(n) for n = 1..10000</a>
%F A374022 a(n) = card{x | x = m/2^(bigomega(m)-1), x noninteger, x<=n}.
%F A374022 a(n) = pi_k(n * 2^(k - 1)) - pi(n) with pi_k(n) as the counting function for k-almost primes and k sufficiently large.
%F A374022 k needs to be at least max(1, floor(log(n/2)/(log(3)-log(2)))) and m = n * 2^(k - 1).
%F A374022 a(n) = A373943(n) - A000720(n).
%e A374022 a(5)  = 1 = card{9/2}.
%e A374022 a(7)  = 2 = card{9/2, 27/4}.
%e A374022 a(8)  = 3 = card{9/2, 27/4, 15/2}.
%e A374022 a(11) = 5 = card{9/2, 27/4, 15/2, 81/8, 21/2}.
%e A374022 a(12) = 6 = card{9/2, 27/4, 15/2, 81/8, 21/2, 45/4}.
%e A374022 a(13) = 7 = card{9/2, 27/4, 15/2, 81/8, 21/2, 45/4, 25/2}.
%e A374022 a(16) = 9 = card{9/2, 27/4, 15/2, 81/8, 21/2, 45/4, 25/2, 243/16, 63/4}.
%e A374022 It appears that Pi*x_n - n/2 + sqrt(n)/2 ~ A002410(n), where x_n is the n-th term of the above vector.
%e A374022 The numerators of the above vector elements are A374074(n).
%e A374022 The denominators of the above vector elements are 2^(bigomega(A374074(n)) - 1).
%t A374022 z = 100;
%t A374022 k[n_] := Max[1, Floor[Log[3/2, n/2]]];
%t A374022 m[n_] := n 2^(k[n] - 1);
%t A374022 PrimePiK = Table[0, Floor[Log[2, m[z]]], m[z]];
%t A374022 For[i = 2, i <= m[z], i++, PrimePiK[[PrimeOmega[i], i]] = 1]
%t A374022 PrimePiK = Accumulate /@ PrimePiK;
%t A374022 a = Table[PrimePiK[[k[n], m[n]]] - PrimePi[n], {n, z}] (*sequence*)
%t A374022 x = Union@Select[Table[i/2^(PrimeOmega[i] - 1), {i, 1, m[z], 2}], # <= z && Mod[#,1] != 0 &] (*set*)
%o A374022 (PARI) nap(n, k) = sum(i=1, n, bigomega(i)==k);
%o A374022 a(n) = my(k=max(1, floor(log(n/2)/(log(3)-log(2))))); nap(n*2^(k-1), k) - primepi(n); \\ _Michel Marcus_, Jun 27 2024
%o A374022 (Python)
%o A374022 from math import isqrt, prod
%o A374022 from sympy import primepi, primerange, integer_nthroot
%o A374022 def A374022(n):
%o A374022     if n<=4: return 0
%o A374022     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 A374022     k = 1
%o A374022     while 3**k<(r:=n<<k-1): k+=1
%o A374022     return int(sum(primepi(r//prod(c[1] for c in a))-a[-1][0] for a in g(r,0,1,1,k))-primepi(n)) # _Chai Wah Wu_, Dec 03 2024
%Y A374022 Cf. A000720, A001222, A002410, A373943, A374074.
%K A374022 nonn
%O A374022 1,7
%A A374022 _Friedjof Tellkamp_, Jun 25 2024