Department of Energy Argonne National Laboratory Office of Science NEWTON's Homepage NEWTON's Homepage
NEWTON, Ask A Scientist!
NEWTON Home Page NEWTON Teachers Visit Our Archives Ask A Question How To Ask A Question Question of the Week Our Expert Scientists Volunteer at NEWTON! Frequently Asked Questions Referencing NEWTON About NEWTON About Ask A Scientist Education At Argonne 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

NEWTON is an electronic community for Science, Math, and Computer Science K-12 Educators, sponsored and operated by Argonne National Laboratory's Educational Programs, Andrew Skipor, Ph.D., Head of Educational Programs.

For assistance with NEWTON contact a System Operator (help@newton.dep.anl.gov), or at Argonne's Educational Programs

NEWTON AND ASK A SCIENTIST
Educational Programs
Building 360
9700 S. Cass Ave.
Argonne, Illinois
60439-4845, USA
Update: June 2012
Weclome To Newton

Argonne National Laboratory