# A pattern in distribution of near-primes less than $2^n$

Let $\pi_k(2^n)$ be the number of almost-primes (numbers with k factors including repetitions) less than $2^n$. I noticed that for large values of n and values of k near n, a sequence $\{\pi_k\}$ emerges. For example, for n = 17, for k = 17,...,12, the sequence is {1,2,7,15,37,84}. The terms of the sequence emerge as n grows.

The sequence is in OEIS as A052130, and there is a brief comment there that may explain the sequence. Could someone elaborate a bit on the comment or provide something a little more substantive?

Thanks.

-
What do you mean by "higher values of $k$?" It seems like $k=12<n=17$, so I don't think you mean $k>n$. – Thomas Andrews Mar 20 '12 at 18:11
And what pattern are you saying breaks down? – Thomas Andrews Mar 20 '12 at 18:15
@ThomasAndrews: Maybe the edit addresses your first question. As for the second, I do not notice a pattern and this too I edited. It's a sequence, whose pattern I surely do not perceive. – daniel Mar 20 '12 at 18:31

You are seeing that for every $k \ge 0$, the sequence $(\pi_n(2^{n+k}))_{(n \ge 1)}$ is stationary :

Let $k \ge 0$. If $x$ is any $n$-almost prime number less than $2^{n+k}$, then $2x$ is an $(n+1)$-almost prime number less than $2^{n+1+k}$, so $\pi_n(2^{n+k}) \le \pi_{n+1}(2^{n+1+k})$ : the sequences are increasing.

Let $x$ be any $n$-almost prime number less than $2^{n+k}$, and write it as $x=2^a y$ with odd $y$. Then $y$ is an $(n-a)$-almost prime number less than $2^{n+k-a}$. Since $y$ is odd, all its prime factors are $3$ or higher, so $3^{n-a} \le y \le 2^{n+k-a}$. This shows that $n-a \le \frac {k \log 2}{\log 3 - \log 2}$. Let $c_k = \lfloor \frac {k \log 2}{\log 3 - \log 2} \rfloor$. Then $y$ has to be an odd number less than $2^{c_k+k}$.

Conversely, for every odd number $y$ less than $2^{c_k+k}$, if $b$ is the number of prime factors of $y$, then the only $n$-almost-prime number $x$ corresponding to $y$ is $2^{n-b}y$ if $n \ge b$, and there is no corresponding $x$ otherwise. So $\pi_n(2^{n+k})$ is less than the number of odd numbers less than $2^{c_k+k}$, i.e. $\pi_n(2^{n+k}) \le 2^{c_k+k-1}$.

An increasing bounded sequence of integers has to be stationary, so there is a sequence $(l_k)_{k \ge0} = (1, 2, 7, 15, \ldots)$ such that for every $k\ge 0$, for every $n$ large enough, $\pi_n(2^{n+k}) = l_k$

-
Before I look at this, do you think the comment at OEIS is consistent with your explanation? He says: a(n) = number of products of half-odd-primes <= 2^n. E.g. a(2) = 7 since 1, 3/2, (3/2)^2, (3/2)^3, (3/2)*(5/2), 5/2, 7/2 are all <= 2^2. His account seems to work...is he saying the same thing you're saying? PS--Yes, "stationary" is the word I sought, thanks. – daniel Mar 20 '12 at 18:39
yes. for $k=2, c_k=3$ they correspond to the odd numbers $1,3,9,27,15,5,7$. They are all less than $2^5$ and they are the odd numbers that can give rise to a suitable $x$ when $n$ is large enough. Those are the numbers $y$ with $b$ factors such that $y \le 2^{k+b}$, i.e. $(y/2^b) \le 2^k$ – mercio Mar 20 '12 at 18:51
This was useful, quickly furnished, and easy to follow. If the question was worth a couple of votes, the answer is worth a lot more. – daniel Mar 23 '12 at 2:04