Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10 5/3/83 based; site hou2d.UUCP Path: utzoo!watmath!clyde!burl!mgnetp!ihnp4!houxm!hou2d!wbp From: wbp@hou2d.UUCP (W.PINEAULT) Newsgroups: net.math Subject: Re: Re: Yet another puzzle Message-ID: <482@hou2d.UUCP> Date: Fri, 7-Sep-84 13:45:24 EDT Article-I.D.: hou2d.482 Posted: Fri Sep 7 13:45:24 1984 Date-Received: Wed, 12-Sep-84 02:58:35 EDT Organization: AT&T Bell Labs, Holmdel NJ Lines: 53 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