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
i'm probably missing something, but isn't the number of strings of natural numbers uncountable?
=> More informations about this toot | More toots from lilacperegrine@clockwork.monster
@lilacperegrine As @glocq worked out, I meant that the finite strings of natural numbers should be contiguous substrings.
=> More informations about this toot | More toots from OscarCunningham@mathstodon.xyz
@OscarCunningham Just so we agree on the priceless: is a "string" necessarily finite? Is a "substring" necessarily contiguous?
=> More informations about this toot | More toots from glocq@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
@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
@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
@OscarCunningham it looks like you can make de Bruijn sequences of order n + 1 by extending a sequence of order n, which would naturally give you all the shorter strings as soon as possible: https://www.sciencedirect.com/science/article/abs/pii/S0020019011001840
=> More informations about this toot | More toots from ianh@mastodon.social
@OscarCunningham now i'm realizing you meant any natural number and not just a fixed set of digits, but maybe it's possible to do something like this while increasing the base by one each time you extend it
=> More informations about this toot | More toots from ianh@mastodon.social
@OscarCunningham after some thinking, it does seem to be possible (since the graph you end up with after increasing the base still has equal in/out degrees). i ended up implementing it here just to see: http://ianhenderson.org/2024-11-15-de-bruijn-type-sequence.html
=> More informations about this toot | More toots from ianh@mastodon.social
@ianh Thanks, this is the best solution I've seen so far
=> More informations about this toot | More toots from OscarCunningham@mathstodon.xyz
@OscarCunningham https://oeis.org/A002262
=> More informations about this toot | More toots from fl@mathstodon.xyz
@fl Ah, I think you are answering a different question than I intended. This sequence contains every infinite sequence as a subsequence, whereas I wanted every finite string as a contiguous substring. I've edited the question to clarify.
=> More informations about this toot | More toots from OscarCunningham@mathstodon.xyz
@OscarCunningham the examples section on the Wikipedia article on disjunctive sequences may be related? Though it doesn't talk about complexity of such sequences as far as I can skim
=> More informations about this toot | More toots from jaycech3n@mathstodon.xyz
@jaycech3n Ooh, 'disjunctive sequence'! Now I have a term to search for
=> More informations about this toot | More toots from OscarCunningham@mathstodon.xyz
@OscarCunningham The continued fraction of any algorithmically random real (e.g. Chaitin's Ω) should satisfy your first criterion.
https://www.sciencedirect.com/science/article/abs/pii/S0890540122000189
I think it's also likely that the regular cf for pi does.
=> More informations about this toot | More toots from metaweta@mathstodon.xyz
@OscarCunningham I can give an example but I'm not sure it's interesting. List the 1-element sequences from {0}, then the 2-element sequences from {0,1}, then the 3-element sequences from {0,1,2} etc.
=> More informations about this toot | More toots from sjb@mstdn.io This content has been proxied by September (3851b).Proxy Information
text/gemini