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

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, 30, 31, 34, 35, 36, 37, 38, 38, 40, 41, 43, 45, 47, 48, 49, 50, 54, 57, 57, 58, 61, 62, 63, 63, 63, 65, 66, 67, 67, 70, 71, 74, 75, 77, 79, 82, 82, 84, 86, 89, 91

Offset: 1

Author

Friedjof Tellkamp, Jun 23 2024

Keywords

• nonn

Examples

			a(10) = 7 = card{2, 3, 9/2, 5, 27/4, 7, 15/2}.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000720, A001222, A052130, A374022.

Programs

Mathematica

z = 100;
k[n_] := Max[1, Floor[Log[3/2, n/2]]];
m[n_] := n 2^(k[n] - 1);
PrimePiK = Table[0, Floor[Log[2, m[z]]], m[z]];
For[i = 2, i <= m[z], i++, PrimePiK[[PrimeOmega[i], i]] = 1]
PrimePiK = Accumulate /@ PrimePiK;
a = Table[PrimePiK[[k[n], m[n]]], {n, z}] (*sequence*)
x = Union@Select[Table[i/2^(PrimeOmega[i] - 1), {i, 1, m[z], 2}], # <= z &] (*set*)

PARI

nap(n, k) = sum(i=1, n, bigomega(i)==k);
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

Python

from math import isqrt, prod
from sympy import primepi, primerange, integer_nthroot
def A373943(n):
    if n<=4: return primepi(n)
    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)))
    k = 1
    while 3**k<(r:=n<Chai Wah Wu, Dec 03 2024

Formula

a(n) = card{x | x = m/2^(bigomega(m)-1), x<=n}.

a(n) = pi_k(n * 2^(k - 1)), with pi_k(n) as the counting function for k-almost primes and k sufficiently large.

k needs to be at least max(1, floor(log(n/2)/(log(3)-log(2)))) and m = n * 2^(k - 1).

a(n) = A374022(n) + A000720(n).

a(2^n) = A052130(n-1).