My Social Security Card Number

Question

I have forgotten my social security card number. All I remember is that it is the largest integer with the property that the block of any two of its digits that are adjacent is either a two-digit prime number or a two-digit perfect square, and that these are all different.

What is it?

Answer 1

I think the answer is

253797364171613119

Proof:

We cannot use zeros; a two digit number ending in zero is not prime and 00 is the only square, so zeros can only appear at the beginning and can therefore be ignored.

Let's list the squares we can use: 16, 25, 36, 49, 64, 81
and the primes: 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

It's a bit like:

domino: to maximize the total number, we first need to maximize the number of pairs we can make.

See the following table:

. start end match
1 5 6 5
2 3 0 0
3 3 6 3
4 4 1 1
5 2 1 1
6 3 2 2
7 3 5 3
8 3 0 0
9 1 6 1

So we can make

16 matches, for a 18 digit Social Security Card Number.

In theory, we want

the largest numbers to appear first, but the only pair ending in 5 is 25.
So we start with 25.
The next one cannot be 59, because we need the 9 for both 79 and 19; one of them can be at the very end
but the other must be somewhere inside the number.
So the next one is 53, then 37, then 79, then 97, then 73, then 36.
67 won't work, as we've used up all our sevens except for the one needed for 17; so we take 64.
We've used up all our nines, sevens and threes except for the one needed for 13; so we take 41.
The next one is 17, then 71, then 16, then 61, then 13, then 31, then 11, and finally 19.

Concatenating all the pairs we get the answer:

253797364171613119