Conference rusure::math

This is the classic 3N+1 problem.

It's fairly easy to find expressions to describe all those numbers that reduce
to one in 1 step, in 2 steps, in 3 steps,... (where a step is "multiply by 3,
add 1, remove all factors of two").

Similarly, you can find expressions to describe all numbers that reduce to
something less than that number in 1 step, in 2 steps, .... 

It's possible to find expressions for all those numbers that cycle in 1 step,
in 2 steps, ....  So far (up to six steps?), solving these always gives the
number 1.

It's possible to prove that no number yields an infinite, ever-increasing
sequence (i.e., at some point, you must divide by 4).

You can verify that all numbers less than N will reduce to 1, for some fairly
large N.  A computer search for a counter-example will have to deal with
128-bit numbers; a computer program can use some tricks to do several steps
per iteration.

Also, interesting bit patterns occur in this problem.

I suspect that certain problems, perhaps this one, are not necessarily that
hard, and that what happens is that someone labels them "open for several
years" and MOST people translate that into "the best mathematicians failed,
so I won't even try".

Maybe as a corporation in this very notes file, WE can solve the problem.
(No, don't buy stock now, it's illegal, inside tip etc.)

Here's what I've done so far:

First of all, since 3n+1 is only done when n is odd, then 3n+1 is always
even.  Hence we never do 3n+1 more than once in a row.

With this in mind, I started representing SIGNATURES of numbers, where
the signature of a number is a series of integers representing how many
times you divide by 2 before having to do 3n+1.  The signature ENDS when
the resulting n is smaller than you started with.

For instance, for 7, we initially can't divide by 2 at all, so we do
3n+1 and get 22, which allows us to divide by 2 once giving 11, the total
operation being
7*3+1=22/2=11*3+1=34/2=17*3+1=52/2=26/2=13*3+1=40/2=20/2=10/2=5.
5 is smaller than 7 so we stop.

So as a signature for 7, we get

	7 = 0 1 1 2 3

I wrote a computer program to print out signatures.  Patterns arise of
repetitions of signatures.  These are easy to prove once observed.

I went on to start an inductive proof of the big question, namely that all
numbers melt to 1.  My proof goes like this:

	Suppose we've verified for some n that all integers 1 through 4n
	melt to 1.

	If we can prove that 4n+1, 4n+2, 4n+3, and 4n+4 all melt to 1,
	we've proved the entire conjecture, since 4n+4 is again of the form
	4n.  Most of these are easily proven (pardon my use of "=" character):

		(4n+1)*3+1=(12n+4)/4=3n+1 which we've already verified.
		(4n+2)/2=2n+1 which we've already verified.
		(4n+3)*3+1=(12n+10)/2=(6n+5)*3+1=(18n+16)/2=(9n+8) ????
		(4n+4)/4=n+1 which we've already verified.

	So 4n+3 is the killer.  We've proved 75% of the problem.  Of course,
	that last 25% is 200% of the work, but it's a start.

More than a start, perhaps this will whet appetites for some other people
to work on it.

Here are my current questions:

1)  I went on to start looking at 9n+8 as two branches, assuming even or odd
    n.  These branches branch out etc.  Perhaps they'll end somewhere ?  I
    haven't written a lisp program to sniff them yet.

2)  Is my signature useful ?  Does someone have a better one ?

3)  Can some side things be proven ?  For instance:  what numbers have
    the longest signatures, here "longest" means longer than any that of
    and number seen before ?  What numbers contain the largest integers
    WITHIN their signatures ?

4)  Remember the pretty pattern resulting from coloring pixels according
    to the parity of numbers in Pascal's triangle ?  Can some sort of pixel
    pattern be derived from this 3n+1 problem that also is "pretty" ?

p.s.	CAUTION:  My father suspects that the Russian's biggest offensive
	strategy against the USA is that they submit interesting math puzzles
	to Scientific American and other magazines.  This causes the best
	minds of the USA to work on puzzles instead of doing more useful
	things -- interesting idea.

	/Eric Osman

Isn't there an initial number which is not known to melt to 1?  I am
talking about something less than 100.  (Maybe I'll go find out).
				/AHM/THX

All small numbers "melt" easily. 27 is the first "hard" one (try it...) but
it finally reaches 1 as well...
p.s. I tried investigated this problem once, and... (well you know it's not
     solved yet :-)

Perhaps I'm onto something:

	To summarize my previous mail, I showed that if we've verified
	all numbers 1 through 4n, we can easily prove 4n+1,2,4.  4n+3
	is the clincher.  If we prove that, we're done (by induction).

By a certain measure of doneness, we're 3/4 through.

Well, I wrote a lisp program to chase the trees.  I asked it to suppose
that we verified all numbers 1 through 16n.  The program easily proved
that 16n+k melts to 1, for all k 1 through 16 EXCEPT 7, 11, and 15.

So, by the same measure as before, we're now 13/16 through, which is BETTER
than 3/4 !

Maybe we can apply induction on these emerging strings of incomplete
inductions to prove that by choosing larger and larger c's in

	cn + k

we can prove larger and larger percentages of the classes of numbers,
and prove that the LIMIT is c/c.

Turning it around slightly, perhaps we can figure out how {7,11,15} relate
to 16 "in the same way" that {3} relates to 4.  Then, maybe we can prove 
that any X melts to 1 by showing how one chooses c for X such that X mod c
is NOT a member of the set {unknowns-for-modulo-c}.

Time to go home.  More tomorrow :=)

Let's see ...

	4x+1 -> 12x+4 -> 3x+1		smaller than 4x+1, if x >= 1
	4x+3 -> 12x+10 -> 6x+5
		-> 18x+16 -> 9x+8

	8x+3 -> 18x+8 -> 9x+4
	8x+7 -> 18x+17 -> 54x+52
		-> 27x+26

	16x+3 -> 18x+4 -> 9x+2		smaller than 16x+3, if x >= 0
	16x+11 -> 18x+13 -> 54x+40
		-> 27x+20
	16x+7 -> 54x+26 -> 27x+13
	16x+15 -> 54x+53 -> 162x+160
		-> 81x+80

	32x+11 -> 54x+20 -> 27x+10	smaller than 32x+11, if x >= 0
	32x+27 -> 54x+47 -> 162x+142
		-> 81x+71
	32x+7 -> 54x+13 -> 162x+40
		-> 81x+20
	32x+23 -> 54x+40 -> 27x+20	smaller than 32x+23, if x >= 0
	32x+15 -> 162x+40 -> 81x+20
	32x+31 -> ... -> 81x+80

Not much progress....

 INTUITIVELY, this type of search doesn't look like any progress, because
1/4 of infinity is still infinity etc. What I try to say is that by limiting
the search to specific classes of natural numbers we've achieved nothing new,
at least so far.

 Some interesting questions that might also help:

 1. What is so special in "27" (in relation to its "neighbors") that makes its
    "melting" sequence so long?

 2. Looking in the binary representation of numbers: Dividing by 2 is just
    "trimming" the trailing 0's. Doing 3n+1 is adding the same number [after
    shift left by 1 bit and inserting 1 in the new rightmost position] to
    itself. For example:

        1010   start with "10" divide by 2 until "5"
       1011    add 2*5+1 to 5 (which yields 3*5+1)
       ----
      10000    getting "16" divide by 2 until "1"

    Maybe this method indicates something?...

 3. The problem can be introduced in a "reversed" way: Starting from 1 you are
    allowed the following operations: (1) Multiplying by 2. (2) Subtracting 1
    and dividing by 3 if the result is integer odd. Do you cover all natural
    numbers this way?

Can anyone make any observations about which signatures can and cannot exist,
or given a signature, determine what number it represents ?

For instance, suppose I want to know what number's signature is [1 2 3 4].

(I'll save you the trouble of re-reading my definition of signature. [1 2 3 4]
means we divide by two ONCE, producing an odd number so we do *3+1, and then
we get an even number (of course!) which we divide by two TWICE getting
an odd number which we *3+1 producing an even number which we divide by two
THREE times, then *3+1, then divide by two FOUR times which finally yields
a number smaller than what we started with).

Another question:  what classes of numbers have been proven to melt to
1 ?  2^n is trivial since you can keep dividing by 2.

All numbers of the form 4n+1 are odd so we go to 12n+4 which we divide by
4 yielding 3n+1 which is smaller than 4n+1.  Hence all 4n+1's have a signature
of [0 2].  But that doesn't prove that all numbers in the class 4n+1 melt to 1,
since 3n+1 is indeterminate.

Therefore it's a bit of a tease to have all 4n+1's having such a simple
signature of [0 2].  For this reason, I'm starting to dislike my choice
of signature.  If the signature calculation ended when the number had
been reduced all the way to 1, or perhaps ended when the number had been
reduced to some number KNOWN TO MELT TO 1 rather than some number LESS THAN
THE STARTING POINT, then perhaps it would be better.

Or, perhaps if the signature were chosen such that we could define operations
on it, it would be useful.  For instance, maybe we can find a signature function
s such that s(f1(a,b)) = f2(s(a),s(b)) for some simple functions f1 and
f2, in the spirit of group theory.

Someone in a previous reply mentioned the idea of going backwards.  We
can start a table like this:

				1
				2
				4
				8
				16
			      32   5
                              64       10
                           128  21  20    3
                           256  42  40    6
                       512 85   84 80 13 12
                               . . .

What it means is that we always end with 1, which definitely comes from
2, which definitely comes from 4, which definitely comes from 8, which
definitely comes from 16, which could have come from 32 or 5.  32 can only
come from 64.  5 can only come from 10.  64 can come from 128 or 21, 10 can
come from 20 or 3 etc.

Can anyone prove anything interesting about this table ?  For instance:

1)	What function describes how many numbers are in the nth row ?

2)	Remember the pretty patterns of triangles within triangles that
	results from displaying the parity of the numbers in Pascal's
	triangle ?  Can anything like that be done with THIS table ?
	Maybe not something as obvious as parity, but then again, maybe
	so.  Or perhaps each row should be SORTED into ascending order,
	and then displayed ?

3)	How about the positions in each row that are prolific, i.e. those
	numbers that come from TWO numbers instead of one.  Is there a
	describable pattern of where these occur ?

4)	What is reality ? :-)

A number n is 'prolific' (in that it could have 'come from' both 2n and 3n+1),
iff n mod 3 = 1.  The 'width' of a level in the tree is roughly an exponential
function of the 'depth' (something like:

	width = a * (4/3)**depth, for some constant a.


FWIW - I think you'd do better to NOT consider 3x+1 and x/2 as separate steps.
Instead, consider (3x+1)/2^n as a single step.  Then, it's interesting to find
regular expressions for all the (binary) numbers that 'melt' to one in 1 step
(1[01]...), 2 steps, 3 steps, ....

The 3x+1 problem (also known as the Collatz problem) has been
around for quite a while and has been worked on by a good many
mathematicians.

Before you spend too much time on it, you might want to read up
on what's been done to date.  A good survey article is

Jeffrey C. Lagarias, The 3x+1 Problem and its Generalizations,
	The American Mathematical Monthly, 92(1985)3-23.

This article also has a long bibliography, containing 70 references.

A reference you should be able to find in a DEC library is:

R. E. Crandall, On the 3x+1 Problem, Math. Comp. 32(1978)1281-1292.

Note also that the world of computer hackers has attacked this problem
(as well as mathematicians) since the problem was published in
HAKMEM back in 1972, q.v.

Thanks for the references.

Is there anyway over the e-net I can order a copy of these references from
a DEC library ?  (Enlighten me as to library services availablility.)

Can any of you in mathland out there send me a copy ?  I work in a shoebox
in Burlington, Ma.  I doubt our library has much.

Thanks for any help.                                                 

Actually, it's probably not a bad thing that we work on the problem
for awhile before reading up on it.  Reading up may influence us to
try the failing methods documented by other people, rather than stumbling
on a winning method of our own !           

 Well, first of all sorry for not reading the book before replying, but just
some more funny ideas I observed (maybe they are in that book?):

 Re.10:
>A number n is 'prolific' (in that it could have 'come from' both 2n and 3n+1),
>iff n mod 3 = 1.
** You mean "iff n mod 6 = 4" (because it's even)

 Now, considering the binary representation mentioned earlier, it's easy to
show that in order for an odd number n to divide k times by 2 after 3n+1, then
n (in its binary form) must terminate with a sequence of k bits "...010101".

 We can go on and find that in order for an odd number n to have a sequence of
k bits "...010101" after 3n+1 and dividing by 2's, then n must have a sequence
of k bits "...000111000111..." left to its own "...010101".

 This can go on and produce complicated bit patterns. Based on the first
observation, it's also easy to show that in order to find the next odd number
following a current odd number, all you need to do is to "trim" the trailing
"...010101", consider the result as "m" and then do 3m+1 (if m even) or 3m+2
(if m odd).

Curious - is it in the book? 

This problem is also known as "Ulam's Conjecture" (after Stanislau Ulam).
(THe conjecture is that you always reach 1.)

It's a particular example of a general procedure for generating sequences
by iterating a function - a(i+1) = f(a(i)). There is currently a great deal
of interest in these kind of sequences, with the recent work on "attractors"
in physics, etc.  Very simple f's - like this one - can produce extremely
"chaotic" behavior - 27 takes a LONG time to reach 1, having (of necessity)
hit some very large numbers alon the way, but right next to 27 are numbers
that are very well behaved.  If you think of f as representing where a
particle in a fluid goes in its next step, then you can see that (for this
simpel evolution function - totally unphysical, of course) the particle
at 27 gets very far from its initial neighbors at 26 and 28.  In fact, the
same kind of thing can occur in real physical situations - even if f() is
continuous, it can produce very chaotic distributions of particles when
iterated.
							-- Jerry

To Stan:

	THANK YOU for sending me the copy of a lengthy article on the
	3n+1 problem !   I received it yesterday.

	/Eric

See also the Computer Recreations column in Scientific American,
both the Jan 1984 and April 1984 issues.  This contains up-to-date
computational information on the 3n+1 problem.

Here goes another balloon !
	This problem has teased me since I first heard about it a few years
ago.  Last week I thought of the following line of reasoning which can prob-
ably be thrown out as being un'mathemetical'.
	The pattern I noticed is that the path followed when melting any
number partially defines/traverses branches of a tree in the following way.

       					            72
	 120			           116 112  36
	  60 184                       176  58	56  18
	  30  92                        88--29  28---9
	  15--46 140               136  44      14
     192      23--70  212      208  68  22-------7        454
      96	  35--106  320 104  34--11           682--227	336
      48	       53--160  52--17	       1024--341	168
      24		    80  26              512		 84
      12	     	    40--13		128		 42
       6		    20			 64--------------21
       3--------------------10			 32
			     5-------------------16
				      		  8
				        	  4
				      		  2
			     			  1
                            
This 'tree' has infinitely high branches of even numbers, and sprouts a 
branch for every odd number! Or we can say :
		1) Every even number is a member of a branch,
                2) Every odd number generates a branch...
	The reasoning that I believe proves termination is that this proves
that every (positive) number is a member of this 'tree' therefore that proc-
edure which generates the tree must terminate since any number picked is
a member of the tree, and every member of the tree is on a 'melt' path to
to the root : 1.

	n'est ce pas ?

    I don't see where you've proved that every odd number is a member
    of the tree.  Or every even number.
    
    It isn't good enough to say "Look at the figure".  Have you got
    something a bit more definite?
    
      John

    well I suppose that defining properties of the tree might not help,
    But here goes :
    I'm building on a previous statement I've seen which proved that
    any odd number results necessarily in an even successor.
    I don't know how to be more definite in 'mathematical'ese but isn't
    division of any even number just as necesarily going to lead to
    an odd number ?
    If so, then this I quess is a proof by construction in that my
    definition of a branch is all 2^n multiples of an odd stacked above it
    ad infinitum.  Any branch can be constructed, and every branch so
    made can be connected to another by the 3n+1 rule.  I haven't thought
    of a notation for identifying branches, but why doesn't the general
    statement of evens and odds satisfy you ?
    The 3n+1 rule to me guarantees connectivity of any branch to another,
    The height of each branch guarantees membership for all evens,
    And by connectivity I mean every and any odd # is assigned to a 3n+1
    neighbor that is even,
    So, pick any # : it has to be on the tree which is a direct analog
    to the sequence.
    The mess I see is the infinite sets of [odd roots] creates graphically
    at least an infinite forest of even infinities at the branch 'tips'.  

To put it another way:

	You haven't demonstrated the nonexistence of some number that
	after some iterations leads back to itself again, rather
	than joining your tree.

I'll leaf it at that.

/Eric

    The same argument can be applied to a '5*n+1' sequence.  But consider:
    
       13->66			17->86
           33->166		    43->216
                83->416		        108
                    208		         54
                    104		         27->136
                     52		              68
                     26		              34
                     13->...	              17->...

    Does the sequence that starts with 7 ever cycle, or does it simply
    grow without bound?

     The author of the following refers to this as the "hailstone
     problem."  That is picturesque; as the number loses weight
     (n -> n/2) the updrafts carry it back up into the clouds,
     where more ice forms on it (n -> 3n+1) making it heavy
     enough to start falling again ....
     
     Dan
     
Newsgroups: sci.math
Path: decwrl!labrea!rutgers!mit-eddie!bu-cs!mirror!rayssd!raybed2!cvbnet2!holstein.uucp!dwilson
Subject: Observation on the hailstone problem
Posted: 6 Dec 88 22:13:21 GMT
Organization: Computervision Div., Prime Computer Inc., Bedford, MA
 
 
 
	Recently, I posted an article about an observation I made
	concerning the hailstone problem, which is as yet unsolved.
	I am surprised that no one replied to it, and so I thought
	that maybe my presentation was bad.  So I am going to repost
	my result, and I hope that someone will tell me whether my
	result is original or old hat.
 
		-------------<>-------------
 
	I am sure that most of you are familiar with the as-yet unsolved
	hailstone problem.  The problem involves the following function,
	whose domain and range are the set of positive integers.
 
		h(x) =	3*x+1,	if x is odd
			x/2,	if x is even
 
	It is conjectured that if h is iterated on any positive integer
	value x, that the value 1 will eventually be reached.  For
	instance, iterating h on the value 7 leads to the sequence
 
		7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5,
		16, 8, 4, 2, 1
 
	Once 1 is reached, the sequence continues
 
		1, 4, 2, 1, 4, 2, 1, 4, 2, 1, ...
 
	ad infinitum.
 
	The possible behaviors of the iteration sequence of h on a given
	positive integer x are:
 
		(1).  A sequence which eventually cycles through
		the values 1, 4, 2.
 
		(2).  A sequence which eventually cycles through
		some set of values not containing 1.
 
		(3).  A sequence which never becomes cyclic, with
		values tending towards infinity.
 
	(1) is the only behavior that has ever been observed for any
	positive integer tested, and the hailstone conjecture asserts
	that this is the only behavior that will ever be observed on
	any positive integer.
 
		-------------<>-------------
 
	In the sequence above, h is called a total of 16 times on 7
	before 1 is reached.  Of these 16 calls to h, 5 calls were on
	odd numbers (and thus amounted to 3*x+1) and 11 were on even
	numbers (and thus amounted to x/2).  If we let a(x) = 3*x+1,
	and b(x) = x/2, we can shorthand the above observation to
 
		levh(7) = 16		[I corrected a typo here - Dan]
		leva(7) = 5
		levb(7) = 11
 
	If the hailstone conjecture is true, then for every positive
	integer x, levh(x), leva(x) and levb(x) are all defined, and
 
		levh(x) = leva(x)+levb(x)
 
	If the hailstone conjecture is false, then levh(x), leva(x)
	and levb(x) will be undefined for those positive integer values
	of x exhibiting behaviors (2) or (3).
 
	Now, for integer z >= 0, let
 
		LEVH(z) = { x | levh(x) = z }
		LEVA(z) = { x | leva(x) = z }
		LEVB(z) = { x | levb(x) = z }
 
	For instance, 7 is in LEVH(16), LEVA(5), and LEVB(11).
 
	If the hailstone conjecture is true, then Sets of the form
	LEVH(z) for z >= 0 are pairwise disjoint and form a partition
	of the positive integers.  The same is true for sets of the
	form LEVA(z) and LEVB(z).
 
	Further, it can be shown that every set of the form LEVH(z) or
	LEVB(z) is finite.  However, every set of the form LEVA(z) is
	infinite.  For instance, LEVA(0) is the set of nonnegative
	integer powers of 2.
 
		-------------<>-------------
 
	The discovery that I have made is the following: 
 
	For any z >= 0, let STRA(z) be the set of base-2 representations
	of integers in LEVA(z).  For instance,
 
		LEVA(0) = { 1, 2, 4, 8, 16, 32, ... }
 
	so
 
		STRA(0) = { "1", "10", "100", "1000", 10000", ... }
 
	Clearly, STRA(0) considered as a language is just the set of
	strings denoted by the regular expression 10*, and is hence a
	regular language.  I have been able to prove that not only is
	STRA(0) a regular language, but STRA(z) for any z >= 0 is a
	regular language.  This result would be a trivial observation
	for STRH(z) or STRB(z), because these sets are finite and
	so trivially regular.  However, STRB(z) is infinite, so the
	characterization of STRB(z) as a regular language has some
	important number theoretical implications for LEVB(z).
 
	For instance, suppose we wish to know, for a given integer x,
	whether the 3*x+1 portion of the hailstone function is called
	more than 100 times before 1 is reached.  My result says that
	there is an algorithm (i.e., feeding the base 2 representation
	of x into a finite automaton) that can answer this question
	in log(x) time (and with an impressively small constant factor
	to boot).
 
	Since each LEVA(z) can be described by a finite automaton, it
	seems reasonable that analyzing the structure of these finite
	automata might yield information that could help in solving the
	hailstone conjecture.
 
 
dwilson@aecmail.prime.com	Disclaimer
David W. Wilson			"You can't have opinions about the truth."
Prime Computer			- Schikele
Bedford MA

     In my title to .-1 I asked about what was meant in reply .1.
     Specifically,
     
> It's fairly easy to find expressions to describe all those numbers that reduce
> to one in 1 step, in 2 steps, in 3 steps,... (where a step is "multiply by 3,
> add 1, remove all factors of two").
     
     Was this a reference to a result as specific as in .-1 about
     the set of base two representations of the elements of an
     infinite set being regular?
     
     Dan

    I tried this approach MANY years ago, ... when this problem was young!
    It doesn't seem to help prove the conjecture, but it does help the
    performance of algorithms that calculate the 'hailstorm' function.
    I doubt that this is a new result.

   I read this note during the Xmas holiday, and found it fascinating. Not 
   being a mathematician, I cant contribute anything deep, but I played 
   around on a spreadsheet, which is a convenient way to calculate and display 
   sequences without any programming. Some thoughts occurred to me.
   
   The 3*N+1 operation on an odd number always produces an even no, and 
   so is always followed by N/2. A more basic operation on odd numbers is 
   1.5*N + 0.5, ie (3*N+1)/2. Call this operation U, ie up, and call 
   dividing an even number by 2, D, for down.
   
   U and D are "complete" in that each can produce either an even or an odd 
   number, and hence can be followed by either type of operation. They are 
   symmetrical, because if applied to all the integers, D to even and U to 
   odd, they produce an equal number of odd and even numbers. 

   Being that it is easy to set up a spreadsheet to perform U and D, and 
   display the resulting sequences, I did this with various starting numbers
   and confirmed that the sequences always ended with 1, 2, 1, 2...  In fact,
   intuitively it would seem that in a hailstorm sequence, U's and D's would
   occur more or less equally, and so it would be unlikely that the sequence
   would grow to infinity - after all, numbers increase by a factor of (more
   or less) 1.5, but decrease by a factor of 2 - surely this will eventually
   produce a reducing sequence! 

   Then it occurred to me U is really multiplying by 1.5 and rounding up. What
   would be the effect of multiplying by a different factor and rounding up?
   Or rounding correctly, or truncating? My guess would have been that any
   factor less than 2 would eventually produce terminating hailstorms. I tried
   factors of 1.5, 1.6, 1.7, 1.8, and 1.9, with a range of starting numbers
   for rounding up, rounding and truncating, and got the following: 

   The hailstorms all seem to terminate, sometimes in big loops, for all cases 
   except rounding up with a factor of 1.6. For this case, for all starting
   values, the sequences seem to grow indefinitely - certainly they quickly 
   get out of range of the spreadsheet. 

   For other cases, I tested with odd starting values to 999, then arbitrary
   values, eg 1234567. Many sequences produced numbers out of range for the
   spreadsheet, but for all of them, I could find large numbers which were in
   range and which terminated. This is a summary for the different types of 
   rounding and the various factors: 

   Round Up: 
     1.5, 1.7, 1.8, 1.9 - All tested sequences terminate 
     1.6 - All tested sequences grow beyond range
             
   Round and truncate were similar:
     1.5, 1.6, 1.7 - All tested sequences terminate
     1.8 - Sequences quickly get out of range even with low starting 
             values like 47 and 51. However, 1234589 terminates for round, and 
             34587 for truncate
     1.9 - Similar to 1.8, but takes longer to get out of range. 1234567 
             terminates for round and 789013 for truncate
          

   Interesting. Does it mean anything?

   Martin.

   Could you also try 11/10, 6/5, 13/10, and 7/5?  I think some statistics on
   the number of Ups, Downs, Terminations, and Explosions may be interesting.

.25> except rounding up with a factor of 1.6. For this case, for all starting.

     I'd like to know if (where) there's a difference between 1.6 and 1.618

  John

    
    I would imagine that most people, after working on this problem for
    awhile, believe even without the as-of-yet-elusive proof, that it IS
    TRUE that all numbers lead to 1.
    
    Let's pretend it's been proven.  Are there any interesting things one
    can then prove by using this as a lemma ?
    
    For example, can we prove Fermat's margin theorem (the one he wrote in
    the margin) somehow by using this as a lemma ?
    
    /Eric

I suspect that a proof would likely be extensible to the companion 5n+1,
7n+1, ... problems, so we would probably gain in smarts by generalization.
Of course, none of this stuff has any immediate practical application, but 
so what? 30 years ago, who would have thought that prime number theory 
would have the impact it now has on computer security issues?

Lynn 

    I have found a fantastic solution for the 3n+1 problem, but this
    editor buffer is too small to contain the solution
                                            
     --naser  
                                  :-)

    Proof by enumeration, eh?

    How did You Know ?
                                          
                         :-)

Because some of you refer to the binary representation of the numbers, it
reminded me of Post-algorithms. Don't remember much of it but they generate
the same sort of problems. Example: take any string of 0' and 1's (NOT
throwing away leftmost 0's!); if the first (leftmost) digit is 0, then
append 00 at the right else append 1101 at the right; in both cases,
remove the 3 digits at the left. Same sort of problem, some strings are cyclic,
some end up as 0 or 1, some just grow (indefinetly?). For starting strings, only
multiples of 100 are choosen (others have of course the same results).
I forgot any theory about Post-algorithms but if there is any, it might be
applicable to this 3n+1 problem
                                                                Hans.

To make things more clear in .33, here are some examples:

0=100
1=1101
2=11101
3=011101
4=10100
5=001101
6=10100
Cycle=2

0=100100
1=1001101
2=11011101
3=111011101
4=0111011101
5=101110100
6=1101001101
7=10011011101
8=110111011101
9=1110111011101
10=01110111011101
11=1011101110100
12=11011101001101
13=111010011011101
14=0100110111011101
15=011011101110100
16=01110111010000
17=1011101000000
18=11010000001101
19=100000011011101
20=0000110111011101
21=011011101110100
Cycle=6

0=100100100
1=1001001101
2=10011011101
3=110111011101
4=1110111011101
5=01110111011101
6=1011101110100
7=11011101001101
8=111010011011101
9=0100110111011101
10=011011101110100
11=01110111010000
12=1011101000000
13=11010000001101
14=100000011011101
15=0000110111011101
16=011011101110100
Cycle=6

0=100100100100
1=1001001001101
2=10010011011101
3=100110111011101
4=1101110111011101
5=11101110111011101
6=011101110111011101
7=10111011101110100
8=110111011101001101
9=1110111010011011101
10=01110100110111011101
11=1010011011101110100
12=00110111011101001101
13=1011101110100110100
14=11011101001101001101
15=111010011010011011101
16=0100110100110111011101
17=011010011011101110100
18=01001101110111010000
19=0110111011101000000
20=011101110100000000
21=10111010000000000
22=110100000000001101
23=1000000000011011101
24=00000000110111011101
25=0000011011101110100
26=001101110111010000
27=10111011101000000
28=110111010000001101
29=1110100000011011101
30=01000000110111011101
31=0000011011101110100
Cycle=6

0=100100100100100
1=1001001001001101
2=10010010011011101
3=100100110111011101
4=1001101110111011101
5=11011101110111011101
6=111011101110111011101
7=0111011101110111011101
8=101110111011101110100
9=1101110111011101001101
10=11101110111010011011101
11=011101110100110111011101
12=10111010011011101110100
13=110100110111011101001101
14=1001101110111010011011101
15=11011101110100110111011101
16=111011101001101110111011101
17=0111010011011101110111011101
18=101001101110111011101110100
19=0011011101110111011101001101
20=101110111011101110100110100
21=1101110111011101001101001101
22=11101110111010011010011011101
.
.
.
390=10100000000000000
391=000000000000001101
392=00000000000110100
393=0000000011010000
394=000001101000000
395=00110100000000
396=1010000000000
397=00000000001101
398=0000000110100
400=01101000000
401=0100000000
402=000000000
403=00000000
404=0000000
405=000000
406=00000
407=0000
408=000
409=00
Stop

We may be able to get some insight into the root behavior of the [3n+1,n/2]
sequences by looking at some other related sequences and treating 3n+1 as a 
special case.

For example, the [5n+1,n/2] sequences are not so predictable. While many
fall into the loop {1,6,3,16,8,4,2,1...} others do not: there is for
example {13,66,33,166,83,416,208,104,52,26,13...}. This suggests that the
fact that all the 3n+1 sequences apparently settle into {1,4,2,1...} is due
to 3 being a small multiplier so fewer possibilities for loops exist. I
conjecture that the larger the multipier the more different loops exist.
Studying the patterns of different loops for large multipliers may give
some insight into the original case. 

Lynn Yarbrough 

On the other hand, starting with n = 9, [5n+1,n/2] exhausts the capacity 
of VAX integers pretty quickly after 66 applications of the rules. Does 
this one eventually settle down?

Lynn 

re .36:

>On the other hand, starting with n = 9, [5n+1,n/2] exhausts the capacity 
>of VAX integers pretty quickly after 66 applications of the rules. Does 
>this one eventually settle down?

I would say no.  Since the result of 3n+1 and 5n+1 operations are always even,
the step immediately following always halves the number, both sequences can be
modified by changing the 'odd' rule to n+(n+1)/2 and 2n+(n+1)/2, respectively
without changing the sequence except to skip some of its members.  Notice that
for the 3n+1 case you are halving the number 50% of the time and multiplying it
by approximately 1.5 (i.e. not quite doubling it) half the time.  Therefore, it
"should" settle down.  On the other hand, the 5n+1 sequence halves the number
50% of the time and more than doubles it 50% of the time.  Therefore, it
"should" run away.

-Mike

	A reference from usenet sci.math:

Path: ryn.esg.dec.com!shlump.nac.dec.com!rust.zso.dec.com!bacchus.pa.dec.com!decwrl!sdd.hp.com!uakari.primate.wisc.edu!uflorida!mathlab!squash
From: squash@boogie.math.ufl.edu (Jonathan King)
Newsgroups: sci.math
Subject: 3N+1 Problem
Message-ID: <SQUASH.90Sep5190127@boogie.math.ufl.edu>
Date: 5 Sep 90 23:01:27 GMT
Sender: news@mathlab.math.ufl.EDU
Distribution: sci.math
Organization: University of Florida Mathematics Computing Laboratory
Lines: 21
FCC: ~/outgoing.mail
 
I am looking for references.
 
The "3N+1" problem goes by several names.  Define a self-map f() on the
set of positive integers by:  
  f(n) = n/2		if n is even;
  f(n) = 3n+1		if n is odd.
 
The, last-I-heard-still-open question is: For every starting value n,
is there an iterate f(f(...f(n)...)) which equals 1; is the "basin of
attraction" of the orbit  1 -> 4 -> 2 -> 1  all of the space?
 
 
I am looking for as-complete-as-possible bibliographic references on
this problem.  I would like to find almost every article ever written
on this problem in English and French.  
  Does any know of an article on this with an extensive bibliography?
--then I can, in Paul Halmos' words, "iterate the bibliography
operator".
 
				Thank you.
Jonathan

	*****	*****	*****	*****	*****	*****	*****	*****

Path: ryn.esg.dec.com!shlump.nac.dec.com!rust.zso.dec.com!bacchus.pa.dec.com!decwrl!wuarchive!cs.utexas.edu!tut.cis.ohio-state.edu!bgsuvax!steiner
From: steiner@bgsuvax.UUCP (Ray Steiner)
Newsgroups: sci.math
Subject: Re: 3N+1 Problem
Summary: Excellent expository article in AMM.
Message-ID: <6218@bgsuvax.UUCP>
Date: 6 Sep 90 14:01:48 GMT
References: <SQUASH.90Sep5190127@boogie.math.ufl.edu>
Distribution: sci.math
Organization: Bowling Green State University B.G., Oh.
Lines: 8
 
See the excellent article by Jeff Lagarias in the
January, 1985 issue of the AMERICAN MATHEMATICAL
MONTHLY.  He has a fine expository article on the
problem and nearly everything done on it up to that
time.
Ray Steiner
-- 
steiner@andy.bgsu.edu

	*****	*****	*****	*****	*****	*****	*****	*****

Path: ryn.esg.dec.com!shlump.nac.dec.com!lemans.dec.com!decuac!haven!udel!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!uflorida!mathlab!mathlab.math.ufl.edu!squash
From: squash@math.ufl.edu (Jonathan King)
Newsgroups: sci.math
Subject: Re: 3N+1 Problem, article reference
Message-ID: <SQUASH.90Sep7140726@boogie.math.ufl.edu>
Date: 7 Sep 90 18:07:26 GMT
References: <SQUASH.90Sep5190127@boogie.math.ufl.edu>
Sender: root@mathlab.math.ufl.EDU
Distribution: sci.math
Organization: University of Florida Department of Mathematics
Lines: 11
Cc: robby@MATH.ORST.EDU guogang@iro.umontreal.ca mfb@super.org hoey@AIC.NRL.Navy.Mil lambert@cwi.nl MITCHELL@ACODKRIS jrs@math.lsa.umich.edu flajolet@margaux.inria.fr squash
 
Thank you to all whom replied for my request of an extensive
bibliography on the 3N+1 problem.   The reference suggested by nearly
everyone is:
 
  J.C. Lagarias, ``The $3x+1$ problem and its generalizations,''
  {\em Amer. Math. Monthly,} 92 (1985) 3-23.
 
If I find articles not in the bibliography tree under this one, I will
post the references.
				Thanks again to all.
JK/jk

Path: ryn.esg.dec.com!shlump.nac.dec.com!bacchus.pa.dec.com!decwrl!uunet!sco!elil
From: elil@sco.COM (Eli Liang)
Newsgroups: sci.math
Subject: Re: 3N+1 Problem
Message-ID: <7763@scolex.sco.COM>
Date: 10 Sep 90 22:36:03 GMT
References: <SQUASH.90Sep5190127@boogie.math.ufl.edu>
Sender: news@sco.COM
Distribution: sci.math
Organization: The Santa Cruz Operation, Inc.
Lines: 56
 
 
In article <SQUASH.90Sep5190127@boogie.math.ufl.edu> squash@boogie.math.ufl.edu
(Jonathan King) writes:
[quote from previous article deleted -- Dan]
 
Besides the previously mentioned bibliographical article of Lagarias,
Amador Muriel of Switz., among others, has been doing a lot of current research
into the Collatz problem.  He has some new results in the further application
of ergodic theory to the behavior of the iterates of the function.  He probably
has a more current list of articles than is in Lagarias.  Since, you
mentioned French, I should mention that his research is being funded
by a French Government agency.
 
Send me email if you would like his mailing address which I have.
 
I believe that currently, the largest prize for a solution of this problem
is much larger than the 1000 pounds which Thwaites offered for a proof in 1982.
 
If your intention is to `iterate the bibliography operator' with a proof, you
should realize that almost 20 years ago Conway proved that a simple
generalization of the problem is algorithmically undecidable.
 
If, in your searches through references, you find Thompsons "proof"(?) for
the Finite Cycle Conjecture, please let me know.  I would be very interested
in reading it.  I suspect however that either his proof is flawed or that
reports of a proof were much exagerated.
 
-eli
 
---------------------------------------------------------------------------
Eli Liang	-- Senior Systems Engineer; OS-EFS Project Manager
 
US MAIL: Systems Engineering; Kernel Group	EMAIL: ...!uunet!sco!elil
	 The Santa Cruz Operation, Inc.		       elil@sco.COM
	 400 Encinal Street			FAX:   408-458-0811
	 P.O. Box 1900				TWX:   910-598-4510 SCO SACZ
	 Santa Cruz, CA  95061

MAPLE and Mathematica algorithms for studying this problem are now 
available, if anyone is interested. The Mathematica version is given in 
"Computational Recreations in Mathematica" by Vardi (Publ. Addison-Wesley); 
the MAPLE version is available through the MAPLE Users' Group share library 
(see the MAPLE conference note 90.29 for details).

I just joined Digital and was reading through the notes. I worked on this
problem before with no luck (of course).
Somebody suggested that the sequence of numbers generated can be traced
backward; i.e., start from 1 then 2, 4, 8, 16 then branch at 16 etc. Is there
a proof that a number can be reached from 1 via a unique path? In other words,
do we have a tree rooted at 1? I remember (but I need to go back to my notes)
that the non-cycling behavior was hard to prove.
-Samer
[Posted by WWW Notes gateway]