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 LaTeX view.

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.

1. [B: Dirichlet's theorem] Replacing the congruence by one modulo \(q_k^2\)

gives the analogous counterexample for squarefree values.

1. [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.

1. 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].

1. Nat Sothanaphan: reported a standard check with no issue and summarized the

diagonal and order arguments.

1. Thomas Bloom: noted that the first two questions were already answered by the

construction in the page remarks.

1. Barschkis: explained that his note gives a sequence with \(n=0\) as the unique good

integer shift.

1. Bloom: clarified the usual positive-integer convention and that the page construction

can also be adjusted for negative shifts.

1. 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, Rényi archive scan. 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), PDF 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, journal PDF, DOI 10.2140/pjm.1967.22.563. 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

Finite obstruction theorem [D]. For every integer

there are a prime \(p\le1423\) and an index

such that

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

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

Induction gives

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

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:

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

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

Representative exact witnesses are:

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]

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

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

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

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

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

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