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:
See also
2005 PMWC (Problems) | ||
Preceded by Problem T9 |
Followed by Last Question | |
I: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 T: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 |