=4in

On One of Erdős' Problems—An
Efficient Search for Benelux Pairs Christian Hercher
Institut für Mathematik
Europa-Universität Flensburg
Auf dem Campus 1c
24943 Flensburg
Germany
christian.hercher@uni-flensburg.de

Abstract:

Erdős asked for positive integers $m<n$ such that $m$ and $n$ have the same set of prime factors, $m+1$ and $n+1$ have the same set of prime factors, and $m+2$ and $n+2$ have the same set of prime factors. No such integers are known. If one relaxes the problem and only considers the first two conditions, an infinite series of solutions is known: $m=2^k-2$, $n=(m+1)^2-1=2^k \cdot m$ for all integers $k\geq 2$. One additional solution is also known: $m=75=3\cdot 5^2$ and $n=1215=3^5 \cdot 5$ with $m+1=76=2^2\cdot 19$ and $n+1=1216=2^6 \cdot 19$. No other solutions with $n<2^{32}\approx 4.3\cdot 10^9$ were known.

In this paper, we discuss an efficient algorithm to search for such integers, also known as Benelux pairs, using sieving and hashing techniques. Using highly parallel algorithms on a modern consumer GPU, we confirmed the previously known results within a minute of computing time. Additionally, we expanded the search space by a factor of more than $2^{16}$ and found no further solutions different from the infinite series given above up to $1.4\cdot 10^{12}>2^{40}$.

For the analogous problem of integers $m<n$ with $m$ and $n+1$ having the same set of prime factors and $m+1$ and $n$ having the same set of prime factors, the situation is very similar: An infinite series and one exceptional solution with $n\leq 2^{22}+2^{12}\approx 4.2\cdot 10^6$ were known. We prove that there are no other exceptional solutions with $n<1.4\cdot 10^{12}$.