Mathematics

495 readers

2 users here now

A community for discussing mathematics and developments in mathematics.

founded 2 years ago

MODERATORS

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? (sociale.network)

submitted 6 months ago* (last edited 6 months ago) by [email protected] to c/[email protected]

6 comments fedilink hide all child comments

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 @[email protected] @[email protected]

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?

#math #maths #numberTheory #combinatorics

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 4 points 6 months ago* (last edited 6 months ago) (3 children)

@oblomov @mathematics @[email protected] @[email protected] 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.

[–] [email protected] 1 points 6 months ago (2 children)

@mrdk @mathematics @[email protected] @[email protected]
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).

[–] [email protected] 1 points 6 months ago (1 children)

@mrdk @mathematics @[email protected] @[email protected] also this might explain why @mau saw some relation to Gray codes in the binary case.

[–] [email protected] 1 points 6 months ago

@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 @[email protected] @[email protected]