I couldn’t find this elsewhere, but if it is, please point me.
If you have a lock that opens (and tells you so) after the correct four digits are put in, in order, without being required to hit “enter” or whatever and start over, what is the most digits you must enter? And what would be the equation/formula for finding this for a decimal string of X digits? An NON-decimal string of X digits? Please label the variables’ meanings. I probably forgot this from “combinations and permutations” in high school.
Like, if you hit “000011”, then you’ve input, and attempted, three 4 digit strings totalling 6 digits: 0000, 0001, and 0011. If the code were one of these, it would have unlocked at the last correct digit entered.
Think of it like those barrel locks for bike racks and briefcases only without having to try it each time, which I opened in about one minute for hapless kids who forgot them, now guitar cases and such–same thing–never revealing my secret of the crappy design. Nevertheless, my expensive weird tire size Schwinn bike was stolen and recovered scuffed after a few days, so I can recommend parents do what mine did, and buy a proper Master lock, and file the combo (assuming there are still kids who ride bikes…driving through the safe old neighbourhood, we only found a group of 3 walking together. I like video games, too, but damn.)
Well, first of all, if there are four digits, each of which can be anything from 0 to 9, there are 10[sup]4[/sup] = 10,000 possible combinations (or I should say, strings of digits, since these aren’t combinations in the way the word is used when you talk about “permutations and combinations”).
More generally, if there are X digits, each of which has N possible values, there are N[sup]X[/sup] possible strings of digits.
But it looks to me like you’re asking a more complicated question. As you note, on something like a barrel lock you don’t have to re-enter all four digits each time you want to try a different possibility: you only have to change one digit to something different, assuming you can do so and hit one of the possibilities you haven’t tried yet.
So I guess your question becomes: Is it possible to run through all the possibilities by changing one digit at a time? and if not, what is the smallest number of “moves” or digit-changes you’d have to make? But I don’t know the answer to this.
If that were the question, I think you go from 0000 to 0009, then 0019, 0018 … 0010, then 0020, 0021… etc.
But that’s not what the OP is asking. I believe the question is about a digital lock that accepts the last 4 digits as the input combination. So if you hit 0000, then hit 1, you’ve just tried 0001. If you then hit 2, you’ve just tried 0012. I’ve seen home alarm systems that work like that.
(And I don’t know the answer to this question, just trying to clarify the question.)
I think I understand what he’s saying. Imagine a push-button combination lock, which requires the right four digits in the right order, but only the last four digits count. So, if you have three different locks with combinations 3712, 1285 and 5238 then entering the string 9673712852385623 will open them all.
Answer is, it is possible to construct a 10003 digit sequence that contains every possible 4 digit sequence.
Ok, yeah, that makes sense. I think I was thrown off by thinking of mechanical locks like those on barrel chain locks and briefcases, which the OP did mention.
Exactly. Then, I’d like to know the formula for this, and for bonus points, a formula that takes a base[sub]n[/sub] of an X string length code. An URL with the answer would be fine
Yes, the barrel - lock thing should have been more clearly labeled as an aside to my question (and a warning to people who still cycle).
The number of required presses is (X[sup]n[/sup] + n - 1) or a little more. That is, either you can fit all possibilities perfectly, or you’ll need a little slop.
With X=10, n=4, as in OP, there is a perfect fit. For X=2, n=5 I don’t think there is any perfect fit. I don’t know the general rule.
A (cyclic) minimum sequence containing every subsequence of a given length over a given set of symbols is called a De Bruijn sequence. Not all that hard to generate or anything.
[FONT=Courier New][SIZE=3]That is EXACTLY what I was looking for, but with a cryptography hobby, if anyone can answer how to amend the formula for different number bases (like hexadecimal) so my headache doesn’t increase, you win the bonus points redeemable at any BS store.[/SIZE=3][/FONT=Courier New]
The formula (in the Wikipedia article) already deals with arbitrary bases. In the formula for B(k,n), k is the base. So your original question asks for a deBruijn sequence B(10,4), which is in fact explicitly described in the article. For a hexadecimal code of 4 characters, it would be B(16,4).
