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 "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.

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).

• Thanks for the info. Since you have found so many counter examples, do you have an idea how i could fix my algorithm? Looking at the example n=46 i see that GetExpression(45)+1 has less 1's than GetExpression(46). So i was thinking of a dynamic programming algorithm where i calculate GetExpression(n) by looking wether GetExpression(n-1)+1 or an multiplication of two numbers has the least amount of 1's. Dec 28 '20 at 12:14
• Your algorithm ends up doing a prime factorisation of n, and for primes p calculates 1 + GetExpression(p-1). I did additionally an exhaustive search trying GetExpression(d) + GetExpression(n-d). Doing this for small d might be good enough. Dec 28 '20 at 20:50