Sequence containing every four-digit combination

[Mike314]

What is the shortest numerical string containing every possible combination of four digits? (0000 - 9999 inclusive)
(To clarify, the string 123456 would contain the combinations 1234, 2345 and 3456.)

In theory, the shortest possible sequence should be 10,003 digits long. But does such a sequence actually exist? Is there a way to prove or disprove it (without writing the whole thing out)?
If it doesn't exist, is there a way to calculate the minimum possible length of our ideal sequence?

Apologies if this is in the wrong forum. Please let me know if I should post elsewhere.

 

[Steven G]

What have you tried? Where are you stuck? Have you tried to solve this same problem with 2 digits? Or do you just want the answer?

 

[Mike314]

More after the answer. It's academic curiosity, rather than a homework problem.

Context: my flat door has a four-digit code, and I found out recently that there's more than one code that works (and still work if part of a longer string).
Which led me to wondering what the best way to find all possible entry codes was, and that led me here.

 

[Steven G]

Sorry, but we do not offers solutions on this forum. Rather we give leading hints. Why not try the problem with 2 digits. It will only take ,maybe ten minutes.

 

[Agent Smith]

There seems to be $10^4$ numbers you have to count. The upper bound would be $4 \times 10^4$ digits then (4 digits for each permutation).

 

[Agent Smith]

The lower bound $y = x - 3$

 

[blamocur]

Pure brute force took 40 seconds for a Python script to find an answer -- see attached

 

[Agent Smith]

Does anyone know if Python has a graphics module?

 

[lookagain]

Why not try the problem with 2 digits. It will only take, maybe ten minutes.

I don't know if you actually did it. My attempt by hand produced this wrap around
length of 103 digits. Looking back and forth I verified that each of 00 through 99,
inclusive, appears for sure at least once.

$\displaystyle 0 \ 0 \ 1 \ 1 \ 0 \ 2 \ 2 \ 0 \ 3 \ 3 \ 0 \ 4 \ 4 \ 0 \ 5 \ 5 \ 0 \ 6 \ 6 \ 0 \ 7 \ 7 \ 0 \ 8 \ 8 \ 0 \ 9 \ 9 \$
$\displaystyle 1 \ 2 \ 1 \ 3 \ 1 \ 4 \ 1 \ 5 \ 1 \ 6 \ 1 \ 7 \ 1 \ 8 \ 1 \ 9 \ 2 \ 3 \ 2 \ 4 \ 2 \ 5 \ 2 \ 6 \ 2 \$
$\displaystyle 7 \ 2 \ 8 \ 2 \ 9 \ 3 \ 4 \ 3 \ 5 \ 3 \ 6 \ 3 \ 7 \ 3 \ 8 \ 3 \ 9 \ 4 \ 5 \ 4 \ 6 \ 4 \ 7 \ 4 \ 8$
$\displaystyle 4 \ 9 \ 5 \ 2 \ 5 \ 6 \ 5 \ 7 \ 5 \ 8 \ 5 \ 9 \ 6 \ 7 \ 6 \ 8 \ 6 \ 9 \ 7 \ 8 \ 7 \ 9 \ 8 \ 9 \ 0$

 

[Dr.Peterson]

I don't know if you actually did it. My attempt by hand produced this wrap around
length of 103 digits. Looking back and forth I verified that each of 00 through 99,
inclusive, appears for sure at least once.

$\displaystyle 0 \ 0 \ 1 \ 1 \ 0 \ 2 \ 2 \ 0 \ 3 \ 3 \ 0 \ 4 \ 4 \ 0 \ 5 \ 5 \ 0 \ 6 \ 6 \ 0 \ 7 \ 7 \ 0 \ 8 \ 8 \ 0 \ 9 \ 9 \$
$\displaystyle 1 \ 2 \ 1 \ 3 \ 1 \ 4 \ 1 \ 5 \ 1 \ 6 \ 1 \ 7 \ 1 \ 8 \ 1 \ 9 \ 2 \ 3 \ 2 \ 4 \ 2 \ 5 \ 2 \ 6 \ 2 \$
$\displaystyle 7 \ 2 \ 8 \ 2 \ 9 \ 3 \ 4 \ 3 \ 5 \ 3 \ 6 \ 3 \ 7 \ 3 \ 8 \ 3 \ 9 \ 4 \ 5 \ 4 \ 6 \ 4 \ 7 \ 4 \ 8$
$\displaystyle 4 \ 9 \ 5 \ 2 \ 5 \ 6 \ 5 \ 7 \ 5 \ 8 \ 5 \ 9 \ 6 \ 7 \ 6 \ 8 \ 6 \ 9 \ 7 \ 8 \ 7 \ 9 \ 8 \ 9 \ 0$

I used a spreadsheet to check, and found that 25 and 52 are duplicated:

0 0 1 1 0 2 2 0 3 3 0 4 4 0 5 5 0 6 6 0 7 7 0 8 8 0 9 9​

1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 3 2 4 2 5 2 6 2​

7 2 8 2 9 3 4 3 5 3 6 3 7 3 8 3 9 4 5 4 6 4 7 4 8​

4 9 5 2 5 6 5 7 5 8 5 9 6 7 6 8 6 9 7 8 7 9 8 9 0​

We can easily use this observation to improve it, by removing the extra 25, which doesn't lose anything:

0 0 1 1 0 2 2 0 3 3 0 4 4 0 5 5 0 6 6 0 7 7 0 8 8 0 9 9​

1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 3 2 4 2 5 2 6 2​

7 2 8 2 9 3 4 3 5 3 6 3 7 3 8 3 9 4 5 4 6 4 7 4 8​

4 9 5 6 5 7 5 8 5 9 6 7 6 8 6 9 7 8 7 9 8 9 0​

This contains every pair exactly once in 101 digits.

 

[Steven G]

I don't know if you actually did it. My attempt by hand produced this wrap around
length of 103 digits. Looking back and forth I verified that each of 00 through 99,
inclusive, appears for sure at least once.

$\displaystyle 0 \ 0 \ 1 \ 1 \ 0 \ 2 \ 2 \ 0 \ 3 \ 3 \ 0 \ 4 \ 4 \ 0 \ 5 \ 5 \ 0 \ 6 \ 6 \ 0 \ 7 \ 7 \ 0 \ 8 \ 8 \ 0 \ 9 \ 9 \$
$\displaystyle 1 \ 2 \ 1 \ 3 \ 1 \ 4 \ 1 \ 5 \ 1 \ 6 \ 1 \ 7 \ 1 \ 8 \ 1 \ 9 \ 2 \ 3 \ 2 \ 4 \ 2 \ 5 \ 2 \ 6 \ 2 \$
$\displaystyle 7 \ 2 \ 8 \ 2 \ 9 \ 3 \ 4 \ 3 \ 5 \ 3 \ 6 \ 3 \ 7 \ 3 \ 8 \ 3 \ 9 \ 4 \ 5 \ 4 \ 6 \ 4 \ 7 \ 4 \ 8$
$\displaystyle 4 \ 9 \ 5 \ 2 \ 5 \ 6 \ 5 \ 7 \ 5 \ 8 \ 5 \ 9 \ 6 \ 7 \ 6 \ 8 \ 6 \ 9 \ 7 \ 8 \ 7 \ 9 \ 8 \ 9 \ 0$

I did try it after I made my post.