jwp@sdchema.UUCP (John Pierce) (10/05/83)
The alogrithm: 1) Select an integer 'X' 2) If X is even, X = X/2 else X = 3X + 1 3) Iterate step 2 with the new value of X The conjecture is that for all integers the alogrithm will eventually generate the sequence "4 2 1" (which cycles). Examples: X = 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1 ... X = 11, 34, 17, 52, 26, 13, 40, 20, 10 ... (as above from 10) X = 51, 154, 77, 232, 116, 58, 29, 88, 44, 22, 11 ... (as above) Does anyone know the name of this conjecture (I believe it was first proposed by a Canadian), and whether or not it has been (dis)proven? John Pierce, Chemistry, UC San Diego ucbvax!sdcsvax!sdchema!jwp
leichter@yale-com.UUCP (Jerry Leichter) (10/10/83)
I believe this problem is due to Stanislaw [?] Ulam; the last I heard, it was not known whether the algorithm settles into a cycle. (There is a small number - 41 or somewhere near there - that produces a VERY long run before settling down. Come to think of it, it may not even be know if the algorithm EVER settles down, starting on that number.) Ulam's conjecture has been discussed more than once in the Scientific American Mathematical Games section. -- Jerry decvax!yale-comix!leichter leichter@yale
emjej@uokvax.UUCP (10/14/83)
#R:sdchema:-88400:uokvax:3300001:000:485 uokvax!emjej Oct 12 09:21:00 1983 Funny you should mention that. Dr. Richard V. Andree here at the University of Oklahoma came up with it one fine day to give a student an example of a recurrence relation, and discovered that it was *far* more interesting than it at first appeared. I recall hearing that every starting value up to 10**40 either terminates or loops. A book by Nievergelt et al., I think called *Computer-Assisted Problem Solving*, gives further analysis of this recurrence relation. James Jones