# Prime to Prime change

Change the Prime Number 71549 to another Prime Number 10067 in Five steps by changing one digit at a time.

Every time you change the digit the new number must be a Prime Number also. You cannot rearrange the digits after the change.

• No computers? You want us to check multiple 5-digit numbers for primality by hand? Hmmmm. – Gareth McCaughan Jun 28 '17 at 14:09
• Point taken will edit – DEEM Jun 28 '17 at 14:10
• Well -- it might turn out that we can "prune" enough by spotting e.g. multiples of 3, 7, 11 that substantial computation isn't needed... – Gareth McCaughan Jun 28 '17 at 14:12
• I was not smart enough to realize the data base may exist. Did it by what you call "prune" method – DEEM Jun 28 '17 at 14:14
• If the original number is 12345 then first step could be 13345. Second could be 13375. So you are changing 1 digit at a time only. – DEEM Jun 28 '17 at 14:16

Here's one the only way (changed number in bold):

71549 -> 71569 -> 71069 -> 11069 -> 10069 -> 10067

Steps taken

First number change:

The only possible (read: still prime) switches are 11549, 70549, and 71569

Second number change:

11549 does not have any possible moves, so that number will not work. The same goes for 70549. Therefore, the only number from the first move that still applies is 71569. The only number that is still prime is 71069.

Third number change:

Taking 71069, the only possible move is 11069.

Fourth number change:

Taking 11069, only 10069 works.

Last number change:

We move on the 10067, the final prime. There are no other ways to get to this number from 71549, changing only one number at a time AND keeping every intermediate value prime.

• Did you check the computer for Prime data base Moose? – DEEM Jun 28 '17 at 14:17
• FWIW, this is also the solution I found. That doesn't necessarily mean it's the only one -- it could just mean that we tried things in the same order. – Gareth McCaughan Jun 28 '17 at 14:18