March 2022 - Challenge
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
Challenge:
28/02/2022 @ 14:00 PM EST
Solution:
04/04/2022 @ 12:00 PM EST
List Updated:
04/04/2022 @ 11:47 AM EST
People who answered correctly:
*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)