[Math] Reverse a mathematics calculation

elementary-number-theory

I have a formula to do the calculation from 7 set of numbers to 4 digits, for example:

04, 05, 19, 21, 22, 31, 13 ====> 4382

These 7 sets of numbers are ranging from 01 to 45, each set will only exists once.

Calculation are as follow:

  1. Sum up 1st to 6th number, and times with 2

    (4 + 5 + 19 + 21 + 22 + 31) * 2 = 204

  2. Take the result of step 1, minus 1st number and 6th number

    204 – 4 – 31 = 169

  3. Take the result of step 2, plus with the 7th number

    169 + 13 = 182

    • From here, take the last 2 digits of the result from step 3

      82

  4. Sum up the 4th and 5th number

    21 + 22 = 43

    • From here, take the last digit of the result from step 4

      3

  5. Sum up the 2nd and 3rd number

    5 + 19 =24

    • From here, take the last digit of the result from step 5

      4

There you get the final result of 4382

If any result from any step above contains 0 (zero), take that as a value in one of the digit into the final result.

So anyone has any idea if I have "4382" with me, can you get back the 7 sets of numbers?
Not necessary must be exactly the same as I've written on top, as long as the 7 sets of numbers can produce the final result into "4382".

Really need a master to gimme some clues. Thanks.

1st to 6th number must be in a sequence from smallest to largest number in the range of 01 to 45. It's a game that comes out with this calculation, and I need to find out the way to reverse it.

Best Answer

Your problem sets out to solve the following system of modular equations:

x1 + 2*x2 + 2*x3 + 2*x4 + 2*x5 + x6 + x7 = A (mod 100)

x4 + x5 = B (mod 10)

x2 + x3 = C (mod 10)

The first equivalence comes from steps 1-3 above, the second from step 4 and the third from step 5. The basic math that you need to solve a system of equivalences is the Chinese Remainder Theorem.

This system will not have a unique solution. To see how redundant it is, count the possibilities for the sequence (x1,x2,x3,x4,x5,x6,x7) and (C,B,A) separately. For the former, x1,x6,x7 are interchangeable as are x4,x5 and x2,x3, so we count them separately. There are (45+3-1 choose 3) ways to choose x1,x6,x7 each between 01 and 45 (remember to choose with repetition), and (45+2-1 choose 2) ways to choose each of the other pairs. This gives a total of

(47 choose 3)*(46 choose 2)^2 = 16 782 525

ways of choosing the xs. For the 4-digit sequence, there are 10 000 possibilities. The number above is far larger, so certainly there is a lot of repetition.

If you want to pin down just one x sequence that yields a given CBA sequence, then you can simplify the problem by choosing arbitrary values for x6,x7,x5,x3 and then using the CRT to solve for x1,x4,x2 (which may or may not exist).

For example, suppose you take 

x3 = 19, x5 = 22, x6 = 31, x7 = 13

Then you solve for the remaining xs by solving this system

x4 + 22 = 3 (mod 10)

x2 + 19 = 4 (mod 10)

x1 + 2*x2 + 38 + 2*x4 + 44 + 31 + 13 = 82 (mod 100)

The first two equations are easy, though the solutions are not unique

x4 = 1 (mod 10) => x4 = 1, 11, 21, 31, or 41

x2 = 5 (mod 10) => x2 = 5, 15, 25, 35, or 45

Adding in the final equation to solve for x1 and pin down x2,x4 gives

x1 + 2*(x2 + x4) = 56 (mod 100)

which has many solutions, among them x1 = 4, x2 = 5, x4 = 21, but also x1 = 44, x2 = 5, x4 = 1 as well as many others.

Related Question