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.





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


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


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

  • $\begingroup$ 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. $\endgroup$ Dec 28 '20 at 12:14
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Dec 28 '20 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.