Replace and Repeat

[davar55]

Start with four integers A,B,C,D.

Replace them with |A-B|,|B-C|,|C-D|, and |D-A|.

Repeat this replacement step until ...

Show that the result must be four zeros.

[petrw1]

Have I misinterpreted your puzzle????
A B C D
4 98 12 3
-94 86 9 -1
-180 77 10 93
-257 67 -83 273
-324 150 -356 530
-474 506 -886 854
-980 1392 -1740 1328
-2372 3132 -3068 2308

[davar55]

The puzzle didn't mention explicitly
that |X-Y| meant absolute value of X-Y,
i.e. all positive terms after the initial values.

[petrw1]

Doh! I should have known that.

Yes it does work .... seems to be no more than 5 steps.

Mind you the chance of me proving it mathematically is not nearly as easy as me showing it programatically.

[petrw1]

Interestingly it seems to only work for 2^n terms (where n is an integer). i.e. it works for 2 or 4 or 8 terms.

I tried it for 3, 5, 6, 7 and 9 terms. None of these ever became all zero but curiously fairly quickly got to a position where where all terms get to either 0 or one other number, usually but not always 1 ... and in each iteration these two terms appeared in different places but eventually the pattern repeated itself ... sorry for the "less than mathematical" explanation.

[gd_barnes]

Originally Posted by petrw1

Interestingly it seems to only work for 2^n terms (where n is an integer). i.e. it works for 2 or 4 or 8 terms.

I tried it for 3, 5, 6, 7 and 9 terms. None of these ever became all zero but curiously fairly quickly got to a position where where all terms get to either 0 or one other number, usually but not always 1 ... and in each iteration these two terms appeared in different places but eventually the pattern repeated itself ... sorry for the "less than mathematical" explanation.

I agree that the # of terms appears to have to be a power of 2 for it to converge on all zeros. I tried it with 16 terms and it always converged on all zeros also.

Now the question is, what is the max # of iterations that it takes to become all zeros for the various powers of 2 terms?

You mentioned for 4 terms that it always seemed to take <= 5 steps. A quick check showed 3 instances where it took 8 steps and numerous more instances where it took 7 steps! 0,1,5,11; 0,1,5,12; and 1,2,5,10 take 8 steps and 0,1,2,4; 0,1,3,7; 0,1,4,9; 0,1,4,10; 0,1,5,13; and 1,2,4,8 all take 7 steps. It makes me wonder if there really is a maximum # of steps or if it can keep getting bigger and bigger as a,b,c, and d get larger. (I suspect there is a maximum.)

Even the #'s that you originally tried in the problem...4,98,12,3 take 6 steps, i.e.
4,98,12,3
#1 94,86,9,1
#2 8,77,8,93
#3 69,69,85,85
#4 0,16,0,16
#5 16,16,16,16
#6 0,0,0,0

VERY strange but COOL!


Gary

[axn]

Originally Posted by gd_barnes

It makes me wonder if there really is a maximum # of steps or if it can keep getting bigger and bigger as a,b,c, and d get larger. (I suspect there is a maximum.)

No. There is no maximum, you can go as high as you want. For ex, here are sequences from 4 to 20 steps (including the formula I used).

0 0 0 1 => 4    : r1
0 1 2 3 => 5    : r2
0 0 1 3 => 6    : r3
=================
0 1 2 4 => 7    : r4 = r1+r2
0 1 4 9 => 8    : r5 = r2+r3*2
0 2 5 11 => 9   : r6 = r3+r4*2
=================
0 2 6 13 => 10
0 5 14 31 => 11
0 6 17 37 => 12
0 7 20 44 => 13
0 17 48 105 => 14
0 20 57 125 => 15
0 24 68 149 => 16
0 57 162 355 => 17
0 68 193 423 => 18
0 81 230 504 => 19
0 193 548 1201 => 20

See the attached for sequences all the way upto 112 steps

[gd_barnes]

Originally Posted by axn1

No. There is no maximum, you can go as high as you want. For ex, here are sequences from 4 to 20 steps (including the formula I used).

See the attached for sequences all the way upto 112 steps

Excellent! I should have gone with my original thinking that there was no max.

You beat me to the punch. I was going to write a small program this weekend to test all values up to 100, but alas it still wouldn't have shown that there was a max but it would have solidified the conjecture. Testing very high values in 1-2 variables was a lot better approach to demonstrating it.

Thanks for the analogy. It's always amazing how such simple problems can be so complex.


Gary