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

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, 24, 25, 25, 26, 27, 27, 29, 30, 31, 33, 35, 36, 36, 37, 40, 43, 43, 44, 46, 47, 48, 48, 48, 50, 50, 51, 51, 54, 55, 58, 58, 60, 61, 64, 64, 66, 68, 71, 72, 72, 74

Offset

1,7

Links

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

Formula

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

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.

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

a(n) = A373943(n) - A000720(n).

Example

a(5)  = 1 = card{9/2}.
a(7)  = 2 = card{9/2, 27/4}.
a(8)  = 3 = card{9/2, 27/4, 15/2}.
a(11) = 5 = card{9/2, 27/4, 15/2, 81/8, 21/2}.
a(12) = 6 = card{9/2, 27/4, 15/2, 81/8, 21/2, 45/4}.
a(13) = 7 = card{9/2, 27/4, 15/2, 81/8, 21/2, 45/4, 25/2}.
a(16) = 9 = card{9/2, 27/4, 15/2, 81/8, 21/2, 45/4, 25/2, 243/16, 63/4}.
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.
The numerators of the above vector elements are A374074(n).
The denominators of the above vector elements are 2^(bigomega(A374074(n)) - 1).

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]]] - PrimePi[n], {n, z}] (*sequence*)
x = Union@Select[Table[i/2^(PrimeOmega[i] - 1), {i, 1, m[z], 2}], # <= z && Mod[#, 1] != 0 &] (*set*)

Prog

(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) - primepi(n); \\ Michel Marcus, Jun 27 2024
(Python)
from math import isqrt, prod
from sympy import primepi, primerange, integer_nthroot
def A374022(n):
    if n<=4: return 0
    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<<k-1): k+=1
    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

Crossrefs

Cf. A000720, A001222, A002410, A373943, A374074.

Sequence in context: A335107 A130499 A020910 * A029065 A263253 A376530

Adjacent sequences: A374019 A374020 A374021 * A374023 A374024 A374025

Keyword

nonn

Author

Friedjof Tellkamp, Jun 25 2024

Status

approved