With my friend ( tommy1729 ) I was thinking about representations of positive integers.
We can write them in binary
$$n = \sum_{i=1}^I a_i 2^i$$
Where the $a_i$ are all either $0$ or $1$.
Or we can write them in base 3 where the coeficients are in the range ${0,2}$.
But we can also mix them.
Now we know that binary is equivalent to the minimum amount of powers of 2 needed. And similar for ternary ( base 3).
So we consider writing positive integers by adding the least amount of powers of 2 and powers of 3.
Tommy1729 immediately pointed out to me that this minimum representation was not Unique !!
His simple example
$$ 20 = 9 + 9 + 2 = 16 + 3 + 1 $$
Shows that.
Many questions occur spontaniously.
Let $f(n)$ be the number of powers ( of 2 and 3 ) that we need. Or equivalently the digit Sum of $x$ in base 2 and $y$ in base 3 such that $n = x + y$ and $x,y$ are chosen such that the digit sum is minimal.
So $ f(20) = 3 $. In 2 ways !
Let $g(n)$ be the number of ways $n$ can be minimally represented. So $g(20) = 2$. Let h(n) = q be the solution to $g(q) = n$ such that $q$ is as small as possible.
Many questions exist for $f,g,h$.
Clearly $ 0 < f(n) < ln(n + 2)/ln(2)$
But unlike the binary case $ f(n) < f(2n+1) $ is not always true.
What is known about these 3 functions ???
I Will have to make Some choices since asking 100 questions is not suited here.
Question 1)
What are the asymptotics of $f,g,h$ ??
Is $f(n)$ on average of the form $ C1 ln(n)/ln(2) + C2 ln(n)/ln(3) $ ? Closed forms for the constants $C1,C2 $ ?
What are the asymptotics of the local max of $f,g,h $ ??
Let $bi(n) $ be the digit Sum in binary for $n$. Are there infinitely many cases where $f(n) = bi(n)$ ?? If So What are the asymptotics of n satisfying that ??
Question 2
How to compute these values well ?
Is there Some kind of greedy type algoritme that works best ?
What is the runtime and memory use of the best algorithms ?
Question 3
How does this relate to data compression ideas ?
I mean , we know representing any or all integers between $1,n$ puts limits on $bi(n)$ because we Cannot expres most by 4 nonzero digits.
A similar thing must exist for $f(n)$.
Question 4
Are there parametric equalities or inequalities known ??
Such as say $f(2n) + f(3n) + f(6n) > f(n) + f(5n) $ ?
Question 5
Are there analytic infinite sums with closed form ?
We know $\sum_{K=1}^{\infty} bi(K)/(K (K+1)) = ln(4)$.
So maybe we have analogues for $f$ ?
Maybe it is easier to make statements about
$$ F(n),G(n),H(n)$$
Where $ F(n) = f(1) + f(2) + ... f(n) $ and similar for $g,h$.
Question 6
Does mod aritmetics matter here ?
Any theorems relating $f$ and modular aritm ? ( like with the partition function )
I have never seen this before.
This is not a full solution to the problem, just a note on applications of the greedy algorithm to it.
First of all, I think you have to allow expressions of the form $2\times 3^k$ in the greedy algorithm. Otherwise, consider $n=54=2\times 3^3$. Clearly, $f(54)=2$ but the largest perfect power of $2,3$ not exceeding $54$ is $32$ and extracting a $32$ does not get you a length $2$ expression.
So, now consider the greedy algorithm where you extract the largest number of the form $2^a,3^b,2\times 3^b$ not exceeding $n$. Does this always get you a minimal expression?
Sadly, the answer is still no. Consider $n=5120=2^{12}+2^{10}=4096+1024$ Obviously $f(5120)=2$. But if you use the greedy algorithm I described you would first extract $4374=2\times 3^7$. We note that $5120-4374=746$ is neither a power of $2$ nor of $3$ so the greedy algorithm I described does not get you a minimal expression. (indeed, since $f(4374)=2$ already there was no chance you'd get a minimal expression this way).