Skip to content

Erdős Problem #276

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, covering systems.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

Editorial authority: The protected GCL V2 admissions ledger alone determines publication status. This source-bounded explanation is not mathematical certification.

The question in plain language

Start with positive integers \(a_0,a_1\) and continue by the Fibonacci-type rule

\[ a_{n+2}=a_{n+1}+a_n\qquad(n\geq 0). \]

Erdős Problem 276 asks whether the starting values can be chosen so that every term is composite, while the sequence does not have one fixed integer factor running through all its terms. “Composite” means having a nontrivial factor; the interesting point is that the recurrence can be infinite even though each individual term has to be nonprime.

There are two similar-looking coprimality statements, and they must not be conflated. The weak statement says that no fixed \(d>1\) divides every term. Because the recurrence determines every later term from the first two, that weak statement is equivalent to

\[ \gcd(a_0,a_1)=1. \]

The pinned formal statement uses the more explicit quantifiers

\[ \forall d>1\;\exists k\;\gcd(d,a_k)=1. \]

This says that each proposed common modulus \(d\) must be defeated by some term. It is a stronger-looking requirement, but equivalence with the weak seed condition has not been established here. In particular, \(\gcd(a_0,a_1)=1\) is not a license to silently replace the displayed universal-existential condition.

A small example

Take \(a_0=5\) and \(a_1=8\). The recurrence begins

\[ 5,8,13,21,34,55,89,\ldots. \]

This is not a solution to the Erdős problem, because it already contains primes such as \(13\) and \(89\). It is nevertheless a useful finite illustration of the quantifiers. The following exact calculation searches the displayed prefix for a term coprime to each \(d\) from \(2\) through \(10\):

from math import gcd

a = [5, 8]
for _ in range(5):
    a.append(a[-1] + a[-2])
print(a)
print({d: next(k for k, x in enumerate(a) if gcd(d, x) == 1)
       for d in range(2, 11)})

It prints

[5, 8, 13, 21, 34, 55, 89]
{2: 0, 3: 0, 4: 0, 5: 1, 6: 0, 7: 0, 8: 0, 9: 0, 10: 2}

The finite output does not establish the condition for every \(d\), just as a finite list of composite terms would not establish an infinite composite sequence. It shows why “there exists a helpful index” is a real quantifier rather than a visual property of the first few terms.

What is known

Graham’s 1964 paper, “A Fibonacci-Like Sequence of Composite Numbers,” Mathematics Magazine 37, pp. 322–324, gives a covering-system construction in which every term is composite. The publisher’s accessible record confirms the bibliographic identity and DOI 10.1080/0025570X.1964.11975551, but the full paper was not accessible in this audit; its proof is therefore reported from the later literature and catalogue, not claimed as independently rechecked here. A covering construction by itself does not settle the no-common-divisor condition.

Ismailescu and Son, “A New Kind of Fibonacci-Like Sequence of Composite Numbers,” Journal of Integer Sequences 17 (2014), Article 14.8.2, provide the important later construction. Their Theorem 1 (p. 3) factors every odd-indexed term of

\[ x_0=p^2+q^2,\qquad x_1=2pq+q^2 \]

as

\[ x_{2n+1}=(pF_n+qF_{n+1})(pL_n+qL_{n+1}), \]

so those terms are composite when \(p\geq1\) and \(q\geq2\). Lemma 2 and Table 2 (pp. 4–5) give a 30-prime partial covering for every even index modulo \(5040\). Their Theorem 3 (p. 6) then claims an explicit sequence whose terms are all composite and whose first two terms have gcd 1.

I checked the finite certificate with exact integer arithmetic: all table primes divide their listed Fibonacci numbers, the even residues are covered modulo \(5040\), the Table 3 residues agree with the concatenated parameter, and the two seeds have gcd 1. A compact reproducible core is:

from math import gcd, lcm

rows = [(2,3,1),(5,5,1),(13,7,1),(17,9,3),(29,14,2),
 (41,20,4),(61,15,2),(181,90,8),(241,120,14),(281,28,4),
 (421,21,3),(541,90,38),(1009,126,90),(1601,80,34),(2161,40,10),
 (2521,60,20),(3041,80,74),(8641,360,18),(20641,120,110),
 (31249,126,42),(103681,72,54),(109441,45,23),(141961,35,12),
 (721561,420,180),(1461601,252,186),(35239681,63,6),
 (764940961,252,0),(8288823481,105,33),(10783342081,180,162),
 (571385160581761,504,222)]
M = lcm(*(m for _, m, _ in rows))
q = int("12951150255508108245872399074061259209531943793351"
         "2025195406541068394745828231264515958532145970461367703231950382110924410768870")
print(M, len(str(q)), gcd(1 + q*q, 2*q + q*q))

The output is 5040 129 1. This validates a finite construction certificate, not the infinite coprimality assertion. The paper itself reports a search through indices \(n\leq200000\) and primes up to \(2\cdot10^6\), including 803 exceptional indices, but finite computation is evidence rather than a proof for every value of \(d\).

There is also a source-fidelity exception: the published TeX splits the 129-digit \(q\) across a line using a minus sign. Literal subtraction conflicts with the stated digit length and Table 3; concatenation is the interpretation used by the certificate above, but it should not be silently presented as what the typographical source literally says.

GCL's current state

The authenticated source return on original issue #1546, RESULT/1 is explicitly DISPOSITION: PARTIAL. The pinned catalogue is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, with file blob 4e60263a80af6207aca494d2e1388e44fa372889: it records Problem 276 as open, solution unformalized, and statement formalized. The live page still calls the Ismailescu–Son conclusion “conjecturally solved”; it has three discussion comments, no proof expositions, and zero proof claims. Those comments are status context, not verified proof evidence.

The pinned FormalConjectures file at SHA 85f863718beeec7b58a3a1926ee92e3472bc2020 and file blob 61fd31acdc857f3a70c0445d20db02cdb8a558ce states the recurrence, compositeness, and the strong \(\forall d>1\;\exists k\) condition, but contains answer(sorry) and a by sorry body. It is a statement formalization, not a checked Lean proof. No GCL internal certification is asserted or supplied by this manuscript.

The neighboring source returns reinforce the boundary rather than resolve #276. #284 is STATUS_CONFLICT because Croot’s published wording says “infinitely many indices” while the catalogue’s claim for every sufficiently large index needs a separate bridge (exact return). #285 is also STATUS_CONFLICT: its Lean Fin k.succ formulation is shifted by one relative to \(f(k)\) and includes sorry (exact return). Neither is evidence for a #276 proof.

What remains

The central mathematical task is to prove the strong universal-existential coprimality condition for the explicit Ismailescu–Son sequence, or to prove that it is equivalent to the intended weaker phrase under the relevant hypotheses. The latter cannot be assumed from seed gcd 1. A separate source review should resolve the split-line \(q\) transcription against the paper’s congruence table and check the published proof in full.

The phrase “no underlying covering system” also needs a formal definition before it can be treated as a theorem. The even terms have a finite covering mechanism by construction; the unresolved issue concerns whether the odd-index mechanism has some finite common-prime explanation. The paper’s search and its two very large-prime examples suggest difficulty, but they do not prove that no such mechanism exists.

Accordingly, the precise status layers are: a published external construction of all-composite terms; catalogue and live-page reports of an open or conjecturally solved problem; an external formalized statement with unfinished proof placeholders; and no GCL mathematical certification. A local calculation can be accepted as a reproducible finite check, but it cannot promote any of those layers.

Sources and claim boundaries

This article preserves the source return’s PARTIAL disposition, its semantic warning about the two coprimality readings, and its fidelity warning about \(q\). It does not promote the live catalogue, an external Lean declaration, or the finite calculation into a proof or protected GCL result.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1546 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction