Problem #473: Is there a permutation $a_1,a_2,\ldots$ of the positive...

---

Progress

Asked by Segal. The answer is yes, as shown by Odlyzko (although no reference is given).

Watts has suggested that perhaps the obvious greedy algorithm defines such a permutation - that is, let $a_1=1$ and let\[a_{n+1}=\min \{ x : a_n+x\textrm{ is prime and }x\neq a_i\textrm{ for }i\leq n\}.\]In other words, do all positive integers occur as some such $a_n$? Do all primes occur as a sum?

In the comments van Doorn has noted that the answer to the latter question is no, since $197$ does not appear as a sum from such a greedy sequence.

In [ErGr80] they also note that Segal asked the finite version: is there, for all $n\geq 2$, a permutation $a_1,\ldots,a_n$ of $\{1,\ldots,n\}$ such that $a_k+a_{k+1}$ is prime for $1\leq k<n$. The answer is likely yes on probabilistic grounds, and is true for infinitely many $n$ (see this discussion).