Ponder This Challenge - March 2022 - Primle

Primle

In the popular game Wordle, players attempt to guess a five-letter word. After each guess, the colors of the letter tiles change to reflect the guess. Green tiles represent a letter in the correct place; yellow tiles represent a letter present in the solution, but not in that place; and gray tiles represent a letter not present in the word at all. The submitted word has to be present in the game's dictionary; one cannot simply choose arbitrary letters.

We discuss a similar game, where instead of guessing a five-letter word, we attempt to guess an $n$-digit prime number (in the decimal system). As in the original Wordle, the guess must be a prime number. For this game, we want to pick a "good" initial guess. While there can be several ways to define "good" in this context, we choose the following: After the first guess, we obtain some pattern of green/yellow/gray connected to the digits in our guess. This pattern excludes some of the possible $n$-digit prime numbers. Let $f(p, q)$ be the number of remaining possible solutions after the first guess, given that $p$ was the guess and $q$ is the solution.

For example, if the solution is the four-digit prime number 4733 and our initial guess was 3637, the resulting pattern will be yellow-gray-green-yellow, and the possible remaining solutions are 1733, 2731, 4733, 7039, 7331, 7333, 7433, 7933, 8731, 9733, 9739.

Note the following exclusions from the possible solution set of the example:
* 6733 is excluded since 6 was gray, and so 6 is guaranteed not to be part of the solution.
* 3733 is excluded since the first '3' was yellow, and so 3 is guaranteed not to be the first digit.
* 2239 is excluded since 7 was yellow, but is not present at all in 2239.
So in this case, $f(3637, 4733)=11$. An even better initial guess would have been 8731, which would have resulted in $f(8731, 4733)=8$.

For $n$-digits, we wish to find a prime number $p$ which minimizes the expected value of $f(p,q)$ for a uniformly generated prime $q$. That is, we wish to minimize $E[p]\triangleq\sum_{q\in P}\frac{f(p,q)}{|P|}$ where $P$ is the set of $n$-digit primes.

Your goal: Find this $p$ for $n=5$ and compute $E[p]$. Return those two values as the solution.

A bonus "*" will be given for finding the solution for $n=7$.

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

  The solutions are 17923 for n = 5 and 1584269 for n = 7. Anders Kaseorg provided a more detailed list:

  For n = 1, every p = 2, 3, 5, 7 has E[p] = 5/2 = 2.5.

  For n = 2, best is p = 17 with E[p] = 89/21 = 4.238095238095238.

  For n = 3, best is p = 179 with E[p] = 149/11 = 13.545454545454545.

  For n = 4, best is p = 1237 with E[p] = 43997/1061 = 41.46748350612629.

  For n = 5, best is p = 17923 with E[p] = 1016453/8363 = 121.5416716489298.

  For n = 6, best is p = 124679 with E[p] = 13169147/34453 = 382.235131918846.

  For n = 7, best is p = 1584269 with E[p] = 729641181/586081 = 1244.9493858357462.

Solvers

• *Paul Revenant (3/3/2022 1:55 PM IDT)
• Daniel Chong Jyh Tar (3/3/2022 6:48 PM IDT)
• *Alper Halbutogullari (4/3/2022 1:02 AM IDT)
• *Bertram Felgenhauer (4/3/2022 2:48 AM IDT)
• *Anders Kaseorg (4/3/2022 3:11 AM IDT)
• *Victor Chang (4/3/2022 6:34 AM IDT)
• *Bert Dobbelaere (4/3/2022 9:21 AM IDT)
• Reiner Martin (4/3/2022 10:08 AM IDT)
• Radu-Alexandru Todor (4/3/2022 7:02 PM IDT)
• Jeremias Herrmann (4/3/2022 9:14 PM IDT)
• *Bertram Felgenhauer (4/3/2022 9:56 PM IDT)
• Sanandan Swaminathan (4/3/2022 11:26 PM IDT)
• Vladimir Volevich (5/3/2022 2:17 AM IDT)
• *Arthur Vause (5/3/2022 10:24 AM IDT)
• Dan Dima (5/3/2022 3:02 PM IDT)
• Vineet Dwivedi (5/3/2022 3:55 PM IDT)
• Graham Hemsley (5/3/2022 10:25 PM IDT)
• Michael Liepelt (6/3/2022 12:15 PM IDT)
• *Phil Proudman (6/3/2022 2:44 PM IDT)
• *Latchezar Christov (6/3/2022 8:17 PM IDT)
• *Amos Guler (6/3/2022 8:59 PM IDT)
• *Gary M. Gerken (6/3/2022 9:17 PM IDT)
• *John Goh (7/3/2022 3:40 AM IDT)
• *Dieter Beckerle (7/3/2022 9:31 AM IDT)
• *David Greer (7/3/2022 1:16 PM IDT)
• *Stéphane Higueret (7/3/2022 3:55 PM IDT)
• *Andreas Stiller (7/3/2022 5:41 PM IDT)
• *Chris Shannon (7/3/2022 6:57 PM IDT)
• Ralf Jonas (8/3/2022 8:14 AM IDT)
• *Paul Shaw (8/3/2022 3:35 PM IDT)
• *Daniel Bitin (8/3/2022 3:59 PM IDT)
• Vladimir Volevich (8/3/2022 4:51 PM IDT)
• Clive Tong (8/3/2022 6:50 PM IDT)
• Bruno Santos (9/3/2022 2:09 AM IDT)
• Alexander Gramolin (9/3/2022 6:36 AM IDT)
• Mathias Schenker (9/3/2022 6:22 PM IDT)
• *Peter Moser (10/3/2022 10:09 PM IDT)
• Sachal Mahajan (11/3/2022 1:12 AM IDT)
• *Jan Fricke (11/3/2022 10:31 AM IDT)
• *Tim Walters (12/3/2022 4:21 AM IDT)
• *Nyles Heise (13/3/2022 9:39 PM IDT)
• Bryce Fore (13/3/2022 10:09 PM IDT)
• *Liubing Yu (15/3/2022 5:50 AM IDT)
• *Sri Mallikarjun J (15/3/2022 8:53 AM IDT)
• Markó Horváth (15/3/2022 9:25 AM IDT)
• *Alexander Marschoun (17/3/2022 9:07 PM IDT)
• *HC Zhu (18/3/2022 1:03 AM IDT)
• Marco Bellocchi (18/3/2022 9:58 AM IDT)
• Quentin Higueret (18/3/2022 11:40 AM IDT)
• Palash Tyagi (18/3/2022 9:06 PM IDT)
• Mark J. Murphy (20/3/2022 2:56 AM IDT)
• *Kai Guttmann (20/3/2022 10:31 AM IDT)
• *Dominik Reichl (20/3/2022 6:14 PM IDT)
• Michael Branicky (20/3/2022 10:32 PM IDT)
• *Wolfgang Kais (21/3/2022 9:02 PM IDT)
• Aviv Nisgav (22/3/2022 8:54 AM IDT)
• Sanjay Rao (22/3/2022 3:10 PM IDT)
• Stefan Wirth (23/3/2022 1:20 PM IDT)
• Ananda Raidu (24/3/2022 8:03 AM IDT)
• Fabio Filatrella (24/3/2022 12:34 PM IDT)
• Kang Jin Cho (24/3/2022 6:20 PM IDT)
• Greg Janée (26/3/2022 9:14 AM IDT)
• Benjamin Lui (27/3/2022 5:39 PM IDT)
• K S (27/3/2022 7:36 PM IDT)
• Phong Kah Ho (28/3/2022 4:38 AM IDT)
• Albert Stadler (28/3/2022 5:22 PM IDT)
• Tamir Ganor & Shouky Dan (28/3/2022 10:15 PM IDT)
• *Motty Porat (29/3/2022 3:33 AM IDT)
• Harald Bögeholz (29/3/2022 5:21 AM IDT)
• Lorenz Reichel (29/3/2022 6:39 PM IDT)
• Sebastian Bohm & Martí Bosch (30/3/2022 10:55 AM IDT)
• Reda Kebbaj (31/3/2022 9:11 PM IDT)
• *Paolo Farinelli & David Dunkley (31/3/2022 10:07 PM IDT)
• Todd Will (2/4/2022 5:26 PM IDT)
• *Jim Clare (2/4/2022 11:01 PM IDT)
• Erik Wünstel (3/4/2022 5:01 PM IDT)
• Franciraldo Cavalcante (4/4/2022 5:20 PM IDT)
• Hansraj Nahata (4/4/2022 7:27 PM IDT)