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 programming please

  • 3
    $\begingroup$ No computers? You want us to check multiple 5-digit numbers for primality by hand? Hmmmm. $\endgroup$
    – Gareth McCaughan
    Commented Jun 28, 2017 at 14:09
  • $\begingroup$ Point taken will edit $\endgroup$
    – DrD
    Commented Jun 28, 2017 at 14:10
  • $\begingroup$ 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... $\endgroup$
    – Gareth McCaughan
    Commented Jun 28, 2017 at 14:12
  • $\begingroup$ I was not smart enough to realize the data base may exist. Did it by what you call "prune" method $\endgroup$
    – DrD
    Commented Jun 28, 2017 at 14:14
  • $\begingroup$ 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. $\endgroup$
    – DrD
    Commented Jun 28, 2017 at 14:16

1 Answer 1


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.

  • $\begingroup$ Did you check the computer for Prime data base Moose? $\endgroup$
    – DrD
    Commented Jun 28, 2017 at 14:17
  • $\begingroup$ 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. $\endgroup$
    – Gareth McCaughan
    Commented Jun 28, 2017 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.