This is Problem 51 “Prime digit replacements”:
The goal is to find the smallest member of a prime number family consisting of exactly eight primes that share one additional property.
With two examples given, the problem description is pretty clear. 56003, 56113, 56333…56**3. Replace the wildcards with the same digit and the resulting number is still prime.
Everything else is just vague as f***. How many wildcards? What’s their position? Will the “smallest” prime be a rather large number or not?
At least the wildcard values are more or less clear. As the prime number family will have eight members, eight different wildcard substitutes out of [0, 1, 2, …, 9] will be required.
Asking “Dr. Google”
Lazy as I am, I started googling for the term “prime number family”. For sure, there must be something on mathworld.wolfram.com. Mathematically illiterate as I am, I couldn’t find anything. Therefore, I had to go back to the drawing board.
Whenever I don’t know what to do, I tend to start with something very simple. In this case, a for-loop to generate numbers and a function to check for primes. With an upper limit of 1.000.000. Working on Project Euler problems often involves comically large numbers. Turns out this one time I got lucky with my uneducated guess.
I also just assumed (hoped) that the correct answer will contain only two or three wildcards. Nevertheless, I added a function to count the occurrences of a given digit within one of my prime numbers. Without paying any attention to its position.
Next, I added a replacement method. Beware of leading zeros!
And finally, a counter for the resulting primes after replacing the wildcards by iterating the list [0, 1, 2, …, 9].
After fiddling around with the parameters of my patchwork code and removing a couple of bugs, I found a promising small number matching the requirements, pasted it in the answer field, and hit jackpot faster than expected.
My solution might not be the most elegant, but it works and still executes reasonably fast (~1 second) after removing all guesswork from the code.
Before calling it a day, here are some hints in case you are stuck working on Problem 51:
- You are looking for a small number (way below 1.000.000).
- It’s a pretty number.
- The number contains more than two wildcards.
- The number 0 does not play a role.