The recurrence R(n) = R(n - 1) + gcd(n, R(n - 1)) generates primes. But why? It turns out it's essentially implementing trial division in disguise.

Previous video on this sequence:    • In 2003 We Discovered a New Way to Ge...  

----------------

Reference:

Eric Rowland, A natural prime-generating recurrence, Journal of Integer Sequences 11 (2008) 08.2.8 (13 pages).
https://cs.uwaterloo.ca/journals/JIS/...

----------------

0:00 Generating primes
1:26 Shortcut
4:42 What if 2 n - 1 is prime?
9:31 What if 2 n - 1 isn't prime?
14:46 Trial division

----------------

Animated with Manim. https://www.manim.community
Music by Callistio.
Audio recorded at the Lawrence Herbert School of Communication at Hofstra University. https://www.hofstra.edu/communication/

Web site: https://ericrowland.github.io
Twitter:   / ericrowland