Given an integer N, I want to represent every integer from 1 to N using a set of symbol combinations drawn from a predefined set of symbols $\mathbf S$ .
- If $\mathbf S$ only has one character 'A', then 1 = 'A', 2 = 'AA', 3 = 'AAA' etc is the only possible solution.
- If $\mathbf S$ has two characters 'A' and 'B', then 'B' can represent anything smaller than N. One solution is 1 = 'A', 2 = 'B', 3 = 'BA', 4 = 'BB'; or we can have 1 = 'A', 2 = 'AA', 3 = 'B', 4 = 'BA' and so on.
The representations are NOT permutations, i.e. 'BA' and 'AB' represent exactly the same number.
I am trying to find a solution that minimizes the total number of characters used specifically for the case N = 24 and $|\mathbf S|$ = 4.
Questions:
- Is there a systematic way to deduce the solution (e.g. using mathematical induction? But how can I do mathematical induction with two varying variables?)
- How can I proof that a solution is optimal? (any other solution will end up using more characters)
- Is it possible to generalize the solution to any N and any size of $\mathbf S$?
Note: I am not asking for the solution. Rather, I am asking for an approach which would lead me to find it.