Journal of Integer Sequences, Vol. 11 (2008), Article 08.2.8

A Natural Prime-Generating Recurrence

Eric S. Rowland
Department of Mathematics
Rutgers University
Piscataway, NJ 08854


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.

Full version:  pdf,    dvi,    ps,    latex,     editor's introduction

(Concerned with sequences A084662 A084663 A106108 A132199 A134162 A135506 and A137613.)

Received July 1 2008; revised version received July 20 2008. Published in Journal of Integer Sequences, July 20 2008.

Return to Journal of Integer Sequences home page