Monitoring prime factorization

Question

$$(p_1 \times p_2 \times \cdots \times p_n) + 1 = (q_1 \times q_2 \times \cdots \times q_m)$$ Where $p_1 \cdots p_n$ and $q_1 \cdots q_m$ are prime factors for two numbers $x$ and $y$ in the equation $x+1=y$. For example: $$99+1=100$$ or $$ (3 \times 3 \times 11) +1 = (2 \times 2 \times 5 \times 5)$$ As in the example above: $3 \times 3 \times 11$ (which are the prime factors of $99$) changes completely into $2 \times 2 \times 5 \times 5$ (which are the prime factors of $100$) after adding $1$.

So I was wondering if there is a way to find out the prime factors of $y$ when you have the prime factors of $x$, or simply a way to monitor the change in the prime factors of both numbers.

Answer 1

First off, if number theory had the power to induce a full factorization at each step (without trial division etc.), we could do away with caring about factorization and induce the first $10^{200}$ factorizations with enough time.

That being said we know a few things:

• Factors will never be shared amongst adjacent numbers.
• Testing the next number for divisibility by prime $r$, is as simple as showing $za\equiv-1\pmod r$, $a$ the additive inverse mod $r$ of $-a$ and $z$ the multiplicative inverse mod $r$ , holds for some subset of the factors clumped together. This of course is non-trivial to test for with a large number of prime factors counted with multiplicities.

• prime factors can be arbitrarily large as $y$ grows.

  This and a few other things, start to make inducing factorization not so useful or practical.