Project Euler – Prime digit replacements

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.

DIY

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.

Have fun!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s