Let $\text{bump}(n)$ for $n\in\mathbb N$ be a function that increases the prime index of each prime factor of $n$ (with multiplicity) by $1$. I'll also use the notation $\text{bump}^k(n)$ to signify $\text{bump}(\text{bump}(\ldots))$ composed $k$ times, with the upshot that $\text{bump}^k(n)$ increases each prime factor of $n$, shifting up by $k$ primes.
e.g. $\text{bump}^2(20)=\text{bump}^2(2^2\cdot 5)=\text{bump}^2(p_1^2\cdot p_3)=p_{1+2}^2\cdot p_{3+2}=5^2\cdot 11=275$.
Properties
I don't think these are strictly related to my question, but am including them just in case.
$\text{bump}^{-k}(n)$ serves as an inverse where applicable.
- For example, $\text{bump}^{-2}(35)=6$, but $\text{bump}^{-3}(35)$ is undefined since it would return $p_0 p_1$.
$\text{bump}^{-k}(\text{bump}^k(n))=n$ works just fine for all nonnegative $k$.
$\text{bump}$ is totally multiplicative: $\text{bump}(a) \cdot \text{bump}(b) = \text{bump}(ab)$.
- $\gcd(\text{bump}(a),\text{bump}(b))=\text{bump}(\gcd(a,b))$.
$\text{bump}(x)$ gives distinct values for all $x$ in its domain.
$\text{bump}(1)=1$.
$\text{bump}(\mathbb N)$ is the set of all odd naturals.
Conjecture
Let $S=\{s \in \mathbb N : 2 \leq s \leq p_i^2\}$, for some prime $p_i$.
Let $R=\text{bump}^i(S)$. I claim that for any two elements $a,b$ in $R$,
$$\Omega(a) < \Omega(b) \implies a < b,$$
where $\Omega$ is a function counting factors with multiplicity.
Informally, the conjecture is that if you $\text{bump}$ all the integers in $[2,p_i^2]$ by $i$ or more, and sort the resulting list, the first (smallest) numbers will be every prime in the list, followed by every semiprime in the list, then every 3-almost prime, and so forth. Each group is contiguous; the largest $m$-almost prime will be strictly smaller than the smallest $(m+1)$-almost prime, for all $m$.
Small example using $i=2$.
$R=\text{bump}^2(S)$, where $S=[2,p_i^2]=\{2,3,4,5,6,7,8,9\}$.
Table is displayed sorted by values in $R$.
Larger example using $i=5$. First column is input ($S$), second is $\text{bump}$ed output ($R$). Tables are separated by factor count for visibility (leftmost is all primes, to the right semiprimes, etc.), but logically it is one long table. You'll see $R$ is ordered as in our last example (e.g. $149$ at the end of the first table precedes $169$ beginning the second table).
I am nearly certain this holds in light of empirical observations and heuristics. Furthermore, it is clear that $i$ is necessarily the smallest sufficient factor-shifting value, as $\text{bump}^{i-1}(S)$ will include $p_i^2$ along with $i-1$ primes larger than $p_i^2$ in the resulting output set, violating the ordering.
However, this assumes that commonly held beliefs about the distribution of primes are true—in particular, the Legendre conjecture or a roughly equivalent result. For this reason, I expect that proving my conjecture above would be insurmountably difficult for the moment, as it implies a substantially stronger claim than Legendre, itself a conjecture which is still famously unresolved.
Given that, my question is whether a relaxed version of this conjecture might be more amenable to proof. For example, instead of $\text{bump}^i(S)$, one could consider adding a constant $c$ such as in the following (progressively weaker) expressions for what is sufficient to guarantee ordering-by-factors:
- $\text{bump}^{i+c}(S)$
- $\text{bump}^{ci}(S)$
- $\text{bump}^{i^{c}}(S)$
- $\text{bump}^{c^{i}}(S)$
It should be apparent with a little thought that $\Omega(a)<\Omega(b) \iff \text{bump}^k(a)<\text{bump}^k(b)$ as $k\to \infty$. This is because in the limit, the difference between factors will become negligible; regardless of the initial argument $n$, as $k\to\infty$, the ratio between the next term and the current term should converge on something like $\left(\frac{p_{k+1}}{p_{k}}\right)^{\Omega(n)}$.
If I have this right, this implies that in the time it takes for a prime to grow by a factor of $x$, a semiprime will grow by approx. $x^2$, and so on. I suppose that means that $$\lim_{k\to\infty} \left(\frac{\log {\text{bump}^k(a)}}{\log {\text{bump}^k(b)}}\right)=\frac{\Omega(a)}{\Omega(b)},$$ though I'd like to have someone confirm that or not. At any rate, what I have no idea about is whether there are some existing formal treatments of this general principle that could be useful here.
I will consider this question answered if: anyone can show a proof of the conjecture with one of those more relaxed expressions listed, if anyone can point me in a useful direction via suggesting relevant theorems, or if anyone can point out a reason that no version of this is likely to be presently provable. Or, of course, if anyone can find a counterexample to my conjecture.
It occurs to me that perhaps this is at least provable for all composite cases in the given range; that would eliminate dealing with the primes, which is the only thing we can be sure would be hard to prove.