Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I took the liberty of turning one of your sequences (the third one) into a link to the OEIS. It might help if you (or someone) did the same with some of the others. –  Barry Cipra Jun 12 '13 at 20:49
    
Thanks. Added two more myself. –  barak manos Jun 12 '13 at 21:08
    
@Barakman, I corrected the link for the two-prime sequence. (I also changed the internal numbering format for the links to correspond to the number of prime factors in each sequence). –  Barry Cipra Jun 12 '13 at 21:16
add comment

1 Answer

up vote 1 down vote accepted

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.

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