How to make the number 100 from any other six-digit number

A couple of weeks ago, in search of an answer to a task that was completely unrelated to the description described here, I, by the will of the search engines, came across the following post: How to make from 123456789 the number 100 or 0 .

After reading it, I remembered how half a year ago I solved the same, but slightly more global task. In this article I would like to share my solution and give the opportunity to "play" with the algorithm. But first, a little background.

Prehistory

Long ago, when people did not have smartphones, when traveling by public transport, everyone entertained himself as best he could. One of these ways not to get bored was an entertaining game that helped not only to pass the trip on the bus, but also a little to “stir the brains”. It sounds like that. There is a six-digit number on the bus ticket. It is necessary, placing brackets and signs of mathematical operations between the numbers, to get an expression that after performing the operations will be equal to 100. The set of operations is standard: addition, subtraction, multiplication, division.
')
I don’t remember who taught me this game, and which of my friends I infected, but until now we periodically like to have fun. And now, six months ago, I got the following example.



Either the combination turned out to be difficult, or at that time I had not practiced for a long time, but with this example I spent 15 minutes in the head. I finally decided the example, but the sediment from the realization that I could have had a few hours to no avail was left. In addition, even for a specific number, it will be problematic to prove such a property (of course, if you are not a professor of number theory). Therefore, I decided to solve this problem using programming.

Solution and algorithm

A warning. The author of this article is not a professional programmer. However, he will gratefully accept useful tips for improving the proposed algorithm or its implementation.

We will solve the task with the help of brute force. In this case, three different characteristics of the solution will have to be searched:

1. Various splits of the original number into subsets;
2. For each partition - a different arrangement of operations;
3. For each arrangement of operations - a different order of operations (arrangement of brackets).

First cycle

In the first loop, we will generate the next partition. To do this, we represent an arbitrary six-digit number in the form of an ordered set of numbers with five “containers” between them: 1_2_3_4_5_6. In each container, we can put either 1, which will mean gluing adjacent numbers, or 0 - adjacent numbers will belong to different numbers. In total there are 2 ^ 5 = 32 different splitting options, not so much. The split specified in the example is encoded by the sequence 10101.

It is possible to iterate over such options elementarily - we set the initial partition (00000), and successively add a unit to it in the binary number system 31 times.

Second cycle

In the second cycle, we have N + 1 numbers and N containers between them. You may notice that the number of containers N is determined by the number of zeros in the partitioning code. But more important here is the realization that in these new containers we have to decompose various operations from the set (+, -, *, /). In the worst case, N = 5, so the worst estimate is 4 ^ 5 = 1024 variants of the arrangement of operations.

You can iterate over the arrangements of operations in a manner similar to the previous one. We encode each operation with our key (0, 1, 2, 3), set the initial set of operations 00000, and successively 4 ^ N - 1 times add to it a unit in the quaternary number system.

Third cycle

And, finally, in the third cycle you need to place brackets. Of course, we will not do this completely “in the forehead”, placing brackets somehow and counting the balance of opening and closing ones. It is easier to note that for the same N containers we only need to prioritize operations. We have N operations, it is necessary to sort through all ordered arrangements of numbers from the set (0, ..., N). The number of all possible orders of execution will be N! In the worst case, 5! = 120.

You can iterate over the prioritization of operations by enumerating different permutations of numbers in the sequence (0,1,2,3,4). In my program, I implemented some kind of non-obvious algorithm that sequentially swaps the numbers in the sequence. (If I wrote now, most likely I would have realized something more understandable).

Combination check

Now there is just a little left to solve the problem - to make a procedure that, using a set of three codes and an initial number, calculates the result of an expression and, if the result is 100, prints the coded expression. Looking through all the options for a number with N + 1 digits in the worst case implies consideration 2 ^ N ⋅ 4 ^ N ⋅ N! expressions. For six-digit numbers, this equals 3.9 million expressions. The estimate turns out to be too high, since in the expression 4 ^ N ⋅ N! in fact, it will not be N, but the number of zeros in the first partition.

Conclusion

In conclusion, I want to make two comments.

First of all, in my program, standard int operations were first used. At the same time, when solving this problem, people work in the field of rational numbers; therefore, many solutions issued by the program cannot be used in practice. After some time I wrote my small module with rational numbers and screwed it to the task.

Secondly, in my program there is an embryo of the fifth operation - exponentiation. The reasons why this operation is not implemented the following. First, it is necessary to add some limiter for the exponentiation (since the number 2 ^ 2 ^ 2 ^ 2 ^ 2 ^ 2, for example, will no longer fit into the memory). Second, in this case, the calculations go out of the field of rational numbers (for example, 2 ^ (1/2)).

Links

I put the software implementation of the proposed algorithm in C ++ on GitHub .
In addition, those who do not want to bother with the compilation can download executable files for Windows in the same place from the release .