Computational research note · Graham's $1000 problem (Erdős–Graham–Ruzsa–Straus, 1975)
Pick a whole number n and form "2n choose n": the number of ways to split 2n labelled items into two equal groups. It grows astronomically fast. Now ask something much smaller: is that huge number divisible by 3? By 5? By 7?
For almost every n, yes to at least one of those three. But every so often, C(2n,n) slips past all three at once, coprime to 3, 5 and 7 simultaneously. Ronald Graham noticed this and, together with Paul Erdős, Imre Ruzsa and Ernst Straus, asked in 1975 whether it happens infinitely often. Graham has offered $1000 for a proof either way. Nobody has claimed it: the question is still open, listed as problem #376 on erdosproblems.com.
No computation can ever settle it. Checking a trillion more values of n can never prove "infinitely many": the next exception, or the last one, might always be one step further out. What a computation can do is push the map of known exceptions outward and see what the terrain looks like. This note pushes that map 216 orders of magnitude past where anyone had taken it before, and the terrain is stranger than the simple guess predicts: long empty stretches, then a flood.
Since November 2015 the complete list of these n was known up to 1070: 1,374 of them, computed by Christopher Thompson and posted to OEIS (extending 62 terms Max Alekseyev had posted in 2008). This session:
The infinite-or-finite question itself is untouched, and cannot be touched by any computation, however large. Everything below is the technical version.
Let G = {n ≥ 0 : gcd(C(2n,n), 105) = 1}, the subject of a $1000 question of Graham (is G infinite?), raised by Erdős, Graham, Ruzsa and Straus in 1975 and listed as erdosproblems.com #376. The published computational frontier was a complete enumeration of G up to 1070 (1,374 terms; C. E. Thompson, OEIS A030979 b-file, Nov 2015). We give a complete, five-way cross-verified enumeration of G below 3600 ≈ 1.87×10286 (585,823,270 terms), extending the complete range by 216 orders of magnitude and the term count ×426,363. Along the way we verify that n = 3160 remains the largest known element of G whose binomial coefficient is also coprime to 11 (Graham conjectured it is the last), now confirmed below 3600, and we compute the counting function G(N) across the full range: the first counts beyond 1070. The counts reveal structure the independence heuristic cannot see: G grows in rare bursts along only 82 of 601 base-3 lengths, separated by certified term-free deserts as long as 26.7 decimal orders of magnitude, while the global exponent stays near the heuristic 0.02595. The infinitude question itself is untouched: it is a question about ideas, not ranges; what this note contributes is the data layer the heuristic arguments rest on.
Are there infinitely many n with gcd(C(2n,n), 105) = 1, where 105 = 3·5·7?
EGRS proved that for any two odd primes p, q there are infinitely many n with gcd(C(2n,n), pq) = 1. Three primes at once is the open case, and 105 = 3·5·7 (the product of the first three odd primes) is Graham's specific instance, still listed as open on erdosproblems.com #376, which states plainly that the problem "cannot be resolved with a finite computation." No computation, including this one, changes that. What a computation can do is described in the rest of this note.
For a prime p and n ≥ 0, p ∤ C(2n,n) if and only if every base-p digit of n is at most (p−1)/2.
Proof. By Kummer's theorem, the exponent of p in C(2n,n) = C(n+n, n) is the number of carries when n is added to n in base p. If every digit di ≤ (p−1)/2, then by induction from the least significant position no carry ever forms: an incoming carry c ∈ {0,1} is 0 by induction, and 2di + 0 ≤ p−1 < p produces none. If some digit has di ≥ (p+1)/2, take the least such i; the incoming carry is c ≥ 0 and 2di + c ≥ p+1 > p−1 forces a carry at position i. So carries exist iff some digit exceeds (p−1)/2. ∎
Hence G = {n : base-3 digits ≤ 1, base-5 digits ≤ 2, base-7 digits ≤ 3}: this is OEIS A030979. The sequence's convention is a(1) = 0 (since C(0,0) = 1 vacuously has gcd 1 with everything); we follow it, and every count below includes n = 0. A related, harder condition (call it the 1155 companion) additionally requires base-11 digits ≤ 5, i.e. gcd(C(2n,n), 1155) = 1 for 1155 = 3·5·7·11; Graham remarked that n = 3160 is likely the last n with this stronger property (Section 3, C2).
Write L for the search height: we enumerate G ∩ [0, 3L). The base-3 condition says n is a sum of distinct powers 3k, k < L. The search fixes the base-3 digits from the most significant end. After d digits are fixed with prefix value A, every completion satisfies
Fix a base b ∈ {5,7} with digit cap c and let W = (3L−d+1)/2, e = min{e : be ≥ W}. For every n in the interval (1), ⌊n/be⌋ ∈ {Q, Q+1} where Q = ⌊A/be⌋, and the base-b digits of n at positions ≥ e are exactly the digits of ⌊n/be⌋. Consequently, if both Q and Q+1 have some base-b digit > c, no completion of the prefix lies in G, and the subtree may be discarded.
Proof. From (1), 0 ≤ n − A ≤ W − 1 < be, so ⌊n/be⌋ can exceed ⌊A/be⌋ by at most one. Writing n = ⌊n/be⌋·be + (n mod be), the base-b expansion of n at positions ≥ e is the expansion of ⌊n/be⌋. A member of G has all base-b digits ≤ c, in particular those at positions ≥ e. ∎
The engines prune exactly when Lemma 2 permits, for b = 5 and b = 7. (A refinement, only considering Q+1 when the interval actually straddles a multiple of be, was measured to prune ~20% more nodes and deliberately omitted: it complicates the constant-time incremental test below and does not change the output, and the omission is exactly what lets the C and Python engines implement identical logic and agree node-for-node.) At a leaf (d = L) the value n = A is fully determined and is tested digit-by-digit in bases 5 and 7 (base 3 holds by construction), and its base-11 digits give the 1155 flag. Soundness of the census is Lemma 2 plus the exhaustiveness of the binary tree over base-3 digit choices; no probabilistic or floating-point step exists anywhere in the search.
Why this is fast. The number of surviving prefixes at depth d grows like the count function itself, ~N0.026 at scale N = 3d, so the tree visited is within a constant factor of the output size. Measured directly from the committed node and term counts (Section 3's table), the ratio is 100.1 nodes per term at L = 148 and stabilizes to 126.1–126.4 nodes per term from L = 300 onward. It is not perfectly constant, but close, and the published frontier at 1070 costs 0.7 s in the Python reference implementation.
The C production engine carries the prefix as little-endian digit arrays in bases 5, 7 and 11 simultaneously: choosing or unchoosing the power 3k adds or subtracts a precomputed digit array of 3k with exact carry/borrow propagation, no bignum library and no division in the hot path. For b ∈ {5,7} it maintains nbadb = the count of over-cap digits at positions ≥ the moving threshold eb(d); Q is invalid iff nbadb > 0, and given that, Q+1 is invalid iff the digit just above the increment run is ≥ c or nbadb exceeds the run length, an O(carry run), amortized O(1), prune test. Thresholds eb(d) are precomputed exactly by comparing 3m with 2·be through the stored digit arrays.
A methodological note the checks are built to catch: the search must confirm the actual extent of prior knowledge before sizing an attack. Early in this session, a bottom-up engine was built on the assumption that the OEIS display line (23 terms, ending near 2.5×1016) was the frontier; it worked correctly, but a literature check then surfaced the actual b-file extent (complete to 1070, 1,374 terms), making the campaign in flight a replication of the bottom 10−49 of the already-known range. The wasted wall-clock time was about two hours; the bottom-up engine was kept as one leg of the cross-verification web below rather than discarded (Section 4).
Labels follow the repository convention (PROVED / CERTIFIED / NUMERICAL), and every number below is emitted by a committed, rerunnable script.
G ∩ [0, 3600) has exactly 585,823,270 elements (3600 ≈ 1.87×10286). The ladder is cumulative and nests: each run reproduces every smaller run's list exactly, checked by fingerprint (term count, sum mod 264, XOR mod 264, sum mod 109+7).
| L | 3L ≈ | terms G(3L) | nodes | nodes / term | engine |
|---|---|---|---|---|---|
| 148 | 4.1×1070 | 1,374 | 137,551 | 100.1 | C + Python, identical |
| 200 | 2.7×1095 | 10,215 | 1,221,201 | 119.6 | C + Python, identical |
| 250 | 1.9×10119 | 95,861 | 11,963,213 | 124.8 | C + Python, identical |
| 300 | 1.4×10143 | 288,836 | 36,430,897 | 126.1 | C full ≡ C 4-worker ≡ Python |
| 350 | 1.9×10167 | 674,540 | 85,263,581 | 126.4 | C full |
| 400 | 7.1×10190 | 4,190,720 | 529,206,039 | 126.3 | C full |
| 500 | 3.6×10238 | 29,814,852 | 3,760,885,157 | 126.1 | C full |
| 600 | 1.9×10286 | 585,823,270 | 73,906,945,791 | 126.2 | C, composite task mode (3,753 + 4,906 tasks, 10.7 core-h) |
The complete term list is committed in full to 3200 (data/terms_3e200_full.txt, verified 10,215 lines) and to 3250 gzipped (data/terms_3e250_full.txt.gz, verified 95,861 terms on decompression). Beyond that the repository commits the first 2,000 terms, every 100,000th term, all 1155-flagged terms, the largest term, per-length histograms and fingerprints for each rung. The full list itself is not committed past 3250 (Section 6). The largest element of G below 3600 is a 286-digit number, base-3 length 600, in data/max600.txt; independently re-counted digit-by-digit for this page, it has exactly 286 decimal digits and its base-3, base-5 and base-7 digits all satisfy the caps of Lemma 1. The previous largest published term (≤ 1070) has 66 digits.
The only n < 3600 with gcd(C(2n,n), 1155) = 1 are n = 0, 1, 3160. Graham's prediction that 3160 is the last such n survives a complete search 216 orders of magnitude beyond the previously published complete range. (The strongest prior statement we could source is the complete-to-1070 census plus a base-11 filter; see Section 6 on an unconfirmed, larger claimed search bound.)
NUMERICAL companion (C6). Conditional on the independence heuristic, the expected number of further 1155-terms beyond 3160 is ≈ 0.81, with 0.72 of that contributed by the seven terms below n = 60,000 and the contribution of every term above 1016 below 10−4. So the probability of the observed "none" is ≈ e−0.81 ≈ 0.44: not small, not certain. The heuristic already made "no further terms" the likely outcome at small n; what C2 adds is that the census now makes it a certified fact below 3600, not merely a probable one.
G(3k) at decade checkpoints (every tenth power of 3, plus k = 148) up to k = 600, with ten band-exponents and a global fit, in data/counts600.txt. These are the first counts beyond 1070. Full detail and the figure are in Section 5.
Thompson's frontier reproduced exactly: G(1070) = 1,374, including the value 0, matching the b-file entry-for-entry. Independently, a bottom-up engine of a completely different design (a Gray-code walk over sums of distinct powers of 3 with staged residue filters, 2,140 exhaustive tasks) reproduced the census below 3.66×1019 > 341, covering Alekseyev's entire reported 2008 range, with zero discrepancies in terms, counts, or flags.
The independence heuristic (Erdős–Graham–Ruzsa–Straus; developed further by Pomerance) predicts G(N) ≍ Nθ with θ = log2/log3 + log3/log5 + log4/log7 − 2 = 0.025954…. A least-squares fit of ln G against ln N over 3100 ≤ N ≤ 3600 gives G(N) ≈ 48.2·N0.0248 (NUMERICAL, fitted range stated). The global exponent tracks the heuristic across 240 orders of magnitude. But the local exponent per 50-level band swings between 0.0144 and 0.0408, a factor of 2.8, and at finer resolution the growth is a staircase of rare bursts, not a gradient. Section 5 has the full picture.
Three bugs the checks caught before any production run: a wrong-stride array cast that misindexed the base-7 threshold comparison (would have silently mangled the e7 tables); task prefixes mis-decoded when the split depth was not a multiple of 4 (would have silently skipped subtrees in parallel runs, the kind of bug that fabricates a census without any error message); and a missing node-reconciliation path, needed to prove task-mode ≡ full-mode. After the fixes, the C engine matched the Python reference exactly (nodes, terms, all four checksums, term lists) at L = 35, 148, 200, 250, 300.
Milestones, all CERTIFIED (data/counts600.txt has G(3k) at every tenth k up to 600, plus k = 148; the underlying per-length histograms, from which the figure below is built, are what carry finer resolution):
| k | 100 | 148 | 200 | 250 | 300 | 350 | 400 | 450 | 500 | 550 | 600 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| G(3k) | 300 | 1,374 | 10,215 | 95,861 | 288,836 | 674,540 | 4,190,720 | 13,502,992 | 29,814,852 | 102,130,119 | 585,823,270 |
Local exponents per 50-level band (ln-ratio over band width): 0.0310, 0.0332, 0.0408, 0.0201, 0.0154, 0.0333, 0.0213, 0.0144, 0.0224, 0.0318 for the ten bands from 3100 to 3600: a swing of a factor 2.8 around the heuristic's 0.02595, while the global fit stays at 0.0248 (C5). At single-length resolution the mechanism is starker still: the number of terms with base-3 length exactly k is zero for 519 of the 601 lengths; the entire census is carried by 82 bursts. The largest sit near the top: lengths 600 (168,330,827 terms), 589 (144,139,469), 567 (86,478,633), 564 (63,277,668) and 531 (39,030,864). 82.6% of all terms below 3600 have length ≥ 564. (Independently recomputed for this page directly from the raw per-worker histogram logs: 82 inhabited lengths, the same five largest bursts, and 483,693,151 / 585,823,270 = 82.57% ≈ 82.6% at length ≥ 564, all confirmed to match.)
Between bursts lie certified deserts, each an exact statement of the form "no term of A030979 has base-3 length in this range":
| lengths | term-free interval | span |
|---|---|---|
| 475–530 | [3474, 3530) | 26.7 decimal orders |
| 395–419 | [3394, 3419) | 11.9 decimal orders |
| 541–563 | [3540, 3563) | 11.0 decimal orders |
| 568–588 | [3567, 3588) | 10.0 decimal orders |
These four are notable examples, not a verified-complete ranking of every desert in the census (Section 6 has a specific discrepancy found while re-checking this list for this page). Under the independence heuristic, the expected number of terms inside the largest gap alone is in the tens of millions; a desert that size has probability indistinguishable from zero under that model.
The qualitative mechanism, heuristic and not proved: a term of length k satisfies n/3k−1 ∈ [1, 3/2), a multiplicatively narrow window; its leading base-5 and base-7 digit blocks are then forced into windows determined by the fractional parts of (k−1)·log53 and (k−1)·log73. Those two rotations (≈ 0.6826 and 0.5646 per step) are incommensurate with each other and with the window widths, and the caps compound down the digit cascade, so for most k the compounded window has measure ~0, and for rare aligned k it opens wide. The bursts are the alignments. Turning this into a quantitative, log-periodic prediction of burst positions and masses is the sharpest open question this data raises (Section 7).