6. A positive integer is a prime number if it is greater than 1 and has no positive divisors other than 1 and itself. For example, the number 5 is a prime number because its only two positive divisors are 1 and 5 .
The integer 43797 satisfies the following conditions:
- each pair of neighbouring digits (read from left to right) forms a two-digit prime number, and
- all of the prime numbers formed by these pairs are different, because $43,37,79$, and 97 are all different prime numbers. There are many integers with more than five digits that satisfy both of these conditions. What is the largest positive integer that satisfies both of these conditions?
6. Let $N$ be the largest positive integer with these properties. We show that $N=619737131179$ through a number of steps.
(i) Each digit of $N$ after the first is 1, 3, 7 or 9 :
Each pair of consecutive digits of $N$ must form a two-digit prime.
Every two-digit prime number is odd and does not end in 5 , since if a two-digit positive integer is even or ends in 5 , it would be divisible by 2 or 5 .
We note that each pair of consecutive digits of $N$ forms a two-digit prime, each of these primes ends in $1,3,7$ or 9 , and each digit of $N$ after the first digit is the second digit of a two-digit prime.
Thus, each digit of $N$ after the first is $1,3,7$ or 9 .
(ii) When the two-digit primes formed by pairs of consecutive digits of $N$ are listed, each prime but the first has each digit equal to $1,3,7$ or 9 :
This is because all digits of $N$ after the first are odd.
We have not yet discussed the first prime generated by $N$, so we cannot make this conclusion about this first prime.
(iii) There are 10 two-digit prime numbers with each digit equal to $1,3,7$ or 9 :
These are $11,13,17,19,31,37,71,73,79,97$.
(iv) $N$ has at most 12 digits:
The number of digits in $N$ is one more than the number of two-digit primes in the list generated by $N$, since these primes are formed starting with each digit of $N$ except the last.
The number of primes in this list is at most one more than the number of primes with each digit equal to $1,3,7$ or 9 , since all but the first prime in the list has this property.
There are 10 primes with this property, so at most 11 primes in the list, so there are at most 12 digits in $N$.
(v) For $N$ to have 12 digits, all 10 primes with each digit equal to $1,3,7$ or 9 must be part of the list generated by $N$ :
If this were not the case, then by (iv), $N$ would have fewer than 12 digits.
(vi) For all 10 primes with each digit equal to 1,3,7 or 9 to be part of the list generated by $N$, then the second digit of $N$ equals 1 and the last digit of $N$ equals 9 :
These 10 primes form the entire list of primes, except for the first in the list. Therefore, these primes are generated by all of the digits of $N$ except for the first digit.
We need to try to put these 10 primes in an order so that the second digit of one prime equals the first digit of the next, so that these primes can be generated by a sequence of 11 digits.
Of the primes in the list,
-4 begin with 1 and 3 end with 1
-2 begin with 3 and 2 end with 3
-3 begin with 7 and 3 end with 7
- 1 begins with 9 and 2 end with 9
Thus, the first prime in the list of 10 begins with 1 (since there is one first digit of 1 that cannot be paired with a second digit of 1 ) and end with 9 (since there
is one second digit of 9 that cannot be paired with a first digit).
(Note that the number of beginning and ending $3 \mathrm{~s}$ and $7 \mathrm{~s}$ match.)
Therefore, $N$ is _ 1 _------_- 9 .
(vii) If $N$ has 12 digits, then $N$ has the form 61 -------.-. 9 :
For $N$ to be the largest possible 12 digit number, it is necessary for its first digit to be as large as possible.
Since the first two digits of $N, \_1$, need to form a two-digit prime, then these digits could be $11,31,41,61$, or 71 .
Since 71 will be used already in the list of 10 primes, then this initial prime cannot be 71 and so must be 61 to make $N$ has large as possible.
Thus, $N$ has the form 61 --------- 9 .
(viii) $N=619737131179$
To maximize $N$, we put the largest possible third digit 9 (using the prime 19) and then the largest possible fourth digit 7 (using the prime 97).
This gives 6197 --.-.-. 9 .
There is only one other prime ending with 9 (namely, 79) so the second last digit is 7 , giving 6197 ----- 79 .
The maximum possible digit for the fifth position is now 3 (using the prime 73 since 79 is already used), giving 61973 _-_- 79 .
The maximum possible digit for the sixth position is now 7 (using the prime 37), giving 619737 _-_ 79 .
The maximum possible digit for the seventh position is now 1 (using the prime 71 ), giving $6197371 \ldots-79$.
We have used the primes $19,97,73,37,71,79$, which leaves the primes 11,13 , 17,31 .
The only remaining prime ending in 7 is 17 , so the third last digit must be 1 , giving 6197371 _-179.
The maximum possible digit for the eighth position is now 3 (using the prime 13 since 17 and 19 are already used), giving $61973713 \_179$.
The only possible digit for the ninth position is now 1 (using the primes 31 and $11)$, giving 619737131179 .

Because we have constructed this integer so that it has as many digits as possible and so that the largest digits possible are in the positions with largest place value, then this is $N$, the largest positive integer satisfying the required properties.
Therefore, $N=619737131179$.
ANSWER: $N=619737131179$