7
$\begingroup$

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, ...)

Improve this question
$\endgroup$
3
  • 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
    Feb 21, 2015 at 18:49
  • 2
    $\begingroup$ You are looking for some modified version of a De Bruijin sequence $\endgroup$
    – Jean-Sébastien
    Feb 21, 2015 at 19:14
  • $\begingroup$ Oops, You're right hvd changed it. $\endgroup$
    – Spencerkatty
    Feb 21, 2015 at 22:04

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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$
    – Spencerkatty
    Feb 21, 2015 at 22:13
  • $\begingroup$ SpectralFlame provided an example in his answer. $\endgroup$
    – user88
    Feb 21, 2015 at 23:08
5
$\begingroup$

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

10011202130314041505160617071808190922324252627282933435363738394454647484955657585966768697787988991

while the largest is

99897969594939291908878685848382818077675747372717066564636261605545352515044342414033231302212011009

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

Improve this answer
$\endgroup$

Your Answer

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

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