Ponder This Challenge - March 2024 - Composite Sequences

This problem was suggested by Latchezar Christov - thanks Latchezar!

Let $X_n$ be the sequence of $n$ natural numbers $a_0, a_1,\ldots, a_{n-1}$ for which three properties are true:

1. $a_i=a_{i-1} + i$ for $0 < i < n$
2. None of the sequence terms is prime.
3. There is no other sequence with the above properties and a smaller initial term $a_0$.

Please note that because of property #1, there will only be n numbers in the sequence, for any given n.

The first such sequences are:

• $X_1 = [1]$
• $X_2 = [8,9]$
• $X_3 = [9,10,12]$
• $X_4 = [9,10,12,15]$
• $X_5 = [15,16,18,21,25]$

Your Goal: Please find the initial term $a_0$ of the sequence $X_{1000}$

A Bonus "*" will be given for finding the initial term $a_0$ of the sequence $X_{2024}$

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

  March 2024 Solution:

  The solution for $X_{1000}$ is 115192665.

  The solution for $X_{2024}$ is 117778830159.

  The $X_{2024}$ case is difficult to obtain, usually requiring low-level optimizations. Here is one approach for example, as described by Asaf Zimmerman:

  I implemented a straightforward check, using a sieve for primality check.

  To be able to run the 2024 case (i.e. to hundreds of billions) I used the following optimizations:

  1. the sieve excluded numbers divisible by 2,3 or 5 (so only 8 remainders modulo 30) which means it needed 8/30 bits for each number covered.
  2. the a0 candidates were batched in jumps of 30 so that they (and consecutive ai) shared a remainder modulo 30 and some checks could be skipped altogether for the entire batch when they all divisible by 2, 3 or 5. this made the checks compatible with the sieve structure
  3. vectorization and caching using the bit structure of the sieve to check 32 numbers in a single operation.

  This was enough to reduce the run time to around 1hr using python+numpy covering numbers to 300,000,000,000

Solvers

• *Lazar Ilic (3/3/2024 11:13 AM IDT)
• Evan Semet (3/3/2024 12:27 PM IDT)
• Dan Dima (3/3/2024 1:08 PM IDT)
• *Alper Halbutogullari (3/3/2024 1:32 PM IDT)
• *Daniel Chong Jyh Tar (3/3/2024 1:32 PM IDT)
• Ashfaque Shaikh (3/3/2024 1:53 PM IDT)
• *Hugo Pfoertner (3/3/2024 2:03 PM IDT)
• Lorenz Reichel (3/3/2024 2:15 PM IDT)
• *Bert Dobbelaere (3/3/2024 3:29 PM IDT)
• Guillaume Escamocher (3/3/2024 3:53 PM IDT)
• Laurence Warne (3/3/2024 5:13 PM IDT)
• *Dominik Reichl (3/3/2024 6:17 PM IDT)
• Kang Jin Cho (3/3/2024 6:43 PM IDT)
• Vamsi Krishna Talupula (3/3/2024 7:17 PM IDT)
• *John Tromp (3/3/2024 7:27 PM IDT)
• Rudy Cortembert (3/3/2024 8:01 PM IDT)
• Giorgos Kalogeropoulos (3/3/2024 8:46 PM IDT)
• *Yi Jiang (3/3/2024 9:11 PM IDT)
• Amos Guler (3/3/2024 9:14 PM IDT)
• *Victor Chang (3/3/2024 10:13 PM IDT)
• Michael Branicky (3/3/2024 10:20 PM IDT)
• Fabio Michele Negroni (3/3/2024 10:35 PM IDT)
• *Michael Liepelt (3/3/2024 10:56 PM IDT)
• *Sanandan Swaminathan (4/3/2024 12:30 AM IDT)
• *Bertram Felgenhauer (4/3/2024 12:43 AM IDT)
• Michał Franczak (4/3/2024 1:43 AM IDT)
• *Reiner Martin (4/3/2024 2:29 AM IDT)
• Shirish Chinchalkar (4/3/2024 2:33 AM IDT)
• *Joaquim Carrapa (4/3/2024 3:53 AM IDT)
• *Cameron Ritson (4/3/2024 4:07 AM IDT)
• Kipp Johnson (4/3/2024 4:31 AM IDT)
• Peter Williams (4/3/2024 5:52 AM IDT)
• *Reda Kebbaj (4/3/2024 7:05 AM IDT)
• Dwij Mehta (4/3/2024 8:02 AM IDT)
• *Zachary Chan (4/3/2024 9:38 AM IDT)
• *Dieter Beckerle (4/3/2024 10:23 AM IDT)
• Christofer Ohlsson (4/3/2024 10:52 AM IDT)
• *Serge Batalov (4/3/2024 11:18 AM IDT)
• Guilliou Robin (4/3/2024 1:41 PM IDT)
• Paul Revenant (4/3/2024 3:26 PM IDT)
• Mathias Schenker (4/3/2024 4:23 PM IDT)
• Prashant Wankhede (4/3/2024 5:17 PM IDT)
• John Spurgeon (4/3/2024 5:21 PM IDT)
• Balakrishnan V (4/3/2024 5:36 PM IDT)
• Dheeraj Reddy (4/3/2024 8:40 PM IDT)
• *Karl-Heinz Hofmann (4/3/2024 8:59 PM IDT)
• Marcelo De Barros (4/3/2024 11:50 PM IDT)
• Kennedy (5/3/2024 12:19 AM IDT)
• *Alexander Marschoun (5/3/2024 12:51 AM IDT)
• Wolfgang Kais (5/3/2024 2:05 AM IDT)
• *Jingran Lin (5/3/2024 2:22 AM IDT)
• *Daniel Bitin (5/3/2024 8:49 AM IDT)
• Christoph Schmidt (5/3/2024 9:24 AM IDT)
• Evan Schor (5/3/2024 9:45 AM IDT)
• *Gary M. Gerken (5/3/2024 9:57 AM IDT)
• Nigel Brumpton (5/3/2024 10:59 AM IDT)
• Alex Fleischer (5/3/2024 12:38 PM IDT)
• Evert van Dijken (5/3/2024 12:56 PM IDT)
• Tamir Ganor & Shouky Dan (5/3/2024 2:39 PM IDT)
• Graham Hemsley (5/3/2024 4:51 PM IDT)
• *Alexander Daryin (5/3/2024 7:36 PM IDT)
• Thomas Egense (5/3/2024 8:58 PM IDT)
• Christoph Baumgarten (5/3/2024 10:40 PM IDT)
• Alex Izvalov (5/3/2024 11:45 PM IDT)
• Matt Cristina (6/3/2024 12:23 AM IDT)
• Kurt Foster (6/3/2024 3:23 AM IDT)
• Lorenzo Gianferrari Pini (6/3/2024 7:43 AM IDT)
• Quentin Higueret (6/3/2024 9:54 AM IDT)
• Clive Tong (6/3/2024 3:34 PM IDT)
• *Franciraldo Cavalcante (6/3/2024 6:57 PM IDT)
• *Guglielmo Sanchini (6/3/2024 6:59 PM IDT)
• Pattu Patnaik (6/3/2024 8:15 PM IDT)
• James Dow Allen (6/3/2024 9:06 PM IDT)
• Diana Gornea (6/3/2024 11:19 PM IDT)
• *King Pig (7/3/2024 8:23 AM IDT)
• *Arthur Vause (7/3/2024 12:31 PM IDT)
• *Vladimir Volevich (7/3/2024 1:17 PM IDT)
• Rajesh Sathiyanarayanan (7/3/2024 5:36 PM IDT)
• *Asaf Zimmerman (7/3/2024 9:30 PM IDT)
• Florian Sikora (8/3/2024 1:08 AM IDT)
• *Yan-Wu He (8/3/2024 3:15 AM IDT)
• Gyozo Nagy (8/3/2024 11:16 AM IDT)
• Ralf Jonas (8/3/2024 1:33 PM IDT)
• Sri Mallikarjun J (8/3/2024 3:53 PM IDT)
• Andrew Gauld (8/3/2024 4:21 PM IDT)
• Yash Pote (8/3/2024 5:40 PM IDT)
• *Hansraj Nahata (9/3/2024 4:36 AM IDT)
• Arnold Yim (9/3/2024 2:45 PM IDT)
• *Rashid Naimi (9/3/2024 5:29 PM IDT)
• Turgay Yuktas (9/3/2024 5:44 PM IDT)
• José Eduardo Gaboardi de Carvalho (9/3/2024 6:48 PM IDT)
• Wenjie Yang (9/3/2024 10:42 PM IDT)
• Hriday Ajinkya (9/3/2024 11:06 PM IDT)
• Julien Vincent Pradier (10/3/2024 1:03 AM IDT)
• *Grant Boudreaux (10/3/2024 6:02 AM IDT)
• Paul Lupascu (10/3/2024 10:21 AM IDT)
• *Ryoma Izumihara (10/3/2024 3:07 PM IDT)
• Andrew Scherbakov (10/3/2024 6:27 PM IDT)
• *Harald Bögeholz (10/3/2024 8:01 PM IDT)
• *Dezhi Zhao (11/3/2024 2:13 AM IDT)
• Mark J. Murphy (11/3/2024 3:29 AM IDT)
• Tim Walters (11/3/2024 11:04 PM IDT)
• Fred Cruz (12/3/2024 7:50 AM IDT)
• *Emmanuel Lazard (12/3/2024 5:56 PM IDT)
• Abdul Isik (13/3/2024 6:25 AM IDT)
• *Andreas Knüpfer (13/3/2024 10:06 AM IDT)
• Adrian Neacsu (13/3/2024 10:21 PM IDT)
• *Phil Proudman (13/3/2024 11:50 PM IDT)
• Shelby Doolittle (14/3/2024 3:33 AM IDT)
• Abhinav Bana (14/3/2024 4:36 AM IDT)
• Blaine Hill (15/3/2024 12:00 AM IDT)
• Piyush Agrawal (15/3/2024 11:17 AM IDT)
• Jean-Marie Madiot (15/3/2024 11:59 AM IDT)
• Stefan Wirth (15/3/2024 2:16 PM IDT)
• Karl D’Souza (15/3/2024 4:04 PM IDT)
• Senthan Sivatharan (15/3/2024 9:52 PM IDT)
• Manish Kumar & R. Subramanian & D. Antony Louis Piriyakumar (16/3/2024 6:00 PM IDT)
• *David Greer (16/3/2024 11:19 PM IDT)
• *Mark Pervovskiy (17/3/2024 12:13 AM IDT)
• *Karl Mahlburg (17/3/2024 2:23 AM IDT)
• *Marco Bellocchi (17/3/2024 5:40 AM IDT)
• *Fakih Karademir (17/3/2024 2:29 PM IDT)
• *Govind Jujare (17/3/2024 10:09 PM IDT)
• Arvind Venkatesan (17/3/2024 11:23 PM IDT)
• Jordan Rinder (18/3/2024 1:33 AM IDT)
• Marco Signoretto (18/3/2024 7:04 PM IDT)
• *David F.H. Dunkley (19/3/2024 5:53 PM IDT)
• Nikhil Mishra (19/3/2024 6:07 PM IDT)
• Dejan Stakic (19/3/2024 6:50 PM IDT)
• *Sean Egan (19/3/2024 10:55 PM IDT)
• *Nyles Heise (20/3/2024 3:41 AM IDT)
• Ethan EJ Watkins (20/3/2024 5:06 AM IDT)
• *Martin Thorne (20/3/2024 4:03 PM IDT)
• Wolfgang Glas (21/3/2024 2:30 AM IDT)
• Puvichakravarthy Ramachandran (21/3/2024 8:07 PM IDT)
• Dan Ismailescu (22/3/2024 8:36 PM IDT)
• Austin Lee (23/3/2024 4:07 PM IDT)
• *Andrea Andenna (23/3/2024 4:24 PM IDT)
• Hakan Summakoğlu (23/3/2024 8:42 PM IDT)
• David Kelly (25/3/2024 7:55 PM IDT)
• *Greg Janée (25/3/2024 11:00 PM IDT)
• Davi Yan Macedo Brandao (26/3/2024 12:09 AM IDT)
• *Mauro Bampo (26/3/2024 12:24 AM IDT)
• Soham Sud (26/3/2024 1:06 PM IDT)
• Igor Karp (26/3/2024 2:33 PM IDT)
• *Li Li (26/3/2024 4:54 PM IDT)
• Michael Swart (26/3/2024 7:41 PM IDT)
• Sanjay Rao (27/3/2024 9:34 AM IDT)
• *Ido Meisner (28/3/2024 3:21 AM IDT)
• *Chris Shannon (28/3/2024 7:55 AM IDT)
• Karthik G (28/3/2024 1:34 PM IDT)
• *Nicholas Daskalovic (28/3/2024 7:35 PM IDT)
• Andrew Fiorillo (28/3/2024 11:33 PM IDT)
• Armin Krauss (29/3/2024 5:50 PM IDT)
• David Vainapel (29/3/2024 8:41 PM IDT)
• *Chintan Maggu (30/3/2024 1:00 AM IDT)
• Nadir S. and Jonas Oja (30/3/2024 2:41 PM IDT)
• *Dillon Davis (30/3/2024 5:44 PM IDT)
• *K S (31/3/2024 12:40 AM IDT)
• Teawoo Kim (31/3/2024 2:40 AM IDT)
• *Liubing Yu (31/3/2024 7:05 AM IDT)
• Guy Daniel Hadas (31/3/2024 11:24 AM IDT)
• Stéphane Higueret (31/3/2024 1:33 PM IDT)
• Pavel Stoimenov (31/3/2024 3:09 PM IDT)
• *Heitor Fernandes (31/3/2024 3:32 PM IDT)
• Jose Coelho (31/3/2024 7:30 PM IDT)
• Justin Snopek (31/3/2024 8:00 PM IDT)
• *Mark Mammel (1/4/2024 12:21 AM IDT)
• Fabio Filatrella (1/4/2024 1:01 AM IDT)
• Hans-Peter Schrei (1/4/2024 1:47 AM IDT)
• Todd Will (1/4/2024 2:05 AM IDT)
• Jeffrey Curtis (1/4/2024 2:47 AM IDT)
• Noam Nisgav (2/4/2024 8:29 AM IDT)
• Shalev Zuriel (2/4/2024 8:29 AM IDT)
• *Zoltan Haindrich (2/4/2024 9:44 AM IDT)
• *Aviv Nisgav (2/4/2024 11:34 AM IDT)
• Brenton Bostick (2/4/2024 5:32 PM IDT)
• Sofia Kozlova (2/4/2024 9:01 PM IDT)
• Dario Filatrella (3/4/2024 4:27 PM IDT)
• Narayan Ramanathan (4/4/2024 12:26 AM IDT)
• Radu-Alexandru Todor (4/4/2024 3:22 AM IDT)
• *Motty Porat (4/4/2024 1:24 PM IDT)
• Ariel Erusalinsky (4/4/2024 1:55 PM IDT)
• Daniel Copeland (4/4/2024 3:47 PM IDT)
• Elena Pavlova (4/4/2024 9:54 PM IDT)
• Thomas Ilsche (5/4/2024 3:36 PM IDT)