Question on consecutive integers with similar prime factorizations

Question

Suppose that $n=\prod_{i=1}^{k} p_i^{e_i}$ and $m=\prod_{i=1}^{l} q_i^{f_i}$ are prime factorizations of two positive integers $n$ and $m$, with the primes permuted so that $e_1 \le e_2 \cdots \le e_k$, and $f_1 \le f_2 \le \cdots \le f_l$. Then if $k=l$ and $e_i=f_i$ for all $i$, we say that $n$ and $m$ are factorially equivalent. In other words, two integers are factorially equivalent if their prime signatures are identical. In particular, $d(n)=d(m)$ if the two are factorially equivalent.

There's a question I've had for a long time, which is: Are there infinitely many integers $n$ such that $n$ is factorially equivalent to $n+1$? There are numerous curious pairs of consecutive integers for which this holds: $(2,3)$, $(14,15)$, $(21,22)$, $(33,34)$, $(34,35)$, $(38,39)$, $(44,45)$, as well as $(98,99)$, and many more. As you can see, many of them are almost-primes, but the last two pairs are quite striking. Although there are so many of them, a proof that there are infinitely many such pairs seems elusive. Has anyone made any progress on (or even asked) such a question? Does anyone here have a solution or progress for this?

Edit: As an added bonus, the $k$th such $n$, as a function of $k$, seems almost linear. It would be interesting to express and prove an asymptotic formula for this. Can anyone guess heuristically what the slope of this line is?

What I'll add, though I'd like to keep my question focused on the above, is that there are many other questions you can ask: How many integers $n$ are there such that $n$ is factorially equivalent to $n^2+1$, or $n^4+5n+3$, or $2^n+1$? You can generate an almost unending list of seemingly uncrackable number-theoretic conjectures this way.

Many of these questions seem to relate to other well-known number theoretic conjectures. The Twin Prime Conjecture would imply that there are infinitely many $n$ such that $n$ is factorially equivalent to $n+2$. The truth of my question above would imply that there are infinitely many $n$ such that $d(n)=d(n+1)$, a result which has actually been proven, so my conjecture is a strengthening of it. Furthermore, the proof of the infinitude of Mersenne primes would prove the infinitude of $n$ factorially equivalent to $2^n-1$. But beyond all these connections to well-known conjectures, I think the question about and its generalizations are aesthetically interesting.

Answer 1

I'm coming into this late, but am wondering why no one seems to have mentioned the results of Goldston, Graham, Pintz and Yildirim:

https://arxiv.org/pdf/0803.2636.pdf

In particular, their Theorem 4 answers the OPs first question in the affirmative.

Answer 2

This is actually meant to be a comment, not an answer, but I'm new here and I don't have enough reputation to post a comment yet...sorry!

I just wanted to note that Dickson's conjecture would imply infinitely many consecutive numbers with the same prime signature.

For example, Dickson's conjecture would say that there are infinitely many k such that 4k+1 and 9k+2 are both prime. For each such k, 4(9k+2) and 9(4k+1) would be consecutive numbers with the prime signature (1,2). One might expect there to be roughly $\frac{3N}{\log 4N \log 9N}$ values of k between 1 and N such that 4k+1 and 9k+2 are both prime.

---

This additional comment is directed toward Davidac897's comment about having more than one prime factor with exponent greater than 1, which TonyK already pointed out that Tom Sirgedas' program has already found examples of.

Dickson's conjecture also would imply infinitely many such examples where more than one prime has exponent greater than 1.

For example, say we want prime signature (1,2,2). Let $a = 2^27^2$ and $b = 3^25^2$. We seek solutions in primes $p$ and $q$ to $ap + 1 = bq$. If $p = bk + 194$, then $q = ak + 169$. Dickson's conjecture would say there are infinitely many $k$ such that $bk+194$ and $ak + 169$ are both prime. (The first consecutive pair using this method is $2463524 = 2^27^212569$ and $2463525 = 3^25^210949$.)

In a similar vein, you can use Dickson's conjecture to force any prime signature you wish provided that at least one of the exponents is 1.

Answer 3

It turns out that there are consecutive integers $7^3y^2$ and $2^3x^2$ where

x=1280501243627863240958544690009528057630666112209166210134539296491713575228511562822601

y=195559058652792360721040748497175750756141280467009959592151199119238991562483618043657

are each a product of 9 primes according to https://www.alpertron.com.ar/ECM.HTM , I could check the purported factors in MAPLE but haven't)

The method in brief: Find a prime p with $p^3-1$ or $p^3+1$ of the form $qz^2$ (with q a prime) then the Pell equation $p^3u^2-qv^2=\pm 1$ has solutions and the values of $v \mod q$ are periodic. If $v$ is ever a multiple of $q$ then there is a sequence of solutions to $p^3x^2-q^3y^2=\pm1$ If $x,y$ ever have the same signature, there's the example (as long as y is prime to q and x to p) .

For the example above: There are solutions to $7b^2+1=8a^2$ the first two are $a_0=1,b_0=1$ and $a_1=31,b_1=29$ with,as easy to find,

$b_n=16a_{n-1}+15b_{n-1}$ and $a_n=14a_{n-1}+15b_{n-1}$.

When $n \equiv 3 \mod 7$ then $b_n \equiv 0 \mod 7$

After misses at n=3,7,10,17,31,38,45,52 (and ignoring $n=24 \mod 49$ where $b_n$ divides by 49) success at n=59.

$27a^2-2b^2=1$ is never $27x^2-8y^2=1$ since b is odd but $7\cdot a^2-3^3 \cdot b^2=1$ is $7^3x^2-3^3y^2=1$ every 7th time.

Answer 4

This question is directly related to when $d(n)=d(n+1)$ where $d(n)$ denotes the divisor function.

Solutions to $d(n)=d(n+1)$:

In 1952, Erdos and Mirsky conjectured that $d(n)=d(n+1)$ has infinitely many solutions. In 1984, Heath Brown proved this result, and gave a lower bound on the counting function. Let $\widetilde{D}(x)$ denote the number of $n\leq x$ satisfying $d(n)=d(n+1)$. Heath Brown showed that $$\widetilde{D}(x)\gg \frac{x}{(\log x)^7}.$$

In 1987 Erdős, Pomerance and Sárközy gave the upper bound $$\widetilde{D}(x)\ll \frac{x}{(\log \log x)^\frac{1}{2}}.$$

Later that year, Hildebrand improved Heath Browns Result that $$\widetilde{D}(x)\gg \frac{x}{(\log \log x)^3},$$ showing that the correct magnitude involves a doubly logarithmic factor.

Consecutive integers with identical prime signature:

Let $\widetilde{\mathcal{P}}(x)$ denote the number of integers $n\leq x$ such that $n$ and $n+1$ have the same prime signature. Then $\widetilde{\mathcal{P}}(x)\leq \widetilde{D}(x)$, and so Erdős, Pomerance and Sárközy result immediately implies that $$\widetilde{\mathcal{P}}(x)\ll \frac{x}{(\log \log x)^\frac{1}{2}}.$$ This means that the counting function is not linear even though the graph resembles a straight line. ($\log \log x$ grows extremely slowly, and is nearly unnoticeable)

Since $d(n)=d(n+1)$ "often" implies that $n$ and $n+1$ have the same signature, it seems likely that one could use Hildebrands lower bound to prove that the set of consecutive integers with identical prime signature is infinite. Bounding the number of times we have $d(n)= d(n+1)$, yet difference signatures, seems like a fruitful approach.

Some References: (Chronological Ordering)

• Erdös, Mirsky 1952: The distribution of the values of $d(n)$.

• Heath-Brown 1984: The divisor function at consecutive integers.

• Erdős, Pomerance and Sárközy 1987: On locally repeated values of certain arithmetic functions. III.

• Hildebrand 1987: The divisor function at consecutive integers.

Answer 5

Sorry, I can't post comments yet (maybe never:))!

I wrote a program to find such numbers in the intervals [2,4000), [10⁶,10⁶+4000), [10⁹,10⁹+4000), [10¹²,10¹²+4000), and [10¹⁵,10¹⁵+4000)

Here are the numbers and signatures: https://pastebin.com/piMZNQKx

Answer 6

Very rough heuristic of the $k$th such $n$ (prime signature twin) as a function of $k$:

1st assumption: The dominant effect is given by primes of the signature $(1,1)$, i.e. by semiprimes.

2nd assumption: The number of semiprimes below $n$ is given by $\pi_2(n) \sim \frac{n}{\ln n} \ln \ln n$, cf. https://en.wikipedia.org/wiki/Almost_prime

Then the probability density of the semiprimes is approximately given by $f_2(n) \sim \frac{\ln \ln n}{\ln n}$.

3rd assumption: The semiprimes are independently distributed.

Then the number of semiprime twins below $N$ is given by $\int^{N} f_2(x)^2 dx$.

Thus the number of prime signature twins is roughly given by $(\frac{\ln \ln n}{\ln n})^2$ (a better value or an asymptotic formula can be obtained by evaluating the integral.)

Thus the $k$th prime signature twin is roughly given byh $n = k \cdot (\frac{\ln k}{\ln \ln k})^2$. For $k = 200$ (as in the figure cited by the OP) this gives approximately a slope of 8,8, the same order of magnitude as in the figure.

Of course this very rough calculation can be improved in various ways.

Answer 7

This is how Heath-Brown resolved the d(n)=d(n+1) problem ! The idea is due to Claudia Spiro who used it for d(n)=d(n+5040) but was unable to reduce the 5040. The same idea has now been used in many places.