Problem #460: Let $a_0=0$ and $a_1=1$, and in general define $a_k$ to be...

---

Progress

This question arose in work of Eggleton, Erdős, and Selfridge, who could prove that $a_k <k^{2+o(1)}$ for $k$ large enough depending on $n$, but conjectured that in fact $a_k\ll k\log k$ is true.

The problem above is from [Er77c]. This question is stated slightly differently in [ErGr80], which has $a_0=n$ instead of $a_0=0$ and $1\leq i<k$ instead of $0\leq i<k$. The material difference this makes is that the main formulation above has $(a_k,n)=1$ for all $k\geq 1$, which is not imposed in the second formulation. Furthermore, in both [Er77c] and [ErGr80] this is stated without the restriction to $a_k<n$ in the sum, although perhaps this was implicitly intended. Without this condition the sum is infinite since the sequence of $a_k$ contains $n+p$ for all primes $p>n$ (this observation was made by Svyable using ChatGPT).

Unfortunately, although both sources mention a forthcoming paper of Eggleton, Erdős, and Selfridge, I cannot find a candidate paper of theirs with this problem in, and hence the motivation behind this problem, and what the precise problem intended was, is unclear.

Chojecki has noted in the comments that a positive solution to the main problem would follow if\[f(n) = \sum_{a<n}1_{P^-(n-a)>a}\frac{1}{a}\to \infty,\]where $P^-(\cdot)$ is the least prime factor. Standard estimates on rough numbers show that $\frac{1}{N}\sum_{n\leq N}f(n)\gg \log\log N$, so $f(n)$ does diverge on average, but it is unclear whether $f(n)\to \infty$ for all $n$.