Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer 1

up vote 1 down vote accepted

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.