Instead of doormen, Stockholm apartment buildings have a little keypad at the front door, into which you key a 4-digit code to gain access to the lobby. The code is known to residents, and is liberally shared with acquaintances, workmen, postmen, and no doubt sold to an underworld of snail-mail spammers and worseI’d love to see a database of Stockholm door codes, though, if only to gain a little humint on what are the most popular 4-digit combinations..

The keypad is unusual in that there is no enter key. Instead, it remembers the last 4 digits you have pressed, and compares those to the code which unlocks the door. In other words, if you key in the sequence 123456, you’ll have tried codes 1234, 2345 and 3456. If the correct code is 2345, you’ll have opened the door after keying in the first 5 digits in the above sequence.

This is different from how a bank machine keypad operates, where you need to key in four digits (and then enter) for every PIN code number you try. If you were to forget your code, you’d have to go through a maximum of 40,000 key punches (not counting the mathematically boring enter key): 10,000 combinations of 4 keys each (0000, 0001 … 9998, 9999).

On a door-code keypad, however, it’s clear that you can cycle through every combination in far fewer than 40,000 key punches: If I key in just the sequence 1234567890, for example, I have already tried 7 different 4-digit combinations with just 10 key punches. On a bank machine keypad, it would have taken me 28 key punches to try 7 different 4-digit combinations.

This is interesting information for all those of us who think it within the bounds of possibility they might one day find themselves standing somewhat stupefied in the snow outside their Stockholm apartment at 3am on a Sunday in January, with the mercury all shrivelled up, not a soul in sight and not a code in mind. Deciding beforehand on the right contingency strategy for such a situation could shave hours off the frigid poking at that dumb but durable little keypad which would then have to follow.

A rundown of the options, then:

The rest of this post concerns itself with exploring the possibility of making this third option a viable one for Stockholmers. To that end, I have been wondering: (1) What *is* the minimum amount of door-code keypad punches needed to try every possible combination? (2) Is it possible to run through every possible combination without being forced to repeat any combination? (3) Is there a unique such solution? (4) If not, how many solutions are there? And finally, (5) How likely am I to spontaneously generate the shortest possible sequence if I pursue the second, random strategy described above?

If the answer to (2) is yes, it’s easy to see that the answer to (1) is 10,003. That’s because after three punches, every subsequent key I press adds a new 4-digit combination to the sequence, and there are 10,000 combinations to go through. In this best-case scenario, at 2 presses per second, we’d go through every combination in under 84 minutes.

As I started looking into this, it felt like the answer to (2) should be yes, but I lacked the mathematical tools to back up my hunch. So I decided to try to simplify the problem and then apply brute force. Instead of looking for the shortest sequence that contains all possible 4-digit combinations without repetitions, I decided to try to find one that contains all 2-digit combinations without repetitions — the shortest sequence that would unlock a door-code keypad with a 2-digit code.

I printed out a 10×10 grid with all 100 combinations (00, 01 … 98, 99) and headed for a café in Kungsholmen. After a café latte’s worth of trying to connect the numbers, I’d found a sequence 101 digits long that contained all the combinations exactly once — showing that (2) is true, at least for 2 digits:

00112131415161718191022324252627282920334353637383930445464748494055657585950667686960778797088980990

I can’t help it, but I happen to feel that that’s a pretty cool sequence — it feels so *dense*, so *efficient*. Just from inspection, some other things become clear:

*have*to be the same. This is the case for any shortest sequence containing all 2-digit combinations.

…0011213141516171819102232425262728292033435363738393044546474849405565758595066768696077879708898099…

It felt like these observations should apply by extension to shortest sequences for combinations of any length, but I still could not demonstrate to my satisfaction that the shortest circular sequence containing all combinations of *x* digits *had* to be of length 10^{x} — in the case of our door-code keypad problem, a loop of 10,000 digits. Also, I was nowhere near being able to count the number of such shortest sequences.

I thought I’d simplify the problem further, then — by reducing the base from 10 to 2. We can do that, because we’ve really just been using digits as stand-ins for distinct objects, and combinations as ordered collections of these objects. For that matter, you could think of our 4-digit codes as being equivalent to 4-letter words, made from an alphabet comprised of 10 letters. In base 2, there are only two letters, if you will: I and O.

In base 2, then, what do the shortest circular sequences containing all 2-letter words“codes” / “combinations” / “words” / “cyphers” / “strings” / “stretches” / “ordered collections”… — it’s all the exact same thing. look like?

…0011…

That’s it, actually (1001, 1100 and 0110 are all shifted versions of the same circular sequence)For completeness’s sake, the shortest circular sequence containing all 1-letter words in base 2 is …01…, and it’s unique, obviously.. Notice that the length is 4, or 2^{2}. How about the shortest sequences containing all eight 3-letter words, in base 2?

…00010111… = …00011101…

There are two, though they are each other’s mirror image; proceeding clockwise on the first is equivalent to proceeding counterclockwise on the second. Length: 2^{3} = 8.

Shortest sequences containing all 16 4-letter words, base 2?

…0000100110101111… = …0000111101011001…

…0000100111101011… = …0000110101111001…

…0000101001101111… = …0000111101100101…

…0000101001111011… = …0000110111100101…

…0000101100111101… = …0000101111001101…

…0000101101001111… = …0000111100101101…

…0000101111010011… = …0000110010111101…

…0000110100101111… = …0000111101001011…

That’s 16 sequences of 16 letters each, including mirror images.

To find these sequences, I had to resort to drawing crude graphs, with all the possible words connected by arrows indicating which word could lead to which as we create a sequence (think “continue punching away at the keypad”). For example, both 1010 and 0010 can be followed by 0100 or 0101, in the exact same way that on the door-code keypad, the codes 1001, 2001, … 9001 and 0001 can be followed by 0011, 0012, … 0019 or 0010, depending on which key you choose to punch next.

The trick is to visit each word only once by following the arrows. Here, for example, is a graph with all possible 2-letter words in base 2 as nodes:

This is a much prettier version, made later, after I got some help online. Notice how there is only one way of cycling through all the nodes once.

Here is a graph with all possible 3-letter words in base 2 as nodes, again made much prettier after the fact:

In all these graphs, I’ve also labelled the arrows, because they represent a unique relationship between two words. For example, the arrow from node 011 to 110 is labelled 0110, because that is the 4-letter word created when these 3-letter words follow one another in our sequence.

This hints at a very profound relationship between these graphs: *Every arrow on the smaller graph corresponds to a node on the larger graph*. Therefore, trying to find a path that cycles through every *arrow* on the smaller graph is the same as finding a path that cycles through every *node* on the larger graph. And visually, at least, it is a lot easier to find all the ways to cycle through every arrow on the smaller graph than it is to find all the ways to cycle through every node on the larger graph. Hence I never needed to draw a graph with all 4-letter words as nodes in order to find the 16 shortest circular sequences containing all 4-letter words listed earlier — instead, I just found all the ways to cycle through all the arrows on the larger graph above.

This is as far as I got on my own. It began to feel like I was trying to reinvent the wheel, badly, so I decided to seek professional help. After rummaging about on Mathworld for a while, I hit paydirt: It turns out a loop sequence of letters or digits is called a necklace. The shortest possible such sequence containing all possible words of a certain length is called a de Bruijn sequence. The graph associated with a de Bruijn sequence is called a de Bruijn graph. The path along such a graph that uses every arrow (edge) exactly once is called a Eulerian circuit (and all graphs that allow such a circuit are called Eulerian graphs, making de Bruijn graphs a subset of Eulerian graphs). The path that uses every node (vertex) exactly once is called a Hamiltonian circuit (and you can guess what a Hamiltonian graph is).

It turns out that Leonard Euler provided us with the crucial link that shows why the answer to question (2), “Is it possible to run through every possible combination without being forced to repeat any combination?” is always yes, regardless of alphabet or word size. According to the Mathworld page on Eulerian graphs,

“Euler showed (without proofI don’t know if someone has supplied a proof of this, in the meantime. Something to look up.) that a connected graph is Eulerian if and only if it has no graph vertices of odd degree. […] A directed graph is Eulerian if and only if every graph vertex has equal indegree and outdegree.”

In other words, if on a graph connected by arrows every node has as many arrows coming in as arrows going out, you will always be able to make at least one Eulerian circuit — you will always be able to find a way to cycle through all the arrows without ever getting stuck at a node. This makes sense, intuitively: Take the larger graph above, the de Bruijn graph for base 2, order 3 (which means the nodes represent 3-letter words): every node has an equal number of arrows going out, because the alphabet (base) from which to choose the next letter as you proceed along your circuit is the same at every node. The same goes for arrows coming in, which represent the letter being dropped as we progress along our circuit — it too has to be a member of the same alphabet.

But what about generating a bona fide de Bruijn sequence for our door-code keypad? Well, Mathworld is linked to the math program Mathematica (the brainchild of Stephen Wolfram), and the page on de Bruijn sequences mentions that Mathematica has an algorithm for generating such sequences for any given alphabet and word length. Although Mathematica is perhaps one of the most impressive applications ever made, it also costs 25,000kr., and hence I’ve never managed to justify buying it. Fortunately, there is a 15-day free trial, so I hurriedly downloaded it, and got to work. Here is a trial run, a de Bruijn sequence for 3-digit combinations in base 10:

…9798787770760750740730720710980970960950940930920910108908708608508408308208889998988081009909008007006005004003002000190180170160150140130120119118117116115114113112912812712612512412312213913813713613513413313214914814714614514414314215915815715615515415315216916816716616516416316217917817717617517417317218918818718618518418318219919819719619519419319212111029028027026025024023022922822722622522422392382372362352342332492482472462452442432592582572562552542532692682672662652642632792782772762752742732892882872862852842832992982972962952942932322202103903803703603503403393383373363353349348347346345344359358357356355354369368367366365364379378377376375374389388387386385384399398397396395394343330320310490480470460450449448447446445945845745645546946846746646547947847747647548948848748648549949849749649545444043042041059058057056055955855755695685675665795785775765895885875865995985975965655505405305205106906806706696686679678677689688687699698697676660650640630620610790780779778978879…

Again, I love the density of these sequences. When it came to generating a de Bruijn sequence for 4 digits in base 10, though, Mathematica took its time — 2 hours and 45 minutes, to be exact. By then I had grown restless and had been googling “de Bruijn sequence”, only to find a most surprising page among the results: A Swedish blogger! Hakan Kjellerstrand has a page up with a much faster algorithm for generating de Bruijn sequences. He even singles out the specific solution for Stockholm door-code keypads. So click on that link, print out the result and keep it handy whenever you have a door-code keypad blocking your way.

But two of the five original questions remained unanswered: First, how many such sequences are there? Hakan and Mathematica both provide *one* sample de Bruijn sequence, not a counting function for de Bruijn sequences for a given alphabet and word length.

It turns out the answer wasn’t even known for sure until 2002, when Vladimir Rosenfeld at the University of Haifa published a proof for the general formula in a paper titled “Enumerating de Bruijn Sequences.” It’s not online, as far as I can tell, but he does talk about his results in another paper of his, *Enumerating Kautz Sequences* (original link).

According to Rosenfeld, in 1946 Dutch mathematician N.G. De Bruijn proved a formula for counting the number of shortest circular sequences containing all *q*-letter words using a 2-letter alphabet (base 2). Here it is:

total number = 2

^{2(q-1)–q}

Indeed, for *q* = 3 the result is 2 and for *q* = 4 the result is 16, as shown earlier. This made him famous, and led to this entire class of sequences being named after him, though it doesn’t seem like he proved a generalized formula for any given alphabet size (base). In 2002, Rosenfeld did just that, apparently. For an alphabet size *s* and word length size *q*, the number of circular de Bruijn sequences of length *s ^{q}*is! means factorial. 4! = 4x3x2x1:

(

s!)^{s(q-1)}s^{–q}

Making s=10 and q=4 gives us 10!^{1000}/10000, or 5.79×10^{6555}**Update 2004-10-09:** Well, you can’t trust the internet for anything, can you? The paper by Rosenfeld misprints the formula for the number of circular de Bruijn sequences (I’ve corrected the main text now). The relationship between the number of circular de Bruijn sequences and the number of linear de Bruijn sequences didn’t look right when I read the paper — I thought the difference between these two formulas should be a factor of s^q, because every circular de Bruijn sequence seemed to me to contain that many starting points for linear de Bruijn sequences. But hey, I didn’t *prove* the results, and my blog doesn’t have “expert anonymous reviewers,” so what would I know? Today, though, I found a different formula for the number of circular de Bruijn sequences in Stephen Wolfram’s *New Kind of Science* and this one confirms my hunch. And so far, Wolfram has never failed me. (The formula for the linear de Bruijn sequence remains the same, though.)

**Update 2004-10-21:**Vladimir sent me his original paper, Enumerating de Bruijn sequences [PDF] and indeed there the formula is correct. And an interesting read., sequences. If we want to tally up the more real-world situation, where you need to key in 10,003 digits into the door-code keypad, then the formula is slightly modified:

(

s!)^{s(q-1)}

which gives 10!^{1000} or 5.79×10^{6559} linear de Bruijn sequences. That’s our answer for question (4).

Which leaves us only question (5): “How likely am I to spontaneously generate the shortest possible sequence if I pursue the second, random strategy described above?” To answer this, all we need is to divide the total number of linear de Bruijn sequences (which we just counted) into the total number of sequences that are 10,003 digits long (which is just 10^{10,003}). The answer: 1 in 5.79×10^{3444} times. Given that the number of stars in the universe is about 7×10^{22}, it’s a safe bet to say that *every* pig will need to fly before anyone ever achieves this feat.

Postscript: De Bruijn sequences are actually useful, and crop up in several seemingly unrelated fields. They provide the mathematical underpinning for DNA manipulation tools — DNA being nothing but sequences of words composed of the letters G, A, T and C. Rosenfeld’s paper, too, aimed to provide mathematical tools for understanding “minimal generating sequences” in DNA, that is, “the sequence of minimal length that produces all possible amino acids.” Also, de Bruijn sequences seem to get mentioned a lot in connection with cryptography, especially by Stephen Wolfram in the footnotes to *A New Kind of Science*, though how or why is something I think I need to look into next.

*head explodes*

The easiest way to open a door in Stockholm is to look closely on the kypad. The code does not get changed often, which means that the keypad get worn. So when you only have four keys to test, it just takes maximum 16 combinations. Been using it for years…

No, I’m not a burglar.

Jacken

Actually, all you need to know is either a 11-year-old or be mates with the friendly postperson.

Door codes in Sthlm have a “postpersons” code, otherwise the postperson needs to know every single code to every single house.

So all houses in a single post district has the same postpersons code. (that’s the code that the police has access too)

The 11-year-old? Well they swap codes with each other . . . so much for security measures . . .

Jesus Stefan, you have way too much free time on your hands! Just kick the damn door in if needed…

de Bruijn-sekvenser (portkodsproblemet)Tänk att du har glömt din portkod och ska försöka testa alla möjligheter men vill knappa in så få siffror som möjligt. Hur ska du gå tillväga? Förutsättningen är att portkoden har fyra siffror (0-9) och att man inte behöver…

Jacken, you mention a very interesting variation. If you can tell that there are 4, and not fewer, worn-out buttons, you indeed can deduce for certain that the code has no repeated digits (or else there would only be 3 or fewer worn out keys). However, in that case, there are not 16 but 4!, 24, different possible combinations to try. And I believe the shortest possible sequence to try all possible combinations in this case is 34 digits long, but don’t quote me on that.

I’ve added an update, correcting one of the counting formulas. Please check the post for details.

Stefan

Honestly- do you expect anyone to read let alone comprehend this stuff? I liked your old website format better- with all the pictures. Colour and movement, that’s the ticket.

Stefan, I would like to congratulate you on a well-researched and illuminating post, even if I did only understand about 15% of it, although I might suggest there is a connection between the effort involved, and your love life. Although inaccessible to most people, including myself – I didn’t try hard, but I’m congenitally lazy – it seems these math whizzes are the guys whom big corporations and the FBI pay fuckloads of wanga to ply their black arts. Neal Stephenson would no doubt have turned this into a novel.

I am firmly in the ‘you have way to much time’ camp on this Stefan… but am also quite fascinated and perhaps a little jealous that I don’t have such time.

Can you do the same thing with the rings and the sequences and the words=numbers=objects in a list, and tell me just how long it would take for the proverbial monkey to type up a copy of Hamlet by randomly banging away at a typewriter?

Seriously.

You will have to cheat a bit… put the monkey in front of a copy of the OED instead of a typewriter… the monkey doesn’t type the word- he points to it (gorillas do this now don’t they?)- this should put it into the realm of possibility, as the OED’s words will fill in for the Swedish door digits. Hamlet has a fixed number of words in a specific order (the Swedish door code)… the OED has a fixed number of words to be arranged.

Go to it. How long will it take the monkey?

Of course once we know the number of monkey hours, it should be easy to figure out the number of monkeys required to make it a reality in ones lifetime (assuming a certain loss factor for different monkeys pointing out the same sequences).

If this goes according to plan… I can retask the monkeys to respond to the piles of work on my desk (instead of Hamlet). Provided I can get enough monkeys at my desk to get through the work of the day… I can spend my day in the cafe as well.

i dozed off after reading the first third of the post….maybe some naked pictures strategically placed could help me get to the bottom.

Don’t you hate it when you’ve got a perfectly fascinating problem and your friends accuse you of being boring?

I’m working on now. I’m trying to decide whether Americans or Europeans — or particular groups in Europe– are more depressed. We’re looking for depressed people per million of the population. Even some keywords for a successful google search would be helpful. I picked Sweden to look into because the Swedes are famous for their depressions. That brought me to your comparison of crime figures, and while suicide rates MIGHT suffice, they really don’t because there are so many more down people who don’t pull the trigger.

Exactly, if life is meaningless, then

what’s the pointin pulling the trigger, right?How about per capita psychiatrists? The one flaw I can see in using that statistic is that, by analogy, societies with the fewest dentists would have the best teeth.

Per capita alcoholics, perhaps? Per capita obesity? World Bank happiness indicators? What if you correlate all these indicators and make an index of some sort?

Re my friends: They like to complain a lot but they’re not a bad bunch, in the end.

Very fascinating. I live in Stockholm myself, and if not every time, at least very often when I enter the door at the bottom of the block of flats I live in, I keep wondering if there is a way to enter all possible 4-digit codes on that little keypad with only 10,003 keypresses.

BTW, I don’t find any part of the page particularly strange. It’s straightforward mathematics, and as such well presented with illustrative figures when needed. Thanks for solving my problem.

Geoff: perhaps this site would help you test your theory? Seems Coriolanus is doing better than Hamlet.

Stefan: gorgeous post.

The de Bruijn CodeBLOG@STEFANGEENS.COM: The de Bruijn Code…

Fantastisk~

I believe all inventions start from curiousity.

Pity that in this case you’re not the first one to be into it, unless there should be sth like “Stefan Graph” or “Stefan’s First Law”.

There may be a fatal flaw in this reasoning.

I’m fairly sure that on most door code systems there is a slight delay between punching in the right code and the door clicking open – something like 1.5-2 seconds. Should you hit another number during that delay, the door will not open. I also think that if you hit the numbers too slowly, they may not register as a sequence, but I’m not entirely certain about that.

Either way, it means that rapid-fire punching of any number series – even with the embedded correct four-digit sequence – may not ever get the door to open.

Another effective method for “breaking” the code (works well during cold weather) is simply to breathe on the keypad ! That will reveal which 4 didgits the code is made up of…. and the rest is simple maths

I can•t beleive it. On Hakan Kjellerstrands page, my door code was printed in clear text. It was right there, for crying out load! How can that be?

*head explodes*

OMG, I read the first post and thought the exploding head was a funny comment. I then decided to include it when commenting about my amazing discovery on Hakan Kjellerstrands page. And so I did. And then I saw that the first guy, who•s head accually exploded (can you believe that), is also named Marcus. Man, what•s with this page, it all goes in circles…

A cafe latte’s worth of numbers….steangeens.com (which, incidentally, has a very elegant blog design – I really like his “sideblog” comments – has a great entry on the most efficient way to crack BLOG@STEFANGEENS.COM: The de Bruijn Code – that is, how to spin through all possible comb…

I’m doing a research paper on the use of DeBruijn sequences, and found your site very helpful. Thanks!

QuickiesScriviner.net has an interesting article about taxes and your phone company. Any article that starts with an error about how long ago the Spanish American war took place is a little worrisome, but I love watching badly written law…

Great research! Thanks!

If anyone intends to use monkeys and throw them at the OED, I want the banana concession.

Nice page.

I never really gave a thought about this type of research. I’m positively surprised that 10 000 codes can be tested in as few as 10 003 key punches.

At my place (near Paris, France) our door code is 5 digits long and the keyboard has additional keys: letters A and B. That makes things harder, doesn’t it.

Wait… stop wasting your time with this. The code is 67B34

hey i need a 4 digit code to unlock a phone and i dont know if its even possible but does anyone know where i can find all of the possible combinations on a keypad of a cell phone?!?!? that would be lovely if you could email me!!!!!!

Interesting analysis. The only thing I can add to this impeccable writeup is that, for the binary codes, at least, the minimum-length solutions seem to be related to (and may be directly derivable from) Gray Codes. See, for example, .

hi……….was wondering if you could send me all the possible 4 didgit complimations 0-9! cus i have locked my phone too and it sucks mostly cus it is brand new!!! eeekkk!

Congratulations, I have to make a homework about de Bruijn sentences and i think that here i have found almost all the information i need and very understandable.

Stefan, I liked your post, I know of another program that can generate necklaces and other stuff you might be interested in: http://theory.cs.uvic.ca/root.html

Also, what if you knew the door codes weren’t simple patterns e.g. 0000, 1111, 0101, 1212 etc and so you didn’t have to include them in your de Bruijn sequence. How many sequences would you have then?

I’m investigating de Brujin codes for designing a memory controller for a computer chip. No kidding. This post was a lot easier to read than some of the papers written by mathematicians.

re: post #24 (Sarah)

Q: Can you give me an approximate number of aliens currently interacting with, or on, or under our planet as a whole?

A: “Aliens?” What constitutes such?

Q: Okay. Well then, non-human beings. Extra- terrestrials, Ultra- terrestrials, and so forth.

A: These bases have naturalized the inhabitants. Anomalies occur as much because of where the bases are chosen to be

located as any other factor. Magnetic faults and their inherent portals, you know!

Q: This guy thinks that there is a rather limited number of aliens, and that people ought to get together and resist this

threat because our numbers are greater. Is that, in fact, correct?

A: Not point. The question of the hour is: what is the motive?

Q: Okay, what is the motive?

A: Build a house step by step, and when it is finished, you can move into the neighborhood and out of the motel.

Q: Oh jeez. That does not sound good.

A: Many of you have recently become “bedazzled” by the “information superhighway,” and its accompanying computer

hardware. Gee, we wonder why?

Q: Well, you told us to network. We have been networking like crazy digging up information. Yes, there is a ton of garbage out there, but if we don’t ask, how will we know?

A: Point was: who is manipulating thee? Not so much you specifically, but the others? So many kids & ‘kids-at-heart’

are thunderstruck by techno-sensory toys. Those cellular phones, those pagers and the Christmas toy computers… they

are like, so cool!

Q: So what are you implying about these techno-toys?

A: Fuzzy Jello-brained kids.

Q: Are you saying that pagers & cell phones & techno-toys that kids get for Christmas can have effects on them that turn their brains to Jello?

A: In a figurative sense. All this technology represents a Brave New World. Like Huxley said: “Woe is to those who have been led to eat their brains for lunch.”

Q: My kids have pagers…

A: What do you think comprises the signal content?

Q: I don’t know. What does comprise the signal content?

A: Microwaves.

Q: What do these microwaves do to the individual?

A: Contour brain cell structure.

Q: Do they emit a signal continuously, or only when they are being used?

A: Wave cycle low to high.

Q: How close does the pager have to be to you to have this effect?

A: 4 meters. Cell phones & television & computer screens can be transmitted through thusly.

Q: Is there any kind of device that we can build or purchase that can emit a blocking signal?

A: Knowledge protects.

Q: When you say ‘contouring brain cell structure,’ what would be evidence or results of such effects?

A: Increasingly narrow outlooks and being unable to employ discriminatory thinking.

Q: Confusion?

A: No. Just lack of depth & breadth to one’s mental & psychic abilities.

You very nicely displayed the material about de Bruijn sequences. These have been rediscovered many times in history (I have had a similar experience:). A survey by Harold Fredricksen, titled :A survey of full length nonlinear shift register cycle algorithms”, SIAM Review vol. 24 No.2, pp. 195–221, discusses the known methods of generating such sequences, (a lot more happened since then.

Two interesting points there are:

1) He starts the paper with exactly your code problem, a code that was needed to enter the Baltimore Hilton Inn!! (2) Also on the first page of his paper he displays the formula that counts the total number of de Bruijn sequences that was dicovered by Flye-Sainte Marie in 1894, a 108 years earlier than Rosenfeld 🙂

@Stefan:

Yes, indeed if you have 4 smudged keys you’ll have 24 4-digit combinations. Manually counting, and combining them in 6 sets of 4, you end up with 17 digits in 2 sets, probably as (n^2+1). But I can’t get these 2 sets to overlap except with one trivial digit, which reduces it to 33 digits. But what is the real formula?