pace@othervax.UUCP (08/22/84)
(new improved bug killer...only $3.99 more) What we have here is a problem one of my lecturers back in the good old days gave me: Please forgive me if you've all seen this before but I havn't been reading net.math for very long. Anyway, here it is; for ANY POSITIVE integer, call it "i", will the following "program" ALWAYS (eventually!) stop ? step 1: if( i == 1 ) then STOP; step 2: if( i is even ) then i = i/2 else i = 3*i + 1; step 3: go to step 1; We do of course assume that 'i' can be infinitely large etc. Well, what do you think, can any of you give a proof showing that it will stop (or halt or exit, whatever) for any positive integer? You will probably immediately think of the old HALTING problem we all learned about back in school. Well, if you want to know whether it can be done or not (that's if you already havn't guessed it by now), drop me a line and I'll tell you. cheers , Scott Pace, Micom Co., Montreal
dgc@ucla-cs.UUCP (08/26/84)
------------------------------------------------------------------------
(Athens -- near Syracuse)
What we have here is a problem one of my lecturers back in the good
old days gave me:
For ANY POSITIVE integer, call it i, will the following program
ALWAYS stop?
while (i is not 1) if (i is even) then i = i/2; else i = 3*i + 1;
stop;
We do of course assume that i can be arbitrarily large, etc.
------------------------------------------------------------------------
This is a famous old problem, usually known as the "Syracuse" problem.
It has been attributed to Stanislaus Ulam (of "Manhatten Project" fame).
It has been verified for extremely large values of i, using Crays' and
other reasonably fast computers.
Great glory will accrue to him (or her) who solves it (in other words,
it ain't easy!).
David G. Cantor
Arpa: dgc@ucla-locus.arpa
UUCP: {ihnp4, randvax, sdcrdcf, trwspp, ucbvax}!ucla-cs!dgcdis2@houxm.UUCP (A.NESTOR) (09/04/84)
Will the following ALWAYS STOP?:
step1: if(i=1) then STOP:
step2 : if ( i is even) i=i/2 else i=3i*i1+1;
step3: go to step1;
____________________________________________________________
State the problem as:
Define f :
f(n)=n/2 for n even
f(n)=3n+1 for n odd
where n is a postive integer (i.e. Z+)
Define fM(n) as the Mth composition of f(n)
i.e. fM=f o f o f o .......f(n)
Mth composition
Define sM(n) as the sequence:
f(n),f o f(n), f o f o f(n),.,.,fM
Defintion:
sM(j)(n) for j<=n is the jth member of sM(n)
Definition:
sM(n) "terminates" iff sM(n)=1.
PROVE: For all n, there exists M such that fM(n)=1.
i.e. sM(n) "terminates".
Consider the Quotient Set Z+/3:
It partitions Z+ into three subsets:
{0} n mod[3]=0 i.e. n=3k
{1} n mod[3]=1 i.e. n=3k+1
{2} n mod[3]=2 i.e. n=3k+2
Example:
n=6
S9(n)=6,3,10,5,16,8,4,2,1
f1(n)=6 s9(1)(n) a member of {0}
f2(n)=3 s9(2)(n) a member of {0}
f3(n)=10 s9(3)(n) a member of {1}
f4(n)=5 s9(4)(n) a member of {2} also f4(n)=(2**4 -1)/3
f5(n)=16 s9(5)(n) a member of {1}
f6(n)=8 s9(6)(n) a member of {2}
f7(n)=4 s9(7)(n) a member of {1}
f8(n)=2 s9(8)(n) a member of {2}
f9(n)=1 s9(9)(n)=1
Outline of Proof:
Prove Lemma I:
If
1. i is a member of sM(k) for some k
( sM(j)(k) for some j and k)
2. sM(k) terminates
3. i is a member of sM(m) for some m
( sM(j)(m) for some j and m)
then
there exists MM such that sMM(m) terminates.
This lemma clumsily says that if k is a member of a terminating
sequence, then any sequence of which k is a member can be made
to terminate. Indeed all sequences terminate after they have
a member of the form (2**m - 1)/3.
Prove Lemma II:
If there exists j such that sM(j)(n) is a member of {0}
then there exits k such that k>=j and sM(k)(n) is a member of {1}.
This lemma says that if n=3k is in the sequence, then there
is a later member n=3k+1.
Prove Lemma III:
If there exists j such that sM(j)(n) is a member of {1}
then there exits k such that k>=j and sM(k)(n) is a member of {2}.
This lemma says that is n=3k+1 is in the sequence, then there
is a later member n=3k+2.
Prove Theorem 1:
For all n, members of {2}; there exists M such that fM(n)=1.
The proof is by Weak Induction:
For k=1, n=3k+2=5
s6(5)=5,16,8,2,4,1
f6(5)=1
Assume:
n=3k+2 imples there exists M such that fM(n)=1
Prove:
n=3(k+1)+2 implies there exists M such that fM(n)=1
Lemma I and Lemmas II and III with j=1 and Theorem 1, provide the desired
result.
Creighton Clarke
sdcsvax!decvax!harpo!eagle!mhuxl!houxm!dis2
201-949-1538wbp@hou2d.UUCP (W.PINEAULT) (09/07/84)
My apologies about my last article on the 3n+1 problem. The equation to be solved is: 2**n - 3**m = 1 not the other way around. Now n=1, m=0 works, as does n=2, m=1. The reason for this connection is found by setting k=f(f(...(k)...) and solving for k given your favorite sequence of operations. The denominator of the value of k will be of the form 2**n - 3**m! Wayne Pineault AT&T Consumer Products Holmdel, NJ
wbp@hou2d.UUCP (W.PINEAULT) (09/07/84)
<WHO IS creighton clarke?>
The 3n+1 problem is a famous unsolved chestnut which has ruined
many good mathematicians' lives. I also got addicted to this problem
while in graduate school.
The lemmas given by Creighton seem to be simple and true, however
I would pay dearly to see that induction step.
Lemma 1: says that once a number is reached which is known to
terminate, then the sequence leading to the number will terminate.
True since the function is deterministic.
Lemma 2: says that for k odd, then 3k will produce 3(3k)+1 which
is in {1} and if k is even, then divide by two until it is odd and again
produce a number in {1}.
Lemma 3: can be reduced to if n is in {1} and even then n/2 must
be in {2} and if n is odd, 3n+1 is in {1}, is even so dividing by 2
will produce a number in {2}.
Please let me know if I am wrong!
The 3n+1 problem seems to break down into modulo 4 instead! If
we let M be the minimum number which does not go to 1, then we see for
instance that n is odd and n != 4k+1 (since 3(4k+1) +1 is divisible by 4
which produces a number which does not go to 1 which is less than M).
Another VERY curious fact is that if the diophantine equation:
3**m - 2**n =1
has a non-trivial solution then there will be many many numbers which
will cycle and never get to 1. As a hint at the relationship, the two
trivial solutions to the equation are m=1, n=0 and m=2, n=1. The m and
n tell how many *3+1 operations and /2 operations respectively. The
first solution corresponds uniquely to the cycle 0->0->0... the second
corresponds to the cycle 1->4->2->1.
Two last notes: The equation does not have to have a solution
for there to exist a nontrivial cycle, but finding m and n such that
3**m-2**n is either small or has lots of little factors would help.
Also there is the possibility that some huge number does not go to
1 and does not cycle, but goes off to infinity which produces an infinite
number of such numbers! Professional 3n+1'ers discount this possibility
but no progress has been made to show this is not the case.
Wayne Pineault
AT&T Consumer Products
Holmdel, N.J.
(201)-834-1094