[link|http://en.wikipedia.org/wiki/Social_Security_number|Wikipedia]
Valid SSNs
Currently, a valid SSN cannot have an area number above 772, the highest area number which the Social Security Administration has allocated.[3]
There are also special numbers which will never be allocated:
* Numbers with all zeros in any digit group (000-xx-xxxx, xxx-00-xxxx, xxx-xx-0000).
* Numbers of the form 666-xx-xxxx, probably due to the potential controversy (see Number of the Beast). Though the omission of this area number is not acknowledged by the SSA, it remains unassigned.
* Numbers from 987-65-4320 to 987-65-4329 are reserved for use in advertisements [citation needed].
The Administration publishes the last group number used for each area number. Since group numbers are allocated in a regular (if unusual) pattern, it is possible to identify an unissued SSN that contains an invalid group number. Despite these measures, many fraudulent SSNs cannot easily be detected using only publicly available information.
Thus, at the moment, there are a little less than 772M possible valid SS numbers. Hey, a 22% savings is nothing to sneeze at! :-)
Cheers,
Scott.
(Who would probably answer a question like this by saying: "I'm sure this is a well-known problem that has been solved many times over the last ~ 70 years. Give me a few minutes with Google and I'll get back to you." - because he's not a programmer.)