Exactly what the title says: What is the shortest (fewest digits) number you can find such that somewhere in it, you can find each number 1- 100?

My thinking for this puzzle is you have an electric numeric lock that can have any code from 1-100 and you want to try all possibilities in the shortest time. (Assuming you don't have to push enter or whatever).

For examples:

1-10 can be 1023456789

1-11 can be 11023456789

1-12 can be 110123456789


Also, is there some sort of formula that can extend this to other numbers (1-1000, 1-50, ...)

  • 4
    $\begingroup$ 10 isn't part of your answer for 1-12? Also, why do 1 and 2 have to be repeated after the 112? Did you mean 112103456789 / 110123456789? $\endgroup$
    – hvd
    Commented Feb 21, 2015 at 18:49
  • 2
    $\begingroup$ You are looking for some modified version of a De Bruijin sequence $\endgroup$ Commented Feb 21, 2015 at 19:14
  • $\begingroup$ Oops, You're right hvd changed it. $\endgroup$ Commented Feb 21, 2015 at 22:04

2 Answers 2


If you use a decimal De Bruijn sequence of order 2, you get a string of 100 digits that contains every possible substring of length 2 - that is, every possible two-digit number, although you need one last digit to account for the wraparound, bring the total to 101.

Suppose further that the first three digits are "100", we get 100 without adding any additional digits. This must be possible because any valid de Bruijn sequence can be "rotated" so that the second and third digits are identical, and then the digits remapped so that the first digit is 1 and the next two digits are 0.

So the shortest number that fits your criteria is 101 digits long.

  • $\begingroup$ Well, I guess that answers what I asked, but can you come up with the number? I didn't realize it had already been done so explicitly. $\endgroup$ Commented Feb 21, 2015 at 22:13
  • $\begingroup$ SpectralFlame provided an example in his answer. $\endgroup$
    – user88
    Commented Feb 21, 2015 at 23:08

Since the problem states that you just want the numbers from 1 to 100 without necessarily having leading zeroes, I thought that maybe you could save a few symbols by omitting strings such as "05" and "08" since all one digit numbers naturally appear as substrings in two-digit numbers.

However, it turns out that the presence of numbers ending with a zero means that you can't save anything in the length. Essentially, every digit must be used as part of two numbers to be efficient, and a zero used in the ones place of a number cannot be used again for the tens place of another (if we disregard leading zeroes).

This does pin the answer at 101 digits. I wrote a program to generate such numbers, and it seems like the smallest one is


while the largest is


although I guess the magnitude of the numbers really doesn't matter much in this problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.