

Social Security Numbers Possibilities [with followup]
Name: Michael
Status: other
Age: 40s
Location: N/A
Country: N/A
Date: N/A
Question:
I work at the Social Security Adm. in the United States
and I would like to know how many
different combinations of Social Security numbers there could be. If you
do not know the
Social Security number is three sets of numbers totaling nine numbers.
XXXXXXXXX
Replies:
If there is no restriction on the numbers that can be used (nothing to say,
for example, that 000000000 can't be a SSN), then there a total of one
billion (10^9) possible social security numbers, from 000000000 to
999999999, just the same as if there weren't any dashes there.
Richard E. Barrans Jr., Ph.D.
Assistant Director, PG Research Foundation
Darien, IL USA
This one is easily solved by inspection.
Since digits range from 0 through 9
and you have a "number" with digits in the form:
XXXXXXXXX, the obvious range of numbers is
000000000 though 999999999. This gives
1,000,000,000 possible combinations. Since, however, I don't think the
government would use the social security number 000000000, there might be
only 999,999,999 useable combinations.
Thanks for using NEWTON!
Dr. Rupnik
,000,000,000, i.e., from 000,000,000 to 999,999,999.
AK
Dr. Ali Khounsary
Advanced Photon Source
Argonne National Laboratory
Argonne, IL 60439
The simplest way to think about this is that there are 999 possibilities for
the first block, 99 possibilities for the second block, and 9999
possibilities for the third block. (These numbers come from excluding one
possibility, the one with all zeroes, from each block, which otherwise would
have been 1000, 100, and 1,000 possibilities, respectively.) So, the number
of permissible arrangements here is 999 x 99 x 9999 = 988,911,099. If the
allzero blocks weren't excluded, the premissible arrangements would be 1000
x 100 x 10000 = 1,000,000,000 = one billion.
A much more complicated way to answer this question is the first way I
thought about it, which is to subtract from one billion the number of
forbidden arrangements.
There are a million numbers in which the first block is all zeroes
000abcdef
There are ten million numbers in which the second block is all zeroes
abc00defg
There 100 thousand numbers in which the third block is all zeroes
abcde0000
Simply adding together these sets overcounts a little, because some numbers
are in more than one set.
There are 10,000 numbers in which the first and second blocks are
all zeroes
00000abcd
There are 100 numbers in which the first and third blocks are all
zeroes
000ab0000
There are 1000 numbers in which the second and third blocks are all
zeroes
abc000000
There is one number in which all three blocks are all zeroes
000000000
The trick now is to add together these sets so that each arrangement is
counted exactly once. SO, let's start from the bottom and work our way up.
There are a million numbers in which the first block is all zeroes. Add to
this the ten million numbers in which the second block is all zeroes, and
subtract out the 10,000 ones in which both the first and second blocks are
zeroes, because they're counted in both sets.
Next, add on the 100,000 numbers in which the third block is all zeroes, and
hold back the ones we have already counted: the 100 numbers in which the
first and third blocks are all zeroes, and the 1000 in which the second and
third blocks are all zeroes. In doing this we are twice subtacting the one
allzero number, so we have to add it back in. Overall, our count of
excluded numbers then is
1,000,000 + 10,000,000  10,000 + 100,000  100  1000 + 1 =
11088901
and the total nunmer of permissible social security numbers would be
1,000,000,000  11088901 = 988911099.
This is the same number we got calculating the other way, so it is probably
right!
Richard E. Barrans Jr., Ph.D.
Assistant Director, PG Research Foundation
Darien, IL USA
There are 1 billion possible SSNs. Are you asking about combinations
among these numbers? There are 10^9 * (10^9  1) combinations of two
SSNs, assuming the order of the number pairs doesn't matter.
Tim Mooney
Some numbers are not issued, e.g. 00000000 or any number where the set
of
numbers are all zeros, e.g. 000661234,
123660000, 123001234. Zeros can be used in any other position. How
would this effect the total?
Sincerely,
Michael D. Young
Michael
Division of Direct Service Operations
Michael,
This a a somewhat modified question. Again, I attempted to solve this by
logic, rather than some formula.
By your new requirement, any separate field of all zeros is not to be used.
By this statement, I understand that numbers in the formats
NNNNN0000
NNN00NNNN
000NNNNNN
will not be used.
I tried to visualize which number would be the first one that is acceptable,
counting from 0. I decided anything from 0 through 1,010,000 (SS format
000000000 through 001010000) is not acceptable. Note that the next
highest digit 1,010,001 (ss 001010001) is acceptable.
So far we have 1,000,000,000 original combinations; we subtract the
1,010,001 bad possibilities (0 through 1,010,000) and end up with
998,989,999 possibilities.
Now is where I involve you in the solution.
Here is a hint to further solve your riddle. Note that the next
'unacceptable" number will occur where we "up" the center two numbers by 1
digit to "02" and the final four digits become "0000" again. This will
result in one additional "bad" combination. Note this happens each time we
increment the center 2 digits, through "03", and "04", etc..
Your assignment: count up all those occurrences, and subtract from our
running tally.
Next hint: the next problem combinations occur when digit 7 from the right
is incremented. This again occurs when 0000 become the last four digits,
AND 00 become the center two digits.
Your assignment: consider how many times this occurs.
Note: this is not any easy riddle to solve, but it is a good one in that it
exercises your mind to visualize how and when the 'bad' combinations will
occur.
Thanks for using NEWTON!
Ric Rupnik
Click here to return to the Mathematics Archives
 
Update: June 2012

