r/AskMath Weekly Chat Thread

Thanks for implementing Rule 1, "include your own progress." I had wondered for years when I punched in a garage code what the shortest number of presses would be to cover every n-digit code, if an enter key wasn't required. While I could describe the same question in terms of strings of lengths M and N from alphabet size A, I had never really looked for an answer. Rule 1 pushed me to look for an answer, and...

TIL about de Bruijn sequences, the exact answer to my question. The Wikipedia article even has a subsection under "uses" describing brute-forcing just the kind of code lock that prompted my curiosity. Rule 1 is a good rule, and in this case, the system worked!

(And if anyone's still curious, the shortest string to contain all strings of length n from alphabet length k will have length kn + n - 1, or 10,003 for 4 digit numerical codes.)

/r/askmath Thread