Fabian Arevalo

Computational research note · Graham's $1000 problem (Erdős–Graham–Ruzsa–Straus, 1975)

The census of Graham's $1000 problem, 216 orders of magnitude further

Complete enumeration of {n : gcd(C(2n,n), 105) = 1} below 3600 ≈ 1.9×10286: 585,823,270 terms, up from the 1,374 known since 2015.
August 14, 2026 · produced with substantial AI assistance (Claude Code) in a research session; every proof was checked by hand and every computed number is reproducible from committed code. AI systems are not authors.
Code, data and certificates in the companion repository.

Start here: no maths required

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.

Hover or tap a column to read its count.
Where the qualifying n actually live, for base-3 lengths 400 to 600. Each column is one length (roughly, one power-of-3 decade): its height is how many qualifying n have exactly that many base-3 digits, read from the certified per-length counts behind data/counts600.txt. Almost every column is flush with the floor: only 19 of these 201 lengths hold any terms at all. The shaded band is lengths 475–530, i.e. every n from 3474 to 3530, a certified, exact, twenty-seven-decimal-order stretch with not one qualifying n in it, followed immediately by 39,030,864 of them at length 531 alone.

What this note adds

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:

  1. Extends the complete list to 3600 ≈ 1.9×10286 (216 orders of magnitude past the old edge) and finds 585,823,270 qualifying values of n in total, a ×426,363 increase in the count. Five independently written programs, in two different search strategies, agree exactly on every value in every range where they overlap. Total cost: about 12.5 core-hours.
  2. Finds the biggest one yet: a 286-digit number (the previous record-holder, below 1070, had 66 digits).
  3. Re-confirms a second, harder prediction of Graham's: that n = 3160 is the last number for which C(2n,n) avoids 3, 5, 7 and 11 all at once, by searching, and finding no counterexample, all the way to 3600.
  4. Discovers the list does not fill in evenly. Counting how many qualifying n exist below each of the first 600 powers of 3, only 82 of those 601 checkpoints ever see a new one. The figure above shows the most dramatic stretch: a twenty-seven-decimal-order gap with nothing in it, then thirty-nine million at once. The overall growth rate still tracks the standard heuristic guess reasonably well; it is the local behaviour the heuristic gets qualitatively wrong.
  5. Re-derives the published 2015 record from scratch in well under a second once the right search tree is used, and independently re-confirms the bottom of the range (below 3.66×1019) with a second, unrelated method.

The infinite-or-finite question itself is untouched, and cannot be touched by any computation, however large. Everything below is the technical version.

AbstractSummary of results

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.

Section 1The problem and its classical reduction

Problem · Erdős, Graham, Ruzsa, Straus (1975); Graham's $1000 question

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.

Lemma 1 · Kummer's criterion (classical)

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).

Section 2The enumeration algorithm and its soundness

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

(1)
A ≤ n ≤ A + (3L−d − 1)/2
the upper bound being the sum of all remaining powers
Lemma 2 · the interval prune

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).

Section 3Results

Labels follow the repository convention (PROVED / CERTIFIED / NUMERICAL), and every number below is emitted by a committed, rerunnable script.

C1 · CERTIFIED · Complete census below 3600

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).

L3L ≈terms G(3L)nodesnodes / termengine
1484.1×10701,374137,551100.1C + Python, identical
2002.7×109510,2151,221,201119.6C + Python, identical
2501.9×1011995,86111,963,213124.8C + Python, identical
3001.4×10143288,83636,430,897126.1C full ≡ C 4-worker ≡ Python
3501.9×10167674,54085,263,581126.4C full
4007.1×101904,190,720529,206,039126.3C full
5003.6×1023829,814,8523,760,885,157126.1C full
6001.9×10286585,823,27073,906,945,791126.2C, 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.

C2 · CERTIFIED · The 1155 companion

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.

C3 · CERTIFIED · Counts

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.

C4 · CERTIFIED, replication · Thompson's frontier and Alekseyev's range

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.

C5 · CERTIFIED counts / NUMERICAL fit · The heuristic exponent

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.

Section 4Verification architecture

  1. Definition-level control. Brute force over all n ≤ 2×107 with literal gcd(math.comb(2n,n), 105), no Kummer shortcut, matches the digit-condition engines exactly (13 terms). For this page, eight small members (0, 1, 10, 756, 757, 3160, 3186, 3187) were independently re-checked the same way, and seven nearby non-members (2, 4, 5, 9, 11, 758, 3161) were confirmed to fail: every one of the fifteen matched the digit-cap prediction.
  2. Five implementations, two algorithm families. Bottom-up: a Python DFS over subset sums, and a C Gray-code grid (32,768-task design, stopped at 2,140 ascending tasks). Top-down: a Python reference, a C digit-array engine, and a C task-mode variant (4 workers). Every overlapping range agrees exactly on term lists, per-task and per-leaf counts, node counts (C ≡ Python node-for-node at L = 35, 148, 200, 250, 300), and all four fingerprints.
  3. Task-mode reconciliation. At L = 300, the 4-worker run's totals plus the task generator's internal node count equal the full-mode run's fingerprint exactly (36,417,860 + 13,037 = 36,430,897 nodes; terms, sums, XOR and mod-p all equal). The same identity, at the scale of the full L = 600 campaign, is what data/census600_summary.txt certifies: 3,753 top-split tasks plus a 4,906-task sub-campaign, every task id present exactly once, reconciling to 73,906,945,791 total nodes and 585,823,270 terms.
  4. Independent per-term validation. Every printed term passes a validator using a Lucas-theorem route disjoint from the search's own carry-free logic (C(2n,n) mod p ≠ 0 iff the digits of 2n dominate the digits of n, with 2n computed by bigint doubling), for p = 3, 5, 7, 11, plus literal math.comb for n ≤ 105. Zero failures across every emitted file.
  5. External anchors, used as assertions. The OEIS display line (23 terms), Thompson's 1,374 at 1070, and Graham's 3160 are all reproduced exactly.
  6. Leaf identities. The Gray-code engine's leaf count equals a digit-DP closed form for #{base-3-valid n ≤ T} exactly, per task and in total: an identity independent of the main search logic entirely.

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.

Section 5Counts against the heuristic: a power law made of bursts

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):

k100148200250300350400450500550600
G(3k)3001,37410,21595,861288,836674,5404,190,72013,502,99229,814,852102,130,119585,823,270
Hover or tap the curve to read off a checkpoint.
The count climbs along the predicted power law for 280 orders of magnitude, but as a staircase, not a smooth curve. The solid line is measurement: the certified G(3k) at every committed checkpoint, connected by straight segments in log-log space as a visual aid (the true function is a step function; the bar chart above and the table below show why it is lumpier than this line suggests). The dashed line is not a fit to this data: it is the independence-heuristic exponent 0.025954 (Erdős–Graham–Ruzsa–Straus; Pomerance) evaluated live from its formula and anchored to pass exactly through the certified value at 3148 (Thompson's 2015 frontier, 1,374 terms). Where the two diverge: measured sits below the heuristic for small k (0.42× at 320), crosses near the anchor by construction, rises to nearly 2.8× the heuristic around 3300, and comes back down to about 1.08× by 3600: a genuine oscillation around the trend line, not noise, and not the same line as C5's separately-fitted 48.2·N0.0248.

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":

lengthsterm-free intervalspan
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).

Section 6Caveats

Section 7Open questions this data sharpens

  1. G(N) grows in rare bursts separated by deserts of up to 27 decimal orders (Section 5). Is there a quantitative, log-periodic prediction of burst positions and masses from the rotations (k·log53, k·log73) mod 1 that reproduces the observed staircase? The 82 inhabited lengths are the data to fit; a proved version would turn the census into theorems about term-free intervals.
  2. EGRS proved infinitude for any two odd primes; three at once is the wall. Croot's 2022 theorem (arXiv:2201.11274) and the newer Bloom–Croot result (arXiv:2509.02835, Sept 2025) both get infinitely many n with only low-multiplicity divisibility across r primes simultaneously, but only for primes larger than a threshold depending on r, and both papers say so explicitly in their own abstracts. The specific small-prime case {3,5,7} is exactly what remains outside their reach. Does the two-prime method, plus any quantitative equidistribution input, reach {3,5,7} along an explicit sparse sequence?
  3. Is the 1155 heuristic sum (C6) provably convergent: can one prove unconditionally that {n : gcd(C(2n,n), 1155) = 1} has a counting function bounded on some subsequence? Even that appears to be open.