Pith. sign in

REVIEW 3 major objections 3 minor 5 references

On one of Erd\H{o}s' Problems -- An Efficient Search for Benelux Pairs

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A GPU search settles Erdős' prime-factor pair problem below 1.4 trillion.

desk verdict Sound algorithmic ideas and an honest negative result, but Theorem 1 rests on an unreleased GPU implementation that cannot be checked from the manuscript. read the letter →

arxiv 2506.01099 v1 pith:PYQPARCG submitted 2025-06-01 math.NT

Christian Hercher This is my paper
classification math.NT MSC 11-0411Y55
keywords BeneluxpairErdősproblemsameprimefactorsradicalsievinghashtableGPUcomputationalnumbertheory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper addresses an Erdős question: can two distinct integers $m < n$ have the same set of prime factors as each other and, simultaneously, the same for $m+1$ and $n+1$? (The variant with three consecutive shifts remains open.) It establishes a complete classification of all such 'Benelux pairs' up to $n < 1.4 \cdot 10^{12}$: the only examples are the exceptional pair $m=75, n=1215$ and the infinite family $m = 2^k - 2$, $n = 2^{2k} - 2^{k+1}$ for $2 \le k \le 20$. The analogous cross-matched 'second kind' pairs are likewise classified up to the same bound, with the exception $(35, 4374)$ and the family $m = 2^k + 1$, $n = 2^{2k} + 2^{k+1}$ for $0 \le k \le 20$. The work matters because it pushes a concrete open problem from $n < 2^{32}$ to $n > 2^{40}$ by replacing factorization with a radical-based sieve and a memory-bounded hash-search algorithm that runs on a GPU.

What carries the argument

The key object is the radical $\mathrm{rad}(n)$, the product of the distinct prime divisors of $n$, which two integers share exactly when their prime-factor sets are equal. The algorithm computes $\mathrm{rad}(n)$ for every $n$ in a chunk by sieving out prime powers $p^e$ (Algorithm 1), forms the set $S_n = \{\mathrm{rad}(n), \mathrm{rad}(n+1)\}$, and then detects Benelux pairs by equality of $S_n$ with $S_m$. A first complete pass sorts all such sets to find collisions in $O(S \log S)$ time with $O(S)$ memory; the production version (Algorithm 3) chunks the range, stores hash values of $S_n$ in a hash table with open addressing, and re-sieves earlier chunks, cutting memory to $O(s)$ at a cost of $O(S^2/s)$ time.

What would settle it

A concrete way to test the claim is to run an independent, transparent implementation of the same exhaustive search over a smaller but non-trivial range (say, all $n$ up to $2^{32}$ or $2^{36}$) and compare the output with the paper's list; any Benelux pair not listed—or, conversely, any listed pair that fails the radical-equality check—would refute Theorem 1. On the larger range, checking a random sample of chunks against a reference radical computation would expose a sieving or hashing bug if one exists.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central assertion is Theorem 1: for all positive integers $m < n < 1.4 \cdot 10^{12}$, the Benelux pairs of the first kind are exactly the single pair $(75, 1215)$ together with the family $m = 2^k - 2$, $n = 2^{2k} - 2^{k+1}$ for integer $2 \le k \le 20$; and the Benelux pairs of the second kind are exactly $(35, 4374)$ plus $m = 2^k + 1$, $n = 2^{2k} + 2^{k+1}$ for $0 \le k \le 20$. This is not a heuristic: the classification is presented as a theorem proved by exhaustive computation over the whole interval, every entry of which is tested for equality of the two radical sets.

Load-bearing premise

The theorem rests on the assumption that the GPU implementation of the sieving and hashing steps is correct and exhaustive—no missed collisions from a software bug or hardware fault, and no skipped multiples in the sieving.

Editorial extensions

If this is right

  • The original three-consecutive-numbers problem has no solutions with $n < 1.4 \cdot 10^{12}$, since every listed Benelux pair fails the third condition.
  • Any undiscovered Benelux pair must have $n \ge 1.4 \cdot 10^{12}$ or be a member of the infinite families with $k$ outside the tested range; the next family member ($k=21$) already lies above the bound.
  • The second-kind variant is also fully classified below the bound, so its next possible exceptional pair is beyond $1.4 \cdot 10^{12}$.
  • The chunked-hashing algorithm offers a general recipe for exhaustive collision searches over very large intervals with bounded memory on parallel hardware.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The bound is just past $2^{40}$, and the largest tested family member has $k=20$; extending the search much further with the same $O(S^2/s)$ algorithm would be impractical on a single GPU, suggesting that a structural proof, not more computing, is the plausible next step.
  • Because no code, data, or independent verification accompanies the paper, the exhaustiveness claim rests on the trustworthiness of one GPU run; a reproducible artifact or an independent reimplementation would turn the computational 'if' into a checkable fact.
  • The collision-search technique (radicals plus hashing) transfers to other problems in which two neighboring numbers must share divisor structure, e.g., searching for consecutive integers with equal radical sets or other rad-equality patterns.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies a problem of Erdős: finding pairs of positive integers m < n such that m and n, and m+1 and n+1, have the same set of prime divisors (Benelux pairs), together with a crossed variant (Benelux pairs of the second kind). It presents two algorithms: Algorithm 2, which sieves radicals and sorts the two-element sets {rad(n), rad(n+1)} in O(S log S) time and O(S) memory, and Algorithm 3, a chunked hashing variant using O(s) memory and O(S^2/s) time that is amenable to GPU parallelization. The manuscript reports that a CUDA implementation reproduces all previously known pairs and finds no additional pairs for n < 1.4 × 10^12, leading to Theorem 1, which asserts an exhaustive classification of both kinds of pairs below that bound.

Significance. If Theorem 1 is correct, the paper extends the known exhaustive range by more than a factor of 2^16 and contributes a useful algorithmic template: sieving radicals, forming two-element radical sets, and using a commutative hash with exact set-equality checks on collisions. The high-level design is sound, and the reproduction of the known infinite families and exceptional pairs is a meaningful integration test. The significance is currently conditional, however, because the only-if direction rests entirely on an unreleased GPU implementation; the manuscript provides no source code, raw output, or independent replica, so the exhaustiveness claim cannot be checked from the text alone.

major comments (3)
  1. [§3, Theorem 1] The only-if direction of Theorem 1 is an exhaustive-computation claim, but the supporting evidence is an unquoted GPU implementation. A single missed pair below 1.4 × 10^12 would falsify the theorem, yet the manuscript gives no source code, no raw output, and no independent verification. The authors should supply the implementation, or at minimum a sufficiently precise kernel specification together with logs and checksums, and preferably an independent re-implementation. Without this, the central claim cannot be independently verified from the manuscript.
  2. [§2.2, Algorithm 3, Steps 8–14 and 26–31] The open-addressing collision handling is not fully specified. During insertion, the pseudocode tests only the data found at the first collision and then proceeds to an unoccupied slot; it does not state that every occupied slot in the probe sequence is checked for equal hash values before inserting. With a load factor of 1/4, an entry with the same hash value can lie beyond slots occupied by different hash values, so under a literal reading a same-chunk Benelux pair could be missed. The correctness paragraph claims every same-chunk pair is identified in Step 9, but that requires an explicit loop over the probe sequence. Similarly, Step 31 should be part of a search loop that continues until an empty slot is found and checks all entries with matching hash values, rather than a single instruction after a successful search. The pseudocode should be rewritten to make this probe-and-test loop explicit.
  3. [§3.1] The hash function is described only as 'commutative' and as mapping a pair of 64-bit integers to a 29-bit address, and the open-addressing probe sequence and thread-locking mechanism for simultaneous insertions are omitted. These details are load-bearing for the exhaustiveness claim: a bug in the probe sequence or in atomic insertion can silently skip a hash-table slot and hence miss a pair. The manuscript should specify the exact hash function, the probing strategy, and the locking protocol, or provide the code itself.
minor comments (3)
  1. [§2.1] The complexity analysis of Algorithm 1 contains a mathematical error: the identity ∫_2^{√S} dx/log x = log log √S − log log 2 is false, since the antiderivative of 1/log x is the logarithmic integral, not log log x. The sum ∑_{p≤√S} 1/log p is of order √S/log S, so the stated O(log S log log S) overhead is an underestimate. This does not alter the main numerical conclusions because √S is far smaller than the chosen chunk size, but the asymptotic statements should be corrected.
  2. [§3.1] The sentence saying that the initial hash addresses of two different sets are equal in 1/4 of the cases is inconsistent with a 29-bit hash into a 2^29-slot table; the probability of equal initial addresses for uniformly random hash values is 2^{-29}. The number 1/4 appears to refer to the load factor, and the phrasing should be corrected.
  3. [Throughout] There are several typographical errors: 'inside' for 'insight' (§2.1), 'requiered' for 'required' (§2.1), 'date' for 'data' (Algorithm 3), and 'Belenux' for 'Benelux' in the Table 2 caption. These should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the search is a from-first-principles exhaustive computation, independently benchmarked against known Benelux pairs and OEIS sequences.

full rationale

Walk of the derivation chain: the target object is the set S_n = {rad(n), rad(n+1)}, and a Benelux pair (m, n) is, by the paper's own definition (Algorithm 2, lines 13-18), exactly a collision S_m = S_n. Algorithm 1 is proven to output the radical of every integer in the interval because each prime power p^e dividing n is processed exactly e-1 times, so the output is rad(n) = product of primes dividing n; no fitted parameter enters. Algorithm 3 keeps the same correctness property: every non-equal set that hashes to one address is rechecked by exact comparison ('Test whether (m, n) is a Benelux pair of 1st or 2nd kind and print it'), and all m in earlier chunks are re-scanned, so the hash function is only a performance device and cannot inject or suppress a result. The findings are validated against external, independently compiled data: Makowski's exceptional pair m = 75, n = 1215 (cited via Guy's book), the infinite families m = 2^k - 2, n = 2^(2k) - 2^(k+1) and m = 2^k + 1, n = 2^(2k) + 2^(k+1), the OEIS sequences A343101 and A088966, and prior exhaustive searches to 2^30, 2^32, and 2^22 + 2^12 by Schott, Ehrenstein, Nomoto, and Wasserman. The run confirms those known values and then reports no new ones up to 1.4*10^12; this is a benchmark against independent facts, not an input fitted to the target. No result from the author's own prior work is imported and no parameter is fitted to the data, so the central claim has independent content. The only gap is that the GPU implementation of the exhaustive search is not released, so the 'only if' direction above 2^32 cannot be rechecked from the manuscript; that is an empirical verifiability limitation of the computation, not circularity. Score 0, steps empty.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new mathematical entities. The free parameters are implementation constants, and the axioms are standard algorithmic assumptions plus the unverified correctness of the GPU code.

free parameters (2)
  • Chunk size s = 2^27
    Chosen by the author to fit available GPU memory; affects runtime and memory usage but does not affect the mathematical theorem.
  • Hash table size = 2^29 = 4s
    Defined as four times the chunk size; a performance choice for the open-addressing scheme.
assumptions (4)
  • standard math Fundamental theorem of arithmetic and the correctness of the sieving procedure for computing radicals.
    Algorithm 1 assumes that dividing by all prime powers with multiplicity greater than one yields the unique radical; this is standard number theory.
  • domain assumption The hash function is deterministic and equal sets {rad(n), rad(n+1)} always produce the same hash value.
    Algorithm 3 requires this to avoid false negatives; the paper only describes a 'commutative hash function' and does not specify or prove its properties.
  • standard math Open addressing with linear probing: probing until an empty slot is sufficient to conclude that a key is absent.
    This is a standard property of hash tables without deletions and is used in Algorithm 3, steps 26-31.
  • ad hoc to paper The GPU implementation executes the described algorithms without computational errors.
    The central theorem depends on the exhaustive computation; no code or independent verification is provided to support this assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On one of Erd\H{o}s' Problems -- An Efficient Search for Benelux Pairs." pith.science (2026). https://pith.science/paper/PYQPARCG

@misc{pith2026250601099,
  author       = {Pith},
  title        = {Pith review of: On one of Erd\Hos' Problems -- An Efficient Search for Benelux Pairs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PYQPARCG}},
  note         = {Machine review of arXiv:2506.01099}
}
abstract

Erd\H{o}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 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}$ 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}$.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

  1. [1]

    Bloom, https://www.erdosproblems.com/go_to/850 (2025)

    T. Bloom, https://www.erdosproblems.com/go_to/850 (2025)

    work page 2025

  2. [2]

    Erd˝ os,Some problems , Analytic Number Theory—Proceedings of a Conference in Honor of Heini Halberstam, B

    P. Erd˝ os,Some problems , Analytic Number Theory—Proceedings of a Conference in Honor of Heini Halberstam, B. C. Berndt, H. G. Diamond, A. J. Hildebrand (Ed.), 1 (1996), 333–335

    work page 1996

  3. [3]

    R. K. Guy, Unsolved Problems in Number Theory , 3rd edition, Springer, 2004

    work page 2004

  4. [4]

    Third Benelux Mathematical Olympiad, Problem 1, http://www.bxmo.org/problems/ bxmo-problems-2011-zz.pdf (2011)

    work page 2011

  5. [5]

    (2025), Entry A343101 in The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A343101

    OEIS Foundation Inc. (2025), Entry A343101 in The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A343101. 2020 Mathematics Subject Classification : Primary 11-04; Secondary 11Y55. Keywords: Erd˝ os problem, Benelux pair, integers with same prime factors. (Concerned with sequences A343101 and A088966 of the On-Line Encyclopedia of Integer Sequ...

    work page 2025

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.