#### Got a credit card? use our Credit Card & Finance Calculators

Thanks to Anonymous,johnhemming,Anonymous,Rhyd6,dredd0, for Donating to support the site

## Subtractions

cinelli
Lemon Slice
Posts: 290
Joined: November 9th, 2016, 11:33 am
Has thanked: 86 times
Been thanked: 51 times

### Subtractions

Choose any four digits (not all the same) such as 3, 6, 2, 8 and rearrange them to form the largest and smallest numbers possible, namely 8632 and 2368. Subtract the smaller number from the larger and repeat the process as the new starting point.

`8632   6642   76412368   2466   1467----   ----   ----6264   4176   6174`

In this example the digits 1, 4, 6, 7 occur at the second stage and no new numbers are generated from then on.
Why do you always get 1, 4, 6, 7? What is the longest chain of subtractions you can find before nothing new occurs?

Cinelli

Gengulphus
Lemon Quarter
Posts: 3130
Joined: November 4th, 2016, 1:17 am
Been thanked: 1686 times

### Re: Subtractions

cinelli wrote:Choose any four digits (not all the same) such as 3, 6, 2, 8 and rearrange them to form the largest and smallest numbers possible, namely 8632 and 2368. Subtract the smaller number from the larger and repeat the process as the new starting point.

`8632   6642   76412368   2466   1467----   ----   ----6264   4176   6174`

In this example the digits 1, 4, 6, 7 occur at the second stage and no new numbers are generated from then on.
Why do you always get 1, 4, 6, 7? What is the longest chain of subtractions you can find before nothing new occurs?

Spoiler...

Suppose the four digits are A, B, C, D in increasing order. Then the smallest and largest numbers resulting from rearranging them is ABCD = 1000*A + 100*B + 10*C + D and DCBA = 1000*D + 100*C + 10*B + A, and the result of the subtraction is 999*D + 90*C - 90*B - 999*A = 999*(D-A) + 90*(C-B). Because A, B, C and D are digits, D-A and C-B must be <= 9, and because of the order of the digits, we must have D-A >= C-B >= 0. Furthermore, D-A cannot be 0, since that and the order of the digits would imply that all four digits are the same.

So the answer after one subtraction will always be one of the following:

If D-A = 1: 0999 or 1089, according to whether C-B is 0 or 1
If D-A = 2: 1998, 2088 or 2178, according to whether C-B is 0, 1 or 2
If D-A = 3: 2997, 3087, 3177 or 3267, according to whether C-B is 0, 1, 2 or 3
If D-A = 4: 3996, 4086, 4176, 4266 or 4356, according to whether C-B is 0, 1, 2, 3 or 4
If D-A = 5: 4995, 5085, 5175, 5265, 5355 or 5445, according to whether C-B is 0, 1, 2, 3, 4 or 5
If D-A = 6: 5994, 6084, 6174, 6264, 6354, 6444 or 6534, according to whether C-B is 0, 1, 2, 3, 4, 5 or 6
If D-A = 7: 6993, 7083, 7173, 7263, 7353, 7443, 7533 or 7623, according to whether C-B is 0, 1, 2, 3, 4, 5, 6 or 7
If D-A = 8: 7992, 8082, 8172, 8262, 8352, 8442, 8532, 8622 or 8712, according to whether C-B is 0, 1, 2, 3, 4, 5, 6, 7 or 8
If D-A = 9: 8991, 9081, 9171, 9261, 9351, 9441, 9531, 9621, 9711 or 9801, according to whether C-B is 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9

Those results from the first subtraction produce just the following thirty combinations of digits (each with the digits in ascending order) going into the second subtraction, which produces the results in brackets according to the above rules:

0,1,8,9 (9621)
0,2,8,8 (8532)
0,3,7,8 (8352)
0,4,6,8 (8172)
0,5,5,8 (7992)
0,9,9,9 (8991)
1,1,7,9 (8532)
1,2,6,9 (8352)
1,2,7,8 (7443)
1,3,5,9 (8172)
1,3,7,7 (6354)
1,4,4,9 (7992)
1,4,6,7 (6174)
1,5,5,7 (5994)
1,8,9,9 (8082)
2,2,6,8 (6354)
2,3,5,8 (6174)
2,3,6,7 (5265)
2,4,4,8 (5994)
2,4,6,6 (4176)
2,5,5,6 (3996)
2,7,9,9 (7173)
3,3,5,7 (4176)
3,4,4,7 (3996)
3,4,5,6 (3087)
3,5,5,5 (1998)
3,6,9,9 (6264)
4,4,4,6 (1998)
4,4,5,5 (1089)
4,5,9,9 (5355)

Those results from the second subtraction produce just the following seventeen combinations of digits (each with the digits in ascending order) going into the third subtraction, which produces the results in brackets according to the above rules:

0,1,8,9 (9621)
0,2,8,8 (8532)
0,3,7,8 (8352)
1,2,6,9 (8352)
1,2,7,8 (7443)
1,3,7,7 (6354)
1,4,6,7 (6174)
1,8,9,9 (8082)
2,3,5,8 (6174)
2,4,6,6 (4176)
2,5,5,6 (3996)
2,7,9,9 (7173)
3,4,4,7 (3996)
3,4,5,6 (3087)
3,5,5,5 (1998)
3,6,9,9 (6264)
4,5,9,9 (5355)

Those results from the third subtraction produce just the following twelve combinations of digits (each with the digits in ascending order) going into the fourth subtraction, which produces the results in brackets according to the above rules:

0,2,8,8 (8532)
0,3,7,8 (8352)
1,2,6,9 (8352)
1,3,7,7 (6354)
1,4,6,7 (6174)
1,8,9,9 (8082)
2,3,5,8 (6174)
2,4,6,6 (4176)
3,4,4,7 (3996)
3,4,5,6 (3087)
3,5,5,5 (1998)
3,6,9,9 (6264)

Those results from the fourth subtraction produce just the following eight combinations of digits (each with the digits in ascending order) going into the fifth subtraction, which produces the results in brackets according to the above rules:

0,2,8,8 (8532)
0,3,7,8 (8352)
1,4,6,7 (6174)
1,8,9,9 (8082)
2,3,5,8 (6174)
2,4,6,6 (4176)
3,4,5,6 (3087)
3,6,9,9 (6264)

Those results from the fifth subtraction produce just the following five combinations of digits (each with the digits in ascending order) going into the sixth subtraction, which produces the results in brackets according to the above rules:

0,2,8,8 (8532)
0,3,7,8 (8352)
1,4,6,7 (6174)
2,3,5,8 (6174)
2,4,6,6 (4176)

Those results from the sixth subtraction produce just the following two combinations of digits (each with the digits in ascending order) going into the seventh subtraction, which produces the results in brackets according to the above rules:

*1,4,6,7 (6174)
*2,3,5,8 (6174)

So the seventh subtraction always produces 6174, and we can then backtrack through the subtractions:

If the sixth subtraction didn't produce the digits 1,4,6,7, it must have produced the digits 2,3,5,8, so the fifth subtraction must have produced the digits 0,2,8,8 or 0,3,7,8, so the fourth subtraction must have produced the digits 1,8,9,9 or 3,4,5,6, so the third subtraction must have produced the digits 1,3,7,7 or 3,5,5,5, so the second subtraction must have produced the digits 2,7,9,9 or 4,5,9,9, so the first subtraction must have produced the digits 0,5,5,8 or 1,5,5,7 or 1,4,4,9 or 2,4,4,8, so the digits going into the first subtraction must have had (D-A,C-B) = (5,1), (5,2), (9,5) or (8,5). That means that the chains of the maximum length 7 are:

`DCBA   8550   9972   7731   6543   8730   8532ABCD   0558   2799   1377   3456   0378   2358----   ----   ----   ----   ----   ----   ----5085   7992   7173   6354   3087   8352   6174for any of DCBA = 5100, 5210, 5320, 5430, 5540,                  6211, 6321, 6431, 6541, 6651,                  7322, 7432, 7542, 7652, 7762,                  8433, 8543, 8653, 8763, 8873,                  9544, 9654, 9764, 9874 or 9984DCBA   7551   9954   5553   9981   8820   8532ABCD   1557   4599   3555   1899   0288   2358----   ----   ----   ----   ----   ----   ----5175   5994   5355   1998   8082   8532   6174for any of DCBA = 5200, 5310, 5420, 5530,                  6311, 6421, 6531, 6641,                  7422, 7532, 7642, 7752,                  8533, 8643, 8753, 8863,                  9644, 9754, 9864 or 9974DCBA   9441   9972   7731   6543   8730   8532ABCD   1449   2799   1377   3456   0378   2358----   ----   ----   ----   ----   ----   ----9441   7992   7173   6354   3087   8352   6174for any of DCBA = 9500, 9610, 9720, 9830 or 9940DCBA   8442   9954   5553   9981   8820   8532ABCD   2448   4599   3555   1899   0288   2358----   ----   ----   ----   ----   ----   ----8442   5994   5355   1998   8082   8532   6174for any of DBCA = 8500, 8610, 8720, 8830,                  9611, 9721, 9831 or 9941`

Gengulphus

UncleEbenezer
Lemon Quarter
Posts: 4631
Joined: November 4th, 2016, 8:17 pm
Has thanked: 538 times
Been thanked: 867 times

### Re: Subtractions

Well, here's a non-cure for insomnia ...
digits 0 <= a <= b <= c <= d <= 9, and d > a.

Subtraction is
1000*d + 100*c + 10*b + a - 1000*a - 100*b - 10*c - d
= 999 * (d-a) + 90 * (c-b)

That looks kind-of like few enough cases to enumerate! We can tabulate cases, with c-b on a vertical axis and d-a horizontal, noting that 9 >= d-a >= c-b >=0 by definition. I'll add a second entry to each number indicating the new values of c-b and d-a: this gives us a state machine which will lead to the answer. Noting that your digits 1,4,6,7 yield c-b=2 and d-a=6, we're looking for everything to converge to state 2/6.

`.       1     2     3     4      5      6     7     8      90      0999  1998  2997  3996   4995   5994  6993  7992   8991       0/9   1/8   2/7   3/6    4/5    4/5   3/6   2/7    1/81      1089  2088  3087  4086   5085   6084  7083  8082   9081       7/8   6/8   4/8   2/8    0/8    2/8   4/8   6/8    7/82            2178  3177  4176   5175   6174  7173  8172   9171             5/7   4/6   2/6    0/6    2/6   4/6   5/7    6/8          3                  3267  4266   5265   6264  7263  8262   9261                   3/5   2/4    0/4    2/4   3/5   4/6    4/84                        4356   5355   6354  7353  8352   9351                         1/3    0/2    1/3   2/4   2/6    2/85                               5445   6444  7443   8442  9441                                1/1    0/2   0/4    0/6   0/86                                      6534  7533   8532  9531                                       1/3   2/4    2/6   2/87                                            7623   8622  9621                                             3/5    4/6   4/88                                                   8712  9711                                                    5/7   6/89                                                         9801                                                          7/8`

Does this converge at 2/6? 2/6 itself does, and states 2/4, 4/8 and 6/8 lead directly there. Iterating backwards and counting states enumerated and length of chain,
2/6 <-- 2/4, 2/6, 4/8, 6/8 (4/0 or 1)
2/4 <-- 3/4, 3/6, 4/7, 6/7 (8/2)
3/6 <-- 0/4, 0/7 (10/3)
0/4 <-- 3/5, 5/7 (12/4)
3/5 <-- 3/3, 3/7, 7/7 (15/5)
5/7 <-- 2/2, 2/8, 8/8 (18/5)
2/8 <-- 1/4, 1/6, 4/9, 6/9 (22/6)
4/8 <-- 1/3, 1/7, 3/9, 7/9 (26/2)
1/3 <-- 4/4, 4/6, 6/6 (29/3)
4/6 <-- 2/3, 2/7, 3/8, 7/8 (33/4)
2/7 <-- 0/3, 0/8 (35/5)
0/8 <-- 1/5, 5/9 (37/6)
7/8 <-- 1/1, 1/9, 9/9 (40/5)
1/1 <-- 5/5 (41/6)
6/8 <-- 1/2, 1/8, 2/9, 8/9 (45/2)
1/8 <-- 0/2, 0/9 (47/3)
0/2 <-- 4/5, 5/6 (49/4)
4/5 <-- 0/5, 0/6 (51/5)
0/6 <-- 2/5, 5/8 (53/6)
0/9 <-- 0/1 (54/4)
So all 54 possible start states do indeed converge on state 2/6 as required. The longest chain is 6, from various start states enumerated.

Gengulphus
Lemon Quarter
Posts: 3130
Joined: November 4th, 2016, 1:17 am
Been thanked: 1686 times

### Re: Subtractions

UncleEbenezer's answer and mine differ, both with regard to the maximum length of a chain of subtractions to get to the digits 1,4,6,7 and to how many starting states produce a maximum-length chain. I've tracked down the reason why, and it's a subtle flaw in UncleEbenezer's solution: it lumps together some sets of digits that require different numbers of subtractions into the same state of its state machine...

Gengulphus

UncleEbenezer
Lemon Quarter
Posts: 4631
Joined: November 4th, 2016, 8:17 pm
Has thanked: 538 times
Been thanked: 867 times

### Re: Subtractions

Gengulphus wrote:UncleEbenezer's answer and mine differ, both with regard to the maximum length of a chain of subtractions to get to the digits 1,4,6,7 and to how many starting states produce a maximum-length chain.

Do they? I haven't read the whole of your post. I note you claim a "chain of length 7", but I don't see one in your post.

If I read you right, you cite 5100 as your first starting number for a chain of length 7. Working through that in my state machine, I get
1/5(6) -> 0/8(5) -> 2/7(4) -> 4/6(3) -> 1/3(2) -> 4/8(1) ->2/6(0)
which looks like six steps.

Aha, got it, your 7 is nodes, my six is steps (actual subtractions).

As for the number of start states, I made no attempt to count them. It wasn't part of the question as I read it!

UncleEbenezer
Lemon Quarter
Posts: 4631
Joined: November 4th, 2016, 8:17 pm
Has thanked: 538 times
Been thanked: 867 times

### Re: Subtractions

There is a simple missing step in my solution. But it turns out, it does matter for the length of chain (which I counted as kind-of an afterthought )

Since my states are equivalence classes of actual sets of numbers, state 2/6 represents not just 1,4,6,7, but also 2,3,5,8 (other would-be candidates can be trivially eliminated by virtue of not being multiples of 9).
Our state machine already verifies that 2,3,5,8 goes to state 2/6, which we can verify instantiates as 1,4,6,7:
8532
-2358
-----
6174

Trying to find Gengulphus' additional step, it seems we do indeed arrive prematurely at node 2/6:

5100 - 0015 = 5085
8550 - 0558 = 7992
9972 - 2799 = 7173
7731 - 1377 = 6354
6543 - 3456 = 3087
8730 - 0378 = 8352
8532 - 2358 = 6174

Ho, hum.

Gengulphus
Lemon Quarter
Posts: 3130
Joined: November 4th, 2016, 1:17 am
Been thanked: 1686 times

### Re: Subtractions

UncleEbenezer wrote:There is a simple missing step in my solution. But it turns out, it does matter for the length of chain (which I counted as kind-of an afterthought )

Since my states are equivalence classes of actual sets of numbers, state 2/6 represents not just 1,4,6,7, but also 2,3,5,8 (other would-be candidates can be trivially eliminated by virtue of not being multiples of 9). ...

Yes - basically the problem was that your 2/5 state really had to be treated as two states, the first of which I might call "End", consisting of only the set of digits 1,4,6,7, and the other of which I might call "Other2/5", consisting of the other 19 sets of digits with c-b = 2, d-a = 5, and only End of those two has chain length 0. The extra subtraction comes for some paths through the state machine because they include an Other2/5 -> End transition that disappears when those two states are inadvertently merged into a single 2/5 state.

Must admit that I too thought at first that the difference between your answer of 6 and mine of 7 was probably a "fencepost problem" (*). It was when I saw that your solution had 9 states at maximum distance and mine had only 4 that I realised it wasn't that simple... Which incidentally is the reason why I mentioned the number of starting states that produce a maximum-length chain - agreed that it wasn't part of the puzzle posed, but it was a fairly simple feature to check about the two solutions, that showed that there was a more fundamental disagreement than an across-the-board off-by-1 counting issue.

(*) In case anyone hasn't come across the term, it refers to the fact that a straight fence of N spans of fencing requires N+1 fenceposts to support it.

Gengulphus

UncleEbenezer
Lemon Quarter
Posts: 4631
Joined: November 4th, 2016, 8:17 pm
Has thanked: 538 times
Been thanked: 867 times

### Re: Subtractions

There's a simple error in my enumeration, where I misclassify the digits 0,1,8,9 - state 7/9 - as 7/8.

The solution happens to work either way (as expected), but this kind of thing is precisely why I generally avoid allowing enumeration (at least beyond the scope of a finger-count) to enter into my solutions on this board!

Anecdote: as a young software engineer back in the 1980s, I made myself very unpopular with the powers-that-be (and determine my career) by pointing out their vulnerability to errors like this, and finding an instance that made a crucial difference. The scenario was software controlling satellite orbits (so a very high potential cost to getting it wrong), and this was about Formal Testing, on a theory that you could mathematically prove your software correct.

I proved that the tests themselves contained errors, and argued that the whole methodology was broken, because it shifted the programmer's focus from getting it right to getting it through the tests. Furthermore, because the tests were more complex than the software tested, there was more scope for errors in them. And there was no process for a junior bod like me to correct an error from something that passed the tests to something that didn't.

cinelli
Lemon Slice
Posts: 290
Joined: November 9th, 2016, 11:33 am
Has thanked: 86 times
Been thanked: 51 times

### Re: Subtractions

Apologies for the lateness of this response. The quality of these answers by Gengulphus and Uncle is superb. And I note the times of these posts: 1:34am and 7:49am. Well done.

Cinelli