Ponder This Challenge - November 2025 - The CAT sequence

We generate a sequence of strings $s_0, s_1, s_2, \ldots$ in the following manner:

• $s_0$ = "CAT"
• $s_n$ is obtained from $s_{n-1}$ by substituting each letter of $s_{n-1}$ according to the following rules:

The first few steps yield the strings

And so forth. One can see from the list that $s_{3}[3..7]$ is "CACA" (here $[a..b]$ means "all the letters, starting from the index $a$, up to and not including the index $b$, where indexing starts from 0")

Your goal: Find $s_{n}[n..(n+1000)]$ for $n=10^{100}$

A bonus "*" will be given for finding $t_{n}[n..(n+1000)]$ for $n=10^{100}$ where the sequence $t$ is defined simiarily to $s$ but with the initial value $t_0$ = "RABBITS" and the rules

Solution

• Click here to view the solution

  The solutions are

  TGTGCTGCCATGCCACATTGCCACATCATTGCATTGTGCTGCCATGCCACATTGCCACATCATTGTGCCACATCATTGCATTGTGCTGCCACATCATTGCATTGTGCCATTGTGCTGCCACATTGTGCTGCCATGCCACATCATTGTGCTGCCATGCCACATTGCCACATCATTGCATTGTGCTGCCATGCCACATTGCCACATCATTGTGCCACATCATTGCATTGTGCCATTGTGCTGCCATGCCACATTGCCACATCATTGTGCCACATCATTGCATTGTGCTGCCACATCATTGCATTGTGCCATTGTGCTGCCACATTGTGCTGCCATGCCACATTGCCACATCATTGTGCCACATCATTGCATTGTGCTGCCACATCATTGCATTGTGCCATTGTGCTGCCATGCCACATCATTGCATTGTGCCATTGTGCTGCCACATTGTGCTGCCATGCCACATTGCCACATCATTGCATTGTGCCATTGTGCTGCCACATTGTGCTGCCATGCCACATCATTGTGCTGCCATGCCACATTGCCACATCATTGTGCCACATCATTGCATTGTGCCATTGTGCTGCCACATTGTGCTGCCATGCCACATCATTGTGCTGCCATGCCACATTGCCACATCATTGCATTGTGCTGCCATGCCACATTGCCACATCATTGTGCCACATCATTGCATTGTGCTGCCACATCATTGCATTGTGCCATTGTGCTGCCACATTGTGCTGCCATGCCACATCATTGTGCTGCCATGCCACATTGCCACATCATTGCATTGTGCTGCCATGCCACATTGCCACATCATTGTGCCACATCATTGCATTGTGCCATTGTGCTGCCATGCCACATTGCCACATCATTGTGCCACATCATTGCATTGTGCTGCCACATCATTGCATTGTGCCATTGTGCTGCCATGCCACATCATTGCATTGTGCCATTGTGCTGCCACATTGTGCTGCCATGCCACATCATTGTGCTGCCATGC
  

  And

  BRTGCBRICATGCISCATBRICAISBCATBRISBTGBRITGCISBRICAISBTGCISCATISBTGBRICAISBCATBRISBTGBRITGCISCATISBTGCATBRTGCISBTGBRITGCISCATBRTGCBRICATGCISCATISBTGBRITGCISBRICAISBTGCISCATISBTGCATBRTGCBRICATGCISCATBRICAISBCATBRTGCISCATISBTGCATBRTGCISBTGBRITGCISBRICAISBTGCISCATISBTGBRICAISBCATBRISBTGBRITGCISCATISBTGCATBRTGCISBTGBRITGCISCATBRTGCBRICATGCISCATBRICAISBCATBRTGCISCATISBTGCATBRTGCBRICAISBCATBRISBTGBRICATBRTGCBRICATGCISCATISBTGCATBRTGCISBTGBRITGCISCATBRTGCBRICATGCISCATBRICAISBCATBRISBTGBRICATBRTGCBRICAISBTGBRITGCISBRICAISBCATBRTGCBRICATGCISCATBRICAISBCATBRTGCISCATISBTGCATBRTGCISBTGBRITGCISCATBRTGCBRICATGCISCATISBTGBRITGCISBRICAISBTGCISCATISBTGCATBRTGCBRICATGCISCATBRICAISBCATBRTGCISCATISBTGCATBRTGCBRICAISBCATBRISBTGBRICATBRTGCBRICAISBTGBRITGCISBRICAISBCATBRTGCBRICATGCISCATBRICAISBCATBRISBTGBRITGCISBRICAISBTGCISCATISBTGBRICAISBCATBRISBTGBRICATBRTGCBRICATGCISCATBRICAISBCATBRTGCISCATISBTGCATBRTGCBRICAISBCATBRISBTGBRICATBRTGCBRICATGCISCATISBTGCATBRTGCISBTGBRITGCISCATBRTGCBRICATGCISCATISBTGBRITGCISBRI
  

  The key observation is that for each letter, the length of the word generated from that letter grows exponentially, so after a very managable number of steps (around 500) the generated words will already be of length $10^{100}$. This enables to compute the letter in a specific position in the following recursive manner, which was written very compactly in Python by Li Li (thanks!):

  D = {'G': 'T', 'T':'CA', 'C': 'TG', 'A': 'C'}
  #D = {'G': 'T', 'T': 'CA', 'C' : 'BR', 'A': 'I', 'R': 'B', 'B': 'IS', 'I': 'TG', 'S': 'C'}
  L = {}
  M = 600
  for c in D:
      L[c] = [1]*M
  for i in range(1,M):
      for c in D:
          L[c][i] = sum(L[d][i-1] for d in D[c])
  print(len(str(L['C'][500])))
  def returnstring (c, N, start, end):
      if end>=L[c][N]+1:
          return 'Error'
      if N == 0:
          return c
      if len(D[c])==1:
          return returnstring(D[c], N-1, start, end)
      if end<=L[D[c][0]][N-1]:
          return returnstring(D[c][0], N-1, start, end)
      if start>=L[D[c][0]][N-1]+1:
          return returnstring(D[c][1], N-1, start-L[D[c][0]][N-1],end-L[D[c][0]][N-1])
      else:
          return returnstring(D[c][0], N-1, start, L[D[c][0]][N-1])+returnstring(D[c][1], N-1, 1, end-L[D[c][0]][N-1])
  
  print(returnstring ('R', 500, 10**100+1,10**100+1000))
  

Solvers

• *Lazar Ilic (29/10/2025 1:26 PM IDT)
• *Paul Lupascu (29/10/2025 4:27 PM IDT)
• *Bert Dobbelaere (29/10/2025 9:35 PM IDT)
• *Bertram Felgenhauer (29/10/2025 10:53 PM IDT)
• *Dan Dima (29/10/2025 11:27 PM IDT)
• *Prashant Wankhede (29/10/2025 11:27 PM IDT)
• *King Pig (30/10/2025 5:42 AM IDT)
• *Guangxi Liu (30/10/2025 9:02 AM IDT)
• *Kang Jin Cho (30/10/2025 2:29 PM IDT)
• *Loukas Sidiropoulos (30/10/2025 7:47 PM IDT)
• *Vladimir Volevich (31/10/2025 10:37 AM IDT)
• Rudy Cortembert (31/10/2025 2:38 PM IDT)
• Juergen Koehl (31/10/2025 7:56 PM IDT)
• *Nadir S. (31/10/2025 11:03 PM IDT)
• *Shirish Chinchalkar (1/11/2025 12:36 AM IDT)
• *Ankit Chakraborty (1/11/2025 4:44 PM IDT)
• Reiner Martin (1/11/2025 5:55 PM IDT)
• *Kevin Cao (1/11/2025 6:08 PM IDT)
• Gary M. Gerken (2/11/2025 6:25 AM IDT)
• *Stephen Ebert (2/11/2025 11:07 AM IDT)
• Aayaam Panigrahi (2/11/2025 2:07 PM IDT)
• *John Tromp (2/11/2025 5:57 PM IDT)
• *Alper Halbutogullari (3/11/2025 8:23 AM IDT)
• *Manish Kumar (3/11/2025 8:29 AM IDT)
• *Latchezar Christov (3/11/2025 2:35 PM IDT)
• *Soonho You (4/11/2025 8:31 AM IDT)
• *Dillon Davis (4/11/2025 9:49 AM IDT)
• *Elias Krainer (4/11/2025 11:32 AM IDT)
• *Karl-Heinz Hofmann (4/11/2025 11:54 AM IDT)
• *Asad Raza (4/11/2025 8:33 PM IDT)
• *Martin Thorne (4/11/2025 8:42 PM IDT)
• Savitha Viswanadh Kandala (5/11/2025 3:57 PM IDT)
• *Ganor Tamir & Shouky Dan (5/11/2025 6:40 PM IDT)
• *Abraham AJ Arshad (5/11/2025 7:01 PM IDT)
• Sathi Gnaneswara Reddy (6/11/2025 4:02 PM IDT)
• *Jiri Spitalsky (7/11/2025 9:26 AM IDT)
• *Ignasi Guillén (7/11/2025 12:06 PM IDT)
• *Daniel Bitin (7/11/2025 5:29 PM IDT)
• *Peter Moser (8/11/2025 5:24 PM IDT)
• Lavanya Kannan (9/11/2025 9:07 PM IDT)
• Reda Kebbaj (10/11/2025 1:57 PM IDT)
• Alex Fleischer (10/11/2025 4:04 PM IDT)
• Steffen Wolf (10/11/2025 6:36 PM IDT)
• Suus Brommer (10/11/2025 10:05 PM IDT)
• *Asaf Zimmerman (10/11/2025 10:09 PM IDT)
• *Dieter Beckerle (11/11/2025 4:54 PM IDT)
• *Nyles Heise (12/11/2025 5:44 AM IDT)
• *Jordan Payette (12/11/2025 10:45 PM IDT)
• *Dominik Reichl (13/11/2025 8:56 PM IDT)
• *Hakan Summakoğlu (14/11/2025 8:41 PM IDT)
• *Eran Vered (15/11/2025 10:41 AM IDT)
• *Zachary Barbanell (16/11/2025 12:53 PM IDT)
• *Daniel Chong Jyh Tar (17/11/2025 12:16 AM IDT)
• *Hubert Puszklewicz (17/11/2025 8:49 AM IDT)
• Romeo III Manzanilla (19/11/2025 11:41 AM IDT)
• Morry Rampel Sami (19/11/2025 2:15 PM IDT)
• *Govind Raj Jujare & Hansraj Nahata (19/11/2025 9:02 PM IDT)
• *James Pepper (19/11/2025 11:24 PM IDT)
• Robert Berec (20/11/2025 6:19 PM IDT)
• *Marijonas Kaunas (20/11/2025 9:11 PM IDT)
• Fabio Michele Negroni (21/11/2025 12:08 PM IDT)
• Kandala Srinivas (21/11/2025 7:26 PM IDT)
• Divy Soni (21/11/2025 9:09 PM IDT)
• David Keyes (22/11/2025 11:06 AM IDT)
• Lorenz Reichel (22/11/2025 6:04 PM IDT)
• *Jan Fricke (22/11/2025 7:22 PM IDT)
• Hyung Sik Hwang (huehuehue) (25/11/2025 1:55 AM IDT)
• *Erik Hostens (25/11/2025 1:00 PM IDT)
• Stéphane Higueret (25/11/2025 4:13 PM IDT)
• *Yug Nakrani (26/11/2025 5:17 AM IDT)
• Amos Guler (27/11/2025 12:25 PM IDT)
• Ananda Raidu (27/11/2025 2:04 PM IDT)
• *Hongcheng Zhu (28/11/2025 7:48 PM IDT)
• Todd Will (28/11/2025 10:08 PM IDT)
• *Ankit Aggarwal (28/11/2025 11:28 PM IDT)
• Tim Walters (29/11/2025 4:05 AM IDT)
• Ahmet Yuksel (29/11/2025 9:50 AM IDT)
• *Motty Porat (30/11/2025 1:04 AM IDT)
• David Greer (30/11/2025 1:34 AM IDT)
• *Naftali Peles (30/11/2025 5:13 AM IDT)
• *Chris Shannon (30/11/2025 8:16 AM IDT)
• Kandala Viswakanth (30/11/2025 3:37 PM IDT)
• *David F.H. Dunkley (1/12/2025 2:53 AM IDT)
• Paul Revenant (1/12/2025 9:30 AM IDT)
• Stefan Wirth (1/12/2025 11:46 PM IDT)
• *Jackson La Vallee (3/12/2025 9:26 AM IDT)
• *Li Li (3/12/2025 8:31 PM IDT)
• *Erik Wünstel (4/12/2025 5:03 PM IDT)
• Zoltan Haindrich (4/12/2025 5:24 PM IDT)
• Karl D’Souza (4/12/2025 6:51 PM IDT)
• *Sanandan Swaminathan (4/12/2025 8:17 PM IDT)
• Wyatt Daviau (4/12/2025 8:37 PM IDT)
• Marco Bellocchi (5/12/2025 1:30 AM IDT)
• Karl Mahlburg (5/12/2025 5:22 AM IDT)
• Fakih Karademir (15/12/2025 4:39 PM IDT)