Why Does This Recurrence Generate Primes?

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: https://youtu.be/OpaKpzMFOpg ---------------- 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/VOL11/Rowland/rowland21.html ---------------- 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: https://twitter.com/ericrowland