Finding the 2nd smallest natural numbers of which have x prime factors.

Question

I've been doing some research into figuring out what the equation for this sort of idea would be, since I haven't been anything related to it online. I've already figured out that the 1st smallest would be $2^x$, since it is the smallest prime and has shown to be most likely answer for it. I tried to figure out the 2nd smallest, and came with a guess of $1.5*2^x$ but it didn't work for $x=7$ since it was 144 instead of 192. Here's my current list of it so far: ${3,6,12,24,48,96,144,384...}$ I wasn't able to find any mention of this sequence on OEIS, so if any of you could either help find new terms for it or find a function for it so it can be eventually posted there, that would be wonderful.

Answer 1

A number with $n$ prime factors has the form $N=p_1p_2\cdots p_n$ with $p_i$ prime. We may assume wlog. that $p_1\ge p_2\ge\ldots\ge p_n\ge 2$.

If $p_1>2$ then $2\cdot \frac N{p_1}$ has $n$ prime factors and is smaller than $N$. We conclude that the smallest number with $n$ prime factors is $2^n$.

On the other hand, this means $p_1>2$ for the second smallest. If $p_1>3$, then both $3\cdot \frac N{p_1}$ and $2\cdot \frac N{p_1}$ are smaller with $n$ prime factors. We conclude $p_1=3$ for the second smallest. If $n>1$ and $p_2>2$, then $4\cdot \frac N{3p_2}$ and $6\cdot \frac N{3p_2}$ are smaller with $n$ prime factors. We conclude that the second smallest number with $n$ prime factors is $3\cdot 2^{n-1}$.

---

Generalization:

Perhaps surprisingly, the 3rd smallest number with $n$ prime factors is not $5\cdot 2^{n-1}$, but $9\cdot 2^{n-2}$ (if $n\ge 2$).

For $m\in\Bbb N$, let $\Omega(m)$ be the number of prime factors of $m$. Define $f(m)=\frac m{2^{\Omega(m)}}$. If $m$ is odd, we can reconstruct $m$ from $f(m)$, i.e., on the odd naturals, $f$ is injective. If $a\in\Bbb R$ and $m>\prod_{3\le p<a}p^{\lfloor\log_{p/2} a\rfloor}$, then clearly $f(m)>a$. We conclude that for each $k$, a unique odd $m$ with $k$th smallest value $f(m)$ exists can can be found efficiently. Now let $r=\max\{\,\Omega(j)\mid j\text{ odd and } f(j)\le f(m)\,\}$. Then for all $n\ge r$, the $k$th smallest natural number with $n$ prime factors is $m\cdot 2^{n-\Omega(m)}$.

While the formulation of the generalization appears somewhat complicated, its proof is not and is essentially the same argument as in the first paragraph.

The sequence of $m$ in ascending order of $f(m)$ is known as A122943 and starts like this: $$1, 3, 9, 5, 27, 7,\ldots $$ corresponding to the forms $2^n$, $3\cdot 2^{n-1}$, $9\cdot 2^{n-2}$, $5\cdot 2^{n-1}$, and so on for the first few smallest numbers with $n$ prime factors (provided $n$ is big enough).

Answer 2

I believe that $1.5 \cdot 2^x$, or $3 \cdot 2^{x - 1}$, is always the second smallest number that has x factors. You can simply prove by contradiction, where the first smallest number is $2^x$, and you can't find a smaller one, nor can you find one that lies between $2^x$ and $1.5 \cdot 2^x$.