What is the shortest string of numbers, which contains all the numbers between 0 and 1000

I'm sat at my desk and I just thought up a problem and I was wondering if anyone could think up a solution or a way to prove this mathematically.

Say I wanted to find the shortest string of numbers, which contained every number between 0 and 1000. For example,开发者_StackOverflow the string "1433" contains the numbers, 1, 4, 3, 14, 43, 33, 143, and 433.

What algorithm could I use to construct the shortest string which contained all numbers 0-1000.

I don't have any practical reason why I want to know, but I'd be interested to hear if there is one.

You are asking for a modified de Bruijn sequence. Specifically, a de Bruijn sequence with the first n-1 characters appended to the end of the string.

For the particular case you ask about, it will be 10^3 + 2 = 1002 digits long (assuming that 1000 is not included -- you can arrange for 1000 to be in the string as well, if you set things up right, but there is no guarantee that an arbitrarily chosen (10,3) de Bruijn sequence will contain "1000").