Express a number with a combination of arithmetic operations and a single number

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.

• Please outline what is yours method to do this. How will you express 10^12 + 7, using only digit 8? Jul 1 '19 at 20:30
• $(8+\frac 8 8 +\frac 8 8)^{\frac {8+8+8}{8+8}8}+8-\frac 8 8$ Jul 2 '19 at 7:22
• 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. Jul 3 '19 at 12:00
• 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. 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$$.