2017 UNCO Math Contest II Problems/Problem 3

Problem

Prime Mates

Find the largest 9 digit integer in which no two digits are the same and the sum of each pair of adjacent digits is prime. That is, the sum of the first two digits is prime, the sum of the second and third digits is prime, the sum of the third and fourth digits is prime, and so on.

Solution

985,674,321 Since we want to maximize the integer, let's first start with . Using a greedy algorithm, we can do this series of changes (commas omitted): is a prime

\[\LaTeX\] (Error compiling LaTeX. Unknown error_msg)