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
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
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
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](https://cs.uwaterloo.ca/journals/JIS/VOL17/Ismailescu/ism8.pdf),
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,
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
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:
1. no finite set of primes covers all \(b_k\);
2. the least prime factor of \(b_k\) is unbounded as \(k\) varies;
3. 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:
1. reconstructs \(q\) by CRT;
2. proves all 30 table moduli prime in the 64-bit range and verifies the
covering certificate;
3. enumerates all 664579 primes through \(10^7\);
4. scans every prime/term modular recurrence pair;
5. regenerates the full integer terms and checks all odd factorizations;
6. 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;
7. checks all 1711 pairwise full-integer gcds;
8. checks the four large primes with PARI/GP; and
9. 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
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.