Transience conjecture for the natural prime-generating recurrence

Let $a(n)$ be the sequence defined by the recurrence in the paper, and let $n_1\geq 1$ satisfy $a(n_1)\geq 1$ . Transience conjecture. There exists an $N$ such that $a(n)-a(n-1)$ is $1$ or prime for every $n>N$ . The conjecture asserts that the states for which the local lemma does not apply are transient. It is motivated by computations showing non-prime values of the recurrence's gcd can occur initially, but suggesting that eventually every increment is $1$ or prime.

Sources & referencesView supporting material

Primary source

Eric S. Rowland, “A natural prime-generating recurrence”, arXiv:0710.3217 (2008).

number-theory prime-generating-sequences

1 week ago

Progress summary

Refreshed 5 days ago

Open

No proof or counterexample has been reported; only special starting values are known to produce prime-or-one increments eventually.

Eric Rowland formulated the conjecture for the recurrence $a(n)=a(n-1)+\gcd(n,a(n-1))$ . It predicts that exceptional non-prime increments are transient for every admissible initial state.

Known results

For $a(1)=7$ , every increment from $n\geq 2$ is $1$ or prime (Rowland).
Analogous results hold for some other initial values, including $a(1)=4$ and $a(1)=8$ .
The stronger assertion that every increment is always $1$ or prime is false: examples include $g(18)=9$ for $a(1)=532$ and $g(21)=21$ for $a(1)=801$ .
A sufficient reduction is to show that some later ratio $a(N)/N$ lies in $\{1,2,3\}$ , but no general proof is known.

Current status (as of August 2026): The conjecture remains open for general initial conditions; special cases and the failure of the stronger all-time claim are settled.

Sources

No solutions have been posted yet.