Recombination of a number into an equal mathematical formula

Question

I was thinking about a math / algorithm problem and would appreciate your input on how to solve it!

If I have a number (for example, 479), I would like to combine its digits or their combination with a mathematical formula corresponding to the original number. All digits should be used in the original order , but can be combined with numbers (therefore, 479 allows 4, 7, 9, 47, 79), but each digit can be used only once , so you cannot have something like 4x47x9. since now number 4 has been used twice.

Now an example to demonstrate how I think about it. The example is mathematically incorrect, because I could not come up with a good example that really works, but it demonstrates the input and expected results.

Input Example: 29485235

Result: 2x9+48/523^5

As I said, my example does not add up (2x9 + 48/523 ^ 5 does not lead to 29485235), but I wondered if there was an algorithm that would actually allow me to find a formula consisting of a source of numeric digits in the original the order that in the calculation gives the original number.

Regarding the type of math used, I would say parentheses () and Add / Sub / Mul / Div / Pow / Sqrt.

Any ideas on how to do this? My idea was to simply roughly force it, dividing the number by random and making calculations, hoping for a result. Should there be a better way though?

Change If it’s easier in an unoriginal way or if you have an idea to solve it, ignoring some of the “conditions” described above, it will still help to understand how to solve this problem.

Answer 1

For numbers up to 6 digits or so, I would say brute force as follows:

1) Divide your initial value into a list (array, regardless of language) of numbers. Initially, these are numbers.

2) For each pair of numbers, combine them together using one of the operators. If the result is the target number, then return success (and print all the operations performed on exit). Otherwise, if it is an integer, write down a new, smaller list consisting of the number you just counted and the number you didn't use. Or you can allow non-integer intermediate results, which will make the search space a bit larger. Binary operations:

• Add
• subtract
• multiply charged
• divide
• power
• concatenate (which can only be used for numbers that are either original digits or were created by concatenation).

3) Suppose that the square root inflates the search space to infinity, since this is a unary operator. So you will need a way to limit the number of applications, and I'm not sure what it will be (loss of accuracy, as the answer approaches 1, maybe?). This is another reason for allowing only integer intermediate values.

4) Rebirth will quickly lead to overflow. 2 ^ (9 ^ (4 ^ 8)) is too large to store all the numbers directly [although in base 2 it is pretty obvious that they ;-)]. Therefore, you will either have to accept that you can skip decisions with large intermediate values, or you will have to write a bunch of code to do arithmetic in terms of factors. Obviously, they do not interact very well with the add-on, so you may have to make some assessment. For example, just looking at the magnitude of the number of factors, we see that 2 ^ (9 ^ (4 ^ 8)) is nowhere near (2 ^ 35), so there is no need to calculate (2 ^ (9 ^ (4 ^ 8)) + 5) / (2 ^ 35). It cannot be 29485235, even if it were an integer (which, of course, is not, this is another way to exclude this specific example). I think that handling these numbers is more complicated than the rest of the problem put together, so perhaps you should limit yourself to unique authority to start with, and possibly results that correspond to a 64-bit integer, depending on what language you are use.

5) I forgot to exclude a trivial solution for any input, just by concatenating all the numbers. However, this is fairly easy to handle by simply supporting the parameter through recursion, which tells you if you have performed any operations not related to route concatenation into your current sub-problem. If you did not, then ignore the false match.

My 6-digit score is based on the fact that it’s quite easy to write a Countdown solver that runs in the second fraction, even when there is no solution. This problem is different in that the numbers must be used in order, but there are more operations (the countdown does not allow exponentiation, square root or concatenation or non-integer intermediate results). In general, I think this problem is comparable if you solve the problems with square root and overflow. If you can solve one case in a split second, then you can go too far through a million candidates in a reasonable amount of time (provided that you do not mind leaving your computer).

At 10 digits, brute force seems impossible, because you need to consider 10 billion cases, each of which requires a significant amount of recursion. Therefore, I think you will reach the limit of brute force somewhere in between.

Note also that my simple algorithm at the top still has a lot of redundancy - it does not stop you (4,7,9,1) → (47,9,1) → (47,91), and then later also (4.7 , 9.1) → (4.7.91) → (47.91). Therefore, if you do not find out where these duplicates will be duplicated, and avoid them, you will try (47.91) twice. Obviously, there is not much work when there are only 2 numbers in the list, but when there are 7 numbers in the list, you probably do not want, for example. add 4 of them together in 6 different ways, and then solve the resulting 4-point problem 6 times. Cleverness is not required here for the Countdown game, but for everyone I know about this problem, it can make the difference between coarse forcing 8 digits and coarse forcing 9 digits, which is very significant.

Answer 2

Such numbers, as I recall, are extremely rare if they survive. Some numbers can be expressed by their components in a different order, for example, 25 (5).

In addition, an attempt to solve brute force is hopeless, at best, given that the number of permutations increases very rapidly as the numbers grow in numbers.

EDIT: Partial Solution.

A partial solution, decisive in some cases, would be to decompose the number into its prime factors. If its prime factors are the same, and the indicator and coefficient are present in the digits of a number (for example, 25), you have a specific solution.

Most numbers that fall into these types of patterns will do this either with multiplication or with pow () as the main driving force; adding just doesn't increase it enough.

Answer 3

Failed to create a neural network that replicates Carol Warderman. I see nothing but brute force work. People are very smart seeing patterns in problems like this, but coding such an understanding is really hard.