1. The door
Imagine a door with a keypad. The keypad has three buttons: 1, 2, and 3.
The door opens when you press all three buttons in the correct order. You don’t know the correct order. And here is the annoying part: there is no enter key, no clear button, nothing. The door just watches the last three buttons you pressed and opens if they happen to be right.
There are six possible codes: 123, 132, 213, 231, 312, 321. So you could just type all six in a row.
123 132 213 231 312 321
That is eighteen presses, and it definitely works. But you can do better, because the door doesn’t know where one attempt ends and the next begins. It only ever looks at the last three. So codes can share presses.
Try this one:
1 2 3 1 2 1 3 2 1
Nine presses. Slide a window of three along it and watch what appears: 123, then 231, then 312, then 121 (not a code, that one is wasted), then 213, 132, 321. Every single one of the six codes shows up, and you used half as many presses. Some presses are doing double duty, ending one code and starting the next.
Nine is the best possible for three buttons. Nobody can do it in eight. That has been checked.
Now the obvious question. What about four buttons? Ten buttons? A hundred?
And that question, which a curious ten year old can ask in one sentence, is unsolved.
2. The pattern that looks like an answer
Let’s collect what we know for small keypads.
For a single button, the shortest sequence is obviously of length 1. For two buttons, the shortest is 3 (you can figure this one out by yourself). For three, we just saw that it is 9. For four buttons, 33, and for five, 153.
Stare at 1, 3, 9, 33, 153 for a moment. They look random. They are not.
1 = 1
3 = 1 + 2
9 = 1 + 2 + 6
33 = 1 + 2 + 6 + 24
153 = 1 + 2 + 6 + 24 + 120
Those numbers being added are 1, 2, 6, 24, 120: the number of ways to arrange 1, 2, 3, 4, 5 things. Mathematicians write them 1!, 2!, 3!, 4!, 5! and call them factorials. So the pattern is: add up all the factorials up to your number of buttons.
Better still, there is a recipe. If you have the best sequence for four buttons, there is a step-by-step method that turns it into a sequence for five buttons of exactly the right length. Then five into six, six into seven, forever. The pattern isn’t a coincidence you spotted. It’s a machine, and you can watch it work.
In 1993 two mathematicians, Dan Ashlock and Jenett Tillotson, wrote this up and conjectured that the recipe always gives the shortest possible answer. Other people found the same recipe independently over the years and believed the same thing. Why wouldn’t you? It matches every case anyone could check, and it comes with an explanation.
3. Something odd about those strings
Go back and look at the small answers again.
1
121
123121321
Read each one backwards.
1 backwards is 1. 121 backwards is 121. And 123121321 backwards is, character by character, 123121321.
They’re all palindromes. Like racecar, or level, or never odd or even. They read the same in both directions.
That is a genuinely lovely thing to notice, and it feels like it must be a clue. Maybe the shortest sequences are short because they’re perfectly symmetric. Maybe the symmetry is the trick.
Hold that thought. We’re going to come back and check it, and what happens when we check it is the most useful part of this whole article.
4. The one character that broke everything
In 2014, Robin Houston decided to attack the six-button case with a computer.
He noticed that this puzzle can be disguised as a completely different famous puzzle: the travelling salesman problem, where you have to visit a bunch of cities using the shortest possible route. There are good solvers for that. So he translated the keypad question into a travelling salesman question, handed it to a solver, and let it run.
On the 9,228th attempt, it came back with a sequence of length 872.
The recipe says 873 (1! + 2! + … + 6!).
One character. After thirty years, and only by one, but that is all it takes. The conjecture was wrong, and not just for six buttons: because the recipe builds each answer from the previous one, that single saved character means every case above six is beatable too.
Nobody had predicted this. Nobody had a reason for it. A computer found it, and the character it saved has never really been explained.
5. So where did the palindromes go
Now let’s check the symmetry idea from Section 3, because it makes a clean prediction: symmetric sequences should be the champion ones.
I ran the recipe and looked at what it produces.
For 1, 2, 3, 4, 5 and 6 buttons, the recipe outputs sequences of length 1, 3, 9, 33, 153 and 873. I checked all six (Yes, I have way too much time on my hands). Every one is a valid answer, and every one is a palindrome, including the 873.
That’s the first crack. The 873 is symmetric, and the 873 is not the champion. The palindrome shows up precisely in the case where the recipe loses.
It gets worse. For five buttons, there are eight different shortest sequences, all of length 153. I checked two of them. Both are perfectly valid, both are length 153, and one is a palindrome and one is not. So even at five buttons, where the recipe genuinely is unbeatable, being a champion doesn’t require being symmetric.
And Houston’s 872? I checked. Not a palindrome.
So the palindromes were never a fact about the answer. They were a fact about the recipe. The recipe happens to build symmetric things, so everything it makes comes out symmetric, whether or not it’s any good.
This is exactly the same mistake as the original conjecture, just smaller and easier to see. Somebody noticed a real, checkable, repeatable pattern, and the pattern was about the method rather than about the thing being sought. It is a good mistake to have made once, on purpose, before you make it by accident.
6. But there is a real symmetry hiding in here
Here’s the thing that survives.
Take any valid sequence and reverse it. You get another valid sequence, the same length.
Why? Reversing the whole sequence reverses every three-in-a-row window inside it. 123 becomes 321. 231 becomes 132. But 321 and 132 are codes too. The full set of codes is a mirror of itself, so a sequence that catches all of them, run backwards, still catches all of them.
That means every answer has a mirror twin. And palindromes are the special ones that are their own twin.
So the picture is: the recipe always parks itself exactly on the mirror line, and the improvement at six buttons is the first time anyone stepped off it. That is a familiar shape in this kind of problem. The most symmetric solution is the best one while the puzzle is small, and then, at some size, the space gets big enough that being lopsided pays.
Which turns the childish observation into a grown-up question: at what size does symmetry stop being free, and does how much you can save track how far off the mirror line you have to go?
That is a much better question than the one we started with, and we only got it by taking a wrong idea seriously enough to test it.
7. Two more numbers, and nobody knows why
Six buttons: recipe says 873, best known is 872. Saved one press.
Seven buttons: recipe says 5913. Greg Egan got it down to 5908. In February 2019, Bogdan Coanda found 5907 and announced it in the comment section of a YouTube video. Days later Egan and Houston tweaked his idea and reached 5906. Saved seven presses.
One, and then seven. That’s the entire dataset. No formula connects them. Both were found by computers grinding away, not by anybody working out why the savings should exist.
This is a strange situation to be in. Normally in mathematics someone has a theory and a computer confirms it. Here the computer sprinted ahead and left the theory behind, and the theory hasn’t caught up in over a decade. We have two answers and zero explanations.
Meanwhile the general question is fenced in but not pinned down. There is a proof that no sequence can ever be shorter than a certain formula, and a recipe that achieves a slightly bigger one. The two don’t meet. The gap between them grows as the keypad grows.
One thing worth saying plainly, because it often gets stated too confidently: even six buttons isn’t officially closed. The published proof only rules out anything below 867, not below 872. There’s an unpublished argument by Cole Fritsch that would finish the job, along with a search that found nothing at 871, but the write-up was left mid-revision. So: almost certainly 872, not formally proved.
8. Counting the waste instead of the presses
Here is a way to think about it that I find much clearer, and it needs no algebra.
Every press you make, after the first couple, reveals a new “last three buttons.” Some of those are real codes. Some are junk, like the 121 we hit earlier. Junk presses are pure waste.
So any sequence, no matter how clever, breaks into exactly three parts:
total presses = codes you must contain + a short run-up to get started + wasted presses
The first two are fixed. You cannot contain fewer codes than there are codes, and you cannot avoid the run-up. So the entire puzzle is: how few presses can you waste?
Now the numbers say something concrete. At six buttons, the recipe wastes 148 presses. Houston’s 872 wastes 147. That’s the whole difference. At seven buttons the recipe wastes 867 and the best known wastes 860. The published proof says you can’t get below 142 waste at six buttons, or below 838 at seven.
This framing also kills a tempting wrong idea, and I want to flag it because I believed it for a while myself. It’s natural to guess that the savings come from some code sneaking in twice, appearing for free as a lucky byproduct. So I checked both the 873 and the 872 (again, too much time on my hands). In each of them, every single one of the 720 codes appears exactly once. No duplicates anywhere, in either. The strings differ only in that one wastes 148 presses and the other wastes 147.
The free lunch isn’t a repeated code. It’s one fewer wasted step. Small difference in words, big difference in what you go looking for.
9. The merry-go-round
To go further we need one structural fact, and it’s the sort you can verify on paper in a minute.
Take a code, say 1234. Move the first button to the back: 2341. Do it again: 3412. Again: 4123. Again: back to 1234. Four spins and you’re home.
Call that a merry-go-round. Every code sits on exactly one, they never overlap, and each has exactly as many codes on it as you have buttons. For four buttons there are six merry-go-rounds of four codes each. For n buttons there are (n−1)! of them, and the reason is a one-line argument that any curious teenager can follow with a little help.
Here’s why they matter. Spinning is the cheapest possible move. Going from 1234 to 2341 costs a single press, and it wastes nothing at all, because the new window is immediately another real code. Riding a merry-go-round is free.
Every other move costs you. Getting from one merry-go-round to a different one means pressing buttons that produce junk windows on the way.
So the recipe, seen properly, is just: hop on a merry-go-round, ride it all the way around for free, pay to jump to the next one, repeat until you’ve ridden them all. Add that up and the sum-of-factorials formula falls out. The recipe was never a mysterious pattern. It’s the cost of the obvious tour, and every wasted press in it happens during a jump.
10. Getting off early
Now the mechanism behind the savings has a name you can picture.
The obvious tour rides each merry-go-round all the way around before jumping off. But nothing forces that. You could hop off halfway, go do other things, and swing back later to pick up the codes you skipped.
Usually that’s a bad deal, because coming back means paying for another jump. But every so often your route was going to pass right by those leftovers anyway, on a jump you already needed. Then the pickup is free, and you’ve shaved off waste that the obvious tour would have paid.
That’s it. That’s where the missing character at six buttons comes from, and presumably the seven at seven buttons.
I should be clear this is not my idea. Zach Hunter and Cole Fritsch have both worked on formalizing exactly this, calling them “early exits” and “exitless paths,” trying to count how many such early hops a route can support. Their work lives in a public Google Group and in unpublished drafts rather than in journals, which is probably why it’s less famous than the record-breaking sequences. Anyone starting on this should read them first.
11. Why nobody has finished it
Here is the wall, and it’s worth understanding because it’s the real reason this is still open.
Whether an early exit is free is not a local question. It doesn’t depend on the merry-go-round you hopped off, or the codes you skipped. It depends on whether some other part of your route, somewhere completely different, happens to swing past them later. Which depends on where the other merry-go-rounds got placed. Which depends on their early exits. Which depends on a third thing.
Everything depends on everything. That’s why 1 and 7 don’t sit in any obvious pattern: the number isn’t built from independent pieces you can count separately and add up. It emerges from the whole arrangement at once. And “count the pieces and add them up” is the main tool mathematics has for questions like this.
Fritsch’s draft handles a single early exit reasonably well and gets stuck exactly where several of them start interacting, where two merry-go-rounds end up depending on each other. In the group discussion he describes the machinery as holding together but needing more work, and there it was left.
That distinction matters. Nobody proved that case is impossible. Somebody ran out of time. Those are very different, and the second one is an open invitation.
12. What you could actually go and do
This problem has a strange history. The best known limit on how short sequences can possibly get was worked out by an anonymous person on 4chan, on a message board, in a thread about what order to watch a TV show in. A record-breaking construction was announced in a YouTube comment. The serious discussion happens in a public Google Group anyone can read. There is very little gatekeeping here, and the entry price is a laptop and some stubbornness.
Three things that are genuinely open and genuinely small:
Explain the 872. The sequence is published. Anyone can download it and check it in a few lines of code. Work out which merry-go-round got left early, and why the pickup cost nothing. Not “one press was saved,” but “it hopped off here, and this later stretch grabbed the leftovers on a jump it needed anyway.” Right now that explanation doesn’t exist in writing, and everything else depends on it.
Then do the same for the 5906, and ask whether the seven savings share a reason. This is the big one. If all seven come from one repeating pattern, there’s a mechanism to generalize and the problem might crack. If they’re seven unrelated flukes, then “waste” isn’t one phenomenon and half of this article needs rewriting. Both strings are public. This is answerable by hand, by anyone, this week.
Try to count the early exits directly. How many early hops can coexist without tripping over each other? That smells like a scheduling problem, the kind where you fit as many overlapping bookings into a calendar as possible. Those have standard tools. If a scheduling argument predicts 147 waste at six buttons and 860 at seven, it’s probably the right way to think and worth pushing to every n. If it predicts the wrong numbers, the size of the error tells you exactly which rule you forgot, which is more useful than being vaguely right.
And one bonus, from Section 6. Since the recipe always sits on the mirror line and both improvements stepped off it, here’s a guess worth testing: maybe no palindrome is ever the champion, once you have six or more buttons. If that’s true it’s a free gift to anyone running a search, because it lets you throw away half the possibilities before you start. I don’t know if it’s true. I haven’t seen anyone check.
13. The moral
Twice in this article a beautiful pattern turned out to be a fact about the method rather than about the answer.
The palindromes were real. Every sequence the recipe produces is symmetric. But that was the recipe’s fingerprint, not a property of good sequences, and the moment somebody found a better sequence it was lopsided.
And the sum of factorials was real too. It’s exactly right, it’s provable, it comes with a construction. It’s just that it is the exact cost of the obvious tour, and for thirty years everyone assumed the obvious tour was the best one.
Both times, the mistake wasn’t sloppiness. It was answering a slightly different question extremely well and not noticing the substitution.
The question was never really “how short can the sequence be.” It’s “how little of it can be wasted.” Somewhere out there is a rule that says exactly how much you can get for free, and as far as anyone knows it’s still sitting there, unwritten, waiting for whoever gets curious enough about a door with a broken keypad.