Ancestors

Written by Oscar Cunningham on 2024-11-15 at 18:03

Are there any interesting integer sequences that contain every finite string of natural numbers as a contiguous substring? In particular ones that try to do so as efficiently as possible? Like the index at which a string first appears isn't too much greater than the number of 'simpler' strings, in some sense.

[#]Math #Maths #Mathematics

=> More informations about this toot | More toots from OscarCunningham@mathstodon.xyz

Written by Grégoire Locqueville on 2024-11-15 at 18:37

@OscarCunningham By the way (but you might already know that), a lower bound for the finite version of your problem was found by an anonymous 4chan user in 2011. @gregeganSF also worked on the finite problem — he wrote an algorithm to explicitly build such finite sequences

https://en.wikipedia.org/wiki/Superpermutation

=> More informations about this toot | More toots from glocq@mathstodon.xyz

Toot

Written by Oscar Cunningham on 2024-11-15 at 21:46

@glocq Yes, except that superpermutations only need to contain all the permutations, whereas I would like all strings even with repeats. In the finite case this is actually an easier problem answered by 'de Bruijn sequences', as @jcreed mentioned.

=> More informations about this toot | More toots from OscarCunningham@mathstodon.xyz

Descendants