1
$\begingroup$

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.

2 Answers 2

2

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$

  • 0
    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.2012-03-23
0

This sequence also emerges when you take each number starting with 2 and separate them into categories based on the number of prime factors they have. For example,

2 has one prime factor:

2 [1]

3 has one prime factor:

3 [2]

4 has two prime factors:

4 [2, 1]

5 has one prime factor:

5 [3, 1]

6 [3, 2]

7 [4, 2]

8 [4, 2, 1]

As we go up the number line, when we hit 2^n another column is added with a value of 1. As you continue you start to see the sequence 1, 2, 7, 15, 37, 84 reversed.

8192 [1028, 2186, 2082, 1405, 770, 392, 182, 84, 37, 15, 7, 2, 1]

4096 [564, 1124, 1049, 669, 367, 177, 83, 37, 15, 7, 2, 1]

2048 [309, 589, 513, 325, 168, 81, 37, 15, 7, 2, 1]

It is my hypothesis that as 2^n becomes increasingly larger, the sequence will continue to develop.

1048576 [82025, 219759, 262865, 207945, 130713, 72515, 37423, 18532, 8917, 4225, 1989, 913, 421, 187, 84, 37, 15, 7, 2, 1]

Moving forward is to determine the relationship between this technique and those above. Help would be appreciated.

  • 0
    I haven't looked at this in 5 years...but if you work through Mercio's remarkable answer it completely answers the question. Will look at this when time permits but I am guessing you will find that your observation is explained by the answer already given.2017-10-19