Author |
Topic: Doomed to be zeros (Read 2712 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: Doomed to be zeros
« Reply #25 on: Oct 19th, 2006, 8:50am » |
 Quote  Modify
|
Well, either of our iterations can give an example of arbitrary length. So there's not much sport in finding the longest example anymore
It'd be interesting to find one that takes longer than 2*log2(max) iteration steps (or prove there can't be)
[edit]Well, there's 7,3,1,0 which takes 7. But it'd be interesting if there was one with significantly higher numbers that also did it.[/edit]
|
| « Last Edit: Oct 19th, 2006, 9:32am by towr » |
 IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Doomed to be zeros
« Reply #26 on: Oct 19th, 2006, 9:31am » |
Quote Modify
|
Using a slight variation of Miles method which eliminates the guessing of x, I'm now generating a sequence which agrees 100% with what we seem to believe are the iteration leaders:
Start with a(2) = 0, b(2) = 1, c(2) = 0, d(2) = 1
Let (these are each 2*Miles step)
x(n+1) = c(n) - a(n),
y(n+1) = c(n) + a(n),
z(n+1) = c(n) + a(n) + 2b(n).
Now let
a(n+1) = x(n+1) / GCD(x(n+1), y(n+1), z(n+1)),
b(n+1) = y(n+1) / GCD(x(n+1), y(n+1), z(n+1)),
c(n+1) = z(n+1) / GCD(x(n+1), y(n+1), z(n+1)),
d(n+1) = a(n+1) + b(n+1) + c(n+1).
To find the leader for n iterations, let
i = d(n) - a(n),
j = c(n) - a(n),
k = b(n) - a(n),
and the leader is the quadruple { i / GCD(i,j,k), j / GCD(i,j,k), k / GCD(i,j,k), 0 }.
[edit]Note: you don't actually need the division by GCD in the recursion step -- it just helps keep the size of the numbers more managable. (You do need it in the "display" step, though.)[/edit]
--SMQ
P.S. 1000:
60,696,463,696,609,488,453,842,426,467,743,141,965,388,286,002,754,450,3 13,498,917,885,666,598,812,677,859,684,420,272,762,958,046,261,769,691,5 38,031,294,152,105,506,080,714,260,233,698,765,249,966,960,314,804,089,6 75,880,977,143,341
27,696,463,275,499,420,171,180,388,442,148,913,766,156,570,687,620,576,2 98,166,409,382,052,837,819,779,628,653,408,223,124,883,799,089,754,494,2 13,792,905,121,064,655,972,387,329,367,582,054,702,475,125,382,649,583,4 88,142,363,249,356
9,754,725,627,707,982,980,048,757,310,730,013,633,685,663,558,605,153,06 0,576,741,037,321,883,961,640,694,881,916,948,937,656,591,940,050,430,20 9,083,885,768,258,022,734,270,937,179,112,852,735,911,298,241,488,703,19 2,907,047,112,824
0
|
| « Last Edit: Oct 19th, 2006, 10:13am by SMQ » |
IP Logged |
--SMQ
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #27 on: Oct 19th, 2006, 9:38am » |
Quote Modify
|
What a shame. I'm away from a PC for the next week, so won't be able to see how this develops. Maybe I'll work it all out myself on paper, or maybe not. And maybe you'll have all moved on by then...
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Doomed to be zeros
« Reply #28 on: Oct 19th, 2006, 11:34am » |
Quote Modify
|
While you were hunting for long sequences I still owe you the proof that N=2^n has always got a finite number of steps (although by now we all take it granted).
So:
Step 1: I have proved that in finite numbers any N gets down to a set that consist only of 0-s and one other number (A).
Step 2. For the sake of simplicity I use 0 and 1 only, although A can be any number.
Step 3. In any iteration a number is the parity of the two neighbours in the previous step (00 - 0, 01 -1, 10 -1, 11 - 0). It is actually the same as the parity of the total of the two neighbours.
Step 4. I want to check how any number of the original sequence contributes to the next and all following sequences.
Let's take the sequence: xxxxAxxxxx where x is undifined. If A is 0, in all following totals its contribution is still 0, i.e. it does not change the parity of any numbers in the future sequences. If A is 1, then its contribution (mod 2) to the following sequences is as follows:
Seq 0: xxxxxxxxxx1xxxxxxxx
Seq 1: xxxxxxxxx11xxxxxxxx
Seq 2: xxxxxxxx101xxxxxxxx
Seq 3: xxxxxxx1111xxxxxxxx
Seq 4: xxxxxx10001xxxxxxxx
Seq 5: xxxxx110011xxxxxxxx
Seq 6: xxxx1010101xxxxxxxx
Seq 7: xxx11111111xxxxxxxx
It can be seen that in steps 2^k -1 a sequence of 2^k pieces of 1s are generated. If the total ring is 2^k long then in the next step we get all 0s as a contribution. With other words if N=2^k then regardless the starting situation of 0-s and 1-s in step N we get all 0-s.
I.e. together with the earlier partial results we can say that it gets down to all 0-s if and only if N=2^k.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Doomed to be zeros
« Reply #29 on: Oct 19th, 2006, 12:21pm » |
Quote Modify
|
And once you've remove any contribution mod 2, you can as it were divide the whole tupple by two and repeat (to remove the next bit's contribution)
So a general upper bound of log2(max)*2k ?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Doomed to be zeros
« Reply #30 on: Oct 19th, 2006, 4:24pm » |
Quote Modify
|
If a=( 5 - cbrt(19 - 3*sqrt(33)) - cbrt(19 + 3*sqrt(33)) )/3 = 0.160713...
and b=( 4 - cbrt(17 - 3*sqrt(33)) - cbrt(17 + 3*sqrt(33)) )/3 = 0.456311...
(cbrt(x)= cube root of x)
Choose four numbers of the form 0, a*N, b*N, N (all rounded to nearest integer), and you should be able to increase the number of steps as much as you want if N is large enough. To maximize number of steps N should be chosen so that a*N and b*N are both close to integers. This approach works because after each step and subtracting the lowest value as towr suggests to zero out the first number, the numbers remain in approximately the same ratio. If the starting values weren't rounded to integers the same ratio would be maintained, while the values decrease at each step.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Doomed to be zeros
« Reply #31 on: Oct 19th, 2006, 11:31pm » |
Quote Modify
|
Yes, Towr.
My understanding is also that since in every N (where N=2^k) steps you can divide the model by 2, the theoretical maximum is N*log(2)A, where A is the largest number in the initial set.
This is fully in line with my original estimate for N=4.
I am also thinking on the impact of the fact that in N steps the largest number surely disappears (eaten up by the small numbers). Unfortunately a new number of A-1 might appear, so it is not true, that in N steps the largest number would be max the original second largest. (It would be nice, giving another limit of A*N.)
So it gives something like N*upperround(log2(A-N)), although not sure in it. It is also not a significant reduction, even if true.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Doomed to be zeros
« Reply #33 on: Oct 22nd, 2006, 1:26am » |
Quote Modify
|
on Oct 21st, 2006, 2:44pm, Aryabhatta wrote:
Wow! I completely forgot that I once contributed to this problem... Where have you been before, Aryabhatta?
So, after refreshing my memory, here's an easy way to construct a sequence with length a multiple of 3:
0, T2k+1 - T2k, T2k+2 - T2k, T2k+3 - T2k has length 3(k+1),
where Tk is the k-th Tribonacci number. Indeed, the quadruple (T2k, T2k+1, T2k+2, T2k+3) after 3k moves becomes (2kT0, 2kT1, 2kT2, 2kT3) = (0, 0, 2k, 2k), and it takes another 3 moves to get to all zeros.
The above solution coincides with SMQ's table for entries that are multiples of 3.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Doomed to be zeros
« Reply #34 on: Oct 23rd, 2006, 10:44am » |
Quote Modify
|
on Oct 22nd, 2006, 1:26am, Barukh wrote:
Wow! I completely forgot that I once contributed to this problem... Where have you been before, Aryabhatta?
|
|
I have been pretty busy with work lately... Thanks for asking
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Doomed to be zeros
« Reply #35 on: Oct 23rd, 2006, 10:54am » |
Quote Modify
|
Welcome back Aryabhatta... another name to cross off!! 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Doomed to be zeros
« Reply #36 on: Oct 23rd, 2006, 12:38pm » |
Quote Modify
|
on Oct 23rd, 2006, 10:54am, Sameer wrote:| Welcome back Aryabhatta... |
|
Thanks
|
|
IP Logged |
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #37 on: Nov 2nd, 2006, 7:14am » |
Quote Modify
|
on Oct 19th, 2006, 8:25am, Miles wrote:| Yes, I'm too practical to be a really good mathematician. While others want to prove existence and bounds (which I find interesting), I'm more curious to actually generate an example (preferably longer than anyone else's!) |
|
I guess my inner mathematician wouldn’t stay quiet after all, as this has been niggling away at me since I last posted. I’ve only thought about the 4-tuple case. I’ve proved that given that the largest number in the 4-tuple is N, an upper bound for the number of steps to zero is 4*log(N)+4, where (here’s the twist)
I’m taking logarithms to base 3 [log(x) should be taken as log3(x) in all that follows].
Empirically, I’ve crunched through lots of cases, and it looks like the actual number of steps can’t be more than 3*log(N) + 4. (I even speculate whether it is e*log(N) + 4).
I could say more about my proof if I get the time. What I’ll say is that a maximal 4-tuple (ie one that takes the maximum possible steps to reach zero) takes the form
(N,0,k*N,(k+j)*N), where j,k are positive with k+j <= 1.
The really interesting region in the space of (j,k) values is where j >= k and 1-2k-j >=0, and I assume these apply...
After one step, the quadruple becomes
(N, N*k, N*j, N*(1-k-j))
which can be translated to
(N*(1-k), 0, N*(j-k), N*(1-2k-j)) [the conditions above ensure all of these are non-negative].
which can be expressed as
(N’, 0, k’ * N’, (k’ + j’) * N’) where N’ = N * (1-k), k’ = (j-k) / (1-k), [a little algebra...] j’ = (1-k-2j)/(1-k), ie after one step, the new quadruple is of the same form.
Dropping the requirement for the elements to be integers, the first question is what is the fixed point, ie for what value of (j,k) does the rule map (j,k) to itself, ie solve
k = (j – k) / (1-k)
j = (1 – k – 2j) / (1-k)
As a pointer, the solution is around (0.30, 0.16) but I’ve an exact solution in terms of radicals.
The closer your starting point to this fixed point, the more steps it takes to get to zero. All of SMQ’s solutions are of this nature.
Anyone like to try calculating the fixed point?
|
|
IP Logged |
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #38 on: Nov 2nd, 2006, 7:23am » |
Quote Modify
|
Recapping, start with the quadruple
(N, 0, k * N, (j+k) * N), with 0 <= j,k; k <= j; 1-2k-j >= 0.
After 4 steps, it can be shown that either the quadruple will reach zero in at most 4 more steps or the maximum number in the quadruple is 2*N/3. We already know that after 4 steps, all the elements are even, so the quadruple can be halved and the maximum reduces to N/3. So every 4 steps, the maximum element reduces to a third or less. This implies that the maximum number of steps to zero is of the form 4*log(N) + c, taking logs to base 3. Experimenting with small cases shows that c=4 covers it.
If the initial quadruple is not of the type defined above, then it can be shown that it cannot beat 2*N/3 in 4 steps (or if it does, it then falls to zero in at most another 4 steps).
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Doomed to be zeros
« Reply #39 on: Nov 2nd, 2006, 9:08am » |
Quote Modify
|
on Nov 2nd, 2006, 7:23am, Miles wrote:Recapping, start with the quadruple
(N, 0, k * N, (j+k) * N), with 0 <= j,k; k <= j; 1-2k-j >= 0. |
|
Taking N=1431, k = 0.16, j = 0.30 (as indicated in your previous post), I get the quadraple (1431, 0, 228, 658), which collapses after 12 steps, whereas your formula predicts at least 25.
Compare this to (0, 230, 653,1431), with 21 steps.
|
|
IP Logged |
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #40 on: Nov 2nd, 2006, 3:12pm » |
Quote Modify
|
on Nov 2nd, 2006, 9:08am, Barukh wrote:
... whereas your formula predicts at least 25.
|
|
No, my formula predicts at most 30.
Sorry, I think you’ve got things back to front. I’m stating the upper bound, which for your case would be 4*log(1431)+4 = 30, so I would expect the best choice to take 20-odd steps.
on Nov 2nd, 2006, 9:08am, Barukh wrote:
Compare this to (0, 230, 653,1431), with 21 steps.
|
|
More precise values for the fixed point would be j = 0.295598 and k = 0.160713 which lead to (1431, 0, 229.98, 652.98) so I’m not surprised your choice performs so well – it must be the optimal choice for N=1431. Using j=0.30, k=0.16 I would expect to do much worse, as you have demonstrated.
In fact j = (5 + cbrt(3 * sqrt(33) – 19) – cbrt(3 * sqrt(33) + 19) / 3 where cbrt is the cube root.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Doomed to be zeros
« Reply #41 on: Nov 2nd, 2006, 6:05pm » |
Quote Modify
|
Miles, did you read my post from Oct 19? Compare to your fixed point values.
|
|
IP Logged |
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Doomed to be zeros
« Reply #42 on: Nov 2nd, 2006, 11:15pm » |
Quote Modify
|
on Nov 2nd, 2006, 6:05pm, SWF wrote:| Miles, did you read my post from Oct 19? Compare to your fixed point values. |
|
Weird - I don't remember seeing that, but I've even used the same notation for cube root as you!
Oh well, my fixed points aren't as original as I thought. However, I don't think anyone's come up with my use of base 3 logs, although I daresay there's a website somewhere... 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print