## If I have valid examples of a nine digit number that includes a check digit algorithm, can I work out what the algorithm is?

Answer by Ryan Wong:

This is my very naïve take on this question.

Before analyzing the situation, one has to realize the trickiness of "non-standard" checksum schemes:Let's say someone devises a checksum scheme as follows:

- Unless otherwise specified, use this well-known checksum scheme:

- Add all the (non-checksum) digits together
- Take the sum modulo 10, and use that as the checksum.
- However, if the sum of all non-checksum digits add up to 35, then

- Use digit "9" as the checksum, regardless of the modulo of the sum (which would have been "5").
A even more crazier "trick" can be used:

- If the non-checksum digits contain all of these numbers: { "3", "5" and "7" }, then add 4 to the sum of digits before taking modulo 10.
How does one catch crazy rules like these?

The simple answer is that:

- If you don't have the exhaustive output from every possible number, then you don't have a 100% guarantee on the correctness.

Here is my analysis.Basically, a checksum scheme maps a 9-digit number to a boolean:

- { true, false },
based on whether the 9-digit number will pass or fail the checksum test.

It is assumed that 8 of the 9 digits are not constrained. This means those 8 digits can be any number.

So, the "map" from 9-digit number to boolean will have:

- 10 ** 9 possible inputs
- For each possible set of (10 ** 8) input digits (the first 8 digits),

- It can be paired with one digit (the correct checksum digit) to give a true output
- If paired with any other digit (not the correct checksum digit), it will give a false output
Assume that the determination of the checksum digit is unknown and unconstrained. That is, even the most craziest scheme (see above) beyond the human's imagination, is allowed.

How many possible ways of choosing the checksum digit?

10 ** (10 ** 8)

That is, there exists that many possible "algorithms" or "mappings" for a scheme for calculating checksum digits.