# Math question about my alarm system **URL:** \ **Category:** Factual Questions\ **Created:** [November 26, 2001, 5:06pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309 "2001-11-26T17:06:48Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![bpaulsen](https://avatars.discourse-cdn.com/v4/letter/b/73ab20/32.png) [@bpaulsen](https://boards.straightdope.com/u/bpaulsen)\ **Post date:** [November 26, 2001, 5:06pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/1 "2001-11-26T17:06:48Z")
My alarm system requires a 4-digit code for me to turn it on and off. I have also learned that I can enter in this 4-digit code in the middle of any key sequence. For example, if my code was 5678, I could press 12345678 and it would successfully turn off when I hit 5678. Now, let’s say that I forgot my code. What would be the fewest key presses that I would need in order to try every 4-digit code? For example, I would be able to do all of the 4-digit codes that are sequences by pressing 1234567890123 (gotta get the wrap-arounds). In other words, that would only take me 13 key presses to try all of those. ---
**Author:** ![Squink](https://avatars.discourse-cdn.com/v4/letter/s/b5e925/32.png) [@Squink](https://boards.straightdope.com/u/Squink)\ **Post date:** [November 26, 2001, 5:57pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/2 "2001-11-26T17:57:56Z")
There are 10,000 four digit numbers. Entered individually that would be 40,000 keystrokes to try them all. You can just count 4 digit subsequences to get an idea of the minimum number of keystrokes needed to get all 10,000 four digit numbers. ```auto sequence sequence length # of four digit subsequences x 1 0 xx 2 0 xxx 3 0 xxxx 4 1 xxxxx 5 2 xxxxxx 6 3 xxxxxxx 7 4 n n n-3 ``` So to get 10,000 distinct four digit sequences you’d need a minimum of n + 3 or 10,003 keypresses. So 10,003 keystrokes is the **minimum** needed to try all the possible combinations. Not just any 10,003 digit number would do however; you’d have to get very lucky to pick a 10,0003 digit number at random and get one that contains all possible 4 digit subsequences. As a WAG, there is at most 1 such number; so unless you are entering it out of a book, you’d be better off just trying all 10,000 distinct numbers in sequence. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [November 26, 2001, 6:12pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/3 "2001-11-26T18:12:13Z")
If there is one, then there are two, since you can also enter the same 10,003-digit sequence in reverse. Oh shoot. What if it’s palindromic? Nevermind that. But, if you have a sequence that works, you should get a different sequence that works by swapping all 2’s and 1’s, or any digits for that matter. It’s my WAG that there are many many many successful sequences, but I agree that you’d be darn lucky to guess one. ---
**Author:** ![John\_Kentzel-Griffin](https://avatars.discourse-cdn.com/v4/letter/j/ccd318/32.png) [@John\_Kentzel-Griffin](https://boards.straightdope.com/u/John_Kentzel-Griffin)\ **Post date:** [November 26, 2001, 7:01pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/4 "2001-11-26T19:01:57Z")
Granted there are a lot of sequences that work, but you can order them. Let’s consider the sequence that represents the smallest integer. You must have ‘0000’ somewhere. The smallest sequence will start with ‘0000’. Then place a ‘1’ three more zeros and a two. So, the smallest such sequence will start like this: 0000 1000 2000 3000 . . . 9990 (spaces added for readability) This 4,000 digit string will give you every sequence that has at least one zero. I’m not sure where to go after this. ---
**Author:** ![Squink](https://avatars.discourse-cdn.com/v4/letter/s/b5e925/32.png) [@Squink](https://boards.straightdope.com/u/Squink)\ **Post date:** [November 26, 2001, 8:10pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/5 "2001-11-26T20:10:20Z")
Oops, swapping 1’s for 2’s really would work wouldn’t it ? Isn’t symmetry grand when you see it properly ! Then counting the possible swaps gives at least 45 10,003 digit numbers that’d work. Has anyone got a proof that there is 1 such number ? ---
**Author:** ![zut](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/zut/32/2875_2.png) [@zut](https://boards.straightdope.com/u/zut)\ **Post date:** [November 26, 2001, 8:49pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/6 "2001-11-26T20:49:35Z")
Seems to me that you ought to be able to construct such a 10,003-digit number. For example, pick any four-digit sequence to start; say, **9439** (just a random choice). For each subsequent digit, follow this procedure: 1) examine the previous three digits ( **439** , in this case). 2) Determine which of the four-digit sequences of the form **439X** have been used already in previous steps. 3) Pick any digit for **X** that gives a sequence not previously used. 4) Repeat the next 9998 times. The trick here is that _there are only ten sequences of the form **Y439**._ Thus, you’re guaranteed to see this sequence ten and only ten times, and you simply choose a different digit **X** every time you see the same sequence. Assuming this logic is correct, there ought to be, uh, (10000)(10[sup]99[/sup])(9[sup]100[/sup])(8[sup]100[/sup])(7[sup]100[/sup])(6[sup]100[/sup])(5[sup]100[/sup])(4[sup]100[/sup])(3[sup]100[/sup])(2[sup]100[/sup]) distinct 10,003-digit numbers that would work. I’m not positive this is correct. Comments? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 26, 2001, 9:05pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/7 "2001-11-26T21:05:09Z")
I’m pretty sure that if you take a number that works, and circular shift it by some number k, which is smaller than the number of digits, you’ll get a valid solution. What k could be is still an open question… ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [November 26, 2001, 9:13pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/8 "2001-11-26T21:13:25Z")
What bpaulsen is looking for is called a “De Bruijn Sequence”. Now go Google yourselves silly. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 26, 2001, 9:50pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/9 "2001-11-26T21:50:46Z")
> [@](#): > > \*Originally posted by ftg \* > \*\*What bpaulsen is looking for is called a “De Bruijn Sequence”. Now go Google yourselves silly. \*\* Here’s a [link](http://mathworld.wolfram.com/deBruijnSequence.html), although it will require some background reading. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [November 26, 2001, 11:28pm UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/10 "2001-11-26T23:28:31Z")
I checked out that link, **ultrafilter**. It says you can generate these things using Mathematica. Does anyone with access to Mathematica want to give it a go and check to make sure that one of length 10,003 actually does exist? Maybe I don’t quite understand these things totally, but one sentence from the MathWorld link confused me. It says, “For example, a de Bruijn sequence of order **n** on the alphabet **{a,b,c}** is given by **{a,a,c,b,b,c,c,a,b}**.” It would make sense to me if they said **2** instead of **n** , but for, say, **n** = 3, the sequence **a,a,a** is not represented. What’s up with that? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 27, 2001, 12:52am UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/11 "2001-11-27T00:52:15Z")
> [@](#): > > \*Originally posted by Achernar \* > **I checked out that link, ultrafilter. It says you can generate these things using Mathematica. Does anyone with access to Mathematica want to give it a go and check to make sure that one of length 10,003 actually does exist?** I have access to Mathematica, but it would take me a while to figure out how to use it. We’ll need to rely on someone else. > [@](#): > > \*\*Maybe I don’t quite understand these things totally, but one sentence from the MathWorld link confused me. It says, “For example, a de Bruijn sequence of order **n** on the alphabet **{a,b,c}** is given by **{a,a,c,b,b,c,c,a,b}**.” It would make sense to me if they said **2** instead of **n** , but for, say, **n** = 3, the sequence **a,a,a** is not represented. What’s up with that? \*\* It may well be an error; they probably did mean to write 2. You may want to e-mail them and ask. ---
**Author:** ![Squink](https://avatars.discourse-cdn.com/v4/letter/s/b5e925/32.png) [@Squink](https://boards.straightdope.com/u/Squink)\ **Post date:** [November 27, 2001, 1:32am UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/12 "2001-11-27T01:32:39Z")
Apparently Lempel (of LZW fame) came up with an efficient method of generating De Bruijn sequences. You can buy a description of the algorithm for $10 [here](http://www.computer.org/tc/tc1997/t0198abs.htm?SMSESSION=NO). The sequences probably do awful things to lossless compression algorithms. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [November 27, 2001, 1:59am UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/13 "2001-11-27T01:59:40Z")
> [@](#): > > \*Originally posted by DrMatrix \* > This 4,000 digit string will give you every sequence that has at least one zero. I’m not sure where to go after this. This is actually too many numbers since 00000001 is too long to account for the actual sequence 0000. You actually only need 00001 to account for 0000 and 0001. We would need to start a pattern as follows: 0000 & 0001 = 00001 0001 & 1000 = 10001 0000 & 0001 & 1000 = 000010001. Also note: 0001 with 1000 = 10001 0002 with 2000 = 20002 0003 with 3000 = 30003 0004 with 4000 = 40004 etc. All palindromic numbers can be “chopped” in such a manner. So there are 10,000 possible combinations (40000 maximum button presses), but there are a ton of palinromes in there for which we can lose a digit. In fact, there are 9 palindromes for every three digit “inner” palindrome. X000X = X000 and 000X XY0YX = XY0Y and Y0YX Or, most generally, XYXYX = XYZY and YZYX. This pattern can cut 3 digits for each number of form XYZY less than 5000. Or, more specifically, there are (I believe) 9_9_9 = 729 such numbers, or 2187 buttons we don’t have to press. How am I doing so far? ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [November 27, 2001, 2:01am UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/14 "2001-11-27T02:01:10Z")
You preview for coding errors but never for content. The cure of vB code. 😛 > [@](#): > > \*Originally posted by erislover \* > Or, most generally, > XYXYX = XYZY and YZYX. That should be XYZYX. 😃 ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [November 27, 2001, 3:05am UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/15 "2001-11-27T03:05:07Z")
Okay, there are 10[sup]10,000[/sup] distinct 10,000-digit sequences, no? I wanted to figure out how many of them contain each of the 10 digits exactly 1,000 times. I seem to remember this being equal to 10,000!/(1,000![sup]10[/sup]). Using Stirling’s approximation, I got that this was equal to 10[sup]10,000[/sup], so I guessed that 1,000 is too small a number to be using this approximation on. I tried punching it up in my calculator, though, and got that it was equal to 10[sup]9,983.4[/sup]. This seems abnormally high to me. One in 4×10[sup]16[/sup]. Where’s my error, if anywhere? ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [November 27, 2001, 4:22am UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/16 "2001-11-27T04:22:10Z")
There is a theorem that proves this type of thing can _always_ be done minimally (i.e., each “word” (string of four digits) occurs once and only once throughout the entire sequence). So there is a 10,000 digit string which has all possible four digit combinations (finding it is another matter, of course). This is assuming that “wrap-arounds” are allowed, i.e., the two digit sequence (a,b) represents two 2 letter words: ab, and ba (since we can wrap around from the end to the beginning). If we don’t allow wrap arounds, then we know there is a sequence of 10,003 digits that includes all possible four digit strings. So the answer to the OP is in fact 10,003 (since wrap arounds won’t be recognized by the alarm system). So it’s always easy to determine the minimum length of such a sequence; the hard part is actually finding it. The thereom was proven by de Bruijn (for two letter alphabets, and arbitrary finit word length) in 1946, and by Good (for arbitrary finite alphabets and arbitrary finite word length), also in 1946. ---
**Author:** ![John\_Kentzel-Griffin](https://avatars.discourse-cdn.com/v4/letter/j/ccd318/32.png) [@John\_Kentzel-Griffin](https://boards.straightdope.com/u/John_Kentzel-Griffin)\ **Post date:** [November 27, 2001, 4:29am UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/17 "2001-11-27T04:29:50Z")
> [@](#): > > \*Originally posted by \*\*\*erislover \*\* > This is actually too many numbers since 00000001 is too long to account for the actual sequence 0000. You actually only need 00001 to account for 0000 and 0001. We would need to start a pattern as follows: > 0000 & 0001 = 00001 But that _is_ what I posted. I started with 0000 1000 which will have all sequences with zeros and at most one 1. The really strange thing is I originally made that mistake, but I caught it in preview. You are weirding me out. I just realized that I did make a mistake. after 9000, go to 1100. I counted 1000 again. (ten followed by two 0s = one followed by four 0s). I should have eliminated multiples of ten. ---
**Author:** ![galt](https://avatars.discourse-cdn.com/v4/letter/g/35a633/32.png) [@galt](https://boards.straightdope.com/u/galt)\ **Post date:** [November 27, 2001, 4:56am UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/18 "2001-11-27T04:56:15Z")
> [@](#): > > \*Originally posted by erislover \* > … 00000001 is too long to account for the actual sequence 0000. You actually only need 00001 to account for 0000 and 0001. We would need to start a pattern as follows: > 0000 & 0001 = 00001 > 0001 & 1000 = 10001 > 0000 & 0001 & 1000 = 000010001. I would contend that finding a number **sufficient** to contain all n-digit sequences is easy, but finding the **shortest** such number is difficult. Your simple example illustrates this pretty well, as I can represent 0000, 0001, and 1000 three characters shorter than you have: 100001. As more and more numbers are involved, it gets trickier to spot the optimizations. ---
**Author:** ![Squink](https://avatars.discourse-cdn.com/v4/letter/s/b5e925/32.png) [@Squink](https://boards.straightdope.com/u/Squink)\ **Post date:** [November 27, 2001, 5:23am UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/19 "2001-11-27T05:23:05Z")
> [@](#): > > There is a theorem that proves this type of thing can always be done minimally (i.e., each “word” (string of four digits) occurs once and only once throughout the entire sequence). That’s nice. If finite sequences behave like that it makes the [Is Pi normal](http://www.astro.univie.ac.at/~wasi/PI/pi_normal.html) question seem less peculiar. ---
**Author:** ![FortMarcy](https://avatars.discourse-cdn.com/v4/letter/f/9de053/32.png) [@FortMarcy](https://boards.straightdope.com/u/FortMarcy)\ **Post date:** [November 27, 2001, 6:09am UTC](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309/20 "2001-11-27T06:09:38Z")
> [@](#): > > \*Originally posted by Cabbage \* > \*\*So it’s always easy to determine the minimum length of such a sequence; the hard part is actually finding it. The thereom was proven by de Bruijn (for two letter alphabets, and arbitrary finit word length) in 1946, and by Good (for arbitrary finite alphabets and arbitrary finite word length), also in 1946. \*\* With computers these days, even this isn’t as difficult as I imagined. I wanted to see how hard it would be to locate a valid sequence and wrote a quick-and-dirty program to find one. It took less than 5 seconds of running time. The sequence is very interesting. It begins “0001000200030004000500060007…” and ends “…9799879998888988998989999000”. One property of a valid sequence is that the first three digits will be the same as the final three. Of course, another 10! sequences could be created through substitution. [Next page](https://boards.straightdope.com/t/math-question-about-my-alarm-system/95309.md?page=2)