Erdoes #276 - working report - Erdős Problem a Day

Erdős problem 276 — wave8q

Accessed and computed on 2026-07-28. The conclusion is PARTIAL, not a solution: I obtain an exact finite obstruction for the Ismailescu--Son construction and isolate the missing uniform lemma.

Claim labels used throughout:

[a] elementary-rigorous;
[b] rigorous modulo the named theorem or faithful primary-source report;
[c] plausible/structural-unverified;
[d] computational-only (exact integer computation unless otherwise said).

0. Mandatory live-page gate

I fetched the rendered live problem page and its discussion thread through the Bright Data browser, not datacenter curl.

[b] Live status: OPEN.
[b] Claimed proofs: 0.
[b] Current-worker field: None.
[b] Collaboration-interest field: Woett. This is an interest

marker, not the current-worker stop condition.

[b] The page was last edited 29 December 2025 and says the statement is

formalised.

The mandatory stop conditions were therefore absent.

The live wording is reproduced below. To respect the short-quotation limit, the verbatim excerpt ends at its last substantive noun; its completion is given immediately afterward by the exact quantified formula.

Is there an infinite Lucas sequence $a_0,a_1,\ldots$ where $a_{n+2}=a_{n+1}+a_n$ for $n\geq 0$ such that all $a_k$ are composite, and yet no integer has a common factor with every term

The completion means exactly

\exists (a_k)_{k\geq0}\quad \bigl(a_{k+2}=a_{k+1}+a_k,\;a_k\text{ composite}\bigr) \quad\text{and}\quad \forall M>1\ \exists k\geq0:\gcd(M,a_k)=1.

This reading agrees with the linked formal statement, which uses ∀ n > 1, ∃ k, Nat.gcd n (a k) = 1.

Live known results and comments

[b] The page records Graham's covering-system construction with

\[ a_0=1786772701928802632268715130455793,\qquad a_1=1059683225053915111058165141686995. \] Graham's 1964 primary paper supplies the 18 covering triples and these starting values.

[b] The page describes Ismailescu--Son as a conjectural resolution:

their sequence is provably all-composite, but they do not prove that it lacks a finite covering set of primes.

[b] Woett's 24 November 2025 comment records Vsemirnov's smaller

covering-based pair $(106276436867,35256392432)$, then accurately separates the two parts of Ismailescu--Son: a finite cover for even indices and an algebraic factorisation for odd indices. It explicitly says nonexistence of a finite cover for the odd indices is unproved and asks whether Hough's ideas could reduce it to finite computation.

[b] Dogmachine's later 24 November comment expresses a belief that the

problem is probably resolved and compares the missing step with a question about $5\cdot2^n+1$; it is not a proof claim.

[b] Dogmachine's 1 September comment says the coprimality assumption can

be omitted from the question; the page notes that it was updated accordingly.

1. Primary-source audit

[b] Erdős and Graham's

1980 monograph, printed p. 27 asks whether an all-composite Lucas sequence can exist without an underlying covering system.

[b] Graham's 1964 paper proves the first all-composite coprime-start

example by a finite prime cover.

[b] Vsemirnov's

2004 paper proves the smaller pair quoted in the live comment, again by a cover.

[b] Ismailescu and Son,

A New Kind of Fibonacci-Like Sequence of Composite Numbers, JIS 17 (2014), Art. 14.8.2, is the directly relevant primary source. Its last paragraph reports 803 pairwise-coprime terms surviving a $2\cdot10^6$ small-prime screen through index 200000, but expressly says the finite-cover question remains unproved. I treat “803” here as the paper's report, not as a recomputed theorem.

[b] Filaseta--Finch--Kozek,

JNT 128 (2008), 1916--1940, explicitly asks whether the least prime factor of $5\cdot2^n+1$ is unbounded, confirming that the analogous uniformity step is genuinely difficult.

[b] Hough's

Annals theorem proves that the least modulus of a distinct-moduli covering system is at most $10^{16}$. The distinctness qualifier is essential below.

[b] Izotov's

2002 paper, found during the search, combines algebraic factorisation and a cover for a class of recurrences, but its theorem assumes recurrence coefficient $a>2$, so it does not include the Fibonacci recurrence $a=1$.

[c] Exact-title, author, citation-graph, and full-text searches found no primary post-2014 paper resolving this specific no-cover question. OpenAlex listed one direct citation, Lunev's 2017 Tribonacci generalisation, which does not address the missing claim; a Semantic Scholar API query returned HTTP 429. This is a reported search miss, not a claim that no uncatalogued result exists.

2. Reconstructing the Ismailescu--Son candidate

Let

\begin{split} q={}&129511502555081082458723990740612592095319437933512025195406541068\\ &394745828231264515958532145970461367703231950382110924410768870, \end{split}

and define

x_0=1+q^2,\qquad x_1=q^2+2q,\qquad x_{n+2}=x_{n+1}+x_n.

A source-level ambiguity resolved

The journal TeX places -\\ between the two displayed digit blocks for $q$. Literal subtraction gives a negative 80-digit integer, contradicting the paper's statement that $q$ has 129 digits.

[a,d] The checker reconstructs $q$ independently from all 30 residues

in the paper's Table 3 using CRT. The least nonnegative solution is exactly the concatenated 129-digit integer above; it is smaller than the product of the 30 prime moduli. The subtraction reading fails these checks.

[a] $\gcd(x_0,x_1)=1$: a common divisor divides $2q-1=x_1-x_0$, and

\[ 4(q^2+1)-(2q-1)(2q+1)=5. \] Since $q\equiv0\pmod5$, it cannot divide $x_0$, so the gcd is 1.

Why every term is composite

Write $F_0=0,F_1=1$ and $L_0=2,L_1=1$.

[a] For every $k\geq0$,

\[ x_{2k+1}=(F_k+qF_{k+1})(L_k+qL_{k+1}). \] Both factors exceed 1. This follows by substituting $x_n=x_0F_{n-1}+x_1F_n$ and the standard doubling identities. The checker verifies the identity with full integers for every odd index through 20000.

[b,d] The 30 rows $(p_i,m_i,r_i,c_i)$ in Ismailescu--Son Table 2

satisfy: $p_i$ is prime, $p_i\mid F_{m_i}$, their classes $r_i\bmod m_i$ cover every even residue modulo $\operatorname{lcm}(m_i)=5040$, and the two initial congruences force $p_i\mid x_n$ when $n\equiv r_i\pmod {m_i}$. The checker verifies every row from scratch, including deterministic 64-bit primality tests and all 2520 even residues.

[a,d] The edge term $x_0$ is covered too:

$764940961\mid x_0$. Thus there is no omitted $n=0$ case.

Consequently this is a rigorously certified all-composite sequence. What is not certified is the absence of a second finite prime set covering its odd terms.

3. Exact reduction of the open part

Three equivalent missing statements

Let $b_k=x_{2k+1}$, the odd-indexed subsequence. The even terms already have the fixed 30-prime cover above.

[a] The following are equivalent:

no finite set of primes covers all $b_k$;
the least prime factor of $b_k$ is unbounded as $k$ varies;
the $b_k$ contain an infinite pairwise-coprime subsequence.

Proof:

If all least prime factors were at most $B$, the finite set of primes

$\leq B$ would cover every $b_k$. Conversely, a finite cover bounds the least prime factor by its largest member.

If no finite cover exists, choose terms greedily. After finitely many

pairwise-coprime choices, the union of their prime divisors is finite, so some further term avoids it. The converse is immediate: one prime can hit at most one member of a pairwise-coprime family.

Because the even terms have a finite cover, each of these is also equivalent to the original sequence having no covering integer.

The induced congruence system

[a] Suppose a prime $\ell\mid x_r$. Consecutive terms are coprime, and the addition formula gives

x_{r+t}=F_{t-1}x_r+F_t x_{r+1}.

Hence

\ell\mid x_{r+t}\quad\Longleftrightarrow\quad \ell\mid F_t.

If $z(\ell)$ is the rank of apparition of $\ell$ in the Fibonacci sequence, the zero indices of $x_n\bmod\ell$ are therefore one residue class modulo $z(\ell)$. On the odd subsequence the zero indices are one class modulo

\mu_\ell=\frac{z(\ell)}{\gcd(z(\ell),2)}.

Thus a hypothetical covering integer produces an ordinary finite covering of the $k$-line by these special residue classes. This is exact, but the moduli need not be distinct.

[d] A concrete repeated-modulus witness is already present:

$z(31)=30$ and $31\mid b_k$ for $k\equiv4\pmod {15}$, whereas $z(61)=15$ and $61\mid b_k$ for $k\equiv8\pmod {15}$. Both induced moduli are 15 but their residues differ. The checker verifies these four assertions directly.

Therefore Hough's $10^{16}$ least-modulus theorem cannot simply be invoked: its hypothesis is distinct moduli. Even if it did apply, factoring Fibonacci numbers up to the corresponding ranks would not be a practical “small” check—$F_{2\cdot10^{16}}$ has about $4.18\cdot10^{15}$ decimal digits.

4. New exact finite certificate

Define the forbidden prime set

\mathcal P=\{p:p\leq10^7\}\ \cup\ \{p_1,\ldots,p_{30}\},

where the second set is Ismailescu--Son Table 2.

[d] Exact prefix result. Among all $0\leq n\leq20000$, exactly the following 59 terms avoid every prime in $\mathcal P$:

123, 719, 1143, 1383, 1799, 1815, 1827, 1887, 2823, 3843,
4095, 4167, 4583, 4823, 5123, 5735, 5819, 6027, 6927, 8363,
8955, 9239, 9323, 9443, 9515, 9539, 10199, 10379, 10415, 10499,
10647, 10763, 11067, 11715, 11795, 11855, 11895, 12143, 12147,
12719, 13379, 13619, 13715, 14247, 14975, 15839, 15855, 15959,
16919, 16979, 17495, 18375, 18659, 18675, 18839, 19079, 19343,
19595, 19887

All 59 are odd-indexed and algebraically composite. Their 1711 pairwise gcds are all exactly 1.

[a+d] Consequence. If an integer $M>1$ has $\gcd(M,x_n)>1$ for every $n$, choose for each of these 59 terms a prime dividing both it and $M$. Pairwise coprimality makes those 59 primes distinct. The forbidden-prime check makes every one larger than $10^7$ and outside the 30-prime table. Therefore

\omega(M)\geq59,\qquad M>(10^7)^{59}=10^{413}.

This does not prove that $M$ cannot exist.

The journal paper's 803-term computation has a larger cardinality at cutoff $2\cdot10^6$. The present certificate is an independent, exactly reproducible higher-cutoff result, not a claim to dominate the paper in every parameter.

[d] Cross-check of two source claims. PARI/GP isprime proves that the four factors associated with $k=913,943$ have digit lengths 319, 320, 326, 326 and are prime. Hence $x_{1827}$ and $x_{1887}$ are indeed semiprimes as reported by Ismailescu--Son.

5. Reproduction and independence checks

Run:

python runs/erdos276_wave8q_reverify.py

The standalone checker:

reconstructs $q$ by CRT;
proves all 30 table moduli prime in the 64-bit range and verifies the

covering certificate;

enumerates all 664579 primes through $10^7$;
scans every prime/term modular recurrence pair;
regenerates the full integer terms and checks all odd factorizations;
independently multiplies all small primes in a balanced product tree and

checks each survivor by a full-integer gcd against that primorial and all 30 table primes;

checks all 1711 pairwise full-integer gcds;
checks the four large primes with PARI/GP; and
hashes the indexed full terms as

19168f99acc0b4c3b6b655f6786218a557ccd2baceb179d8645c835b79bebf80.

The final clean run passed in 104.44 seconds. Its last substantive output was:

Independent primorial-gcd check: PASS
Full-integer pairwise gcds: PASS (1711 pairs)
PARI proven-prime checks at x_1827 and x_1887: PASS
ALL CHECKS PASSED in 104.44 seconds

6. Precise wall and cost

[a] The exact missing lemma is: the least prime factor of

$(F_k+qF_{k+1})(L_k+qL_{k+1})$ is unbounded. Equivalently, its prime divisibility classes do not contain a finite covering system; equivalently, these products have an infinite pairwise-coprime subsequence.

[b] The closest standard covering theorem found, Hough's, assumes

distinct moduli, while the induced rank moduli here can repeat.

[c] A useful new theorem would have to control coverings with the

particular multiplicities $\#\{\ell:z(\ell)/\gcd(z(\ell),2)=m\}$, or directly force an uncovered residue in this rank-residue family. No such applicable theorem was found.

[d] The present scan performs about

$20000\pi(10^7)\approx1.33\cdot10^{10}$ vector residue updates. At its measured rate, a segmented scan through $10^9$ and 200000 indices would require roughly $1.02\cdot10^{13}$ updates, about 22 core-hours. At a realistic \$0.05--\$0.10 per core-hour this is roughly \$1--\$2 of raw CPU; as a current anchor, Google's listed 56-vCPU c2d-highcpu-56 on-demand rate is about \$0.0375 per vCPU-hour (official pricing). This also needs a few GB of working-memory traffic and engineering for segmentation. It would still be only another finite lower bound, not a proof.

The obstruction is therefore mathematical uniformity, not the next finite sieve range.

PARTIAL: the Ismailescu--Son candidate is re-certified, and any covering integer must contain at least 59 distinct primes above 10^7 (and outside its 30 covering primes), but ruling out every finite cover remains equivalent to the unproved unbounded-least-prime-factor lemma.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger