6
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
this post was submitted on 22 Apr 2024
6 points (75.0% liked)
Mathematics
502 readers
1 users here now
A community for discussing mathematics and developments in mathematics.
founded 2 years ago
MODERATORS
@oblomov @mathematics @math@lemmy.ml @math@kbin.social No solution, but the problem is related to de Bruijn sequences (https://en.wikipedia.org/wiki/De_Bruijn_sequence), for which there exists a lot of literature.
@mrdk @mathematics @math@lemmy.ml @math@kbin.social
oh, interesting. It's definitely related, although we allow different substrings to start at the same place, and this has a huge impact on the lengths (also it's not cyclic in our case, but that probably makes things worse).
@mrdk @mathematics @math@lemmy.ml @math@kbin.social also this might explain why @mau saw some relation to Gray codes in the binary case.
@oblomov well, a Gray code codes all n-bit sequences from 000...0 to 111...1. It's a bit overkill (we don't need the sequence with all 0) but probably the overhead is just 1.
Cc: @mrdk @mathematics @math@lemmy.ml @math@kbin.social