Ponder This Challenge - September 2023 - Prime Number Generation using GCD

This riddle was proposed by Marco Bellocchi - thanks Marco!

Define a sequence $a_1, a_2, a_3$ recursively by setting $a_n = a_{n-1}+\text{gcd}(n, a_{n-1})$ where $\text{gcd}(x, y)$ denotes the greatest common divisor (GCD) of the pair of numbers x, y.
For example, when $a_1 = 11$ we have $a_2=12$ since $\text{gcd}(2,11)=1$, and we have $a_3=15$ because $\text{gcd(3,12)=3}$.
Continuing, we arrive at the sequence:

We now look at the sequence of differences beginning from $n=2$, $d_n=a_n-a_{n-1}=\text{gcd}(n, a_{n-1})$:

(i.e., $d_2=1$ is the first element of the sequence, $d_3=3$ is the second, etc.)

A curious property enjoyed by this sequence is that it contains only the number 1 and the prime numbers 3, 11. If we continue this sequence long enough and erase all the occurrences of 1, we arrive at this sequence

which contains only prime numbers. It can be proven that indeed, when $a_1=11$, all elements of the sequence obtained in this manner will be prime.

Returning to the original difference sequence, it is easy to see that $3=d_{3}=d_{12}=d_{24}=d_{48}=d_{51}$ and these are the first 5 occurrences of 3 in the sequence. Hence, 3 appears for the fifth time for $n=51$.

Your goal: For the sequence defined by $a_1=531$, find the value of $n$ for which 5 appears for the tenth time.

In addition, find values $k, n$ such that for the sequence defined by the initial value $a_1=k$, we have $d_n>1$ but not a prime.

A Bonus "*" will be given for finding, for the sequence defined by $a_1=531$, the value of $n$ for which 5 appears for the 200th time.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  September 2023 Solution:

  The solutions are 79820644 and 202373481820525416280764330407686074634 ($\pm 1$, depending on how you're counting).

  The paper ["A Natural Prime-Generating Recurrence"] by Eric S. Rowland gives a good overview of this this nice prime-generation method. While the main solution can be reached by rather naive programming, the bonus one requires additional tricks, and Rowland gives a nice trick allowing to bypass the "1" elements of the sequence, with the price being the need to factor numbers (or rather, find the smallest factor)

Solvers

• Lazar Ilic (30/8/2023 2:35 PM IDT)
• Daniel Chong Jyh Tar (30/8/2023 4:41 PM IDT)
• Alex Fleischer (30/8/2023 6:04 PM IDT)
• Grant Boudreaux (30/8/2023 6:20 PM IDT)
• Paul Revenant (30/8/2023 8:30 PM IDT)
• *Reda Kebbaj (30/8/2023 11:14 PM IDT)
• *Alper Halbutogullari (30/8/2023 11:15 PM IDT)
• *Franciraldo Cavalcante (31/8/2023 12:38 AM IDT)
• Kipp Johnson (31/8/2023 2:41 AM IDT)
• *Bertram Felgenhauer (31/8/2023 2:53 AM IDT)
• Prashant Wankhede (31/8/2023 6:17 AM IDT)
• *Giorgos Kalogeropoulos (31/8/2023 11:06 AM IDT)
• Xiao Liu (31/8/2023 11:07 AM IDT)
• Christofer Ohlsson (31/8/2023 12:05 PM IDT)
• John Tromp (31/8/2023 12:30 PM IDT)
• *Sanandan Swaminathan (31/8/2023 1:06 PM IDT)
• Ralf Jonas (31/8/2023 3:36 PM IDT)
• *Yan-Wu He (31/8/2023 6:38 PM IDT)
• *Ariel Landau (31/8/2023 11:11 PM IDT)
• *Andrew Gauld (1/9/2023 8:58 AM IDT)
• Dieter Beckerle (1/9/2023 10:27 AM IDT)
• *Vladimir Volevich (1/9/2023 11:40 AM IDT)
• Thomas Egense (1/9/2023 1:37 PM IDT)
• Jon Namnath (1/9/2023 2:50 PM IDT)
• Fabio Michele Negroni (1/9/2023 3:09 PM IDT)
• *Lorenzo Gianferrari Pini (1/9/2023 3:16 PM IDT)
• Florian Sikora (1/9/2023 3:53 PM IDT)
• Guillaume Escamocher (1/9/2023 3:59 PM IDT)
• *Lorenz Reichel (1/9/2023 6:09 PM IDT)
• Erik Wünstel (1/9/2023 7:13 PM IDT)
• Blaine Hill (1/9/2023 7:48 PM IDT)
• *Latchezar Christov (1/9/2023 9:50 PM IDT)
• Rashid Naimi (2/9/2023 4:43 AM IDT)
• Evan Semet (2/9/2023 7:49 AM IDT)
• *David Greer (2/9/2023 11:04 AM IDT)
• *Gary M. Gerken (2/9/2023 4:35 PM IDT)
• Matt Cristina (3/9/2023 1:10 AM IDT)
• Shouky Dan & Tamir Ganor (3/9/2023 10:06 AM IDT)
• Albert Stadler (3/9/2023 1:03 PM IDT)
• Amos Guler (3/9/2023 1:38 PM IDT)
• Reiner Martin (3/9/2023 2:57 PM IDT)
• *Hansraj Nahata (3/9/2023 6:40 PM IDT)
• Michael Liepelt (3/9/2023 11:30 PM IDT)
• *Mark Beyleveld (3/9/2023 11:45 PM IDT)
• Victor Chang (4/9/2023 1:34 AM IDT)
• Marcelo De Barros (4/9/2023 7:30 AM IDT)
• Serino Dario (4/9/2023 9:15 AM IDT)
• Yasodhar Patnaik (4/9/2023 1:31 PM IDT)
• Quentin Higueret (4/9/2023 4:40 PM IDT)
• Hakan Summakoğlu (4/9/2023 5:35 PM IDT)
• *Guglielmo Sanchini1 (4/9/2023 6:46 PM IDT)
• Kang Jin Cho (4/9/2023 6:55 PM IDT)
• *Alain Michiels (4/9/2023 8:03 PM IDT)
• Marco Bandiera (4/9/2023 11:55 PM IDT)
• Michael Branicky (5/9/2023 12:35 AM IDT)
• *Li Li (5/9/2023 2:56 AM IDT)
• *Yi Jiang (5/9/2023 7:10 AM IDT)
• Yannick Müller (5/9/2023 8:41 AM IDT)
• Joaquim Carrapa (5/9/2023 5:00 PM IDT)
• Stéphane Higueret (5/9/2023 7:15 PM IDT)
• Kamlesh Nahata (5/9/2023 7:49 PM IDT)
• *Martin Thorne (5/9/2023 8:13 PM IDT)
• Dieter Beckerle (5/9/2023 8:20 PM IDT)
• *David F.H. Dunkley (6/9/2023 12:52 AM IDT)
• *Guglielmo Sanchini1 (6/9/2023 12:09 PM IDT)
• Viswanadh Kandala (6/9/2023 1:14 PM IDT)
• Michael Chirozzi (6/9/2023 4:30 PM IDT)
• *Dan Dima (6/9/2023 5:38 PM IDT)
• José Eduardo Gaboardi de Carvalho (7/9/2023 2:08 AM IDT)
• *Mark Beyleveld (7/9/2023 4:09 PM IDT)
• *Tim Walters (7/9/2023 6:08 PM IDT)
• *Dominik Reichl (7/9/2023 6:15 PM IDT)
• Dheeraj Reddy (9/9/2023 1:46 PM IDT)
• Kandala Srinivas (9/9/2023 2:11 PM IDT)
• *Guy Daniel Hadas (9/9/2023 5:43 PM IDT)
• Clive Tong (9/9/2023 7:37 PM IDT)
• Rodrigo Viana Rocha (9/9/2023 8:38 PM IDT)
• Sachal Mahajan (9/9/2023 8:51 PM IDT)
• *Dan Ismailescu (10/9/2023 4:29 AM IDT)
• Phil Proudman (10/9/2023 7:08 PM IDT)
• *Govind Jujare (10/9/2023 11:58 PM IDT)
• Nicolas Paris (11/9/2023 9:12 AM IDT)
• Abhinav Bana (11/9/2023 3:17 PM IDT)
• *Dario Filatrella (11/9/2023 5:46 PM IDT)
• Christoph Schmidt (11/9/2023 6:26 PM IDT)
• Sri Mallikarjun J (11/9/2023 7:17 PM IDT)
• Kandala Viswakanth (12/9/2023 3:56 PM IDT)
• Daniel Bitin (12/9/2023 5:00 PM IDT)
• Rashid Zia (13/9/2023 3:06 AM IDT)
• Thibault RENOU (13/9/2023 10:22 AM IDT)
• Paul Lupascu (13/9/2023 1:38 PM IDT)
• Abhinav Bana (13/9/2023 1:45 PM IDT)
• *Nyles Heise (13/9/2023 8:49 PM IDT)
• *George D. Logan (14/9/2023 5:57 AM IDT)
• Igor Karp (15/9/2023 8:56 PM IDT)
• *Lyes Belhoul (15/9/2023 10:59 PM IDT)
• Gyozo Nagy (15/9/2023 11:45 PM IDT)
• Prakash Jalan (16/9/2023 10:07 PM IDT)
• *Carl Löndahl (17/9/2023 10:14 AM IDT)
• *Karl Mahlburg (18/9/2023 3:59 AM IDT)
• *Harald Bögeholz (19/9/2023 12:15 AM IDT)
• Evert van Dijken (19/9/2023 10:44 AM IDT)
• *Aleksey Galak (19/9/2023 10:56 PM IDT)
• Julius Fritz Barth (21/9/2023 6:30 AM IDT)
• Hugo Pfoertner (22/9/2023 7:52 PM IDT)
• Christoph Baumgarten (23/9/2023 5:36 PM IDT)
• Adrian Neacsu (24/9/2023 11:52 PM IDT)
• Anders Bisbjerg Madsen (25/9/2023 10:48 PM IDT)
• Andras Varga (26/9/2023 12:09 PM IDT)
• Omid Gheibi (26/9/2023 2:36 PM IDT)
• *Armin Krauss (26/9/2023 4:36 PM IDT)
• Logan Howard (26/9/2023 7:57 PM IDT)
• Jonathan Martin (27/9/2023 4:28 AM IDT)
• Moignet Gabriel (27/9/2023 11:49 AM IDT)
• David Kelly (27/9/2023 10:41 PM IDT)
• Rayan Swidan (28/9/2023 1:47 AM IDT)
• *Aaron Kim (28/9/2023 1:59 AM IDT)
• Daniel Stadtmauer (28/9/2023 5:36 AM IDT)
• Ritson Cameron (28/9/2023 9:14 AM IDT)
• Thibaud LEROUX (28/9/2023 9:34 AM IDT)
• Serkan Muhcu (29/9/2023 2:23 AM IDT)
• Kai Guttmann (29/9/2023 10:27 AM IDT)
• Fabio Filatrella (29/9/2023 5:22 PM IDT)
• Ananda Raidu (29/9/2023 5:42 PM IDT)
• *Daniel Copeland & Whitney Fish & Isaac Lawrence (29/9/2023 7:53 PM IDT)
• Chris Shannon (29/9/2023 9:29 PM IDT)
• Daniel Stadtmauer (30/9/2023 12:06 AM IDT)
• Eytan Rosenstock (30/9/2023 12:15 AM IDT)
• Rajesh Sathiyanarayanan (30/9/2023 3:00 PM IDT)
• *Motty Porat (1/10/2023 2:57 AM IDT)
• Sakai Jun (1/10/2023 4:38 AM IDT)
• Todd Will (1/10/2023 2:35 PM IDT)
• Fakih Karademir (1/10/2023 5:30 PM IDT)
• *Bert Dobbelaere (1/10/2023 11:37 PM IDT)
• Radu-Alexandru Todor (3/10/2023 3:34 AM IDT)
• *Nathan Salo (4/10/2023 5:46 AM IDT)
• Khadar Abdi (5/10/2023 7:18 AM IDT)
• Vaskor Basak & Kermit Rose (5/10/2023 7:09 PM IDT)