Ponder This Challenge - November 2020 - The power game

The following game is played with a list of natural numbers (greater than 1). At each turn, one of the following two operations is performed:

1. The numbers a,b are removed from the list and the number a^b (a to the power of b) is added to the list.
2. A number of the form a^b (where a,b>1) is removed from the list, and the numbers a,b are added to the list.

Note that the list can contain multiple instances of the same number.

A game can be described by a sequence of lists, each obtained from the previous one by one of the operations above. As an example consider the following list:

The above list demonstrates how, starting with a list containing 64, a list containing 256 can be obtained via four steps (although two steps suffice).

To avoid writing large numbers explicitly, we can also use the shorthand notation for powers:

Your goal: Demonstrate a game that within 20 steps reaches a list containing the number 2147483647 (the Mersenne prime discovered by Euler). The initial list is constrained as follows. It cannot contain more than five numbers. 2. All the numbers except one should be at most 50. 3. The remaining number can be at most 1,000,000,000 Provide your game solution in the exact format presented above.

A bonus '*' for explaining (without giving the full game) how 2147483647 can be reached from a list containing the number 64 alone. More than 20 steps can be used.

Solution

• Click here to view the solution

  A simple solution can be based on the ability to use power manipulations to perform subtractions:

   4, 2^2, 31
   4, 2^2^31
   4^2^2^31
   4^2, 2^(2^31-1)
   4^2, 2, 2^31-1
  

  Even without the subtraction trick, there are many other methods of solution, e.g.,

   2, 2^4, 536870911, 2^3
   2, 2^2147483644, 2^3
   2^2^2147483644, 2^3
   2^2^2147483647
   2, 2^2147483647
   2, 2, 2147483647
  

  If we begin with 64, an endless stream of "2" can be generated:

   64
   2, 8
   256
   16, 2
   2^16
   2, 2^8
   16, 2, 2
  

  Repeating this and using a subtraction trick, one can reach 4, 2^2, 31 and proceed as before. Also, for those who love brute-force solutions, one can simply generate "2" for 2147483647 times and apply as powers on 2^2.

Solvers

• *Uoti Urpala (29/10/2020 11:25 PM IDT)
• *Tyler Mullen (29/10/2020 11:37 PM IDT)
• *Radu-Alexandru Todor (29/10/2020 11:51 PM IDT)
• *Bert Dobbelaere (30/10/2020 12:00 AM IDT)
• *Dan Dima (30/10/2020 3:06 PM IDT)
• *Seth Cohen (30/10/2020 7:15 PM IDT)
• *Eden Saig (30/10/2020 7:30 PM IDT)
• *Dominik Reichl (30/10/2020 9:33 PM IDT)
• *Florian Fischer (31/10/2020 12:00 AM IDT)
• *John Tromp (31/10/2020 1:01 AM IDT)
• *Victor Chang (31/10/2020 1:15 AM IDT)
• Clive Tong (31/10/2020 1:42 PM IDT)
• *Motty Porat (31/10/2020 4:06 PM IDT)
• Dan Piponi (31/10/2020 7:32 PM IDT)
• *Alper Halbutogullari (31/10/2020 10:27 PM IDT)
• *Bertram Felgenhauer (1/11/2020 4:23 AM IDT)
• *Harald Bögeholz (1/11/2020 4:59 AM IDT)
• *Lorenz Reichel (1/11/2020 12:17 PM IDT)
• Guillaume Escamocher (1/11/2020 3:57 PM IDT)
• Raymond Nicholson (1/11/2020 4:31 PM IDT)
• Jim Roche (1/11/2020 7:52 PM IDT)
• *Au Lawrence (1/11/2020 8:09 PM IDT)
• Reiner Martin (2/11/2020 12:17 AM IDT)
• *Aaron Chong (2/11/2020 12:56 AM IDT)
• *Jacob Burnim (2/11/2020 8:26 AM IDT)
• Srinivas Vasudevan (2/11/2020 8:40 AM IDT)
• *Vladimir Volevich (2/11/2020 11:42 PM IDT)
• *Kai Guttmann (3/11/2020 1:58 AM IDT)
• *David Greer (3/11/2020 2:32 AM IDT)
• *Karl Mahlburg (3/11/2020 4:47 AM IDT)
• Graham Hemsley (3/11/2020 12:42 PM IDT)
• *Amos Guler (3/11/2020 1:01 PM IDT)
• *Muralidhar Seshadri (3/11/2020 6:57 PM IDT)
• *Daniel Stanley (3/11/2020 11:33 PM IDT)
• *Karl D’Souza (4/11/2020 2:17 AM IDT)
• *James Muir (4/11/2020 7:08 PM IDT)
• *Ben Lee (4/11/2020 7:27 PM IDT)
• *Rainy Sokhonn (4/11/2020 8:03 PM IDT)
• *Jacob Bandes-Storch (4/11/2020 9:55 PM IDT)
• Almog Yair (5/11/2020 2:42 AM IDT)
• Nguyen Khac Tung (5/11/2020 6:27 AM IDT)
• *Oscar Volpatti (5/11/2020 10:24 AM IDT)
• *Ilya Tarygin (5/11/2020 10:06 PM IDT)
• *Dieter Beckerle (6/11/2020 10:26 AM IDT)
• *Pål Hermunn Johansen (7/11/2020 4:35 AM IDT)
• *Amir Sarid (7/11/2020 8:00 PM IDT)
• *Dylan themathgeek (8/11/2020 12:39 PM IDT)
• *Hu Shuai (8/11/2020 2:27 PM IDT)
• *Brian Patton (9/11/2020 4:03 AM IDT)
• *Xiao Liu (9/11/2020 5:19 PM IDT)
• *Thomas HUET (10/11/2020 9:05 AM IDT)
• *Eitan Levine (10/11/2020 9:54 AM IDT)
• *Arthur Vause (9/11/2020 11:57 AM IDT)
• *Jonathan Kariv (9/11/2020 8:58 PM IDT)
• *James Dow Allen (10/11/2020 4:11 PM IDT)
• Rif A. Saurous (10/11/2020 6:28 PM IDT)
• *Benjamin Lui (10/11/2020 6:34 PM IDT)
• *Liubing Yu (11/11/2020 8:04 AM IDT)
• *Marco Bellocchi (11/11/2020 8:04 PM IDT)
• *Chuck Carroll (11/11/2020 8:38 PM IDT)
• *Daniel Chong Jyh Tar (12/11/2020 8:17 AM IDT)
• *Chris Shannon (13/11/2020 9:59 AM IDT)
• *Oliver Gronau (13/11/2020 7:38 PM IDT)
• *Ivo Zerkov (13/11/2020 9:37 PM IDT)
• *K S (15/11/2020 12:57 AM IDT)
• *Sean Egan (15/11/2020 12:37 AM IDT)
• *Shouky Dan & Tamir Ganor (15/11/2020 6:29 PM IDT)
• JJ Rabeyrin (15/11/2020 11:29 PM IDT)
• Ricardo Koller (16/11/2020 12:00 AM IDT)
• *Daniel Bitin (18/11/2020 7:21 PM IDT)
• Iván Rendo Barreiro (18/11/2020 8:12 PM IDT)
• *Yasodhar Patnaik (19/11/2020 5:14 AM IDT)
• Sebastian Bohm & Martí Bosch (20/11/2020 3:06 PM IDT)
• *Tommy Pensyl (20/11/2020 11:46 PM IDT)
• Ananda Raidu (21/11/2020 2:16 PM IDT)
• *Tejas Deshpande (21/11/2020 5:00 PM IDT)
• *Jens Voß (22/11/2020 11:16 AM IDT)
• *Colas Kerkhove (24/11/2020 11:46 AM IDT)
• *Ingo Ogertschnig (25/11/2020 12:52 AM IDT)
• *Govind Raj Jujare (26/11/2020 1:37 AM IDT)
• *Dan Salajan (26/11/2020 12:29 AM IDT)
• *Andreas Stiller (26/11/2020 11:00 PM IDT)
• Li Wang (29/11/2020 2:11 PM IDT)
• *Zhou Hangbo (29/11/2020 2:22 PM IDT)
• Todd Will (29/11/2020 8:54 PM IDT)
• *Igor Karp (29/11/2020 8:57 PM IDT)
• *Hansraj Nahata (30/11/2020 1:34 AM IDT)
• Michael Branicky (30/11/2020 6:08 AM IDT)
• *Rostyslav Hermanyuk (30/11/2020 6:40 PM IDT)
• *Kang Jin Cho (30/11/2020 11:34 PM IDT)
• *Li Li (1/12/2020 7:39 AM IDT)
• Daniel Moolman (1/12/2020 3:03 PM IDT)
• *Vincent Beaud (3/12/2020 10:39 PM IDT)