2005 PMWC Problems/Problem T10

Problem

Find the largest 12-digit number for which every two consecutive digits form a distinct 2-digit prime number.

Solutions

We list all 2 digit primes:

11, 13, 17, 19

23, 29

31, 37

41, 43, 47

53, 59

61, 67

71, 73, 79

83, 89

97

Note that can only appear as the first digit. We can construct the solution by appending digits to the right of the current number with the following maps from the current units digit. . These alone give a maximum of digits (counting the first digit of the first prime). Note that may only map one time, but is mapped to from both and , so must also be used as the last digit. To obtain digits, we must let the first digit must be of the aforementioned alternatives.

We also note that we need to use both the strings and , since the s may only appear twice. Also, the strings and must appear, barring from being the second digit. These together imply that cannot be the first digit, so the second digit must be . We greedily use first.

At each step, we pick the maximal number that does not yield a contradiction. This immediately gives: