(ab,bc,cd,da),Continue this process,Is it necessary that we will get (0,0,0,0) at the end of process?In how many steps?(ab means absolute value of the difference between a and b)
[ December 23, 2003: Message edited by: Capablanca Kepler ]
MH
My longest time so far:
Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.
for example:
if a>b>c>d
then ab = ab, bc=bc, cd=cd, da=ad
if b>a>c>d
then ab = ba, bc=bc, cd=cd, da=ad
....
same at each step below. a program will solve the program.
[ January 15, 2004: Message edited by: Dean Lee ]
systematically
ab=ab
bc=bc
cd=cd
da=ad
(00) if a+c>2b, b+d>2c
 abbc =a+c2b,
 bccd =b+d2c,
 cdda =ac,
 daab =bd
(000) if a+3c>3b+d
  abbc    bccd  =a+3c3bd
  bccd    cdda  =a+cbd
  cdda    daab  =a+dbc
(0000) if ab>bc+bd
  daab    abbc  =a+d+c3b
(0001) if ab<bc+bd
  daab    abbc  =3badc
(00000)
2b2c
2c2d
2b2c
2c2d
(00010) if 2a+4c>6b
2b2c
2c2d
4b2a2d
2a+4c6b
(00011) if 2a+4c<6b
2b2c
2c2d
4b2a2d
6b2a4c
(000000)
2b+2d4c
2b+2d4c
2b+2d4c
2b+2d4c
(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)ab>bc+bd
Now let us follow another scenario:
(00010) if 2a+4c>6b
2b2c
2c2d
4b2a2d
2a+4c6b
(000100) if 2a+2c+d>5b; a+3c>4b
2b+2d4c
2c+2a4b
4a+4c+2d10b
2a+6c8b
(0001000) if a+5c>5b+d
2a+6c6b2d
6b2a2c2d
2a2b2c+2d
2a10b+10c2d
(0001001) if a+5c<5b+d
2a+6c6b2d
6b2a2c2d
2a2b2c+2d
10b10c+2d2a
(00010000) a+c>3b; a+d>2b; 2b+d>3c
4a12b+8c
4a8b+4d
8b+4d12c
4b4c
(000100000)
4b+4d8c
4a16b+12c
4b+4d8c
4a+12c16b
(0001000000) if a+d>5b+5c; a+5c>5b+d
4a20b+20c4d
4a20b+20c4d
4a20b+20c4d
4a20b+20c4d
(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 ]
systematically
etc
ie (a,b,a,b) > (ab,ab,ab,ab) > (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 ]
[ January 15, 2004: Message edited by: Dean Lee ]
systematically
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
systematically
Sheriff
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: (ab, ab)
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 ]
"I'm not back."  Bill Harding, Twister
Originally posted by Capablanca Kepler:
Take any four integers a,b,c,d.So we have(a,b,c,d) now change this to
(ab,bc,cd,da),Continue this process,Is it necessary that we will get (0,0,0,0) at the end of process?In how many steps?(ab 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 => dac>=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 ]
systematically
Sheriff
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 bruteforce approach. But don't be too quick to discount empirical approaces, since there's no guarantee that proofbased techniques will actually yield a useful result. It certainly may though, and I'll await further developments with interest. Good luck...
"I'm not back."  Bill Harding, Twister
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:
y1y2 = x1
y2y3 = x2
y3y4 = x3
y4y1 = x4
so first of all, x1, x2, x3, x4 all have to be >= 0.
if y1>=y2, y2>=y3, y3>=y4
then,
y1y2=x1
y2y3=x2
y3y4=x3
y1y4=x4
add first 3 equations together,
y1y4=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,
y2y1=x1
y2y3=x2
y3y4=x3
y1y4=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 ]
systematically
Sheriff
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 ]
"I'm not back."  Bill Harding, Twister
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,
y1y2 = x1
y2y3 = x2
y3y4 = x3
y4y1 = x4
take square on both side,
(y1y2)^2 = x1^2
(y2y3)^2 = x2^2
(y3y4)^2 = x3^2
(y4y1)^2 = x4^2
then
y1^22*y1*y2+y2^2 = x1^2 ....... (1)
y2^22*y2*y3+y3^2 = x2^2 ....... (2)
y3^22*y3*y4+y4^2 = x3^2 ....... (3)
y4^22*y4*y1+y1^2 = x4^2 ....... (4)
(1)(2)+(3)(4):
y2y3y1y2+y1y4y3y4=0.5*(x1^2+x3^2x2^2x4^2)
then,
(y3y1)(y2y4)=0.5*(x1^2+x3^2x2^2x4^2)
now let us make some simplification,
let y1=y4=0; y3=1, .......................(5)
then
y2=0.5*(x1^2+x3^2x2^2x4^2)
so the (y1,y2,y3,y4) we are looking for is:
(0, 1/2*(x1^2+x3^2x2^2x4^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^2x2^2x4^2) ,1,0)
one thing i want to add is:
make sure (0, 1/2*(x1^2+x3^2x2^2x4^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 ]
systematically
Sheriff
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^2x2^2x4^2) ,1,0)
we get
(y1, y2, y3, y4) = (0, 1/2*(1+000), 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.
"I'm not back."  Bill Harding, Twister
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.:
y1y2 = x1
y2y3 = x2
y3y4 = x3
y4y1 = 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:
y1y2 = x1 = 1
y2y3 = x2 = 0
y3y4 = x3 = 0
y4y1 = 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 ]
systematically
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.
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 ( x1x2, x2x3, x3x4, x4x1 ) and innitially assuming x1>x2>x3>x4 the standard devation is
sd2 = 1/4 * [ (x1x2)^2 + (x2x3)^2 + (x3x4)^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 (x1x2) is less than x1 and (x2x3) is less than x2 etc. It looks smaller, but how to prove it?
[ January 20, 2004: Message edited by: David O'Meara ]
Sheriff
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?
"I'm not back."  Bill Harding, Twister
Sheriff
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'm not back."  Bill Harding, Twister
a fool thinks himself to be wise, but a wise man knows himself to be a fool  shakespeare. foolish tiny ad:
Thread Boost  a very different sort of advertising
https://coderanch.com/t/674455/ThreadBoostfeature
