A curious math problem I came up with: given a target, what’s the fewest digits an integer must have (in a given base) to contain all integers from 0 to the target, as substrings?
http://wok.oblomov.eu/mathesis/number-substrings/
@mathematics @math@lemmy.ml @math@kbin.social
e.g. for a target of 19 a candidate representative would be 1011213141516171819 in base 10, that has 19 digits. Can it be done in less, or is $\sigma_10(19) = 19$?
Can we find a general rule? Any properties of this function?
@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.