chongo@nsc.UUCP (Landon C. Noll) (08/02/84)
at the 1979 Western Number theory conference, this problem was discussed by some number theory heavy weights (Lehmer, Ehrman, Williams, Selfridge, etc.) felt that this was a VERY VERY VERY hard problem. to quote one of them: "Fermat's last theorm will be proved long before the 3n+1 problem is put to rest!" chongo <dont let that get you down, you just might pull it off> /\33/\ -- Mail to me, i Mail back... hplabs!nsc!chongo "One thing is for certain, the sheep is not a creature of the air!" \/xx-~
jpl@allegra.UUCP (John P. Linderman) (08/02/84)
If there is a least integer for which the problem fails to converge, we can be sure it will be of the form 4n+3. This is a fairly simple exercise that I will leave to the reader, with the clue that the number is necessarily of the form 4n, 4n+1, 4n+2 or 4n+3, and being the least such number will eliminate the first 3 possibilities. John P. Linderman Department of Trivial Observations allegra!jpl
howard@metheus.UUCP (Howard A. Landman) (08/04/84)
Several interesting properties of this puzzle pop up when you consider everything modulo 6. One thing to note is that no sequence can have more than a single odd element which is divisible by 3, and it must be the first odd element. This can easily be seen from looking at the mod 6 transition tables: 0 -> 0 or 3 *0-->3 * = can remain 1 -> 4 or is done | in same state 2 -> 1 or 4 v 3 -> 4 2<->4<->5 4 -> 2 or 5 | ^ 5 -> 4 v | 1---- Another thing of interest is that there are only three cycles in this graph: (4,2), (4,2,1), and (4,5). Of these, only the (4,5) cycle has gain, i.e., results in an increase in the number when the whole cycle is taken into account. Letting "epsilon" be 1 divided by the number that is congruent to 4: Cycle Gain ------- ---------------- (4,2) 0.25 (exactly) (4,2,1) 0.75 (+ epsilon) (4,5) 1.50 (+ epsilon) These gains can be translated into constraints on the relative frequency of the three cycles in any non-terminating sequence, since the net gain must be >= 1.00. For example, at least 4/9ths of the cycles in any non-terminating sequence must be (4,5) cycles [excluding the singular cycle at 1,2,4 for which epsilon = 0.25, giving a gain of 1.00]. If we observe that, averaged over all integers > 1, 4 (mod 6) is equally likely to become 2 or 5, and that 2 is equally likely to become 1 or 4, then the typical gain for every four cycles is (3/2)*(3/2)*(3/4)*(1/4), or 27/64, and the expected length of four cycles is 9 elements of the sequence, so that the expectation of log(S(n+1)/S(n)) is just log(27/64)/9, or log(3/4)/3 (i.e., the log of the cube root of .75). We can conclude, since .75 is less than 1, that numbers which are sufficiently large tend to go down more than they go up. From this viewpoint, one would expect that for any N, there are infinitely many starting numbers for which the sequence increases to more than N-fold its starting value (before probably decaying to 1). In fact, a non-zero fraction of all integers should fall into this category. As a simple example, for N=3 the fraction is clearly greater than one half, including all odd numbers and many even numbers. However, one would also expect that this fraction decreases for increasing N, approaching 0 as N approaches infinity. Hence the set of numbers which begin sequences which grow without bound should be a set of measure zero. This does not imply there aren't any; the primes are also a set of measure zero, and there are infinitely many of them. In fact if there is one such number, there are infinitely many, because all the numbers in the sequence it begins also qualify. But it does mean that they must be sparse, and get sparser as you look at larger integers. Another possibility is that there could be a cycle of numbers other than the obvious (1,4,2) (these are absolute now, not modulo 6). Any such cycle must of course include several numbers each which are congruent to 2, 4, and 5 (mod 6); may include numbers which are congruent to 1 (mod 6); and cannot contain any numbers divisible by 3. Howard A. Landman ogcvax!metheus!howard (until August 14th)