# 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 $0,2,4,5,6,8$ 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. $1 \to 1,3,7,9; 3 \to 1,7; 7 \to 1,3,9; 9 \to 7$. These alone give a maximum of $11$ digits (counting the first digit of the first prime). Note that $9$ may only map one time, but is mapped to from both $1$ and $7$, so $9$ must also be used as the last digit. To obtain $12$ digits, we must let the first digit must be of the aforementioned alternatives.

We also note that we need to use both the strings $131$ and $737$, since the $3$s may only appear twice. Also, the strings $17$ and $97$ must appear, barring $7$ from being the second digit. These together imply that $3,7,9$ cannot be the first digit, so the second digit must be $1$. We greedily use $61$ first.

At each step, we pick the maximal number that does not yield a contradiction. This immediately gives: $$\boxed{619737131179}$$