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

Toot

Written by ianh on 2024-11-15 at 18:59

@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

Descendants

Written by ianh on 2024-11-15 at 19:03

@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

Written by ianh on 2024-11-15 at 22:15

@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

Written by Oscar Cunningham on 2024-11-16 at 13:57

@ianh Thanks, this is the best solution I've seen so far

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