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
@OscarCunningham this sounds like a generalization of https://en.wikipedia.org/wiki/De_Bruijn_sequence
=> More informations about this toot | More toots from jcreed@mastodon.social
@OscarCunningham the biggest difficulty I have in trying to come up with a nice, canonical definition of such a thing is there seems to be an inherent tension between a sequence trying to cram in as early as possible substrings of larger and larger alphabets, versus trying to cram in longer and longer substrings of a given alphabet.
=> More informations about this toot | More toots from jcreed@mastodon.social
@OscarCunningham To put it another way: it seems obvious you have to both gradually turn up the alphabet size and the sequence-length, but there seems to be a missing parameter to tell us how we're suppose to trade off one goal with the other.
=> More informations about this toot | More toots from jcreed@mastodon.social
@jcreed Yes definitely. My intuition was that we should prioritise them according to nᵏ, where n is the largest symbol in the string and k is the string length.
=> More informations about this toot | More toots from OscarCunningham@mathstodon.xyz
@OscarCunningham huh I see how that is a nice choice, since that counts how many such strings there are
=> More informations about this toot | More toots from jcreed@mastodon.social This content has been proxied by September (3851b).Proxy Information
text/gemini