# Question on consecutive integers with similar prime factorizations

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.

-
I can't answer your question, but note that your sequence is Sloane's A052213. [1] oeis.org/classic/A052213 –  Charles Jul 18 '10 at 22:24
You have a triple, (33, 34, 35). It seems you could cut down considerably on frequency by considering triples or quadruples. Is it known there are infinitely many triples with $$d(n) = d(n+1) = d(n+2)$$ or that there are not infinitely many? –  Will Jagy Jul 19 '10 at 0:29
Can you conclude much from small numbers? The product of the first four primes is 210. Below that you have only a handful of signatures, and some adjacencies are to be expected. –  Charles Matthews Jul 19 '10 at 7:30
Yes, parity seems to give something here. The other effect worth thinking through is the number of signatures, given that the possible signatures for integers of size N is apparently the partition function summed up to log N. We certainly know the average order of the partition function. So (this currently looks a bit crude, since small primes are not dealt with) what do we expect from random adjacencies of the same partition? –  Charles Matthews Jul 19 '10 at 10:04

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

http://arxiv.org/pdf/0803.2636.pdf

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

-

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)

-

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 http://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.

-

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.

-

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

I wrote a program to find such numbers in the intervals [2,4000), [106,106+4000), [109,109+4000), [1012,1012+4000), and [1015,1015+4000)

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

-
Very interesting - notice that for smaller values, there are fewer prime signatures with lots of prime factors, but many of them start showing up as you go higher. When you get high enough, semiprimes seem to be almost non-existent. I also haven't seen a single instance in which more than one prime factor has an exponent greater than $1$. In what language did you write this? Could you possibly provide source code? –  David Corwin Jul 21 '10 at 9:22
@Davidac897 ("I also haven't seen a single instance in which more than one prime factor has an exponent greater than 1"): just searching for the string "2," in Tom's list turns up two such instances: 1000001456 {1,1,2,4} and 1000000000475 {1,2,2}. –  TonyK Jul 21 '10 at 10:38
@Davidac897: C++, simple source code is here: pastebin.com/UkJkspJN –  Tom Sirgedas Jul 22 '10 at 2:00
Every prime signature in the list has a 1 in it. Is that true in general? That is, if two consecutive integers have the same prime signature, must that signature contain a 1? –  Ken Fan Jul 23 '10 at 6:29
According to the most recent answer, the answer is no. –  David Corwin Aug 11 '10 at 23:06

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. http://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 rougly 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.

-
Why should semiprimes be dominant? –  Michael Lugo Jul 21 '10 at 3:32