Still might be a good guess, but neither my searches or Desmostylus’s yielded Fibonaaci rich sequences AFAICT.
Okay, I did more work, and Fibonacci’s will limit themselves after at most 7 steps. I’d encourage anyone (eg, ultrafilter) to check this for mistakes, but:
f(n), f(n+1), f(n+2), f(n+3) [Starting numbers]
f(n-1), f(n), f(n+1), 2f(n+1)
f(n-2), f(n-1), f(n+1), [f(n+1)+f(n)]
f(n-3), f(n), f(n), [f(n) + 2f(n-1)]
2f(n-2), 0, 2f(n-1), [2f(n-2)+2f(n-1)] * [here's a step to check!]
2f(n-2), 2f(n-1), 2f(n-2), 2f(n-1)
2f(n-3), 2f(n-3), 2f(n-3), 2f(n-3)
0, 0, 0, 0
7 steps max
*This is the step I did the most work on:
[f(n) + 2f(n-1)] - f(n-3) =
f(n-1) + f(n-2) + 2f(n-1) - f(n-3) =
f(n-2) + f(n-3) + f(n-2) + 2f(n-1) - f(n-3) =
2f(n-2) + 2f(n-1)
1 55 89 144 243
2 34 55 99 188
3 21 44 89 154
4 23 45 65 133
5 22 20 68 110
6 2 48 42 88
7 46 6 46 86
8 40 40 40 40
9 0 0 0 0
9 is not 7, QED.
Bloody hell. Either I can’t count, or I can’t type into a spreadsheet. Well, I’m a computer programmer, so it’s time to solve this. Actually, I’ll probably do it this evening.
ultrafilter, we’re all at it, 243 is not 233 and certainly isn’t a F-number.
NE Texan you might well be right, I keep getting eights (which correspond to your seven, I include 0,0,0,0)
Needs more work…
I haven’t seen QED in this thread, but I’ll comment on TGU’s numbers. 243 is not in the Fibonacci sequence with 89 and 144; 233 would be next in the sequence.
I got a bunch of eights. Like I said, I’m gonna throw some processor power at this, and see if anything interesting pops up. I’m going to play around with powers of 2 as well.
What might be interesting is to get a set of four numbers whose binary representations have a Hamming distance of exactly one.
I’m too slow on the keyboard, apparently…
I think certain powers of 2 has promise (prime powers? not certain), but I don’t have time to work it out at the moment.
And yes, your 8 rows of numbers would correspond to my 7 steps (see my example - I have 8 rows). I really should have written 8 - it would be 8 squares drawn as the OP suggested. My bad.
Speaking of Fibonnaci numbers and such sequences- I’m sure you’ve noticed that the solutions that Desmostylus provided form their own sequence- each solution reduces to the previous one, once you discard any remainders.
e.g. Desmostylus’ solution for 23 squares:
1 275 779 1706
the square inside this would be
274 504 927 1705
which reduces to (is the same as)
1 231 654 1432
which is Desmostylus’ solution given for 22 squares.
Hmm… Im trying a slightly different tack and trying to work it out backwards.
“aahala’s conjecture”
All solutions will be proceeded by a=c, b=d after n squares. If a does not equal b, then there will be two more squares. If a=b, then just one more square.
Now just solve for n.
Aahala, your conjecture is valid, of course.
Working backwards from the final 0, 0, 0, 0 square, the previous square must be of the form x, x, x, x. The previous square must be of the form y, z, y, z where abs(y-z) = x.
I note, in passing, the tendency, particularly in long series of squares, to encounter a square of the form n, 0, n, 0 where n is a power of 2. Significant?
An observation which may or may not be of interest.
If you take away the “absolute value” part of the OP’s rule, and simply take the differences of the corners in a fixed direction, allowing them to become negative, it still converges. I found that mildly surprising at first, but thought that variant might be more analytically tractable. Running through the values of the corners at each step, expressed as coefficients involving the original numbers, it actually is guaranteed to converge at 65 steps:
Step 0: (1,0,0,0)(0,1,0,0)(0,0,1,0)(0,0,0,1)
Step 1: (1,-1,0,0)(0,1,-1,0)(0,0,1,-1)(-1,0,0,1)
Step 2: (1,-2,1,0)(0,1,-2,1)(1,0,1,-2)(-2,1,0,1)
Step 3: (1,-3,3,-1)(-1,1,-3,3)(3,-1,1,-3)(-3,3,-1,1)
Step 4: (2,-4,6,-4)(-4,2,-4,6)(6,-4,2,-4)(-4,6,-4,2)
Step 5: (6,-6,10,-10)(-10,6,-6,10)(10,-10,6,-6)(-6,10,-10,6)
Step 6: (16,-12,16,-20)(-20,16,-12,16)(16,-20,16,-12)(-12,16,-20,16)
Step 7: (36,-28,28,-36)(-36,36,-28,28)(28,-36,36,-28)(-28,28,-36,36)
Step 8: (72,-64,56,-64)(-64,72,-64,56)(56,-64,72,-64)(-64,56,-64,72)
Step 9: (136,-136,120,-120)(-120,136,-136,120)(120,-120,136,-136)(-136,120,-120,136)
Step 10: (256,-272,256,-240)(-240,256,-272,256)(256,-240,256,-272)(-272,256,-240,256)
…
Step 64: (-2147483648,0,-2147483648,0)(0,-2147483648,0,-2147483648)(-2147483648,0,-2147483648,0)(0,-2147483648,0,-2147483648)
Step 65: (-2147483648,-2147483648,-2147483648,-2147483648)(-2147483648,-2147483648,-2147483648,-2147483648)(-2147483648,-2147483648,-2147483648,-2147483648)(-2147483648,-2147483648,-2147483648,-2147483648)
Step 66: (0,0,0,0)(0,0,0,0)(0,0,0,0)(0,0,0,0)
Step 67: (0,0,0,0)(0,0,0,0)(0,0,0,0)(0,0,0,0)
Step 68: (0,0,0,0)(0,0,0,0)(0,0,0,0)(0,0,0,0)
Throwing the “absolute value” bit in means that some of those tuples along the way will be reversed in sign based on the relative values of the original corners. You could break each of those steps into branching subcases with different sets of the corners being reversed, and I’ll bet all possible cases would terminate. I REALLY don’t want to try to go down that route at the moment, and I’m sure there’s a more elegant way of approaching it.
My apologies for inducing a horizontal scroll. If a mod wants to fix that, I would suggest changing some of the larger tuples to look like:
Step 64: (…)
(…)
(…)
(…)
Ah. Which implies that you can construct the sequence from the inside out, as it were. Note that your reduction from (274 504 927 1705) to (1 231 654 1432) involves subtracting 273. And 1432 - 654 - 231 - 1 = 546 = 2*273. So, starting from (1 231 654 1432), I can construct (1 275 779 1706) by:
- Calculating 1432 - 654 - 231 - 1 = 546 = 2*273
- Adding 273 to this set to get square 2 of the higher sequence (274 504 927 1705)
- Recognizing the pattern, I know that the first digit of the higher sequence is 1.
- The second is 1 + 274 = 275.
- The third is 1 + 1705 = 1706
- And the last = 275 + 504 = 1706 - 927 = 779.
- Final sequence is (1 275 779 1706)
Does this work on the next step? 1706 - 779 - 275 - 1 = 651. Hm. Apparently not. But the next step, 4064 - 1855 - 654 - 1 = 777*2 appears to work. (1 654 1855 4164) + 777 = (778 1431 2632 4841) -> (1 779 2210 4842) by procedure above. OK, what gives?
Oh HELL, forget what I said. I was overflowing the integer value, of course - that final value made me suspicious. It doesn’t appear that the “non absolute value” version converges in general, which at least makes more sense.
Get coffee before posting.
Another way of putting this is that the square must be of the form (y, x+y, y, x+y). I want to point out another possibility: The square of the form (y, x+y, 2x+y, x+y), whose next step is also (x, x, x, x). I believe that if you work the math out backwards, at each stage you get two choices like this - but some of them start to overlap.
Towards the reducing that hammos1 and zut are doing:
if you have a set of numbers (a, b, c, d), it will converge exactly the same way as (ax, bx, cx, dx). The extra factor (x) in each one stays in there all the way until zero is reached. Also, it will converge exactly the same way as (a+x, b+x, c+x, d+x). The extra number (x) disappears after the first iteration. Any set of numbers that you can transform into each other with those 2 operations (plus rotation of the group, or reflection), will take the same number of steps to converge.
But I’m not quite sure if that conclusion is of any use.
Bingo! Good observation, NE Texan. I propose the following procedure for working backwards from the set (a, b, c, d):
- Calculate d-c-b-a.
- If d-c-b-a is odd, then double the original set; i.e, replace (a, b, c, d) with (2a, 2d, 2c, 2d) and go back to step 1.
- If d-c-b-a is even, then divide it by 2 and call (d-c-b-a)/2 = X.
- Construct the set (a+X, b+X, c+X, d+X) as the second square of the larger series.
- The first square of the larger series is then (1, 1+a+X, b+1+a+2X, 1+d+X)
Which takes care of my confusion above. To get from (1, 275, 779, 1706) to (1, 654, 1855, 4064): Double (1, 275, 779, 1706) to (2, 550, 1558, 3412); calculate (3412-1558-550-2)/2 = 651; add to series (653, 1201, 2209, 4063), and finally construct (1, 654, 1855, 4064). So you can use the same procedure ad ifinitum to construct larger and larger squares.
Which is easily coded into Excel, I might add. Starting with the #23 seed (1, 275, 779, 1706), I get the following:
23 1 275 779 1706
24 1 654 1855 4064
25 1 779 2210 4842
26 1 928 2633 5769
27 1 2210 6273 13746
28 1 2633 7474 16378
29 1 3137 8905 19514
30 1 7474 21219 46500
31 1 8905 25282 55404
32 1 10610 30123 66013
33 1 25282 71781 157306
34 1 30123 85526 187428
35 1 35891 101903 223318
36 1 85526 242831 532160
37 1 101903 289330 634062
38 1 121416 344733 755477
39 1 289330 821489 1800282
40 1 344733 978794 2145014
41 1 410745 1166221 2555758
42 1 978794 2779075 6090308
43 1 1166221 3311234 7256528
44 1 1389538 3945295 8646065
45 1 3311234 9401541 20603362
46 1 3945295 11201822 24548656
47 1 4700771 13346835 29249426
48 1 11201822 31805183 69700672
49 1 13346835 37895490 83047506
50 1 15902592 45152017 98950097
51 1 37895490 107596161 235795682
52 1 45152017 128199522 280947698
53 1 53798081 152748177 334745778
54 1 128199522 363995203 797691076
55 1 152748177 433695874 950439252
56 1 181997602 516743379 1132436853
57 1 433695874 1231386949 2698569578
58 1 516743379 1467182630 3215312956
59 1 615693475 1748130327 3831006430
60 1 1467182630 4165752207 9129195488
Voila! Note I’m matching The Great Unwashed’s numbers for 24, 25, and 26.
If I drop the restriction to using integers, I can get a steady-state (well, exponentially decreasing) analytic solution that explains features of Desmostylus’s list (and the longer lists, also). It’s easiest to first restrict the largest and smalles numbers to be 1 and 0.
Then, there are three possible cases to look at:
(0, X, Y, 1), (0, X, 1, Y), and (0, Y, X, 1) where I’ll always use Y > X.
For the case (0, Y, X, 1), this becomes all zeros in four steps. For the case (0, X, 1, Y), this becomes all zeros in six steps.
The interesting case is (0, X, Y, 1), because this case can give a steady state solution.
(0, X, Y, 1) --> (X, Y-X, 1-Y, 1)
–> (0, Y-2X, 1-Y-X, 1-X) (by subtracting off X (*))
–> (0, (Y-2X)/(1-X), (1-Y-X)/(1-X), 1) (by scaling to make largest number 1)
Now solve the two equations
(Y-2X)/(1-X) = X
(1-Y-X)/(1-X) = Y
to get
Y = 3X-X^2
X^3 - 5X^2 + 7X - 1 = 0
I get (approximately) X = 0.16071, Y = 0.45631. So cases with integers which are close to multiples of (0, 0.16071, 0.45631, 1) should work well.
This agrees with Desmostylus’s list, after subtracting 1 from each number. The cases shown are good approximations of the analytic X and Y I obtained. For example, the last row gives X = 274/1705 = 0.160704, and Y = 778/1705 = 0.45630
Also, my solutions decrease in amplitude by 1-X = 0.83929 each step. This also agrees with Desmostylus’s list. For the last two rows, for example, the relative amplitudes decrease by 1431/1705 = 0.838804. This works for rows 58 versus 59 of zut’s longer list, but fails for rows 59 versus 60. The difference is almost exactly a factor of two, so I suspect there’s a solution for 60 with smaller numbers. Actually, there are several such “extra large” jumps, the first between 23 and 24. Are these lists minimal solutions?
(*)This step assumes X is smaller than 1-Y, which it is in the final result. There may be a second solution where 1-Y is smaller than X, but I haven’t looked for it.