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

Erdős problem #695 — wave w010

Date: 2026-07-28 UTC

Claim labels used throughout:

(a) elementary-rigorous: proved below from elementary facts.
(b) rigorous-modulo-named-theorem: depends on the cited theorem/source.
(c) plausible/structural-unverified: heuristic only.
(d) computational-only: exact finite output of the supplied exhaustive

program, not an asymptotic theorem.

Mandatory live-page gate

(d) I fetched the rendered live page <https://www.erdosproblems.com/695>, its LaTeX view, and its discussion thread through the Bright Data browser on 2026-07-28, before doing mathematics. The page says:

status: OPEN;
last edited: 17 October 2025;
claimed proofs: 0;
“Interested in collaborating”: None;
“Currently working on this problem”: None;
“I am working on formalising the results”: None.

Thus none of the mandatory stop conditions applies.

(c) The one page comment, by StijnC on 10 August 2025, guesses that the answer to the first question is yes. Its heuristic is that, because the current modulus is prime, the possible multipliers in $kq+1$ have no fixed excluded prime divisor and should have average size at least about $\log q$. It suggests the greedy sequence OEIS A061092 for the second question. The comment supplies no proof and is explicitly marked unverified by the site.

Verbatim live statement

Let $p_1<p_2<\cdots$ be a sequence of primes such that $p_{i+1}\equiv 1\pmod{p_i}$. Is it true that\[\lim_k p_k^{1/k}=\infty?\]Does there exist such a sequence with\[p_k \leq \exp(k(\log k)^{1+o(1)})?\]

The live page also calls such a sequence a prime chain. It records the greedy construction, Linnik's double-exponential upper bound, the conjectural polylogarithmic least-prime bound, and Ford--Konyagin--Luca as known context.

Literature audit

(b) The original source is Paul Erdős, Some unconventional problems in number theory, Astérisque 61 (1979), 73--82 (primary PDF). On pp. 80--81 he states the prime-chain questions and derives the double-exponential construction from Linnik's theorem.

(b) Kevin Ford, Sergei V. Konyagin, and Florian Luca, Prime chains and Pratt trees, Geom. Funct. Anal. 20 (2010), 1231--1258, doi:10.1007/s00039-010-0089-0, arXiv:0904.0473, is the cited primary research paper. It defines $H(p)$ as the longest prime-chain length ending at $p$, proves the effective chain-counting bound

N(x;p)\leq x\exp\!\left\{ \frac{\log x(\log_3x+O(1))}{\log_2x}\right\},

and proves $H(p)\leq(\log p)^{0.9503}$ for almost all primes $p$. The qualifier “almost all” is essential below.

(b) Gérald Tenenbaum's historical survey, Some of Erdős' unconventional problems in number theory, thirty-four years later (Bolyai Soc. Math. Stud. 25 (2013), 651--681; corrected version arXiv:1908.00488), explicitly says that both questions were still open and points to Ford--Konyagin--Luca for the partial progress.

(b) Douglas S. Stones, On prime chains, arXiv:0908.2166, treats the much more special recurrence $x_{j+1}=ax_j+b$. In particular it proves that no fixed pair $(a,b)$ produces an infinite strictly increasing all-prime sequence. This does not cover the varying multipliers in #695.

(d) I additionally queried arXiv for the exact phrases “prime chains” and “Pratt tree”, searched the exact displayed limit/bound on the web, and screened the 20 works which OpenAlex currently indexes as citing the 2010 paper. I found related work on fixed-multiplier chains, Pratt trees with missing primes, and iterated totients, but no later primary source claiming either question here. This is a documented search miss, not a proof that no such paper exists. The live page remains the authoritative current-status source.

An exact multiplier reduction

(a) There is no asymptotic loss in assuming $p_1=2$: if a chain starts with an odd prime, prepend $2$, since every odd prime is $1\bmod 2$. This only shifts the index by one.

(a) Put

m_i=\frac{p_{i+1}-1}{p_i}\in\mathbb Z_{>0}.

Then

\begin{aligned} \log p_k &=\log p_1+\sum_{i<k}\log\frac{p_{i+1}}{p_i}\\ &=\log p_1+\sum_{i<k}\log m_i+ \sum_{i<k}\log\left(1+\frac1{m_ip_i}\right). \end{aligned}

Because $p_i\geq i+1$ and $\log(1+x)\leq x$,

0\leq \sum_{i<k}\log\left(1+\frac1{m_ip_i}\right) \leq\sum_{i<k}\frac1{p_i}=O(\log k).

Consequently,

\boxed{\quad \log p_k=\log p_1+\sum_{i<k}\log m_i+O(\log k). \quad} \tag{1}

(a) Equation (1) gives an exact reformulation of the two targets:

$p_k^{1/k}\to\infty$ if and only if

\[ \frac1k\sum_{i<k}\log m_i\longrightarrow\infty. \]

The requested upper bound is, up to the negligible $O(\log k)$ term,

equivalent to finding one infinite prime-producing multiplier word with \[ \sum_{i<k}\log m_i\leq k(\log k)^{1+o(1)}. \]

This isolates the first question as a compulsory divergence of average multiplier cost and the second as construction of a low-cost infinite path.

Exact finite proposition through chain length 14

For primes $q,p$, write $q\prec p$ when $q\mid p-1$, and let $H(p)$ be the maximum number of vertices in a prime chain ending at $p$.

(a) The Pratt-height recurrence is

H(2)=1,\qquad H(p)=1+\max_{\substack{q\mid p-1\\q\ {\rm prime}}}H(q) \quad(p\ {\rm odd\ prime}). \tag{2}

Indeed, the penultimate member of any chain ending at $p$ is a prime factor $q\mid p-1$, and any longest chain ending at such a $q$ can be extended by $p$.

Define

M_h=\min\{p:p\text{ prime and }H(p)\geq h\}.

(a) It is enough to find the first prime of exact height $h$. If $H(p)>h$, iterating a maximizing predecessor in (2) produces a smaller prime of height exactly $h$. Thus any length-$h$ prime chain has terminal prime at least $M_h$, while a reconstructed height-$h$ chain ending at $M_h$ attains equality.

(d) Exhaustive enumeration gives the following sharp finite table. Each row states both the lower bound on every terminal prime and a chain attaining it.

| $h$ | exact $M_h$ | one attaining chain | |---:|---:|:---| | 1 | 2 | $2$ | | 2 | 3 | $2,3$ | | 3 | 7 | $2,3,7$ | | 4 | 23 | $2,5,11,23$ | | 5 | 47 | $2,5,11,23,47$ | | 6 | 283 | $2,5,11,23,47,283$ | | 7 | 719 | $2,5,11,89,179,359,719$ | | 8 | 1,439 | $2,5,11,89,179,359,719,1439$ | | 9 | 2,879 | $2,5,11,89,179,359,719,1439,2879$ | | 10 | 34,549 | $2,5,11,89,179,359,719,1439,2879,34549$ | | 11 | 138,197 | $2,5,11,89,179,359,719,1439,2879,34549,138197$ | | 12 | 1,266,767 | $2,5,11,89,179,359,719,1439,2879,316691,633383,1266767$ | | 13 | 14,619,833 | $2,3,7,127,509,1019,2039,4079,32633,65267,913739,1827479,14619833$ | | 14 | 36,449,279 | $2,5,11,89,179,359,719,8629,103549,2278079,4556159,9112319,18224639,36449279$ |

(d) For the last chain, the successive multipliers are

\[ (2,2,8,2,2,2,12,12,22,2,2,2,2). \]

The checker recomputes every primality and every divisibility rather than accepting this displayed certificate.

(d) The full height distribution among the $2{,}230{,}095$ primes $p\leq36{,}449{,}279$ is:

| $H(p)$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |:--|--:|--:|--:|--:|--:|--:|--:| | count | 1 | 5 | 540 | 66,057 | 562,164 | 852,412 | 514,493 |

| $H(p)$ | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |:--|--:|--:|--:|--:|--:|--:|--:| | count | 181,699 | 43,616 | 7,755 | 1,186 | 157 | 9 | 1 |

(d) The greedy chain through the same 14 lengths is

\begin{split} 2,3,7,29,59,709,2837,22697,590123,1180247,\\ 9441977,169955587,2719289393,5438578787. \end{split}

Thus the greedy chain already ceases to minimize the endpoint at length 4 ($29$ versus $23$); at length 14 its endpoint is $5{,}438{,}578{,}787$, whereas the globally least possible endpoint is $36{,}449{,}279$. This is finite evidence only and makes no asymptotic claim about the greedy chain.

Why the computation is exhaustive

The standalone verifier is erdos695_wavew010_verify.py. It uses no third-party packages and performs two independent calculations.

(a) Forward calculation: an Eratosthenes sieve first determines all primes through the cutoff. Primes $q$ are processed in increasing order. At that moment all prime factors of $q-1$ are smaller and have already propagated, so $H(q)$ is final. The code sends $H(q)+1$ to every prime $p\equiv1\bmod q$.

(a) Backward calculation: a separate smallest-odd-prime-factor sieve identifies and factors every $p-1$, without consulting the Eratosthenes flags. Scanning primes upward, it evaluates (2) directly. It then checks equality with the forward height at every one of the 2,230,095 primes, not just at the 14 records.

The core loops are:

# Forward
for q in increasing_primes:
    for prime_p in primes_congruent_to_1_mod_q:
        H_forward[prime_p] = max(H_forward[prime_p], H_forward[q] + 1)

# Backward
for p in increasing_primes:
    H_backward[p] = 1 + max(H_backward[q] for q in prime_factors(p - 1))
    assert H_backward[p] == H_forward[p]

(d) On this VM the final run took 21.23 seconds and 176,416 KiB peak RSS. Deterministic audit hashes are

sha256_prime_flags     = ba1d458fcb43e3040522d117feb209f9ac1f6cee1f8081d91633fe1fefc029f5
sha256_forward_heights = 5a9693b629f0a23e909f3885d96ac84f687199d0324de115fdcc01e8bee246aa

Reproduce with:

python runs/erdos695_wavew010_verify.py

The final line must be:

PASS: two independent exhaustive Pratt-height computations agree

Exact obstruction and remaining wall

(a) Fixed-multiplier reasoning cannot settle the first question. If $x_{t+1}=ax_t+1$, $x_0=p$ is prime, and $p>a$, then

x_t=a^tp+\frac{a^t-1}{a-1}.

Fermat's little theorem gives $p\mid x_{p-1}$, and $x_{p-1}>p$, so a constant-$a$ all-prime block has at most $p-2$ transitions. The verifier brute-checks this identity for small $p,a$. The obstruction length depends on the already enormous starting prime, however, and it says nothing strong enough about variable multiplier words of small average logarithmic cost.

(a,b) If the first question failed, there would be a constant $B$ and infinitely many indices $k$ with $p_k\leq B^k$. Since $H(p_k)\geq k$, these endpoints would satisfy

H(p_k)\geq \frac{\log p_k}{\log B}.

Ford--Konyagin--Luca's almost-all bound excludes this behavior for almost all primes but permits an exceptional zero-density set, and a single infinite chain could lie entirely in that exceptional set. A uniform extremal bound

H(p)=o(\log p)\qquad(p\to\infty)

would settle the first question, but the cited results do not provide it. Equivalently, the exact missing pathwise lemma is the divergence of the average multiplier cost in (1) for every infinite prime-producing word.

(b) Linnik's theorem gives constants $C,L$ such that the greedy successor can be chosen with $p_{i+1}\leq Cp_i^L$. Writing $y_i=\log p_i$ gives $y_{i+1}\leq Ly_i+O(1)$, hence only

p_i\leq\exp(\exp(O(i))).

The conjectural uniform estimate

\min\{q\text{ prime}:q\equiv1\bmod p\}\leq p(\log p)^C

would instead give $y_{i+1}\leq y_i+C\log y_i+O(1)$, hence $y_i=O(i\log i)$, which is more than enough for the second target.

(c) No cited unconditional theorem supplies that polylogarithmic successor at every recursively selected prime. The exact weaker task is to construct just one self-feeding path whose cumulative cost satisfies (1); average distribution results for moduli do not ensure that their good moduli link into one infinite path. This uniformity/path-selection gap, rather than primality testing or finite enumeration, is the present wall.

(d) A bounded one-backend pilot extended the search beyond the reported cutoff, but I omit its next putative record: its minimality was not independently recomputed within the chosen verification budget. Nothing beyond $h=14$ is claimed here.

PARTIAL: Exact multiplier-cost reduction and independently verified sharp terminal-prime bounds for every prime-chain length 1 through 14; the uniform exceptional-path lemma needed for either asymptotic question remains open.

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