# Prime-Generating Recurrence

Prime-Generating Recurrence

This Demonstration explores solutions of the recurrence through the difference sequence , which exhibits complex behavior. For the initial condition , the sequence consists entirely of s and primes, making this recurrence a rare "naturally occurring" generator of primes.

a(n)=a(n-1)+gcd(n,a(n-1))

a(n)-a(n-1)

a(1)=7

a(n)-a(n-1)

1

This result is not true in general: for example, letting produces , and letting produces . However, for these initial conditions, the difference sequence eventually consists entirely of s and primes. It is an unsolved problem to determine whether all initial conditions eventually produce only s and primes.

a(1)=532

a(18)-a(17)9

a(1)=800

a(21)-a(20)21

1

1

You can choose to view all terms of the difference sequence or only the terms which are not .

1