The Nth number with M prime factors

Question

Hi.

Suppose we arrange all natural numbers in a matrix P defined as follows:

P[I][J] = The Jth number with I prime factors. So P looks something like:

1

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , ...

4 , 6 , 9 , 10 , 14 , 15 , 21 , 22 , 25 , 26 , 33 , 34 , 35 , 38 , 39 , ...

8 , 12 , 18 , 20 , 27 , 28 , 30 , 42 , 44 , 45 , 50 , 52 , 63 , 66 , 68 , ...

16 , 24 , 36 , 40 , 54 , 56 , 60 , 81 , 84 , 88 , 90 , 100 , 104 , 126 , 132 , ...

32 , 48 , 72 , 80 , 108 , 112 , 120 , 162 , 168 , 176 , 180 , 200 , 208 , 243 , 252 , ...

64 , 96 , 144 , 160 , 216 , 224 , 240 , 324 , 336 , 352 , 360 , 400 , 416 , 486 , 504 , ...

I noticed that P[i][j] = P[i-1][j]*2 if and only if j < O(1.666^i).

Examples:

i = 2 AND j < 2

i = 3 AND j < 4

i = 4 AND j < 7

i = 5 AND j < 13

i = 6 AND j < 22

i = 7 AND j < 38

i = 8 AND j < 63

i = 9 AND j < 102

i = 10 AND j < 168

i = 11 AND j < 268

i = 12 AND j < 426

I suppose that there is a more accurate approximation of the condition above.

What work has been previously done on the relation between "The Nth number with M prime factors" and "The Nth number with M-1 prime factors"?

Thanks

Answer 1

Each sequence of "$n$-almost-primes" opens with a string of even numbers that are twice the entries that begin the previous sequence. The first odd $n$-almost-prime is $3^n$. Thus the sequence the OP has observed, $2,4,7,13,22,38,63,\ldots$, is basically the sequence A078843 $(3,5,8,14,23,39,64,\ldots)$ in the OEIS. There's a recursive formula given there, attributed to Max Alekseyev:

$$a(n) = a(n-1) + \text{appi}3(n-k,[3^n/2^k]),$$ where $k = \text{ceil}(nc)$ with $c = \log(5/3)/\log(5/2) = 0.55749295\ldots$ and $\text{appi}3(k,n)$ is the number of $k$-almost-primes not divisible by $3$ and not exceeding $n$. This might supply the "more accurate approximation" the OP referred to. The ratio of consecutive terms in A078843 seems to be tending to around $1.53$-something, far less than the OP's $1.666$, but all that could be quite illusory.

The link from the OEIS entry to the MathWorld entry on "Almost Primes" may also be of interest.