Erdős problem #1209: live-page audit and a finite squarefree obstruction
Accessed and computed on 2026-07-28 UTC.
Claim labels used below:
- [A] elementary-rigorous: proved here using elementary arguments.
- [B: theorem] rigorous-modulo-named-theorem: the named theorem is the only imported input.
- [C] plausible/structural-unverified: heuristic or an unverified comment, never used as a theorem.
- [D] computational-only: exact finite computation, reproducible by the standalone checker.
1. Mandatory live-page gate
I fetched the live page through the Bright Data browser path, then separately fetched its
discussion thread and LaTeX-source view. The authoritative live record was:
- status: OPEN;
- last page edit: 17 April 2026;
- claimed proofs: 0;
- “Currently working on this problem”: None;
- “Interested in collaborating”: None.
The remaining displayed markers were: liked by ebarschkis; “looks difficult” marked by
ebarschkis; “looks tractable” None; “results could be formalisable” None; “working on
formalising” None. The database fields said “Formalised statement? Yes” and “Related OEIS
sequences: Possible.”
Thus the mandatory stop condition did not fire. The page incorporates proofs of some
subquestions, but the page as a whole is open, has zero formal proof claims, and has no current
worker.
Verbatim live statement
> Let $A=\{a_1<a_2<\cdots\}$ be a sequence of integers which tends to infinity sufficiently fast. If there is an $n$ such that all $n+a_k$ are primes then must there exist infinitely many such $n$?
>
> What if we ask for $n+a_k$ to be squarefree instead of prime?
>
> Are there $n$ such that $n+2^{2^k}$ is always a prime (or always squarefree, or infinitely often a prime, or infinitely often squarefree)?
Source: live problem and its
Known results displayed on the live page
1. [B: Dirichlet's theorem] The first prime-shift question has a counterexample.
The page takes \(a_1=2\) and, for \(k\ge2\), a prime \(a_k>a_{k-1}\) satisfying
\(a_k+k\equiv0\pmod {q_k}\), where \(q_k\nmid k\). Dirichlet's theorem lets the
\(a_k\) grow arbitrarily fast. This kills every positive shift while \(n=0\) remains
good.
2. [B: Dirichlet's theorem] Replacing the congruence by one modulo \(q_k^2\)
gives the analogous counterexample for squarefree values.
3. [A] There is no integer \(n\) for which every
\(n+2^{2^k}\) is prime. The page records the multiplicative-order recurrence, and
the linked note treats the parity cases and \(n=1\) (where \(F_5\) is composite).
The page points to problems #429 and
#1102 as related.
All seven live comments, condensed without upgrading them to theorems
The discussion thread contained:
1. Dogmachine: a general assertion about composite values in a doubly exponential
family, except Fermat-type subsequences. [C] No proof or precise theorem was
supplied in the comment, so I do not use it.
2. Enrique Barschkis: a linked TEX/PDF/Lean treatment of the first two questions and
the “always prime” question, explicitly excluding the added always-squarefree and
infinitely-often variants; the comment conjecturally compares the leftovers with
Fermat-number questions. The proof portions are represented by the live known
results above; the comparison is [C].
3. Nat Sothanaphan: reported a standard check with no issue and summarized the
diagonal and order arguments.
4. Thomas Bloom: noted that the first two questions were already answered by the
construction in the page remarks.
5. Barschkis: explained that his note gives a sequence with \(n=0\) as the unique good
integer shift.
6. Bloom: clarified the usual positive-integer convention and that the page construction
can also be adjusted for negative shifts.
7. Barschkis: accepted that clarification.
Comments are explicitly marked unverified by the site. None is a claimed proof in the
page's proof-claim tracker.
2. Primary-source literature check
- The original source exists and contains the question on p.111:
P. Erdős, A survey of problems in combinatorial number theory,
Annals of Discrete Mathematics 6 (1980), 89–115,
The scan confirms that the special sequence is \(2^{2^k}\), despite ambiguous OCR.
- The 2026 page-linked note exists:
Enrique Barschkis, Erdős Problem #1209 (15 April 2026),
and LaTeX source.
It proves the stronger unique-shift construction using Dirichlet and gives the
elementary order proof that “always prime” is impossible. It does not claim the
three added variants.
- The classical squarefreeness obstruction is documented in a primary paper:
L. J. Warren and H. G. Bray, *On the square-freeness of Fermat and Mersenne
numbers*, Pacific J. Math. 22 (1967), 563–564,
It states the conjectured squarefreeness and proves the Wieferich necessary condition
discussed in Section 5 below.
Exact-formula and title searches found no primary paper resolving the three variants still
left open on the 2026 live page. That is an honest search miss, not a claim that no such
literature exists.
3. New exact finite result
Put
\[ U_k(n)=n+2^{2^k}. \]Finite obstruction theorem [D]. For every integer
\[ -10\,000\le n\le10\,000,\qquad n\notin\{-1,1\}, \]there are a prime \(p\le1423\) and an index
\[ 1\le k\le250270 \]such that
\[ p^2\mid U_k(n). \]Consequently none of these 19,999 shifts can make every \(U_k(n)\) squarefree.
Using only \(k\ge1\) makes the certificate valid whether the original indexing convention
starts at \(0\) or \(1\).
The two exceptions mean only “not eliminated by a prime \(p\le1423\).” They are not
unconditional positive examples.
Concrete-regime reduction [A+D]. Within \(|n|\le10\,000\), there exists an
always-squarefree shift if and only if every Fermat number
\[ F_j=2^{2^j}+1 \]is squarefree. For positive shifts \(1\le n\le10\,000\), the only possible shift is
\(n=1\), so the same equivalence holds.
The forward implication uses the finite obstruction theorem to force \(n=\pm1\), followed
by the identities in Section 5. The reverse implication uses \(n=1\).
This is genuine progress on a concrete infinite-\(k\) regime, but it does not control
\(|n|>10\,000\), and it says nothing by itself about the “infinitely often squarefree”
property for the eliminated shifts.
4. Why the finite certificate is exhaustive
Elementary orbit lemma [A]
Fix a prime \(p\), let \(q=p^2\), and define
\[ x_{1,p}=4\pmod q,\qquad x_{k+1,p}=x_{k,p}^2\pmod q. \]Induction gives
\[ x_{k,p}\equiv2^{2^k}\pmod {p^2}. \]Because there are only \(p^2\) residues and the update \(x\mapsto x^2\) is
deterministic, after the first repeated state the sequence is periodic and no new
residue can appear. Thus enumerating from \(k=1\) through the first repeat checks all
\(k\ge1\) for that \(p\).
For every enumerated state, all integers
\[ n\equiv-x_{k,p}\pmod {p^2} \]receive the witness \((p,k)\). The checker enumerates all primes \(p\le1423\) and all
such orbits.
Starting the cycle detector at \(k=1\) matters. For example, the state for \(p=7\)
at \(k=6\) repeats its \(k=0\) value, but it is an admissible witness:
\[ 49\mid 2^{64}-2=U_6(-2). \]Independent arithmetic audit [A+D]
The coverage pass uses repeated squaring. Every stored witness is then recomputed by
a different formula. For odd prime \(p\), Euler's theorem gives
\[ 2^{2^k}\bmod p^2 =2^{\,2^k\bmod p(p-1)}\bmod p^2. \]For \(p=2\) and \(k\ge1\), the residue modulo \(4\) is \(0\). The audit checks
\((n+2^{2^k})\bmod p^2=0\) for all 19,999 stored witnesses. The prime list is built by
an in-script Eratosthenes sieve and separately checked by trial division.
Recomputed output
| Quantity | Exact output |
|---|---:|
| Signed shifts tested | 20,001 |
| Eliminated shifts | 19,999 |
| Survivors | \([-1,1]\) |
| Candidate primes | 224 primes through 1423 |
| Orbit states enumerated | 4,112,370 |
| Largest single orbit | 433,622 |
| Distinct primes used by first witnesses | 108 |
| Largest first-witness prime record | \((n,p,k)=(27,1423,4350)\) |
| Largest first-witness index record | \((9717,1019,250270)\) |
| Certificate SHA-256 | 717d13f3bf1dc1a3a6d362c9d0fa31137594997c5ab93bdab453689b663853cf |
| Runtime on this VM | about 2.5 seconds |
Representative exact witnesses are:
| \(n\) | \(p\) | \(k\) | Certified divisibility |
|---:|---:|---:|---|
| \(-10000\) | 2 | 1 | \(2^2\mid U_1(n)\) |
| \(-9717\) | 107 | 2732 | \(107^2\mid U_{2732}(n)\) |
| \(-27\) | 23 | 41 | \(23^2\mid U_{41}(n)\) |
| \(-2\) | 7 | 6 | \(7^2\mid U_6(n)\) |
| \(0\) | 2 | 1 | \(2^2\mid U_1(n)\) |
| \(2\) | 3 | 2 | \(3^2\mid U_2(n)=18\) |
| \(27\) | 1423 | 4350 | \(1423^2\mid U_{4350}(n)\) |
| \(1587\) | 1291 | 5284 | \(1291^2\mid U_{5284}(n)\) |
| \(3675\) | 1117 | 4809 | \(1117^2\mid U_{4809}(n)\) |
| \(9717\) | 1019 | 250270 | \(1019^2\mid U_{250270}(n)\) |
| \(10000\) | 2 | 1 | \(2^2\mid U_1(n)\) |
Computational kernel
The complete dependency-free program is
runs/erdos1209_wave8k_reverify.py. Its core is:
for p in primes_through(1423):
q = p * p
x, k, seen = 4 % q, 1, set()
while x not in seen:
seen.add(x)
residue = (-x) % q
first = LOW_N + ((residue - LOW_N) % q)
for n in range(first, HIGH_N + 1, q):
if witness[n - LOW_N] is None:
witness[n - LOW_N] = (p, k)
x = x * x % q
k += 1
# Independent audit, not the recurrence used above.
phi = p * (p - 1)
residue = pow(2, pow(2, k, phi), p * p) # odd p
assert (n + residue) % (p * p) == 0
Run:
python runs/erdos1209_wave8k_reverify.py
The program asserts the survivor list, every individual divisibility, the structural
identities below, and the certificate count before printing PASS.
5. Exact interpretation of the two survivors
\(n=1\) [A]
\[ U_k(1)=F_k. \]Therefore:
- \(U_k(1)\) is always squarefree iff every Fermat number is squarefree;
- \(U_k(1)\) is prime infinitely often iff there are infinitely many Fermat primes;
- \(U_k(1)\) is squarefree infinitely often iff infinitely many Fermat numbers are
squarefree.
These are exact specializations for \(n=1\). They do not prove that the unrestricted
existential questions are equivalent, because another shift outside the computed interval
could behave differently.
\(n=-1\) [A]
The standard identity and pairwise coprimality are
\[ U_k(-1)=2^{2^k}-1=\prod_{j=0}^{k-1}F_j, \qquad \gcd(F_i,F_j)=1\quad(i\ne j). \]Hence every \(U_k(-1)\) is squarefree iff every \(F_j\) is squarefree. More strongly,
\(U_k(-1)\) is squarefree infinitely often iff every \(F_j\) is squarefree: if one
\(F_j\) has a squared prime factor, that square divides every \(U_k(-1)\) for
\(k>j\).
This proves the concrete-regime equivalence stated in Section 3.
Why repeated Fermat factors are difficult [A]
If an odd prime \(p\) satisfies \(p^2\mid F_j\), then the order of \(2\) modulo
\(p^2\) is exactly \(2^{j+1}\): the \(2^j\)-th power is \(-1\), while the next
power is \(1\). This order divides
\(\varphi(p^2)=p(p-1)\), and because it is a power of two it divides \(p-1\).
Thus
\[ 2^{p-1}\equiv1\pmod {p^2}; \]\(p\) must be a base-2 Wieferich prime. This elementary argument agrees with
Warren–Bray's classical necessary condition.
The condition is only necessary. It neither produces a squared Fermat factor nor proves
that none exists.
6. What remains, and the precise wall
1. Always squarefree. The finite theorem removes every \(|n|\le10\,000\) except
the two Fermat shifts. Closing the unrestricted existential question requires either:
- constructing one shift and proving absence of every prime-square divisor for all
\(k\); or
- ruling out every shift, which in particular would have to rule out \(n=1\) by
finding a nonsquarefree Fermat number.
The exact missing lemma at \(n=1\) is the squarefreeness of all Fermat numbers (for
a positive result) or one explicit squared prime divisor of a Fermat number (for a
negative result).
2. Infinitely often prime. The order argument used for “always prime” starts from
a prime term and forces composite terms along one arithmetic progression of later
indices. It does not cover the complementary indices. The missing step would be a
finite covering of all sufficiently large indices by such forced-composite
progressions, or a method proving infinitely many prime values. At \(n=1\), the
latter is exactly the infinitude of Fermat primes.
3. Infinitely often squarefree. A single \(p^2\)-witness, including every witness
in this report, is irrelevant to “infinitely often.” For fixed \(p\), the bad
indices are eventually periodic; the unresolved task is to control the union over
all primes. A positive result must prove that infinitely many indices avoid every
prime-square obstruction, while a negative result needs a covering of all large
indices. No such uniform lemma was found.
4. Why simply increasing the computation does not close the problem. The present
run is finite in \(n\) and in the searched primes, even though each searched prime
is handled for every \(k\). Increasing the bounds can extend the certified interval
but supplies no uniform finiteness step. Naive trial division for just
\(F_{20}=2^{2^{20}}+1\) would extend to about
\(2^{2^{19}}\approx10^{157826}\); even an unrealistic \(10^8\) trials/second is
on the order of \(10^{157811}\) core-years. This is a cost diagnosis, not a
proposed computation.
No conjectural comparison in the live comments is used to claim closure. The original
problem remains open in exactly the three variants identified by the live page.
PARTIAL: [D] Every integer \(|n|\le10000\) except \(n=\pm1\) is explicitly ruled out for the always-squarefree variant by a prime-square witness with \(p\le1423\) and \(k\le250270\); within this range existence is exactly the unresolved all-Fermat-numbers-squarefree conjecture, while the infinitely-often variants remain open.