Summary: For the sequence defined by $a(n) = a(n-1) + gcd(n,a(n-1))$ with $a(1) = 7$ we prove that $a(n) - a(n-1)$ takes on only 1's and primes, making this recurrence a rare "naturally occurring" generator of primes. Toward a generalization of this result to an arbitrary initial condition, we also study the limiting behavior of $a(n)/n$ and a transience property of the evolution.

11A41, 11B37

prime-generating recurrence, prime formulas, discrete dynamical systems, greatest common divisor