Connect with us:    

IBM Research YouTube IBM Research Blog

Ponder This

Welcome to our monthly puzzles.
You are cordially invited to match wits with some of the best minds in IBM Research.

September 2023 - Challenge

<< August October >>

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: 

11, 12, 15, 16, 17, 18, 19, 20, 21, 22, 33, 36,...
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}): 
1, 3, 1, 1, 1, 1, 1, 1, 1, 11, 3, ...
(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 
3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, 941, 3, 7, 1889, ...
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

 

Challenge: 28/08/2023 @ 15:30 PM EST
Solution: 05/10/2023 @ 12:00 PM EST
List Updated: 06/11/2023 @ 12:10 PM EST

People who answered correctly:

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)