research.muzz.in

The only pairs x < y ≤ 10¹⁶ with rad(x) = rad(y) and rad(x+1) = rad(y+1) are the known ones, and none of them extends to x + 2

2026-11-01 · number-theory, computation, erdos-850
Draft.

The question

Write rad(n) for the product of the distinct primes dividing n, so rad(1215) = rad(3⁵·5) = 15. Erdős asked in 1963 whether two different numbers x < y can have rad(x) = rad(y) and rad(x+1) = rad(y+1) other than in the family x = 2^r − 2, y = 2^r(2^r − 2). In a 1996 note, as quoted by Hercher, he wrote that Balasubramanian had reminded him of an old problem of his own that he had forgotten: can the agreement ever continue for three steps, rad(x+i) = rad(y+i) for i = 0, 1, 2? The three-step question is Erdős problem #850. It is open. A yes would contradict a strong explicit form of the abc conjecture.

What was known

What we did

Everything rests on one divisibility. If rad(x) = rad(y) = P and rad(x+1) = rad(y+1) = Q, then P and Q are coprime and both divide y − x, so

rad(y)·rad(y+1) = PQ ≤ y − x < y.

So the larger member y of any two-step pair is a number whose radical and its neighbour's radical multiply to less than y itself. Call such y HP. These are rare: there are 21,025 of them below 10¹⁶. The smaller member is either another HP number with the same pair (P, Q) or the residue y mod PQ, so a list of all HP numbers up to S, sorted by (P, Q), yields every two-step pair with y ≤ S.

The HP numbers can be listed without sieving the whole range. One of y and y + 1, say n, satisfies rad(n)² ≤ n, and those n are generated directly: pick a squarefree P ≤ √S, then all multiples n = P·m with every prime of m dividing P. There are 4,554,409,812 of them with 2 ≤ n ≤ 10¹⁶, about the square root of the range up to logarithmic factors. For each, the neighbour's radical only has to be compared with a bound, which trial division up to the square root of that bound decides without a primality test or a factorisation in almost every case. The census to 10¹⁶ took 8,141 seconds of wall time on 8 low-priority threads.

For three steps, every prime of rad(y(y+1)(y+2)) divides y − x, so rad(y(y+1)(y+2)) < y. One of y, y + 1, y + 2 then has rad(n)³ ≤ 2n. The factor 2 appears because rad(y) and rad(y+2) share the prime 2 when y is even. We enumerate those n the same way; there are about the cube root of the range of them, which puts 10¹⁹ within reach. Before checking the second candidate member, both remaining members are tested against the square root of the budget, since one of them must fit under it. The first version of this program used rad(y)·rad(y+1)·rad(y+2) < y for every y, which is correct for odd y and too strict for even y. We noticed this during the write-up and corrected it. A second error turned up the same way. The bounded-radical routine stripped square, cube and fifth roots from what was left after trial division, but not seventh or higher powers, so on numbers like 2·3⁷ it could wrongly report "radical too large". The two-step census to 10¹⁶ was run before the fix. Rather than trust it or wait for a rerun, we listed every number up to 10¹⁶ of the only shape on which the old routine could err: s·p^k with p an odd prime below 571, k having a prime factor of at least 7, and s built from primes below p. There are 103,177 of them. 315 of the y they could affect are HP numbers, and all 315 are in the census list, so the census is complete as it stands.

A third program covers the opposite corner: for every x ≤ X it walks through all y ≤ 10³⁸ built from the primes of x and keeps those with y ≡ −1 modulo rad(x+1), using 128-bit arithmetic. It has been run for X = 10⁵, 10⁶ and 10⁷; the last run visited 1.26·10¹² nodes in 3,730 seconds.

The machine was shared: 32 cores, most of them busy with other jobs (load average between 90 and 155), our programs at the lowest priority with at most 8 threads. Wall times are given where nothing better was recorded and overstate the cost.

Validation, with the corrected code: the two-step program agrees exactly with a brute-force sieve that hashes (rad(n), rad(n+1)) for every n up to 2³⁰ (859 HP numbers, 15 pairs). It reproduces A343101 to 10⁹ and Hercher's theorem at 1.4·10¹², where its list of 4,113 HP numbers is identical to that of the pre-fix run. The self-test of the bounded radical now includes numbers s·p^k with k ≥ 7, which the old routine fails. The three-step program, run with its bound loosened by a factor λ so that the candidate lists are not empty, agrees with a numpy sieve for λ up to 1000 at 4·10⁶ and up to 300 at 2²⁶. Every pair reported below, and all 21,025 HP numbers, were factored again with sympy, which shares no code with the C programs.

What we found

Every pair (x, y) with y ≤ 10¹⁶ and equal radicals at x, y and at x + 1, y + 1 is one of the 26 below: (75, 1215) and the family x = 2^r − 2, y = 2^r(2^r − 2) for r = 2, …, 26 (y = 2^{2r} − 2^{r+1} ≤ 10¹⁶ exactly when r ≤ 26). There is no new pair.

search region pairs new
Schott, Ehrenstein (OEIS A343101) y < 2³² 16 –
Hercher (2025) y < 1.4·10¹² 20 –
this census y ≤ 10¹⁶ 26 0
this lattice search x ≤ 10⁷, y ≤ 10³⁸ 23 0

The census enumerated 4,554,409,812 numbers with rad(n)² ≤ n and found 21,025 HP numbers below 10¹⁶; the HP count per dyadic range grows slowly, from 135 in [2³⁰, 2³¹) to 2,286 in [2⁵², 2⁵³). The largest pair is x = 67,108,862 = 2·31·601·1801, y = 4,503,599,493,152,768 = 2²⁷·31·601·1801, with x + 1 = 3·2731·8191 and y + 1 = (x + 1)². The census extends Hercher's bound by a factor of about 7000.

Figure 1. The searched regions in the (x, y) plane, logarithmic in both axes, with the known pairs. The family lies along y ≈ x².

No pair extends to three steps below 10¹⁶: none of the 26 pairs does, and every three-step pair is a two-step pair. The margin is wide. A three-step pair needs its larger member y to be HP and to satisfy rad(y(y+1)(y+2)) < y. For every one of the 21,025 HP numbers below 10¹⁶ we computed rad(y+2) with sympy, and none comes close: log y / log rad(y(y+1)(y+2)) is at most 0.724, attained at y = 48 (rad(48·49·50) = 210), so rad(y(y+1)(y+2)) ≥ y^{1.38} throughout. Figure 2 shows the whole list.

In abc terms a three-step pair gives the triple 1 + y(y+2) = (y+1)² with quality log c / log rad(abc) above 2. The best quality known for any abc triple is 1.62991 (Reyssat), and Martin and Miao (arXiv:1409.2974) report from de Smit's tables exactly 236 triples of quality at least 1.4 with at most 20 digits. On this one family of triples the census reaches c ≈ 10³², twelve digits further.

The corrected three-step search over all y ≤ 10¹⁹ enumerated 582,123,758 numbers n with rad(n)³ ≤ 2n and found no y at all that meets the necessary condition, so there is no three-step pair with y ≤ 10¹⁹. It took 384 seconds on 8 threads. An earlier 10¹⁹ job, started with the first version of the program, which used the too-strict bound for even y and the old bounded radical, was stopped; its output is not used.

Figure 2. For each of the 21,025 HP numbers y ≤ 10¹⁶: log y / log(rad(y)·rad(y+1)) in grey (above 1 by definition) and log y / log rad(y(y+1)(y+2)) in blue, which must exceed 1 for a three-step pair. The best value is 0.724, at y = 48.

How many sporadic pairs should one expect? Every two-step pair is x = y − t·rad(y)rad(y+1) for an HP number y and some t ≥ 1. We treat "x is built from the primes of y" and "x + 1 is built from the primes of y + 1" as independent events with their natural densities and sum over t and over the 21,025 HP numbers, leaving out the y of the family and of (75, 1215). The model does not give those pairs probability 1: their own terms are about 1 in most dyadic bins and between 0.29 and 0.89 in bins 10, 11, 23, 35, 37, 39, 41, 43 and 47.

y HP numbers expected pairs beyond the known ones cumulative
< 2²⁰ 139 7.05 7.05
[2²⁰, 2³⁰) 719 1.44 8.48
[2³⁰, 2⁴⁰) 3,078 0.275 8.76
[2⁴⁰, 2⁵⁰) 10,465 0.0265 8.78
[2⁵⁰, 10¹⁶] 6,624 0.00122 8.78

The model expects 8.78 pairs beyond the known ones, and none exists. To calibrate it, add back its own term for (75, 1215), 0.65: it then expects 9.43 sporadic pairs against the one observed, so it over-predicts about ninefold. 80 % of the 8.78 sits below 2²⁰, where the model assigns probabilities near 1 to near misses among tiny numbers. Its useful content is the decay. Over bins 29–53 the expectation per dyadic bin falls like y^(−0.36); the last bin is only 11 % covered by y ≤ 10¹⁶, and without it the slope is y^(−0.34). Extrapolated beyond 2⁵⁴ ≈ 1.8·10¹⁶, the fit over bins 29–53 gives 6·10⁻⁴, or 6·10⁻⁵ after dividing by the over-prediction factor 9.43; the fit without bin 53 gives 7·10⁻⁴ and 8·10⁻⁵.

An earlier version of this post gave 11.0 against one observed pair, tenfold, 82 %, y^(−0.37) and 5·10⁻⁵. Two things were wrong. The sum leaves out (75, 1215) and so cannot be compared with it directly. And the census program added the term of every HP number y with both y and y + 1 of the form rad(n)² ≤ n twice, once from each neighbour; 2,096 of the 21,025 are of that kind. The HP list and the pairs were deduplicated and are unchanged; only these sums were wrong. The corrected program was rerun to 10¹⁶ and gives the same 26 pairs and the same HP list.

For three steps the analogous count is the expected number of HP y whose third radical also fits, rad(y+2) ≤ g(y − 1)/(rad(y)rad(y+1)) with g = 2 for even y. Taking the probability that a number of size y has radical at most B to be B/y, with B rounded down and B < 2 discarded, the expectation is 0.47 for y ≤ 10¹⁶, of which 3.7·10⁻⁴ lies above 2²⁰. With a generous extra factor (ln y)² it is 8.5 and 0.086. Per dyadic bin it is down to about 10⁻¹¹ (10⁻⁸) at 10¹⁶. This counts candidate y, not pairs. Every three-step pair needs such a y, so under the model it bounds the probability that one exists; the B/y law is itself an estimate.

Figure 3. Left: the model's expected number of two-step pairs outside the known ones, per dyadic bin of y, with the least-squares fit over bins 29–53. Right: the cumulative expectation, with the model's own term for (75, 1215) added back, against that one sporadic pair.

What it means and what it does not mean

What is left

Reproduce it

cd /neptune/erdos-woods
make && make test                                   # self-tests, brute-force comparisons at 2^24 and 4*10^6
./bin/ew2 10000000000000000 8 results/ew2_1e16_dedup   # two-step census, y <= 10^16
./bin/hp_dupcheck results/ew2_1e16_dedup.hp.txt 10000000000000000   # the double count in the old sums
python3 scripts/check_radle_gap.py 10000000000000000 results/ew2_1e16.hp.txt
python3 scripts/verify_pairs.py results/ew2_1e16.txt --hp results/ew2_1e16.hp.txt
python3 scripts/near3.py results/ew2_1e16.hp.txt > results/near3_1e16.txt
./bin/ewlat 10000000 38 8 results/ewlat_1e7      # x <= 10^7, y <= 10^38
python3 scripts/heuristic.py results/ew2_1e16_dedup.txt > results/heuristic2_1e16.txt
python3 scripts/heuristic3.py results/ew2_1e16.hp.txt > results/heuristic3_1e16.txt
python3 scripts/brute3.py 67108864 20 all > b.txt   # diff against: ./bin/ew3 67108864 8 t all 20; grep ^C t.txt
./bin/ew3 10000000000000000000 8 results/ew3_1e19_all all   # three-step, y <= 10^19
mkdir -p figs && python3 scripts/figures.py figs results/ew2_1e16_dedup.txt results/ewlat_1e7.txt \
    results/heuristic2_1e16.txt results/near3_1e16.txt