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 "1"
- 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 "(GetExpression(divider)$\times$GetExpression($\frac{n}{divider}$))"
- if n is prime return "(1+GetExpresion(n-1))"
Runtime:
Due to the loop trying to find the divider going in $\mathcal{O}(n)$ and both options of recursive calls having $0<\alpha_1=\frac{n-1}{n}<1$ (in the prime case) and $0<\alpha_2+\alpha_3<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<1$ but only for $\alpha_1<1$ and $\sum_{i=2}^3\alpha_i<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.
