The generalized case that include sequences with repeated elements[1] are De Bruijn sequences[2]. These are cyclic sequences that contain each possible n-length string using k symbols, each appearing exactly once.
I was introduced to this idea on the comp.risks forum, where it was presented as an attack on an answering machine with a 5-digit passcode, which, naively, would require an average of 50,000 guesses of 5 digits each, or 250,000 key presses. But this particular device not only didn't lock out after some number of incorrect guesses, it didn't require a separator character between guesses. It just listened for the correct five digits consecutively, regardless of what you had entered before. So a superpermutation just 153 digits long was sufficient to crack every device.
Possibly. It was 20 years ago. I'm reconstructing via my (possibly flawed) understanding of the linked article. (My vague recollection was something like 250 digits for a 4-digit passcode.)
And I just realized I mistakenly conflated 5-digit permutations of 5 digits with 5-digit passcodes of 10 digits. Whoops.
You’re thinking of De Brujin sequences, not superpermutations, unless there’s an additional restriction that a digit cannot be used twice in a password.
Yes, and in this case the sequence is specifically the "classic" De Bruijn sequence [1]; however, there are other sequences that bear De Bruin's name, such as the Moser de Bruijn sequence, which is the one I reference most due to its relation to Z-order curves and pairing functions.
Greg Egan has some great sci-fi books. Some of the concepts are a little beyond me as he dips into advanced mathematics and physics, but he does a pretty good job of keeping it accessible.
Permutation City, Diaspora, and his various collections of short stories (e.g. Axiomatic, Luminous) are worth reading.
He takes ideas, like what's linked in the OP, and builds worlds and stories around them in terms of their implications and impacts on society and individuals.
I would recommend starting with the short stories (e.g. Axiomatic) as Egans style is a perfect fit for that format (take an idea, try to craft an interesting story around it). The formula fails for some of the novels as they can be difficult to read if you are only superficially familiar with the technical details.
Agreed. His work shines in short story format. The full length novels I mentioned (Permutation City and Diaspora) are the ones that I think hold up the best to the longer format.
He posits a different structure for spacetime and then builds a whole universe around it. Some of it is indeed heavy going but a lot of it is also really inspired storytelling.
In case you just came to read the comments (as I often do) - this page links to discussions by Egan on a ton of other interesting topics like some special cases of general and special relativity, unusual orbits, and higher-dimensional geometry. Pretty cool stuff!
Yesterday I came across this interesting result dealing with shortest number with the digits 1 through 7 arranged in all possible orders, thanks to John Baez on twitter [1]. Great to discover this here.
De Brujin sequences as mentioned in one of the comments deals with the generalized case involving repetition as well. There is an interesting mnemonic for remembering the composition of different "ganas" (syllabic units) in Sanskrit poetry that is an example of De Brujin sequence - Ya-Maa-Taa-Raa-Ja-Bhaa-Na-Sa-La-Gam . In Sanskrit metre, syllables can be either long (Maa for example) or short (Ma). The basic units are composed of 3 syllables and thus 2x2x2 = 8 possible types - long-short-long for example. These basis units are called ganas and have a name attached to them. The mnemonic helps one decode the composition of a gana. If you want to know the composition of "Ja Gana" for example, go to the part that starts with Ja and get the substring with three syllables starting with Ja i.e Ja-Bhaa-Na. Since these syllables are short, long and short, Ja Gana corresponds to short, long and short.
Not sure how much it could add to the conversation, but I implemented a library to find almost minimal superpermutations in go a while back. Uses a technique I didn't see anywhere else.
This method produces superpermutations of length 1! + 2! + ... + n!, which was believed for a long time to be the best possible. But Greg Egan’s new result shows it’s possible to do a lot better than that.
The generalized case that include sequences with repeated elements[1] are De Bruijn sequences[2]. These are cyclic sequences that contain each possible n-length string using k symbols, each appearing exactly once.
[1] i.e. "111", which isn't a permutation of the set {1, 2, 3}, but can be made from the elements of that set
[2] https://en.wikipedia.org/wiki/De_Bruijn_sequence
I was introduced to this idea on the comp.risks forum, where it was presented as an attack on an answering machine with a 5-digit passcode, which, naively, would require an average of 50,000 guesses of 5 digits each, or 250,000 key presses. But this particular device not only didn't lock out after some number of incorrect guesses, it didn't require a separator character between guesses. It just listened for the correct five digits consecutively, regardless of what you had entered before. So a superpermutation just 153 digits long was sufficient to crack every device.
I think you must be misremembering; if you dial a sequence of 153 digits, you can't possibly test more than 149 different 5-digit substrings.
Possibly. It was 20 years ago. I'm reconstructing via my (possibly flawed) understanding of the linked article. (My vague recollection was something like 250 digits for a 4-digit passcode.)
And I just realized I mistakenly conflated 5-digit permutations of 5 digits with 5-digit passcodes of 10 digits. Whoops.
Why not just re-read RISKS?
* https://catless.ncl.ac.uk/Risks/7/69#subj5.1
* https://catless.ncl.ac.uk/Risks/7/73#subj4.1
* https://catless.ncl.ac.uk/Risks/9/68#subj2.1
You’re thinking of De Brujin sequences, not superpermutations, unless there’s an additional restriction that a digit cannot be used twice in a password.
Yes, and in this case the sequence is specifically the "classic" De Bruijn sequence [1]; however, there are other sequences that bear De Bruin's name, such as the Moser de Bruijn sequence, which is the one I reference most due to its relation to Z-order curves and pairing functions.
[1] https://en.wikipedia.org/wiki/De_Bruijn_sequence
[2] https://en.wikipedia.org/wiki/Moser-de_Bruijn_sequence
NB: I suspect the number you are thinking of is a 2530 digit sequence on a 4-digit lock, not 153 on 5...
https://en.wikipedia.org/wiki/De_Bruijn_sequence#Uses
Greg Egan has some great sci-fi books. Some of the concepts are a little beyond me as he dips into advanced mathematics and physics, but he does a pretty good job of keeping it accessible.
Permutation City, Diaspora, and his various collections of short stories (e.g. Axiomatic, Luminous) are worth reading.
He takes ideas, like what's linked in the OP, and builds worlds and stories around them in terms of their implications and impacts on society and individuals.
I would recommend starting with the short stories (e.g. Axiomatic) as Egans style is a perfect fit for that format (take an idea, try to craft an interesting story around it). The formula fails for some of the novels as they can be difficult to read if you are only superficially familiar with the technical details.
Agreed. His work shines in short story format. The full length novels I mentioned (Permutation City and Diaspora) are the ones that I think hold up the best to the longer format.
Check out his Orthogonal trilogy
https://news.ycombinator.com/item?id=8895331
He posits a different structure for spacetime and then builds a whole universe around it. Some of it is indeed heavy going but a lot of it is also really inspired storytelling.
Ditto for Dichronauts.
In case you just came to read the comments (as I often do) - this page links to discussions by Egan on a ton of other interesting topics like some special cases of general and special relativity, unusual orbits, and higher-dimensional geometry. Pretty cool stuff!
Yesterday I came across this interesting result dealing with shortest number with the digits 1 through 7 arranged in all possible orders, thanks to John Baez on twitter [1]. Great to discover this here.
De Brujin sequences as mentioned in one of the comments deals with the generalized case involving repetition as well. There is an interesting mnemonic for remembering the composition of different "ganas" (syllabic units) in Sanskrit poetry that is an example of De Brujin sequence - Ya-Maa-Taa-Raa-Ja-Bhaa-Na-Sa-La-Gam . In Sanskrit metre, syllables can be either long (Maa for example) or short (Ma). The basic units are composed of 3 syllables and thus 2x2x2 = 8 possible types - long-short-long for example. These basis units are called ganas and have a name attached to them. The mnemonic helps one decode the composition of a gana. If you want to know the composition of "Ja Gana" for example, go to the part that starts with Ja and get the substring with three syllables starting with Ja i.e Ja-Bhaa-Na. Since these syllables are short, long and short, Ja Gana corresponds to short, long and short.
[1] https://twitter.com/johncarlosbaez/status/105338502434972057...
Edit: Formatting and correction
Not sure how much it could add to the conversation, but I implemented a library to find almost minimal superpermutations in go a while back. Uses a technique I didn't see anywhere else.
https://github.com/g-harel/superpermutations
The technique may be different, but the results seem to be identical to what you get from the standard method e.g. described in Section 2 of http://www.njohnston.ca/wp-content/uploads/2013/03/minimal_s...; or section 1 of https://arxiv.org/pdf/1408.5108.pdf; or as implemented by https://github.com/superpermutators/superperm/blob/master/bi...
This method produces superpermutations of length 1! + 2! + ... + n!, which was believed for a long time to be the best possible. But Greg Egan’s new result shows it’s possible to do a lot better than that.
It looks like 4chan had us all beat according to Robin Houston
https://threadreaderapp.com/thread/1054637891085918209.html
https://news.ycombinator.com/item?id=18292061
One person in the 4chan discussion suggested writing an answer at https://math.stackexchange.com/questions/15510/ .
The original link is inaccessible to me; alternate link: http://members.iinet.net.au/~gregegan@netspace.net.au/SCIENC...
That's unusual. You could forward that to Greg Egan [1] to see if it's due to a configuration issue on his side.
[1] On Twitter: https://twitter.com/gregeganSF
He's aware. https://twitter.com/gregeganSF/status/1032880814457901056