13
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ That's a very interesting thing to remember about your social security card number ... $\endgroup$ – Rand al'Thor Nov 3 '18 at 16:38
  • 2
    $\begingroup$ Do we know how many digits is the number? $\endgroup$ – Rand al'Thor Nov 3 '18 at 16:39
  • 1
    $\begingroup$ @Randal'Thor: No, I cannot remember that either. Quite a few... $\endgroup$ – Bernardo Recamán Santos Nov 3 '18 at 16:43
  • 1
    $\begingroup$ Do the 2-digit blocks overlap? Can a 2-digit number have a leading 0? $\endgroup$ – Weather Vane Nov 3 '18 at 17:42
  • 6
    $\begingroup$ For no particular reason... What is your mother's maiden name and what was the name of your first/current/favorite pet? :) $\endgroup$ – Chowzen Nov 3 '18 at 18:18
15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If we actually add two leading zeroes, the properties still hold $\endgroup$ – Hagen von Eitzen Nov 4 '18 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.