My Social Security Card Number

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?

• That's a very interesting thing to remember about your social security card number ... Nov 3 '18 at 16:38
• Do we know how many digits is the number? Nov 3 '18 at 16:39
• @Randal'Thor: No, I cannot remember that either. Quite a few... Nov 3 '18 at 16:43
• Do the 2-digit blocks overlap? Can a 2-digit number have a leading 0? Nov 3 '18 at 17:42
• For no particular reason... What is your mother's maiden name and what was the name of your first/current/favorite pet? :) Nov 3 '18 at 18:18

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.