wood burning stoves*
The moose likes Programming Diversions and the fly likes quadruple Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "quadruple" Watch "quadruple" New topic
Author

quadruple

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
Take any four integers a,b,c,d.So we have(a,b,c,d) now change this to
(|a-b|,|b-c|,|c-d|,|d-a|),Continue this process,Is it necessary that we will get (0,0,0,0) at the end of process?In how many steps?(|a-b| means absolute value of the difference between a and b)
[ December 23, 2003: Message edited by: Capablanca Kepler ]

MH
Shalu Ban
Ranch Hand

Joined: Feb 18, 2003
Posts: 72
The 4 numbers must be unique or they can be repeated?


Happiness is doing what is right.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
They can be repeated. Uniqueness is not a requirement.


"I'm not back." - Bill Harding, Twister
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
I think in four to five steps you get (0,0,0,0),not only for integers but also for rational numbers.
Joel McNary
Bartender

Joined: Aug 20, 2001
Posts: 1817

I think that you always will get (0,0,0,0), but not necessarily in four to five steps. Granted, I can't prove my assertion, but random testing has not yet discovered a situation where I did not get (0,0,0,0).
My longest time so far:



Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

Do you always take the absolute value before applying the next step?
that is, the first element of the next step would be
| (|a-b|) - (|b-c|) |
and not
| (a-b) - (b-c)
Dean Lee
Greenhorn

Joined: Aug 27, 2003
Posts: 11
i guess this is a good example to use recursion method. i think you have to break it into differnet assumption, then solve each assumption.
for example:
if a>b>c>d
then |a-b| = a-b, |b-c|=b-c, |c-d|=c-d, |d-a|=a-d
if b>a>c>d
then |a-b| = b-a, |b-c|=b-c, |c-d|=c-d, |d-a|=a-d
....
same at each step below. a program will solve the program.
[ January 15, 2004: Message edited by: Dean Lee ]

systematically
Dean Lee
Greenhorn

Joined: Aug 27, 2003
Posts: 11
(0) if a>b>c>d
|a-b|=a-b
|b-c|=b-c
|c-d|=c-d
|d-a|=a-d
(00) if a+c>2b, b+d>2c
| |a-b|-|b-c| |=a+c-2b,
| |b-c|-|c-d| |=b+d-2c,
| |c-d|-|d-a| |=a-c,
| |d-a|-|a-b| |=b-d
(000) if a+3c>3b+d
| | |a-b|-|b-c| | - | |b-c|-|c-d| | |=a+3c-3b-d
| | |b-c|-|c-d| | - | |c-d|-|d-a| | |=a+c-b-d
| | |c-d|-|d-a| | - | |d-a|-|a-b| | |=a+d-b-c
(0000) if a-b>b-c+b-d
| | |d-a|-|a-b| | - | |a-b|-|b-c| | |=a+d+c-3b
(0001) if a-b<b-c+b-d
| | |d-a|-|a-b| | - | |a-b|-|b-c| | |=3b-a-d-c
(00000)
2b-2c
2c-2d
2b-2c
2c-2d
(00010) if 2a+4c>6b
2b-2c
2c-2d
4b-2a-2d
2a+4c-6b
(00011) if 2a+4c<6b
2b-2c
2c-2d
4b-2a-2d
6b-2a-4c
(000000)
2b+2d-4c
2b+2d-4c
2b+2d-4c
2b+2d-4c
(0000000)
0
0
0
0
so, in one of the coditions, after 7 steps, you will get 4 same numbers: 0
the conditions are
1)a>b>c>d
2)a+c>2b, b+d>2c
3)a+3c>3b+d
4)a-b>b-c+b-d
Now let us follow another scenario:
(00010) if 2a+4c>6b
2b-2c
2c-2d
4b-2a-2d
2a+4c-6b
(000100) if 2a+2c+d>5b; a+3c>4b
2b+2d-4c
2c+2a-4b
4a+4c+2d-10b
2a+6c-8b
(0001000) if a+5c>5b+d
2a+6c-6b-2d
6b-2a-2c-2d
2a-2b-2c+2d
2a-10b+10c-2d
(0001001) if a+5c<5b+d
2a+6c-6b-2d
6b-2a-2c-2d
2a-2b-2c+2d
10b-10c+2d-2a
(00010000) a+c>3b; a+d>2b; 2b+d>3c
4a-12b+8c
4a-8b+4d
8b+4d-12c
4b-4c
(000100000)
4b+4d-8c
4a-16b+12c
4b+4d-8c
4a+12c-16b
(0001000000) if a+d>5b+5c; a+5c>5b+d
4a-20b+20c-4d
4a-20b+20c-4d
4a-20b+20c-4d
4a-20b+20c-4d
(00010000000)
0
0
0
0
it takes 11 steps to get 4 "0", the conditions are:
1)a>b>c>d
2)a+c>2b, b+d>2c
3)a+3c>3b+d
4)a+c+d>3b
5)a+2c>3b
6)2a+2c+d>5b; a+3c>4b
7)a+5c>5b+d
8)a+c>3b; a+d>2b; 2b+d>3c
9)a+d>5b+5c; a+5c>5b+d
[ January 15, 2004: Message edited by: Dean Lee ]
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

Not quite the way I was approaching it. I was taking the logic-programming route.

etc
ie (a,b,a,b) -> (|a-b|,|a-b|,|a-b|,|a-b|) -> (c,c,c,c)
It would also be useful to prove (a,b,c,d) -> (b,c,d,a) (commutitive) and (a,b,c,d) -> (d,c,b,a) (reflective) rules.
The only useful identity I haven't worked out so far is (a,a,b,c)
[ January 15, 2004: Message edited by: David O'Meara ]
Dean Lee
Greenhorn

Joined: Aug 27, 2003
Posts: 11
i have not quite got your point yet. but i am sure there are many approach here. once again, i believe this is a typical recursion problem. a computer program with recursion algorithm will be the most efficient way to solve it, in my humble opinion.
[ January 15, 2004: Message edited by: Dean Lee ]
Dean Lee
Greenhorn

Joined: Aug 27, 2003
Posts: 11
is it possible there is some relation between (a,a,b,c) and (a,b,a,c)?
which you have proved above.
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

I'm pretty sure the rules I've 'built' so far don't support swapping values, so while I feel the reflective and commutitive rules are correct, I'm not sure that (a,b,c,d) -> (b,a,c,d) But I wish it did!
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

Hardly a proof yet, but here are some more identities:
Dean Lee
Greenhorn

Joined: Aug 27, 2003
Posts: 11
looks good.
but your approach is too theoratical for me. in my approach, i think the only thing tricky is that as you recurse, you have to keep track all the conditions, and when you attempt to add new conditions, you have to make sure:
1) it is not redundant
2) it is not contrary to existing ones
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
The sequences always seem to converge, usually in 4 or 5 steps, but there's no difinite upper bound - there are a few rare sets of numbers that require many more steps.
Searching for the longest sequences possible, here are the best results I've found so far.
Using positive ints:
(1278803968, 583532544, 205520896, 0) --> 28 steps to (0, 0, 0, 0)
Using positive longs:
(8164210999759470592, 3725419181890338816, 1312096840887304192, 0) --> 54 steps to (0, 0, 0, 0)
And using BigInteger, I can generate a sequence that has any number of step you like. The only catch is, I need bigger and bigger numbers to do it. E.g.
1817259805347476915735490125212155904,
829235615973112320612610445538230272,
292057719936274949636267345975443456,
0
--> 100 steps to (0, 0, 0, 0)
and
93622369971645644338230883259672944794082414233030991664651359611110031360,
42720916075869326782257660804684375746580940126611282490388402611014336512,
15046354862683456706396778735761803830395538735325586923419259932264890368,
0
--> 200 steps to (0, 0, 0, 0)
I haven't been able to establish a formula relating max number of steps to max range of the integers used. That is, I can generate a sequence of n steps using numbers no larger than 6^n; that's an upper bound. But I have no definite proof that it's not possible to get a cycle of n with numbers considerably smaller than 6^n. This is just the result of one particular technique of generating long sequences; there may be much longer sequences available using smaller numbers.
I can say fairly definitely that if we include all rational numbers, or all integers (unbounded) (rather than just integers within particular bounds) then there is no maximum bound on the number of steps. Given any 4 rational numbers a, b, c, d, which have n cycles we can always find another set a', b', c', d' (bounded in [0, 1] if you like) which has n + 1 cycles. So we could also find another set a'', b'', c'', d'' with n + 2. By induction we can generate a set of 4 rational numbers with any number of cycles desired.
I also experimented a bit with this problem using different numbers of integers. E.g. for three integers, it's quite easy to generate an infinite sequence:
1 0 0
1 0 1
1 1 0
0 1 1
1 0 1
1 1 0
0 1 1
1 0 1
...
In fact it's easy to find such infinite sequences for any number of integers except a power of two. If you have 2 integers in a set (a, b), there are just two cycles:
1: (|a-b|, |a-b|)
2: (0, 0)
For 4, 8, 16 cycles - well as discussed previously, the sequences generally converge to zeroes pretty quickly, but there are oddball sequences that take longer. But the do always seem to converge eventually. I'm guessing that for any set of 2^n integers, the number of steps is always finite. (No infinite sequences.) Alas though, no proof of this yet.
[ January 16, 2004: Message edited by: Jim Yingst ]
Dean Lee
Greenhorn

Joined: Aug 27, 2003
Posts: 11
Originally posted by Capablanca Kepler:
Take any four integers a,b,c,d.So we have(a,b,c,d) now change this to
(|a-b|,|b-c|,|c-d|,|d-a|),Continue this process,Is it necessary that we will get (0,0,0,0) at the end of process?In how many steps?(|a-b| means absolute value of the difference between a and b)
[ December 23, 2003: Message edited by: Capablanca Kepler ]

the original question seems to be:
1) whether the result has to be 0;
2) how many step?
so i think using random number generation won't be the solution. You can't not try all the possible combination, therefore you can't prove the resut will always be 0, unless you find 4 numbers, which does not come out to be (0,0,0,0), then you disprove it.
my proposed solution is to systematically explore the configuration of four numbers (in term of distance between 4 starting numbers). hopefully, there is a limit for number of different configurations for our purpose, so we can find out whether the result will always be 0. Or there will be unlimited configuration, but we will be able to draw the conclusion.
i will use recursion algorithm, starting from step one, going through all possibility, it is easy to record the number of step and four number at each step. the tricky thing is to keep track all assumption made, and to make judgement based on past assumption, or to make new assumptions.
the way i want to do it:
1) the generalized form of any assumption is (let a,b,c,d be the four starting numbers):
Na*a+Nb*b+Nc*c+Nd*d >= 0
here Na, Nb, Nc, Nd are rational numbers.
so all the assumption made in past can be expressed in a matrix.
for example:
a>b =>
1*a+(-1)*b+0*c+0*d >=0
b>c =>
0*a+1*b+(-1)*c+0*d >=0
a+c<d => d-a-c>=0 =>
(-1)*a+0*b+(-1)*c+1*d>=0
the these three assumption can be expressed in a metrix:
| 1 -1 0 0 |
| 0 1 1 0 |
| -1 0 -1 1 |
or
| Vector_1 |
| Vector_2 |
| Vector_3 |
if f(a,b,c,d)>=0
then f(a,b,c,d) must be a combination of past assumption, please note, combination means:
Vector_f = sum(Ni*Vector_i)
Ni can only be 0 or positive, since multipling negative number changes the direction.
so now we know how to judge an expression based on the past assumptions, if an expression can not be expressed in a combination of past assumption, new assumption have to be made to proceed. then update the matrix.
these are the main ideas of the tricky part of my future program.
[ January 16, 2004: Message edited by: Dean Lee ]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
so i think using random number generation won't be the solution. You can't not try all the possible combination, therefore you can't prove the resut will always be 0, unless you find 4 numbers, which does not come out to be (0,0,0,0), then you disprove it.
Agreed. You can however get useful information about behavior, which can help guide in the types of solutions you look for.
the original question seems to be:
1) whether the result has to be 0;
2) how many step?

And to answer the second part first, there is no limit to the number of steps that may be necessary, unless you limit the problem to integers within a particular finite range. No random numbers are necessary to prove this. Though they did help guide my thinking in the first place. As I found longer and longer sequences (using random numbers) I stopped thinking about how to possibly prove that there was a limit to the number of iterations required, and instead prove that there is no limit. The latter path proved far more productive.
Of course, once we switch over to talking only about a finite range of integers (e.g. using only positive ints) then it becomes theoretically possible to prove a limit computationally, simply by enumerating and testing all possible combinations of numbers. Though of course it could take a while to actually perform the computation. I'd certainly like to see a nice simple formula for a solution, rather than a very computationally intensive brute-force approach. But don't be too quick to discount empirical approaces, since there's no guarantee that proof-based techniques will actually yield a useful result. It certainly may though, and I'll await further developments with interest. Good luck...
Dean Lee
Greenhorn

Joined: Aug 27, 2003
Posts: 11
Originally posted by Jim Yingst:
I can say fairly definitely that if we include all rational numbers, or all integers (unbounded) (rather than just integers within particular bounds) then there is no maximum bound on the number of steps. Given any 4 rational numbers a, b, c, d, which have n cycles we can always find another set a', b', c', d' (bounded in [0, 1] if you like) which has n + 1 cycles. So we could also find another set a'', b'', c'', d'' with n + 2. By induction we can generate a set of 4 rational numbers with any number of cycles desired.

I am not so sure about that.
assume you have four rational numbers: x1, x2, x3, x4, which take n steps to converge to (0,0,0,0). there may not exit y1, y2, y3, y4, that (y1,y2,y3,y4) converge to (x1,x2,x3,x4).
what happened is:
|y1-y2| = x1
|y2-y3| = x2
|y3-y4| = x3
|y4-y1| = x4
so first of all, x1, x2, x3, x4 all have to be >= 0.
if y1>=y2, y2>=y3, y3>=y4
then,
y1-y2=x1
y2-y3=x2
y3-y4=x3
y1-y4=x4
add first 3 equations together,
y1-y4=x1+x2+x3
so x1+x2+x3 = x4 must be true, otherwise, you can not find solution.
if y2>=y1, y1>=y3, y3>=y4
then,
y2-y1=x1
y2-y3=x2
y3-y4=x3
y1-y4=x4
then you have to have
x1+x4=x2+x3
to have solution.
.....
so there is restriction on (x1, x2, x3, x4). no just any 4 rational number.
i guess my point is: you can have any 4 rational numbers, they will converge to (0,0,0,0) (to be proved). but you may not always be able to "reverse engineering" them, so that is a hint to me: that there may be a upper limit for the number of steps to converge.
[ January 17, 2004: Message edited by: Dean Lee ]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[Dean]: assume you have four rational numbers: x1, x2, x3, x4, which take n steps to converge to (0,0,0,0). there may not exit y1, y2, y3, y4, that (y1,y2,y3,y4) converge to (x1,x2,x3,x4).
That's true. As a simple example, consider (1, 0, 0, 0), which converges to (0, 0, 0, 0) in 4 steps. There is no possible (y1, y2, y3, y4) which can transform to (1, 0, 0, 0). But that's OK, because the goal is to find a sequence that transforms to another sequence that has the same number of steps to 0 as (1, 0, 0, 0) did.
That is, if
(x1, x2, x3, x4)
converges in n steps, then there are a number of transformations which we can perform which will not change the fact that there convergence occurs in n steps. E.g. we can multiply all the numbers by a constant:
(mx1, mx2, mx3, mx4)
and we can add a constant
(mx1 + k, mx2 + k, mx3 + k, mx4 + k)
We can also reverse the order, or rotate the elements. The resulting set of numbers will still converge in n steps.
To see how this is useful, look again at
(1, 0, 0, 0)
Multiply by 2:
(2, 0, 0, 0)
Add 1:
(3, 1, 1, 1)
This still converges in 4 steps, same as (1, 0, 0, 0) did. But now we've got a set that we can find a (y1, y2, y3, y4) for:
(0, 3, 2, 1)
This sort of thing can actually be done with any set (x1, x2, x3, x4). It's a bit tricky to work out the details for all cases, but there's always some combination of transformations (mx + k, rotate, reverse) which can convert (x1, x2, x3, x4) to an equivalent form (equivalent in the sane of having the same number of steps to convergence) from which we can find a (y1, y2, y3, y4) with one more stpe to convergence.
By the way I did fib earlier when I said I have a "formula" to derive (y1, y2, y3, y4). It's more of an algorithm, with several formulas within. The initial form was a bit messy; I've been simplifying its presentation before I post if here.
[ January 17, 2004: Message edited by: Jim Yingst ]
Dean Lee
Greenhorn

Joined: Aug 27, 2003
Posts: 11
Jim, you are correct. I really enjoy discussing with you.
Here is what I got:
assume we want to get (y1,y2,y3,y4) for (x1,x2,x3,x4), so that it takes 1 step for (y1,y2,y3,y4) to converge to (x1,x2,x3,x4), then, by definition,
|y1-y2| = x1
|y2-y3| = x2
|y3-y4| = x3
|y4-y1| = x4
take square on both side,
(y1-y2)^2 = x1^2
(y2-y3)^2 = x2^2
(y3-y4)^2 = x3^2
(y4-y1)^2 = x4^2
then
y1^2-2*y1*y2+y2^2 = x1^2 ....... (1)
y2^2-2*y2*y3+y3^2 = x2^2 ....... (2)
y3^2-2*y3*y4+y4^2 = x3^2 ....... (3)
y4^2-2*y4*y1+y1^2 = x4^2 ....... (4)

(1)-(2)+(3)-(4):
y2y3-y1y2+y1y4-y3y4=0.5*(x1^2+x3^2-x2^2-x4^2)
then,
(y3-y1)(y2-y4)=0.5*(x1^2+x3^2-x2^2-x4^2)
now let us make some simplification,
let y1=y4=0; y3=1, .......................(5)
then
y2=0.5*(x1^2+x3^2-x2^2-x4^2)
so the (y1,y2,y3,y4) we are looking for is:
(0, 1/2*(x1^2+x3^2-x2^2-x4^2) ,1,0)
yes, there are always many (y1,y2,y3,y4) for (x1,x2,x3,x4) (if all of x1,x2,x3,x4 are >=0). one of them is:
(0, 1/2*(x1^2+x3^2-x2^2-x4^2) ,1,0)

one thing i want to add is:
make sure (0, 1/2*(x1^2+x3^2-x2^2-x4^2) ,1,0) is not the same (x1,x2,x3,x4).
if they are the same, it is easy to get arround it, at (5), make sure they are not the same.
[ January 17, 2004: Message edited by: Dean Lee ]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
One problem with squaring both sides of an equation is that you can create additional solutions that aren't solutions of the original equation. E.g.
x - 1 = 1
has one solution, x = 2. But if we square both sides, we get
x^2 - 2x + 1 = 1
x = 0, 2
When we square both sides of an equation we're obligated to check our solution(s) to see if they're still valid for the original equation. I fear this is a problem for your solution. E.g. if we start with
(x1, x2, x3, x4) = (1, 0, 0, 0)
and plug in
(y1, y2, y3, y4) = (0, 1/2*(x1^2+x3^2-x2^2-x4^2) ,1,0)
we get
(y1, y2, y3, y4) = (0, 1/2*(1+0-0-0), 1, 0) = (0, 1/2, 1, 0)
If we apply our transformation seqence to this we get:
0: (0, 1/2, 1, 0)
1: (1/2, 1/2, 1, 0) (Not our original (1, 0, 0, 0) or equivalent)
2: (0, 1/2, 1, 1/2)
3: (1/2, 1/2, 1/2, 1/2)
4: (0, 0, 0, 0)
Thus the "solution" (a) doesn't transform to the original (1, 0, 0, 0) and (b) still has only 4 steps to (0, 0, 0, 0), same as (1, 0, 0, 0) did. (a) isn't necessarily a problem, except that as I understand your solution you never replaced (x1, x2, x3, x4) with some equivalent (mx1 + k, mx2 + k, mx3 + k, mx4 + k) as I'd suggested, so it seems you should expect to still see the original (x1, x2, x3, x4) when you transform your solution.
I still say it's always possible to find a set for numbers with n+1 cycles, but I don't think your solution works.
Dean Lee
Greenhorn

Joined: Aug 27, 2003
Posts: 11
Originally posted by Jim Yingst:
One problem with squaring both sides of an equation is that you can create additional solutions that aren't solutions of the original equation. E.g.
x - 1 = 1
has one solution, x = 2. But if we square both sides, we get
x^2 - 2x + 1 = 1
x = 0, 2
When we square both sides of an equation we're obligated to check our solution(s) to see if they're still valid for the original equation.

i think square does not introduce problem in this case, because here we have equations with absolyte value.:
|y1-y2| = x1
|y2-y3| = x2
|y3-y4| = x3
|y4-y1| = x4
I fear this is a problem for your solution.

yes, there is a problem, i guess i was not careful.
at equation (5) of my last post,

let y1=y4=0; y3=1, .......................(5)



in fact i can not do that, it is contrary to initial condition:
|y1-y2| = x1 = 1
|y2-y3| = x2 = 0
|y3-y4| = x3 = 0
|y4-y1| = x4 = 0
in fact, if (x1,x2,x3,x4)=(1,0,0,0), then the initial condition contradict itsef. so maybe we should call it a deadend.
******************************************************************
however, everything so far is a guess,
it is highly likely that:
1) the result for any four rational numbers will converge to (0,0,0,0)
2) there is no upper limit on the steps required to converge
but there is no proof yet. once again, i think one of the best ways to prove them is to use recursion method described in my previous posts.
[ January 18, 2004: Message edited by: Dean Lee ]
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

I was enjoying my logical approach, but I doubt that will produce a solution. So, in a change of direction I'm looking at showing that any initial combination will converge to (a,a,a,a).
How? I'm working with showing that the standard deviation of step n+1 is less than or equal to the standard deviation of step n. I believe the 'equals' case is where Jim shows an infinite series, proving this is not possible in our case would be a separate exercise.
The maths is a bit larger than I expected, lucky I'm on holidays.
On a side note, I was considering the possibility of an infinite series, and the solution reminded me of Conway's "Game of Life" with weightings. The "standard deviation" proof will remove these infinite series if it works.
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

I meant to also mention that Jim's example shows that there is no upper bound to the number of steps required, so that 'solves' one part of the problem as it was set. I was more interested in the "is it necessary we'll get to (0,0,0,0)" part.
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

No luck so far.
For (a,b,c,d) the standard deviation is
sd1 = 1/4 * [ a^2 + b^2 +c ^2 + d^2 - 1/4 * (a+b+c+d)^2 ]
For a single case ( |x1-x2|, |x2-x3|, |x3-x4|, |x4-x1| ) and innitially assuming x1>x2>x3>x4 the standard devation is
sd2 = 1/4 * [ (x1-x2)^2 + (x2-x3)^2 + (x3-x4)^2 ]
The next step would be to show sd1>sd2 then have a look at the other combinations for x1>x2 etc, but I can't see how to show sd1>sd2 given the above.
I tried replacing (a+b+c+d) with 4m where m=min(a,b,c,d), but that didn't work. I'm currently looking at the cases where it may cause sd1<sd2. I also tried expanding various elements, but the terms start to get nasty.
In sd2, note that (x1-x2) is less than x1 and (x2-x3) is less than x2 etc. It looks smaller, but how to prove it?
[ January 20, 2004: Message edited by: David O'Meara ]
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
I was wrong earlier for stating that process stops in 4/5 steps.Now I think in at the end of four steps,all numbers are even.that is in 4 steps all numbers are divisible by 2.In 8 steps,all numbers will be divisible by 4 and so on.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
That's an interesting idea, Cap. If it's true, it will allow us to prove that all sequences eventually converge. And also we'll be able to limit the maximum number of steps to convergence, as a function of the maximum absolute value of the initial 4 numbers. Basically, if all 4 initial numbers are <= 2^k, then the sequence must converge within 4(k + 1) steps. Because after 4k steps all numbers must be multiples of 2^(k+1), and the numbers can't get any larger than their initial max magnitude which was 2^k, so the only possible values are (0, 0, 0, 0).
However, this will only work if it's always true that after 4 steps, the values will be multiples of 2. (I can see how this would extend to 4, 8, etc. every four steps, if 4 steps makes everything even.) Do you have some sort of proof that this is true? Or is it just a general observation?
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Actually I see it's not that difficult to prove that after four steps, all numbers will be even. Let E represent an even number, and O is an odd number. Two E's are not necessarily the same even number, and two O's are not necessarily the same odd number. The difference between two even numbers is even; the difference between two odd numbers is also even; the difference between an even number and and odd number is odd. So in terms of even and odd, there are 16 possible combinations for the initial 4 numbers. Let's see what sequences we get:
0: E O O O
1: O E E O
2: O E O E
3: O O O O
4: E E E E
(O E O O), (O O E O), (O O O E) are like (E O O O) above - 4 steps to (E E E E)
(E E O O), (O O E E), (E O O E) are like (O E E O) above - 3 steps to (E E E E)
(E O E O) is like (O E O E) above - 2 steps to (E E E E)
(O O O O) above is 1 step from (E E E E)
(E E E E) is 0 steps from (E E E E)
That's 12 of the possibilities. For the remaining 4:
0: E E E O
1: E E O O
2: E O E O
3: O O O O
4: E E E E
(E E O E), (E O E E), (O E E E) are like (E E E O) above - 4 steps to (E E E E)
So for all 16 possible arrangements of even and odd numbers, after 4 steps, all will be even. And after 4k steps, all numbers will be multiples of 2^k. So if initially all numbers have magnitude < 2^k, the series will converge in 4k steps. Excellent. I think the problem is essentially solved now.
[ January 21, 2004: Message edited by: Jim Yingst ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: quadruple
 
Similar Threads
yet another postfix/prefix precedence question
Having trouble choosing a data structure
SAMPLE QUESTIONS- Part B
mock exam question
I have 3 doubts question? can help me?