A while back it was tax season in Canada and a friend of mine was trying to do his taxes online. But since he was foreign and didn't have a Social Insurance Number (their equivalent of an SSN), the helpful webapp wouldn't let him print the thing (of course it only informed him of that after he had already entered everything). We tried a few guesses before finally just using mine and crossing out my numbers after printing it. But I always wondered how the form knew our guesses were invalid. Luckily, I recently stumbled across a mention of how credit card numbers are validated.

It turns out SINs and credit card number are checked with something called the Luhn algorithm. Basically the algorithm just involves taking each digit, multiplying the second, fourth, sixth and so on digit from the right by 2 and adding up all the resulting *digits* (e.g. if 7 is multiplied by 2 then the resulting 14 is split into 1+4). If the sum of the digits is a multiple of 10, the number passes.

For example, to check 345678, you'd split it into 3,4,5,6,7,8. Then multiply 3, 5 and 7 by 2 to give 6, 4, 10, 6, 14, 8. Then split all the digits again to give 6, 4, 1, 0, 6, 1, 4, 8. That adds up to 30 so 345678 would be a valid credit card number (if there wasn't a set length).

Just for fun, here's a quick function in R to run the Luhn Algorithm on a number (or tell you the remainder so you can adjust):

So the next time some stupid web form needs a SIN number I'm going with 999999998.