how to prove a conjecture on a "canonical equivalent" of factoring

Question

The following statement about finite differences of the positions of the ordered multiset of factors of $n$ in the sequence of primes seems to be true based on my empirical tests.

Let $n=p_0^{j_0} \ldots, p_i^{j_i}$, where $p_0, \ldots, p_i$ are the prime factors of $n$ in increasing order. Let $[q_0, \ldots, q_m]$ be the list of the positions in the sequence of primes starting with 2 of these factors with their respective multiplicities. Let $[q_1-q_0,\ldots, q_m-q_{m-1}]$ be the list of their consecutive differences, clearly all $\geq 0$. Let $b(x)=\lfloor log_2(x+1) \rfloor$.

Then $b(n) \geq \sum_{l=1}^m b(q_l-q_{l-1})$.

Is this a known result? Does it obviously follow from some known theorem? Can someone point to the best proof techniques to approach this problem?

As an example, the differences between the left and the right side of the inequality on [1..31] are [1,0,2,1,1,0,3,2,2,1,2,1,1,1,4,2,3,1,3,2,2,1,3,3,2,3,2,1,2,1,5,2].

My interest in representing the prime factors of a number through a bijection to the finite differences of their positions in the sequence of primes comes from its use as a succinct representation for the factoring of $n$. Also, if applied recursively, it provides an interesting tree representation of $n$.

Thanks in advance for any hints on this,

Paul Tarau

http://www.cse.unt.edu/~tarau

Answer 1

After a small rephrasing, here it is together with the proof, hopefully correct.

PROPOSITION:

For $n \in \mathbb{N}$, let $n+1=p_0^{j_0} \ldots, p_i^{j_i}$, where $p_0, \ldots, p_i$ are the prime factors of $n+1$ in increasing order. Let $[q_0, \ldots, q_m]$ be the list of the positions in the sequence of primes starting with $2 $ of these factors with their respective multiplicities. Let $[q_1-q_0,\ldots, q_m-q_{m-1}]$ be the list of their consecutive differences, clearly all $\geq 0$. Let $b(x)=\lfloor log_2(x+1) \rfloor$.

Then $b(n) \geq \sum_{l=1}^m b(q_l-q_{l-1})$.

PROOF:

For $n=0$ equality holds, the list on the right (factoring of $1$) being empty. For $n>0$ observe that
$\sum_{l=1}^m b(q_l-q_{l-1}) = \sum_{l=1}^m \lfloor log_2(1+q_l-q_{l-1}) \rfloor \leq \lfloor \sum_{l=1}^m log_2(1+q_l-q_{l-1}) \rfloor \leq \lfloor \sum_{l=1}^m log_2(q_l) \rfloor$ $= \lfloor log_2(\prod_{l=1}^m q_i) \rfloor \leq \lfloor log_2(\prod_{l=0}^m p_i) \rfloor = \lfloor log_2(n+1)\rfloor$ $= b(n)$

This opens a more general question: what conditions are sufficient for a bijection from $\mathbb{N}$ to finite sequences of $\mathbb{N}$ for a similar property to hold? A necessary one (that the bijection derived from primes satisfies) seems to be that all elements in the sequence corresponding to $n$ are smaller then $n$.