Originally posted by mtthwI came up with a couple tricks to narrow the search, but I ultimately had to use brute force as well.
I spent some time trying to come up with a pattern that worked. No luck so far.
So went for the brute force approach 🙂. Best so far is [4910, 4163, 2789, 262], which gives the 20 iterations you wanted.
I'm sure there's a better way.
My best solution is [077822094841] with 23 iterations.
Originally posted by FabianFnasThree zeroes and then any non-zero number gives a row of 4 zeroes very quickly (even for a googolplex).
What a bout 0, 0, 0, gogolplex ?
(A gogol is 10^100, a gogolplex is 10^gogol)
0, 0, 0, x [where x>0]
0, 0, x, x
0, x, 0, x
x, x, x, x
0, 0, 0, 0
I like the fact that the version with pi, e and surds in it still reverts to a row of zeroes very quickly!
Nice problem - thanks for raising it.
Originally posted by DiapasonOkay, suppose we skip the whole number principle and use whatever number system.
Three zeroes and then any non-zero number gives a row of 4 zeroes very quickly (even for a googolplex).
0, 0, 0, x [where x>0]
0, 0, x, x
0, x, 0, x
x, x, x, x
0, 0, 0, 0
I like the fact that the version with pi, e and surds in it still reverts to a row of zeroes very quickly!
Nice problem - thanks for raising it.
You show easily and nicely that any 0,0,0,x reverts to 0,0,0,0 in 4 iteration. Even where x is very high or real or whatever.
What about 0,0,0,i? (where i = sqrt(-1)
Originally posted by FabianFnasYou'd have to redefine the problem somehow to make it any different. As it stands, since you take the modulus every time then you lose any complex numbers after one iteration.
Okay, suppose we skip the whole number principle and use whatever number system.
You show easily and nicely that any 0,0,0,x reverts to 0,0,0,0 in 4 iteration. Even where x is very high or real or whatever.
What about 0,0,0,i? (where i = sqrt(-1)
I cracked this problem by building from the ground up.
Let's say a row of numbers is
a b c d
and the row above it is
a' b' c' d'
and we always list the numbers in order of smallest (a) to largest (d), for convenience.
Now the 'above' row can be expressed:
b' = a + a'
c' = a' + a + b
d' = a' + a + b + c
substitute the last equation into the 'wrap around' equation:
a' - d' = d
a' - (a' + a + b + c) = d
a + b + c = d
In other words, once we get a row in which a, b, and c do NOT sum to d, that is the last valid row, and we can't build any more above it [this is also true if any non-whole numbers occur on the row]. This leads to:
d' = a' + b' + c'
d' = a' + (a' + a) + (a' + a + b) substituted b' and c'
d' = 3a' + 2a + b
substitute d':
(a' + a + b + c) = 3a' + 2a + b
-a + c = 2a'
(-a + c)/2 = a'
We now have enough equations to start with any a b c d and fill in the above rows 'automatically'.
For some reason, 0, 0, 2^x, 2^x works really well as the starting a, b, c and d. In fact, the higher x used, the more valid iterations produced. Example:
0, 0, 1024, 1024 [1024 = 2^10] leads to 42762, 78652, 144664, 266079 as the highest valid row. When plugged into the original problem, this yields 33 iterations before all-0.
Can any of you math wizards tell me why this pattern [0, 0, 2^x, 2^x] works so well in this problem?
This post is in response to the post above. If this post is not clear, chances are that you didn't read/understand the post above. Otherwise, I may have not made myself clear. Please tell me if it is the latter.
Well, [0,0,n^x,n^x], where n and x are natural numbers, would fail to "rise" (and only have 3 iterations) if the prime factorization n^x has no factor of 2 in it.
Proof: Due to the fact that in the set [0,0,n^x,n^x], a = 0. a' is calculated by (c-a) / 2. Since, a = 0, c must be even. Therefore, if c is even, c must have a factor of 2.
Also, I found that, building up from [0,0,2,2] leads to [1,1,2,4]. Then:
[1,1,2,4]
[0,1,2,3]
[1,1,1,3]
[0,0,2,2]
[0,2,0,2]
[2,2,2,2]
[0,0,0,0]
6 iterations.
Building up from [0,0,4,4] (since 2^2=4) leads to [2,4,7,13]. Then:
[2,4,7,13]
[2,3,6,11]
[1,3,5,9]
[2,2,4,8]
[0,2,4,6]
[2,2,2,6]
[0,0,4,4]
[0,4,0,4]
[4,4,4,4]
[0,0,0,0]
9 iterations.
It seems that the formula for iterations is 3x+3, where x is defined as in the set [0,0,n^x,n^x], were n is any number with only one factor of 2 in its prime factorization (meaning it's divisble by 2 but not 4).
And now, I try to use x.
[5(2^(x-3)), 9(2^(x-3)), 17(2^(x-3)), 31(2^(x-3))] *
[2^(x-1), 2^x, 7(2^(x-2)), 13(2^(x-2))]
[2^(x-1), 3(2^(x-2)), 3(2^(x-1)), 11(2^(x-2))]
[2^(x-2), 3(2^(x-2)), 5(2^(x-2)), 9(2^(x-2))] *
[2^(x-1), 2^(x-1), 2^x, 2^(x+1)]
[0, 2^(x-1), 2^x, 3(2^(x-1))]
[2^(x-1), 2^(x-1), 2^(x-1), 3(2^(x-1))] *
[0, 0, 2^x, 2^x]
[0, 2^x, 0, 2^x]
[2^x, 2^x, 2^x, 2^x]
Notice that the sets with asterisks at the end signify when the power is first reduced. The 4th lowest set has a = 2^(x-1). The 7th lowest has a = 2^(x-2). The 10th lowest has a = 2^(x-3). If a isn't a natural number, then it's an invalid set and the highest valid row is reached. For example, if x=2, then a = 2^(x-3) is invalid. Therefore, if x=2, there are 9 sets, and therefore 9 iterations. Somehow, every 3 iterations, a greater power of 2 is needed. Therefore, we only need to start at [0,0,64,64]. Thus:
1. [301,634,1130,2065]
2. [333,496,935,1764]
3. [163,439,829,1431]
4. [276,390,602,992]
5. [114,212,390,716]
6. [98,178,326,602]
7. [80,148,276,504]
8. [68,124,228,420]
9. [56,104,192,352]
10. [48,88,160,296]
11. [40,72,236,248]
12. [32,64,112,208]
13. [32,48,96,176]
14. [16,48,80,144]
15. [32,32,64,128]
16. [0,32,64,96]
17. [32,32,32,96]
18. [0,0,64,64]
19. [0,64,0,64]
20. [64,64,64,64]
21. [0,0,0,0]
Feel free to correct my errors. Also, if I got the definition of iterations wrong, tell me as well.
Originally posted by SwissGambitFinally, I have figured this thing out.
I cracked this problem by building from the ground up.
Let's say a row of numbers is
a b c d
and the row [b]above it is
a' b' c' d'
and we always list the numbers in order of smallest (a) to largest (d), for convenience.
Now the 'above' row can be expressed:
b' = a + a'
c' = a' + a + b
d' = a' + a + b + c
substitute the last equ s pattern [0, 0, 2^x, 2^x] works so well in this problem?[/b]
The last equation from my previous post is the key to the problem.
(-a + c)/2 = a'
If we start with a, b, and c on the bottom row, and express everything on the rows above in terms of the original a, b and c, we find that the denominator increases by a power of 2 each iteration. [Even if it cancels out with coefficient terms, it's still a power of two.] b', c' and d' are all based on the value of a', so this holds for all terms.
By setting a and b to 0, and selecting a large power-of-two for c, we get many rows where c is larger than the denominator, and cancels it out, leaving some power-of-two still in the numerator. This gets rid of any odd numbers remaining in the coefficient of c.
Once c is no longer larger than the denominator, we soon end up with odd coefficient divided by power-of-two, which results in a fraction and signals the last valid, or "top", row.