Create an optimal to express all natural number as an arithmetic expression using the alphabet $\Sigma=\{(,),1,+,\times\}$ Hope you had a fantastic christmas break :)
I am trying to find an algorithm in polynomial time that finds the shortest arithmetical expression (the one with the least amount of 1 symbols) to express any natural number, while only using the elements of $\Sigma=\{(,),1,+,\times\}$.
As an example there are multiple ways to express $6\in \mathbb{N}$. but we want the one with the least amount of 1 symbols.
1+1+1+1+1+1
(1+1)*(1+1+1)
(1+1)*1+1+1+1+1
Algorithm:
My current algorithm GetExpression(n) uses a recursive mechanism to get the expression for a number $n\in \mathbb{N}$.

if $n=1$ return &quot;1&quot;
trying to find a divider for n (for loop from i=2 to $\lceil \sqrt{n} \rceil$ with trying $n\mod i=0$)
if there is a divider return &quot;(GetExpression(divider)$\times$GetExpression($\frac{n}{divider}$))&quot;
if n is prime return &quot;(1+GetExpresion(n-1))&quot;

Runtime:
Due to the loop trying to find the divider going in $\mathcal{O}(n)$ and both options of recursive calls having $0&lt;\alpha_1=\frac{n-1}{n}&lt;1$ (in the prime case) and $0&lt;\alpha_2+\alpha_3&lt;1$ (in the non-prime case) we can use the master theorem to see, that our agorithm runs in $\mathcal{O}(n)$ (since we only make one of both options at a time we dont need to look for $\sum_{i=1}^3\alpha_i&lt;1$ but only for $\alpha_1&lt;1$ and $\sum_{i=2}^3\alpha_i&lt;1$)
(actually we need to make a special case for $divider=2$ since there couldbe $\alpha_2+\alpha_3=\frac{1}{2}+\frac{2}{4}=1$ if $n=4$ but we don't care right now).
Correctness:
My problem is how to proof that this algorithm is correct. I was thinking about a induction but i have no glue how to build it.
You can't prove that your algorithm is correct because it isn't. First counter example is n = 46. If we don't bother writing 2 = 1+1 to make it more readable, your algorithm gives
46 = 2 * (1 + 2 * (1 + 2 * (1 + 2 * 2)))

which uses 13 1's.
A better solution is
46 = 1 + ((1 + 2) * ((1 + 2) * (1 + 2 * 2))

which uses only 12 1's.
The difference is bigger for n = 235 (difference 2), n = 649 (difference 3), n = 1,081 (difference = 4), n = 7,849 (difference = 5), n = 33,793 (difference = 6), n = 221,617 (difference = 8).