On one of Erdős’ Problems—An Efficient Search for Benelux Pairs

2025

Read On one of Erdős’ Problems—An Efficient Search for Benelux Pairs (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01099.txt.

Introduction

Christian Hercher takes on a number puzzle posed by Erdős, in a 2025 mathematics paper on so-called Benelux pairs. The puzzle asks for two whole numbers where each pair of neighbors, the numbers themselves, the numbers plus one, and the numbers plus two, share exactly the same set of prime factors. No such pair is known for the full version. Dropping the third condition leaves a relaxed version with one endless family of solutions and one lone extra case.

Hercher describes a fast search method built on sieving and hashing, run in parallel on a home graphics card. The known results were confirmed within a minute. The search then pushed past earlier limits by a factor of more than sixty-five thousand, reaching beyond a trillion, and found nothing new. For a cousin problem with the conditions crossed, the paper proves no extra solutions hide below the same bound.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-01099

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On one of Erdős’ Problems—An Efficient Search for Benelux Pairs Abstract Erdős asked for positive integers m < n m<n , such that m m and n n have the same set of prime factors, m + 1 m+1 and n + 1 n+1 have the same set of prime factors, and m + 2 m+2 and n + 2 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 m=2^{k}-2 , n = ( m + 1 ) 2 − 1 = 2 k ⋅ m n=(m+1)^{2}-1=2^{k}\cdot m for all integers k ≥ 2 k\geq 2 . One additional solution is also known: m = 75 = 3 ⋅ 5 2 m=75=3\cdot 5^{2} and n = 1215 = 3 5 ⋅ 5 n=1215=3^{5}\cdot 5 with m + 1 = 76 = 2 2 ⋅ 19 m+1=76=2^{2}\cdot 19 and n + 1 = 1216 = 2 6 ⋅ 19 n+1=1216=2^{6}\cdot 19 . No other solutions with n < 2 32 ≈ 4.3 ⋅ 10 9 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 functioning algorithms on a modern consumer GPU, we could confirm the hitherto known results within a minute of computing time. Additionally, we have expanded the search space by a factor of more than 2 16 2^{16} and found no further solutions different from the infinite series given above up to 1.4 ⋅ 10 12 > 2 40 1.4\cdot 10^{12}>2^{40} . For the analogous problem of integers m < n m<n with m m and n + 1 n+1 having the same set of prime factors and m + 1 m+1 and n n having the same set of prime factors, the situation is very similar: An infinite series and one exceptional solution with n ≤ 2 22 + 2 12 ≈ 4.2 ⋅ 10 6 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 ⋅ 10 12 n<1.4\cdot 10^{12} . Christian Hercher Institut für Mathematik Europa-Universität Flensburg Auf dem Campus 1c 24943 Flensburg Germany [email protected] 1 Introduction In [ 2 ] , Erdős wrote: Balsubramanian called to my attention another old problem of mine which I had forgotten. Can there ever be two distinct integers m and n for which for 0\leq i\leq 2 the integers m+i and n+i have the same prime factors? The answer is Yes for a more restricted problem. For m,n and m+1,n+1 we can take m=2(2^{k}-1),n+1=(m+1)^{2} . Then m and n also have the same prime factors. Are there other integers m,n and m+1,n+1 with the same prime factors? Note: variable names have been changed in this quote for improved readability. Clearly, for all k\geq 1 , • the terms m=2\cdot(2^{k}-1) and n=(m+1)^{2}-1 are positive integers with m<n , • m and n=(m+1)^{2}-1=m(m+2)=2\cdot(2^{k}-1)\cdot 2^{k+1} have the same prime factors, • and m+1 and n+1=(m+1)^{2} have the same prime factors, too. Thus, all these pairs are solutions to the restricted problem. (But, since m+2=2^{k+1} is a power of two and n+2=(2^{k}-1)\cdot 2^{k+2}+2\equiv 2\pmod{4} is not, none of these pairs is a solution to the original problem.) Section B19 of [ 3 ] lists the restricted problem, too. Here, the information is provided that Ma̧kowski found the exceptional solution m=3\cdot 5^{2} , n=3^{5}\cdot 5 with m+1=2^{2}\cdot 19 and n+1=2^{6}\cdot 19 . (But n+2=7\cdot 11 and m+2=1217 is a prime.) No other exceptional solution is known. In 2011, the mathematical competition Benelux Olympiad coined in their Problem 1 the term Benelux pair for positive integers m<n when m and n , as well as m+1 and n+1 share the same prime factors. The original problem from Erdős cited above is listed as Number #850 on Bloom’s list [ 1 ] of Erdős’ problems. A variant of this problem is mentioned in Section B19 of [ 3 ] . This variant asks for two positive integers m<n such that now m and n+1 should share the same prime factors and m+1 and n do as well. The situation for this variant is nearly the same as with Benelux pairs. An infinite series of solutions is given by m=2^{k}+1 , n=m^{2}-1 . With this setting m and n+1=m^{2} have the same prime factors, and m+1=2^{k}+2=2\cdot(2^{k-1}+1) and n=(m-1)(m+1)=2^{k}\cdot 2\cdot(2^{k-1}+1) have the same prime factors. There is also one known exceptional solution. According to Guy [ 3 ] , if m=5\cdot 7 , n+1=5^{4}\cdot 7 , then n=2\cdot 3^{7} , m+1=2^{2}\cdot 3^{2} . In an analogous way, this paper uses the term Benelux pair of second kind for positive integers m<n with m and n+1 having the same prime factors, and m+1 and n having the same prime factors. 1.1 Computational verification and contributions from Schott, Ehrenstein, Nomoto, and Wasserman According to the Online Encyclopedia of Integer Sequences [ 5 ] , Schott computed all Benelux pairs (m,n) with n up to 2^{30} . Ehrenstein has expanded the list up to n<2^{32} . For the variant of the problem, Nomoto and Wasserman computed all Benelux pairs of second kind in the OEIS sequence A088966 up to n\leq 2^{22}+2^{12} . 1.2 Contribution of this work In this paper, we present an algorithm which computes all Benelux pairs and all Benelux pairs of second kind up to m<n<S with a time complexity of \mathcal{O}\left(S\log S\right) and a space complexity of \mathcal{O}\left(S\right) . Since the desktop PC used for the computation had a limited amount of RAM, this algorithm is impractical for larger values of S . Therefore, we provide a second algorithm, which only uses a separately changeable amount of space of \mathcal{O}\left(s\right) . But in a time-space-trade-off it needs a time of \mathcal{O}\left(\frac{1}{s}\cdot S^{2}\right) to compute, assuming s\in\Omega(\log S\log\log S) . This second algorithm has the advantage that the parts that need the most computations can be highly parallelized. Thus, we used the GPU of the PC in hand to extend the search for such pairs by a large amount. 1.3 Outline In Section 2 , we construct and discuss in detail the two aforementioned algorithms before we conclude in Section 3 with a discussion of further improvements for high parallel computing, and provide the results of our computation. 2 Algorithms 2.1 Finding Benelux pairs quickly Both problems—finding Benelux pairs of first and second kind—consider pairs of positive integers and their respective prime factors (ignoring multiplicities). Thus, a good way to start would be to calculate for every positive integer n\leq S the set of primes which divide n . A first inside in these problems is that we do not have to know which primes exactly divide n , but whether two such sets are identical or not. Hence, we do not need to compute the whole prime factorization of n if we only compute a number r(n) with the property that r(n)=r(m) , if and only if n and m have the same prime factors. Such a function r is the radical of n : rad(n):=\prod_{p\mid n}p

Read the complete text