 |
 |
Social Security Numbers Possibilities [with follow-up]
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.
XXX-XX-XXXX
Replies:
If there is no restriction on the numbers that can be used (nothing to say,
for example, that 000-00-0000 can't be a SSN), then there a total of one
billion (10^9) possible social security numbers, from 000-00-0000 to
999-99-9999, 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:
XXX-XX-XXXX, the obvious range of numbers is
000-00-0000 though 999-99-9999. This gives
1,000,000,000 possible combinations. Since, however, I don't think the
government would use the social security number 000-00-0000, 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
all-zero 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
000-ab-cdef
There are ten million numbers in which the second block is all zeroes
abc-00-defg
There 100 thousand numbers in which the third block is all zeroes
abc-de-0000
Simply adding together these sets over-counts 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
000-00-abcd
There are 100 numbers in which the first and third blocks are all
zeroes
000-ab-0000
There are 1000 numbers in which the second and third blocks are all
zeroes
abc-00-0000
There is one number in which all three blocks are all zeroes
000-00-0000
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
all-zero 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. 000-00-000 or any number where the set
of
numbers are all zeros, e.g. 000-66-1234,
123-66-0000, 123-00-1234. 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
NNN-NN-0000
NNN-00-NNNN
000-NN-NNNN
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
000-00-0000 through 001-01-0000) is not acceptable. Note that the next
highest digit 1,010,001 (ss 001-01-0001) 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
|
|
