Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Nov 17 '11 at 11:44

This question came from our site for professional and enthusiast programmers.

2  
Do you mind sharing the origin of this problem? It's very ill-posed, so I'm curious as to how it arose. –  PengOne Nov 17 '11 at 5:05

2 Answers 2

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.

share|improve this answer

The easiest way to find a solution to this would be to reverse your operations. However, this is actually not possible with the given algorithm. Take, for example your last step, " take the last digit of the result of the sum of the 2nd and 3rd number". since there are multiple possible combinations of numbers that will give you this result, the step is irreversible.

If your last digit is 4 as in your example, the 2nd and 3rd number could be any of the following:

21 + 23 = 44, 23 + 21 = 24, 32 + 02 = 34, 02 + 32 = 34, etc.

What do you need this for? Hopefully not some sort of home-baked encryption/security mechanism :)

share|improve this answer
    
@PengOne Not sure how this has anything to do with the Chinese Remainder Theorem, but even it is does, the question was how to get back to the 7 number sequence from the 4 digit number, which your answer does not mention. –  tjscience Nov 17 '11 at 5:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.