# Finding the (smallest) next number with the same distinct prime factors as a previous number

(Since there is no answer yet, I removed most "EDIT"'s to make the text more readable)

Today, I was trying to find a natural number $$n_{2}$$ such that this number has the same distinct prime factors as another, previous number $$n_{1}$$ with $$n_{2}>n_{1}$$, but does not differ too much from it. The extreme would be a difference of $$2$$ because $$gcd(n,n+1)=1$$.

There is one trivial example: $$n_{1}=2$$ and $$n_{2}=2+2=4=2^2$$. Another example (which is wrong, but illustrates the problem) is something like: $$n_{1}=2^{80}*3^{90}*5^{100}$$ and $$n_{2}=n_{1}+2=2^{82}*3^{89}*5^{100}$$. Notice how the exponents can be smaller than in the previous number.

In my case composite numbers are more interesting. It would actually be nice if there was an efficient algorithm for this (I am aware that prime factorization is a hard problem in general, which could be important here I assume).

Maybe we should assume that the distribution of these primes where this condition is met is crucial for a fast algorithm because we could just search by incrementing $$n_{1}$$.

To phrase this as a search problem:

Input: $$k,d\in \mathbb{N}$$.

Problem: Find a (small) number $$n_{1}=p_{1}^{e_{1}^{(1)}}p_{2}^{e_{2}^{(1)}}...p_{k}^{e_{k}^{(1)}}$$ with exponents $$e_{1}^{(1)},...,e_{k}^{(1)}>0$$ such that $$n_{2}=n_{1}+d$$ has the same $$k$$ distinct prime factors with exponents $$e_{1}^{(2)},...,e_{k}^{(2)}>0$$.

Suggestions for finding a solution to $$d=2$$ would be awesome. Perhaps this problem is already well known.

It seems like $$d$$ might not be "enough" at some point (when $$k$$ grows), meaning that the number of cases where the conditions are met for a specific $$d$$ is always finite and therefore it might be wise to not let the problem input depend on $$d$$, but soley on $$k$$. Maybe this is not true. Since this would help refining the problem statement, maybe someone knows how to deal with this behaviour.

The new problem would be:

Input: $$k\in \mathbb{N}$$.

Problem: Find the least $$d$$ and a (small) number $$n_{1}=p_{1}^{e_{1}^{(1)}}p_{2}^{e_{2}^{(1)}}...p_{k}^{e_{k}^{(1)}}$$ with $$e_{1}^{(1)},...,e_{k}^{(1)}>0$$ such that $$n_{2}=n_{1}+d$$ has the same $$k$$ distinct prime factors with $$e_{1}^{(2)},...,e_{k}^{(2)}>0$$.

(Okay, actually it would not be a huge problem if some exponents were equal to zero for $$n_{2}$$. But then I would still need to be able to have some lower bound for the number of distinct prime factors that does not grow too slowly with $$k$$.)

• @Piita Not the same number of prime factors, but the same distinct prime factors (the exponents have to differ because the factorizations are unique).
– user1114342
Commented May 20, 2023 at 22:41
• Well, this would be a nice way if $d$ was not given as an input. For example, I could say the difference should be $d=3$ and you could not just square the number because it will be too large.
– user1114342
Commented May 20, 2023 at 22:45
• Are you assuming known the prime factors of $\,n_1?\,$ E.g. given $\, p^i q^j\,$ you seek least $p^m q^n > p^i q^j?\ \$ Commented May 20, 2023 at 22:46
• @BillDubuque Not really. I see how knowing the factorization might speed up an algorithm, but this is not the main focus of the problem.
– user1114342
Commented May 20, 2023 at 22:48
• @Piita I updated the problem in the question to make it more clear. This is kind of what I had in mind. But if $d=2$ then there would be not example for any $p,q$, right?
– user1114342
Commented May 20, 2023 at 22:53

Note that $$n_{2} = n_{1} + d$$ implies that $$gcd(n1, n2) \vert d$$. Since $$n_{1}=p_{1}^{e_{1}^{(1)}}p_{2}^{e_{2}^{(1)}}...p_{k}^{e_{k}^{(1)}}$$ and $$n_{2}=p_{1}^{e_{1}^{(2)}}p_{2}^{e_{2}^{(2)}}...p_{k}^{e_{k}^{(2)}}$$, and for each $$i$$ and $$j$$, $$e_{i}^{({j})} > 0$$, then $$gcd(n1, n2) >= p_{1}p_{2}...p_{k}$$. For a fixed $$k$$, this means that the least $$d$$ that satisfies the conditions will be the smallest positive integer that has $$k$$ positive factors, i.e. $$d=\Pi_{i=1}^k P_{i}$$, where $$P_{i}$$ is the $$i$$-th prime number. The least $$n1$$ and $$n2$$ that satisfy the problem will be $$n_{1}=d$$ and $$n_{2} = 2d$$.
This result can also be applied to the original problem. For any fixed $$k$$ and $$d = p_{1}^{e_{1}}p_{2}^{e_{2}}...p_{l}^{e_{l}}$$, it follows that there will only be solutions if $$k <= l$$. For the special case $$d=2$$, i.e. $$l = 1$$, there will only be a single solution (the one you already mentioned in your question).
There's also a question of whether, whenever there is a solution for a fixed $$k$$ and $$d$$, there are infinite solutions as well. For $$k = 2$$, this problem can be reduced to solving the Catalan's Conjecture, which is now known to be true, i.e. there is only a single solution for $$6 \nmid d$$, and only two solutions $$d = 2 \cdot 3$$. For $$k > 3$$, the problem seems to be a special case of Pillai's conjecture for $$C = 1$$, and $$A, B, x, y$$ having all of their divisors intersect with those of $$d$$.