Prime-Generating Recurrence

initial condition

7

steps

terms

all terms

only nontrivial terms

visualization

list

log plot

This Demonstration explores solutions of the recurrence

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

through the difference sequence

a(n)-a(n-1)

, which exhibits complex behavior. For the initial condition

a(1)=7

, the sequence

a(n)-a(n-1)

consists entirely of

1

s and primes, making this recurrence a rare "naturally occurring" generator of primes.

This result is not true in general: for example, letting

a(1)=532

produces

a(18)-a(17)9

, and letting

a(1)=800

produces

a(21)-a(20)21

. However, for these initial conditions, the difference sequence eventually consists entirely of

1

s and primes. It is an unsolved problem to determine whether all initial conditions eventually produce only

1

s and primes.

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

1

.