Today I ran into a this relatively simple (At least from my perspective ) problem. Basically the task is to be able to express any number using only a single number an any combination of arithmetic operations, square roots, exponentiation or factorials. To further elaborate I will make an example.

The input of the program would be a number 57 and a 8. The solution would be expressing the number 57 using only 8s and any of the defined operations.

In this case the number 57 could be expressed as 57 = (8+8+8+8+8+8+8)+8/8 Alternatively if we had the number 25 and 3 as an input, we could also do 25 = 3^3 - 3/3 - 3/3

The task is to define the input number with a similar method mentioned above, using the least amount of operations.

The person who created this problem defined it as difficult and no matter how hard I think about it, I just can not find a reason why. In most cases the problem will spin around simple integer factorization and in special cases, using factorials (With big numbers) or exponentiation will yield a less lengthy result.

What I am asking for is if there is any better, more efficient method to solve this problem and whether I am missing something obvious which would make this problem look as "Difficult" as it was defined.

Thanks for the answers in advance.

  • 2
    $\begingroup$ Please outline what is yours method to do this. How will you express 10^12 + 7, using only digit 8? $\endgroup$ Jul 1 '19 at 20:30
  • 1
    $\begingroup$ $(8+\frac 8 8 +\frac 8 8)^{\frac {8+8+8}{8+8}8}+8-\frac 8 8$ $\endgroup$ Jul 2 '19 at 7:22
  • $\begingroup$ Are you looking for a formal proof of, e.g. NP-hardness, EXP-hardness or a related complexity theoretic notion? Or are you more interested in intuition or whether the rough idea you describe will work? You claim that this is easy. Have you created an algorithm for this problem that is efficient and provably correct? Note that many problems which appear easy to humans are hard to compute and vice versa. $\endgroup$
    – Discrete lizard
    Jul 3 '19 at 12:00
  • $\begingroup$ More like whether my idea is correct, but I am also willing to accept NP hardness. As you said, problems seem easy till you try to solve them. That is why I am asking this question. Whether I have an algorithm, I do. I will edit my post and send it here. There are still slight problems with the algorithm. $\endgroup$
    – Erik9631
    Jul 3 '19 at 15:05

If you have any number at all, say $N$, then you can write it as $\frac 8 8$ followed by $N-1$ occurrences of $+\frac 8 8$.

The difficulty of the problem lies in finding short sequences of 8s that will work. The best known way is to enumerate all the possibilities.

For instance, with six 8s, write them out in a row and then insert operators between them and after them, to generate all valid reverse-Polish notation expressions which lead to a single result.

As well as the usual arithmetic operators, include a “concatenate” one which, immediately following two 8s, produces 88.

Enumerating all conceivable RPN strings is not hard: there can only ever be five dyadic operators. Filtering them to select just the valid ones is not hard either: probably the best way is to include that process in the process of evaluating each one.

  • $\begingroup$ Could you make an example? I got lost at "with 6 8s". What do you mean by that? $\endgroup$
    – Erik9631
    Jul 2 '19 at 12:17
  • $\begingroup$ This lends itself to a breadth first search, but the challenge will be the exponential growth in the size of the search space as you add levels i.e. combinatorial explosion. $\endgroup$
    – gandalf61
    Jul 2 '19 at 16:44

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.