Talk:Collatz conjecture

Bottom-up Collatz Graph Section

I have several objections to this section:

<quote>

There is another approach to prove the following conjecture, which considers the bottom-up method of growing Collatz graph. Collatz graph is defined by an inverse function,

$f(n)=\{2n\}$ if $n\equiv 0{\pmod {3}}$

$f(n)=\{2n,(2n-1)/3\}$ if $n\equiv {-1,1}){\pmod {3}}$

Thus looking from this perspective, we have the problem redefined in the following way. The Collatz conjecture states,

• The inverse function forms a tree except for the 1-2 loop.
• All integers are present in the tree.

</quote>

First of all, it is wrong. It should be

$f(n)=\{2n\}$ if $n\equiv {0,1}{\pmod {3}}$

$f(n)=\{2n,(2n-1)/3\}$ if $n\equiv {-1}{\pmod {3}}$

If n=7 then the original rule would have 7 branch to 14 and 13/3 which is not an integer and thus, invalid. The second rule is invoked ONLY when n == 2 (mod 3). Or -1 if you prefer.

Second, it is implied, but not specifically stated, that the rules that are being inverted are not the same as given in the top of the article. This inverse tree modifies the odd number rule to be (3n+1)/2. This modification changes the sequence to

3 -> 5 -> 8 -> 4 -> 2 -> 1 -> 2 -> 1 ...

Whereas the sequence under the original 3x+1 rule is

3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 ...

From the modified rule, you get a "V" tree:

 32 10 3
 |  | /
 |  |/
 16 5
 | /
 |/
 8
 |
 |
 4  [1]
 | /
 |/
 2
 |
 |
 [1]

The original rule produces an "inverted L" tree:

 32 10__3
 |  |
 |  |
 16_5
 |
 |
 8
 |
 |
 4__[1]
 |
 |
 2
 |
 |
 [1]

Generating an "inverted L" tree is a bit trickier, but the rules would be

$f(n)=\{2n\}$ if $n\equiv {0,1,2,3,5}{\pmod {6}}$

$f(n)=\{2n,(n-1)/3\}$ if $n\equiv {4}{\pmod {6}}$

Lastly, why is the 1-2 loop not considered part of the tree? And when saying that all numbers are on "the tree", I think it should be specifically pointed out that the conjecture being true implies that there is only one tree. The reason is that there are other systems, such as 3x+5 or 3x+1 with negative numbers, in which case there is more than one tree (and thus the conjecture fails for such systems).

--Mensanator 21:47, 3 Feb 2005 (UTC)

---

Where is a proof? -- Taku 03:13, Mar 23, 2005 (UTC)

---

Proof of what? What are you asking about? Proof that the bottom-up method described is wrong? Proof that other systems fail the conjecture? I'll be happy to back up my claims if you tell me what you object to.

--Mensanator 23:27, 25 Mar 2005 (UTC)

Well, by a proof I meant a proof of this conjecture. But sorry, I missed this in the article: "The conjecture has been checked by computer for all start values up to 3 × 2⁵³ = 27,021,597,764,222,976, but a proof of the conjecture has not been found." -- Taku 00:25, Mar 26, 2005 (UTC)

Would somebody double check the recent anon changes?

Thanks. Oleg Alexandrov 23:48, 30 Mar 2005 (UTC)

I'm going through this article slowly; so far I've added a stub article about Collatz and added a clear statement of the conjecture itself; also I've made the unproven status of the conjecture clearer (responding to the fact that Taku was able to be confused). I'll be double checking everything, so I imagine I will be checking the anon changes. ACW 18:55, 12 May 2005 (UTC)

Rewrite pass

As I mentioned in the last item, I've started a fairly careful rewrite pass, trying to tighten and clarify, and check for accuracy. I don't know exactly how long it'll take; of course anybody is free to help. I've gotten up through the "Examples" section so far. My most major change is to merge the first two sections; the distinction between the "halting" and "non-halting" formulation seemed not worth the trouble to maintain, and could easily confuse the reader.

I mostly decided to use the "non-halting" formulation; the conjecture states that each sequence reaches 1, and doesn't say anything about halting there. This formulation is more amenable to formal rigor, since you can say a[i] = f(a[i-i]) for all i > 1 (and not have to jump through hoops to forbid extension past the first occurrence of 1).

I also adopted a style in which I state things in informal English, followed by a rigorous formula. The non-expert can read just the informal descriptions, and not miss anything. Please read what I've got so far and see what you think. I'd love in particular to hear from Taku to see if it's now clearer that the conjecture is unsettled.

ACW 18:49, 14 May 2005 (UTC)

I am strongly tempted to remove the two sections, "Other ways of looking at it" and "Optimizations". A reader who has read down to this point now knows everything about the conjecture that a non-specialist could be expected to know. A reader who is tempted to actually try to solve the problem has been given the basics, and can now be directed to the masterful summary by Lagarias. Somebody should convince me that we need to do more here. "Other ways of looking at it" discusses a small handful of the isomorphism-based approaches that have been tried; "optimizations" might help you make a program for computing Collatz sequences run faster. Both topics are treated with more care in Lagarias.

Without these two sections, the article will be clear, tight, and to the point. With them, it trails off into vague observations of questionable value. Is there any real objection to cutting them? ACW 20:04, 18 May 2005 (UTC)

review/shortening of the entry

Hi -

just stepped in and nearly was to add some contributions - now that discussion says me, that this would be obsolete.

Few comments to the arguments above:

- the Lagarias-article is a deep resource. But for me, as an amateur, it was difficult to understand more than a handful of arguments. If you think of reducing topics like "optimizations" and "other views", then you should at least mention the article of Peter Schorer(*1), which is also concise and deep, but much more readable for a beginner of that subject (Don't forget that especially the Collatz-Problem is a hobby for amateurs).

- There were some definite findings in the Collatz-research, worth to be noted. Those I know are results concerning loops.

Now, why are loops of interest?

a) Finding a loop *disproves* the Collatz-conjecture with one counterexample

b) Proving the non-existence of a loop is half of a proof of the whole conjecture:

   - if no divergent trajectory exists  AND
   - if no loop exist
  then the Collatz-conjecture is settled.

A general loop is still not disproven, but Ray Steiner (1978) and Benne de Weger/John Simons(2000 and 2002) succeeded in disproving certain types of loops (called 1-cycle (Steiner) resp. m-cycle with m=1 to 68 (deWeger/Simons)). The deWeger/Simons-paper was recently online and is possibly still available.

- Reading the above discussion, I think, I better do not involve in that subject myself. But keeping in mind that we have an open question here which attracts many amateurs and has the power to lead them to deeper aspects of number-theory, I'd guessed it a somehow paedagogic aspect to adress accessible subtopics for some cursory num-theory-engaged reader. In my own attempt of the disproof of a 1-cycle-loop I found important connections to the still not completely settled question of bounds of the approximation of m*log(2) to n*log(3) and to the (also not completely solved) waring-problem (see chapter of power-fractions in mathworld.wolfram.com).

But surely - that's a matter of the preferences of a wikipedia and of the intentions of the project-team, where I could not involve myself due to lack of time and intensity.

Kind regards (and thanks for your engagement anyway) -

Gottfried Helms

(*1) In his online-article he even announces a (small) price for some findings. (Don't have the url available at the moment)

--Gottfried 20:06, 1 Jun 2005 (UTC)

The recent work is interesting to me ... I can't think of any reason not to add a link to the Schorer work: please do!

It's a difficult question of policy how much information to put here. I have not yet looked at the page on the Four-Color Theorem, but I would wager that it does not contain a proof! My feeling is that we should provide elementary information, enough for readers to decide whether they are interested, and then appropriate links to the outside world. Wikipedia is not the Internet. Lagarias, Schorer, Erik Weisstein ... that would probably be enough.

ACW 03:33, 2 Jun 2005 (UTC)

Would it be appropriate to balance the "evidence" by pointing out that evidence is not proof? Say, by adding a link to The Law of Small Numbers showing that no matter how many numbers are tested, it will never be enough. And speaking of loops, the "probablistic evidence" falls apart when loop sequences are encountered.

As far as having too much, I don't think there's a problem there. Look up something silly like Andre The Giant. Stupid articles ramble on endlessly. I am in favor of cutting The Abstract Machine because it is terse to the point of being wrong and its author won't budge on that issue. He should make a seperate article where he has the space to give it a proper treatment and then link to it. Otherwise, lose it.

--64.144.30.11 00:50, 16 July 2005 (UTC)

Review/ add. links

The site of P.Schorer is http://www.occampress.com it contains several articles; the introductory is: http://www.occampress.com/intro.pdf

I'm a bit surprised: today I find it not so readable as I recalled from my last visit (about 2003) - maybe it is due to new versions and more abstraction, but he is linked in many pages.

[No: the reason you didn't find it as readable was because you were linked to the paper containing all proofs, instead of to the introductory paper. The above is now the correct link. (Actually, the introductory paper consists of two files. I have linked to the first.) -- Peter Schorer, 8/11/05]

The B. de Weger-article about the loops ("m-cycles") is in http://www.win.tue.nl/~bdeweger/3n+1_v1.33.pdf

The Steiner-article of 1978, which was the first proof in the study of loops (to prove or disprove), disproving the most simple type, called "1-cycle", has never been online, but is referred by the de Weger/Simons - article.

Pls excuse I didn't place the links directly to the right place in the wiki-article: I don't want to possibly damage its html.

Regards -

Gottfried

Gottfried: I was going to do this, but then I had second thoughts. You should do it. You found the references. Don't worry about messing up the wiki. If you mess it up, somebody will fix it. You should just jump in and do it without fear! ACW 00:11, 4 Jun 2005 (UTC)

Ways for the conjecture to be false

I don't think it's possible for it to fall into a loop that excludes 1. For that to happen, $(3x+1)/2^{n}$ would have to equal x, where x is a number in the loop. n = 1 and n >= 3 are obviously not possible if x is a positive integer, so n must equal 2. If $(3x+1)/2^{2}$ equals x, then x must equal 1, so the only possible loop contains 1. --Bart133 (t) 15:12, 25 August 2005 (UTC)

Why do you think "x: (3x+1)/2ⁿ = x" is required for a loop that excludes 1? Isn't the whole point that n/2 and 3n+1 operations are interleaved, seemingly at random? --noösfractal 17:25, 25 August 2005 (UTC)

Bart133: Your reasoning doesn't cover the cases where a loop contains more than one $3x+1$-step. I think you have successfully proven that the 4-2-1 loop is the only one with exactly one tripling step. ACW 16:04, 27 August 2005 (UTC)

Unless you also include the negative integer domain. Here you will find the sequence -1 -2 -1 which also contains exactly one tripling loop. All issues of structure based on patterns of halving and tripling span the entire integer domain, not just the positive integers. In fact, the conjecture is simply false in the negative integers and is usually not discussed. Nevertheless, to properly understand the patterns, you cannot ignore the negative integers because the math takes you there whether or not you want to go there. Every possible pattern of halving and tripling occurs infinitely many times on the Collatz tree and from those patterns one can derive a formula that determines whether of not said pattern forms a loop. But that loop can be either positive or negative. It would be better to say that $3x+1$ has only one positive loop. And you should leave 1 out of it since in the generalization to $3x+C$ (C a positive odd integer) you'll find that the sequence [3x+C][x/2][x/2] always loops at C, not 1. Of course, the conjecture is provably false for any C not a power of 3, but if one is actually interested in learning "ways for the conjecture to be false" then $3x+C$ can be a useful study. --Mensanator 20:49, 3 September 2005 (UTC)

Mensanator: In this case I think we should cut Bart133 some slack, since he did specify "positive" when he stated what he was trying to prove.

Now, continuing just for fun down the path you mention: it turns out that some patterns of halving and tripling can only occur in loops if you generalize to rational numbers. Here, you have to regard a fraction as being even if its numerator is even, and odd if the numerator is odd. So, for example, 1/5 -> 8/5 -> 4/5 -> 2/5 -> 1/5, thus realizing the pattern THHH. Ah, you are actually getting the same generalization by replacing 1 with C above. Excellent. ACW 23:57, 3 September 2005 (UTC)

Sure, Bart133 can have all the slack he needs. I was just trying to point out that things are sometimes clearer when you look at the whole picture. The loop function I refered to is (Z*C)/(X-Y) where X is a power of 2 (and is the number of halving steps) and Y a power of 3 (the number of tripling steps). The sequence is trivially an integer (and thus a loop) if X-Y is 1 or -1. Now the only places where a power of 2 differs from a power of 3 by 1 are {2,3}, {4,3} and {8,9} which give you loops at -1, +1 and -5. If you restricted your research to positive integers, you may not ever discover that interesting bit. Any additional loops would be non-trivial. But it would be wrong to think that there are no non-trivial loops in $3x+1$. A non-trivial loop exists at -17. Sure it's negative, but the very fact it exists means we can't conclude that non-trivial loops are impossible.--Mensanator 01:22, 4 September 2005 (UTC)

dcorradini_argentina

Algoritmo de Syracuse _ Demostración 05/02/06

Terminología:

Impar: x

Par: y

Nº: Números naturales positivos

Impar: 2n-1

Par: 2n

A) Primero quiero demostrar que la ecuación 3x+1 da como resultado siempre un Nº par.

• 3 x + 1 = y = 2n • 3(2n-1)+1 • 6n – 2

• 2 (3n-1) (tiene la forma 2 n, por lo tanto es par para cualquier Nº Natural positivo)

B) Segundo quiero demostrar que la ecuación 3x+1 es una sucesión convergente al Nº 4, tenemos como surge en A lo siguiente:

2 (3n - 1) =

2 [3n1-1, 3 n2-1, 3 n3-1,…….3nn -1]

   Lim 2     ((3n1-1), (3 n2-1), (3 n3-1),…….(3nn -1)] = 4

N (n1…nn)==> 1

C) Tercero, demuestro que un Nº par que se divide por 2 es una sucesión convergente al Nº 1.

Y = 2n, por las reglas impuestas, tenemos que a todo N° par se lo debe dividir por 2

Y= 2n/2 = [2 (N1, N2, N3……Nn) / 2] = (2/2) (N1/2, N2/2, N3/2, ……Nn/2)

   Lim.       (2/2) (N1/2, N2/2, N3/2, ……Nn/2) = 1

N (n1 …nn) ==> 2

Complementando a esto, tenemos el siguiente teorema, que se desprende de las propiedad de los números naturales=

[ (2n1/2) < (2n2/2) < (2n3/2) < ……..< (2nn/2) ]

Por lo tanto tenemos que la sucesión de cualquier N° Natural positivo, donde se aplique las dos reglas del algoritmo de Syracuse/Collatz, siempre que sea un N° positivo so obtendra un N° par y todo N° par se dividira por 2, llegando siempre al N° 1 (después de sucesivas factorizaciones del N° par), a partir de este momento se repite el ciclo por la ecuación 3x+1.

Diego Corradini Buenos Aires Argentina

Obtenido de "http://es.wikipedia.org/wiki/Usuario:Dcorradini"

I was wondering if somebody could add some research paths that people have taken to try to prove it. --yoshi 19:04, 17 February 2006 (UTC)

Why did you post the Spanish version here when you have an English translation at "http://es.wikipedia.org/wiki/Usuario:Dcorradini"?

And speaking of translating, even I know better than to use "Y" as a variable if I'm translating Spanish to English (you might want to go patch up your translated equations).

As to content, is that supposed to be some kind of proof? Aren't you using circular logic? Don't the convergences you speak of assume the conjecture is true? Try the convergences in the negative numbers, specifically, -17. Don't work, do they? You are assuming, without proof, that there are no non-trivial loops in the positive integers. Don't you need to prove that before you can trot out the convergences?

Or did I not understand what you're saying (quite possible since I don't speak Spanish and am relying on the dubious translation). --Mensanator 05:59, 22 February 2006 (UTC)

La demostración esta dada para numeros naturales, no enteros, es decir mayor a cero. en el link de wikipedia vas a encontrar las formulas mejor expresadas, y por cierto no tomo que la conjetura es verdadera, en cambio SI surge que es verdadera por la demostración.-

Saludos cordiales

Diego

Syracuse funcion?

It is not clear what is the relation between syracuse function/conjecture and the collatz conjecture.--Pokipsy76 09:34, 1 March 2006 (UTC)

The problem of Syracusa or Conjecture of Collatz (he/she also has other names) it is the same thing: 3x+1

Greetings

Diego

Re: Syracuse conjecture concerns only odd numbers, so Syracuse function f is the main tool for the Syracuse conjecture, it is the same as the function f defined in [[1]],To prove the Syracuse Conjecture, is to show that for all k ∈ I , there exists an integer n ≥ 1 such that : f ⁿ(k) = 1.

greetings

Samiciel

Just looked at your link and I have one question: have you tried making the graph G using negative integers? You say that

The only possibilities for this would be that a cycle exists somewhere in the tree and forms a "whirlpool" which integers cannot leave.

but if you look at -17, you will find just such a "whirlpool". Yes, it's in the negative domain instead of the positive, but the underlying cause of such "whirlpools" is independent of the domain. So there is nothing preventing such a "whirlpool" from occuring in the positive domain.

The fact that integers are determined by their leaving connection, which is oriented toward 1, seems to provide an argument against the existence of such cycles.

The argument is false. The "whirpool" at -17 is the counter-example.

--Mensanator 08:44, 9 March 2006 (UTC)

Sequences in the Collatz 3x+1 problem

moved:

---

It has been shown that a binary tree can be used to find infinite sequences of numbers that definitely satisfy the Collatz conjecture ([2] Sequences in the Collatz 3x+1 problem).

---

Original reasearch violates Wikipedia's rules.

And there is a reason for this: the paper is flawed.

 Program 2.1 (edited to show entire tree on one line)
 
 zack's 'tree' (Program 2.1)
 
 [1]
 [2]
 [4]
 [1, 8]
 [2, 16]
 [4, 5, 32]
 [1, 8, 1, 10, 64]
 [2, 16, 2, 3, 20, 21, 128]
 [4, 5, 32, 4, 6, 40, 42, 256]
 [1, 8, 1, 10, 64, 1, 8, 1, 12, 13, 80, 13, 84, 85, 512]
 [2, 16, 2, 3, 20, 21, 128, 2, 16, 2, 3, 24, 26, 160, 26, 27, 168, 170, 1024]

Whoa, dude, you got a serious problem. What's with all the repeated values? Why do I see 27 on the 11th level? Because in this line,

 if (old_tree[n]-1)/3 % 2 == 1:

you didn't check to see if (old_tree[n]-1)/3 is an integer! For 84, it's not, so you should NOT append 27 to your tree at this point.

And why the infinite recursion? There's no need for that, but I won't quibble about that absurdity.

Here is the proper way to generate the binary tree:

 def numerical_tree(tree):
 	print tree
 	old_tree = tree
 	tree = []
         # zack's algorithm
 #	for n in range(len(old_tree)):
 #		print old_tree[n],
 #		if (old_tree[n]-1)/3 % 2 == 1:
 #			tree.append((old_tree[n]-1)/3)
 #		tree.append(old_tree[n]*2)
 #
 #       the proper way to do it
 #
 	for n in range(len(old_tree)):
 		tree.append(old_tree[n]*2)
 		if (old_tree[n] != 4) and (old_tree[n] % 6 == 4):
 #                       # an odd number can't spawn a new branch
 #                       # old_tree[n] % 6 == 4 ensures that only
 #                       # even numbers divisible by 3 after subtracting 1
 #                       # spawn new branches of the binary tree
 			tree.append((old_tree[n]-1)/3)
 	numerical_tree(tree)
 numerical_tree([1])

My tree, formated to show proper binary relationship

 [1]
 [2]
 [4]
 [8]
 [16]
 [32,                         5]
 [64,                        10]
 [128,                  21,  20,                3]
 [256,                  42,  40,                6]
 [512,        85,       84,  80,       13,     12]
 [1024,      170,      168, 160,       26,     24]
 [2048, 341, 340,      336, 320,  53,  52,     48]
 [4096, 682, 680, 113, 672, 640, 106, 104, 17, 96]

That's as far as I got in your paper, but I think it's enough to disqualify its inclusion in the Wikipedia. What you should do is fix up that paper so that it actually accomplishes something, submit it to a journal for publication (and don't be surprised when it's rejected), and then you can reference it here.

--Mensanator 00:35, 29 March 2006 (UTC)

---

"you didn't check to see if (old_tree[n]-1)/3 is an integer! For 84, it's not, so you should NOT append 27 to your tree at this point."

(84-1)/3 % 2 != 1. 27 comes from (82-1)/3. There are going to be repeated values. This simple algorithm is not the focus of the paper; it's just an example from which the paper branches. Don't worry and just keep reading.

---

Why do you think the 27 comes from 82? There's no 82 in the previous tree. If you line up the numbers, you'll see that 27 is a left child of 84.

[1,  8, 1,    10,      64, 1,  8, 1,    12, 13,  80, 13,      84,  85,  512]
[2, 16, 2, 3, 20, 21, 128, 2, 16, 2, 3, 24, 26, 160, 26, 27, 168, 170, 1024]

Are you aware that Python does integer division? That it simply discards the remainder?

 >>> print (84-1)/3
 27

If you don't know what you're doing, use divmod:

 >>> print divmod(84-1,3)
 (27, 2)

then you can see that your division was invalid.

Look at my tree. There are NOT supposed to be repeated values. You say in your paper

the program actually generates the Collatz tree level by level

But your program doesn't do that, does it? How did you come to the conclusion that Program 2.1 was generating the Collatz tree level by level? Do you acually think numbers appear on the Collatz tree more than once? Is there any point in reading the rest of the paper having demonstrated that a) you don't understand how to program, b) you don't understand the Collatz problem and c) you make no effort at quality control? What do you think an actual peer reviewer would do with your paper?

27, by the way, properly appears on level 112, which cannot be reached by your program even if you take out the silly infinite recursion. If you do it properly and save your trees into text files to prevent running out of memory, you'll find that the files are 3 GB by the time you reach level 84. That's where I stopped because the level files exceeded the capacity of a CD even when zipped.

And why not register with Wikipedia and get a user account. Then you can sign your posts. Right now I'm just talking to an IP address.

--Mensanator 05:42, 29 March 2006 (UTC)

Ok, I read the rest of the paper. Program 4 & 5 basically do the same thing, so I'll only make a distinction when necssary.

First of all, Programs 4 & 5 appear to work better than Program 2 (possibly because they don't use division).

They are, however, incomplete. You state that they "creates and follows a general binary tree". Your programs do NOT create a binary tree. They don't even create any Collatz numbers because you neglected to assign any values to "n" in

 (2**(i+r*n)-a)/3**b

All your programs do is create the parameters a,b,i,r. This can be easily rectified by wrapping a,b,i,r in a for loop once a,b,i,r are calculated:

 for n in range(0,10):
   p = (2**(i+r*n)-a)/3**b
   print 'n: %2d %d' % (n,p)

from which we get:

 1 1 0 2
 n:  0 0
 n:  1 1
 n:  2 5
 n:  3 21
 n:  4 85
 n:  5 341
 n:  6 1365
 n:  7 5461
 n:  8 21845
 n:  9 87381

Oh dear, 1,1,0,2 produces a 0 for n=0 and 0 isn't on the Collatz tree (other a,b,i,r sets give negative numbers). Should I start the n-loop at 1? No, because some a,b,i,r sets require n=0.

Ignoring that, let's look at the numbers actually produced. Plotting the numbers on the Collatz tree:

 a b i r
 1 1 0 2
                             87381-----x
                                       x
                       21845-----------x
                                       x
                  5461-----------------x
                                       x
             1365----------------------x
                                       x
         341---------------------------x
                                       x
      85-------------------------------x
                                       x
   21----------------------------------x
                                       x
 5-------------------------------------x
                                       x
                                       x
                                       x
                                       1

shows that they are all on order 1 branches. But not the entire branch, just the first element. To see the second element, we have to re-calculate a,b,i,r:

 2 1 1 2
 n:  0 0
 n:  1 2
 n:  2 10
 n:  3 42
 n:  4 170
 n:  5 682
 n:  6 2730
 n:  7 10922
 n:  8 43690
 n:  9 174762
 
 a b i r
 2 1 1 2
                                  174762
                                  x------x
                            43690        x
                            x------------x
                      10922              x
                      x------------------x
                 2730                    x
                 x-----------------------x
             682                         x
             x---------------------------x
         170                             x
         x-------------------------------x
     42                                  x
     x-----------------------------------x
 10                                      x
 x---------------------------------------x
                                         x
                                         x
                                         2
                                         x

Uhh...this isn't exactly a binary tree. The numbers created by any given set of a,b,i,r are cousins, not children.

How does it follow from this that EVERY node on the tree is generated? Program 2 (when done correctly) generates every child of every element of a given level. By induction, all nodes are created.

And even if I discount the 0's and negative numbers, there's another problem: duplicates. If you are properly generating a Collatz tree, there won't be any duplicate values. Yet, a=38 b=2 i=1 r=6 n=1 evaluates to

 (2**(1+6*1)-38)/3**2 = (2**7-38)/3**2 = (128-38)/9 = 10

as does a=2 b=1 i=1 r=2 n=1

 (2**(1+2*2)-2)/3**1 = (2**5-2)/3**1 = (32-2)/3 = 10

Furthermore, both a=67 b=2 i=2 r=6 n=1 and a=1 b=1 i=0 r=2 n=3 evaluate to 21. Did you even know this was happening? Do you want to know why?

a=1 b=1 i=0 r=2 n=3 is the "correct" answer. Since b corresponds to the number of 3n+1 steps in a sequence, that set of parameters corresponds to the actual sequence from 21:

 21--64
     32
     16
      8
      4
      2
      1

So where does the other 21 come from?

Note that it has b=2. But also note that (i+r*n) corresponds to the number of n/2 steps in a sequence. If we start at 21 and do 8 even steps and 2 odd steps instead of 6 evens and 1 odd, we get:

 21--64
     32
     16
      8
      4
      2
      1--4
         2
         1

Thus,

 (2**(2+6*1)-67)/3**2

defines the sequence if you MAKE TWO LOOPS AROUND THE ROOT.

Finally, to reach 27 with this "sieve", the b lookup table needs 2*3**40 or 2199023255552 entries. I doubt this will be of any use to push the research limit past 6*2**58.

Oh, and by the way, there's nothing inherrently wrong about the ideas presented in Program 5, I use a similar technique in my own programs. But I don't claim it's something it's not.

--Mensanator 02:34, 31 March 2006 (UTC)

Obvious Optimization

Wouldn't the most obvious optimization be to stop if the current value of the function is less than the original input, since all numbers below the input must have terminated, or the program would have screamed, "i've found a counterexample!"? If so, perhaps it should be added? or was it perhaps considered too obvious to do so?

Hmmm, I thought it was there. I'll check soon, unless somebody else beats me to it. You're right, though: if a starting value has a smaller iterate, the search program should immediately proceed to the next starting value; and if all starting values could be shown to have smaller iterates, the conjecture would be established. ACW 04:48, 23 August 2006 (UTC)

Pseudocode Standard

I used the standard found here: [3] What standard are you referencing? --Mensanator 22:39, 24 August 2006 (UTC)

Probabilistic evidence

The statement "A rebuttal by contradiction would be the number 3 : 3 10 5 16 8 4 2 1" is not a rebuttal because it clearly says average and about. Rolling snake-eyes on a pair of dice does not rebut the claim that the average outcome of a roll of dice is 7.

One can always find an example of a sequence of n consecutive increasing odd numbers simply by starting with a Mesenne Number (2**n-1) or any number having n consecutive 1's at the least significant bit position of the number when represented in binary. But such patterns are not representative of the average.

For a binary number of n bits chosen at random, the distribution of consecutive 1's will be a Negative Binomial, specifically, a Geometric Distribution. In such a distribution, there will be twice as many 1-bit patterns as 2-bit, twice as many 2-bit as 3-bit, twice as many 3-bit as 4-bit, etc. The mean of a Geometric Distribution is the inverse of the probability. Thus, for such a randomly chosen number the mean bit pattern length will be 2 regardless of how large n is. And a mean of 2 consecutive 0's at the least significant bit position implies that the mean number of consecutive n/2 operations will be 2 for every 3n+1 operation resulting in the consecutive odd numbers being about 3/4 on average.

For example 2**177149-1 has 177149 consecutive increasing odd numbers. But the last of those odd numbers has 177149*1.585 bits whose pattern is a Geomtric Distribution (the result of converting 3**177149-1 to base 2) from which point on the sequence will indeed average 3/4. From this relationship we can predict that there will be

   n + (1.585 * n)/0.415     or    4.819 * n

odd numbers, where n is the number of bits in the Mersenne Number.

Therefore, the sequence should have

   4.819*177,149    or    853,681 

odd numbers. It actually has

   854,697

making the prediction accuracy 99.88%.

So the probalistic evidence is still correct despite the sequence beginning with 177149 consecutive increasing odd numbers. --Mensanator 18:14, 26 August 2006 (UTC)

Suppose n is odd. Then 3n+1 is even. With probability 1/2 the next odd number is (3n+1)/2;

So half of all even numbers have a single factor of 2.

with probability 1/4, the next odd number is (3n+1)/4;

So half the remaining even numbers have 2 factors of 2.

with probability 1/8, the next odd number is (3n+1)/8;

So half the remaining even numbers have 3 factors of 2.

and so on.

Making the factors of 2 a Geometric Distribution with probability 1/2.

Of course, these probabilities are only heuristic.

And the mean of a Geometric Distribution is the inverse of the probability.

Anyway the expected size of the next number is

(3n+1)/(2*2)

I'm not sure about this. Where's the error in my derivation? See below for further thoughts. DRLB 22:42, 18 January 2007 (UTC)

therefore

$(3n+1)(1/2^{2}+1/4^{2}+1/8^{2}+\dots )=(3n+1)(1/4)(1-1/4)^{-1}=(3n+1)(1/4)(4/3)=n+1/3$.

In other words, the probabilistic evidence suggests that the next odd number should be slightly larger.

Then we would expect to see sequences diverging to infinity, but we don't see that.

Please correct me if I'm wrong.

Sequences do NOT diverge to infinity, they converge to 1.

Assuming I'm right,

I don't see how.

for now, then I'd guess that there may be still be a strong heuristic probabilistic argument that the sequence will hit 1 in general. I estimate the standard deviation to be about ${\sqrt {2/7}}n$, and perhaps this is large enough that one can argue heuristically the sequence will decrease sufficiently often to eventually hit 1.

Have you tried this with, say, numbers with 53000 decimal digits? Think your standard deviation covers that case? Or did I just get lucky? --Mensanator 06:06, 18 January 2007 (UTC)

DRLB 20:07, 16 January 2007 (UTC)

Hmm ... I checked one of the references and found a page [4] on this heuristic argument.

I don't exactly agree with Mensanator or this page (which are essentially the same argument), but the disagreement is over a technicality. Expectation must be calculated as a sum of the possible outcomes weighted by their probabilities.

My calculation, according this rule, gives n+1/3. The other arguement uses a product of the outcomes, weighted by the probalities (using power to define the weight). Formally speaking, this is not expectation, per se. But of course it has meaning, and is good heuristic evidence.

Of course, it can be converted to an expectation by applying a logarithm. So, the expected value of the logarithm can the ratio of consecutive odd numbers is log (3/4).

Note that the logarithm of expectation is not the same as expectation as the logarithm. In other words, we're both right.

I think the article could be corrected to avoid this confusion from arising again. DRLB 22:42, 18 January 2007 (UTC)

Ok, so expectation isn't the same as heuristics. So what? The point being discussed here is heuristics. And if we're both right, then one of us is more right than the other. The article should remain as it is. Any confusion on your part is not Wikipedia's problem as long as the point it's making is made correctly, which it is.

And even if your Great Expectations are correct, what good are they? How does "the expectation that the odd successor of an odd number is slightly larger" provide any insight into why Collatz sequences always converge to 1?

In contrast, look at how useful the heuristic is: every odd number in a Collatz sequence will be succeeded by a mean of two even numbers. Earlier, I showed how to predict the number of odd numbers in the Collatz sequence of 2**177149-1 and got an answer (853681) that was within 0.12% of the actual result of 854697. By the heuristic, the number of evens should then be 2*853681 or 1707362. It actually has 1531812, only 89.7% acurate.

Oops, in my haste I miscalculated the even number prediction. Because the seed of the sequence in question is a Mersenne Number, the heuristic is not applicable until after the first 177149 odd numbers of the sequence. The correct calculation is 177149+(853681-177149)*2 = 1530213 or accurate to 99.9%. --Mensanator 18:08, 19 January 2007 (UTC)

Not as good, but these calculations are based on statistics, so your mileage may vary. I don't see how n+1/3 provides any clue at all as to how to figure sequence length. As evidenced by this discussion, you seem to be introducing confusion as opposed to reducing it.

If you can justify the expectation (assuming you have a citation), then go ahead and add it as further probabilistic evidence, but leave the discussion of the heuristic alone. --Mensanator 07:19, 19 January 2007 (UTC)

Just to be sure, I ran some tests on the first 20,000 odd numbers. The average difference between the next odd number and the current for these was 0.6987. In particular, note that, the next odd was slightly larger, on average. Indeed, it is even larger than the 1/3 difference that I heuristically estimated. However, exponentiating the average logarithm of the ratio of the next odd to the current odd gave 0.7500979897, which is about the 3/4 one expects heuristically, suggesting that the next odd should be considerably smaller, on average. This difference arises because of different meanings of average. Maybe this is worth adding to Paradox, provided that there is some published literature about such kinds of counterintuitive phenomena, which is surely more general than the Collatz problem. Then again, maybe it's not worth it. DRLB 23:21, 18 January 2007 (UTC)

Questions: [1] How are you actually calculating this? My two attempts at figuring out what you meant produce results nothing like yours. [2] How did you decide that 20000 was statistically significant? [3] Why did you use the first 20000 odd numbers as opposed to 20000 random odd numbers or 20000 odd numbers having 50000 bits each? [4] Can you re-run this test using 20000 consecutive odd numbers from an actual Collatz sequence? Otherwise, I'd say your test is pretty meaningless since consecutive odd numbers do not form a Collatz sequence. --Mensanator 07:19, 19 January 2007 (UTC)

Here's a smaller example of what I did. Take the first four odd numbers: 1,3,5,7. For Collatz sequences beginning with these numbers, the next odd number is 1,5,1,11, respectively. The differences are (1-1),(5-3),(1-5),(11-7), that is, 0,2,-4,4. The average difference is (0+2-4+4)=1/2. More precisely, the arithmetic mean of the difference is 1/2. The other sense of average growth, the sense in probabilistic evidence of the article, can be expressed as the geometric mean of the ratios, (1/1),(5/3),(5/1),(11/7), which is the fourth root of 11/21, or about 0.85. DRLB 18:07, 19 January 2007 (UTC)

No, the differences are (1-1), (3-5), (5-1) and (7-11), that is, 0,-2,4,-4. The average difference is (0-2+4-4)/4=-1/2. And your ratios are also wrong. Should be (1/1),(3/5),(5/1),(7/11) so the geometric mean would be 4th root of 105/55, or about 1.175. And even the wrong ratios you gave don't have a product of 11/21, the product would be 275/21 whose 4th root is about 1.9. Now I understand why I couldn't figure out how you came up with that goofy result from the 1st 20000 odd numbers. Perhaps you should re-think your role as a Wikipedia contributor until you learn how to use your calculator. --Mensanator 00:53, 20 January 2007 (UTC)

Mensanator, you negated the differences I used. The next odd number after 3 is 5, because 3(3)+1 = 10, and 10/2=5. 3 has increased by 2, that is to 5, so the difference I gave was correct. Also, the ratios I gave had an glaring typo, 5/1 should have been 1/5. My apologies. Again, once corrected, these are exactly the inverses of the ratios you gave. Anyway, their product (after correcting the typo) is 55/105 = 11/21, the inverse of the ratio that you give, because you again divided the previous odd by the next. We both can calcuate fourth roots, it seems, since 0.85 * 1.175 = 0.99875, which is close to 1, as it should be since we used inverse values. Clearly, we can use both calculators, unless you calculated the fourth root by hand. Finally, this is a talk page, so we ought to be more forgiving, don't you agree? DRLB 17:12, 24 January 2007 (UTC)

Ok, I can be more forgiving. Provided you make an effort to see the forest instead of the trees. It doesn't matter whether you use n/succ(n) or succ(n)/n. The geometric mean of n/succ(n)=1.175 implies that the next odd number will be slightly smaller. The geometric mean of succ(n)/n=0.85 implies that the next odd number will be slightly smaller, which is exactly the same conclusion as the other ratio. In neither case is the implication that the next odd number will be slightly larger as you originally claimed. You have more than just your values inverted, your whole argument is inverted and thus wrong and the original Wikipedia article is correct. Oh, and your claim of n+1/3 was bogus also. When you use the wrong ratios like you did, you get 4/3 or 1.333... decimal, so the correct thing is 1+1/3, not n+1/3. --Mensanator 06:37, 25 January 2007 (UTC)

Finally, we agree on the geometric mean. All I've trying to say here is that, in the geometric mean, the next odd is smaller. This is the forest that you allude to, and I see it. I was never claiming that the article was wrong, rather imprecise on what is meant by average. Maybe I'm being pedantic, but to me the default meaning of average is arithmetic mean, so a clarification was in order. I maintain that, in the arithmetic mean, the next odd is larger, by a difference of 1/3. This presumes that one takes a random odd starting value. Earlier, however, you asked me compute the arithmetic mean (of the difference between successive odds) for the odd numbers in a Collatz sequence. If you run the sequence until it hits 1, then it will be negative, i.e. not positive 1/3. Thus the heuristic that the odd number in a Collatz sequence have the same distribution as uniform seems to fail (by the way, the evidence of a geometric mean of 3/4 for suggesting convergence to 1 depends on the very same heuristic, that odd numbers in a Collatz sequence behave as uniform odd numbers). Anyway, this is a curious phenomenon, perhaps worth mentioning, but obviously not in a way that distracts from the main point. It's interesting to me that the geometric mean predicts a decrease while the arithemtic mean predicts an increase, but maybe I'm just goofy in general. Again, I'd be surprised if all this was not noted somewhere else. DRLB 15:39, 25 January 2007 (UTC)

At least we are slowly starting to communicate. I've obviously not been understanding some things you said, BOTOH, I think you were not very clear. In the following, I've made sure I used the same thing you did, succ(n)-n and succ(n)/n for Arithmetic Mean (AM) and Geometric Mean (GM). But I'm still confused.

You said the AM of the first 20000 odd numbers is 0.6987. I get that now also, but I fail to see what the significance is.

   AM of  100 odd numbers: 0.56
   AM of  200 odd numbers: 0.77
   AM of  300 odd numbers: 0.34
   AM of  400 odd numbers: 0.64
   AM of  500 odd numbers: 0.48
   AM of  600 odd numbers: 0.753333333333
   AM of  700 odd numbers: 0.394285714286
   AM of  800 odd numbers: 0.6925
   AM of  900 odd numbers: 0.544444444444
   AM of 1000 odd numbers: 0.806
   AM of 1100 odd numbers: 0.376363636364
   AM of 1200 odd numbers: 0.585
   AM of 1300 odd numbers: 0.507692307692
   AM of 1400 odd numbers: 0.734285714286
   AM of 1500 odd numbers: 0.433333333333
   AM of 1600 odd numbers: 0.66
   AM of 1700 odd numbers: 0.581176470588
   AM of 1800 odd numbers: 0.787777777778
   AM of 1900 odd numbers: 0.357894736842
   AM of 2000 odd numbers: 0.62

The AM is completely unstable for the odds, so of what use is this when comparing to the AM of a Collatz sequence?

The GM of the odds at least is somewhat stable:

   GM of  100 odds: 0.763088110546
   GM of  200 odds: 0.75433373718
   GM of  300 odds: 0.749584108063
   GM of  400 odds: 0.75368585376
   GM of  500 odds: 0.751960072532
   GM of  600 odds: 0.753409836832
   GM of  700 odds: 0.749230723047
   GM of  800 odds: 0.751297997523
   GM of  900 odds: 0.751170047199
   GM of 1000 odds: 0.751586927746
   GM of 1100 odds: 0.750506937857
   GM of 1200 odds: 0.750040383186
   GM of 1300 odds: 0.750845232813
   GM of 1400 odds: 0.751163263524
   GM of 1500 odds: 0.75074441619
   GM of 1600 odds: 0.751028202758
   GM of 1700 odds: 0.75158478744
   GM of 1800 odds: 0.750922077419
   GM of 1900 odds: 0.750329418241
   GM of 2000 odds: 0.750576235761

Although the GM of an actual Collatz sequence looks more like this:

   An actual Collatz sequence (built by tree crawler) from:
   115965183147145828891382318276603995721415182948139056866257
   72398441281808105172818431359253618093491566168722452508153

   GM of first 100 Collatz: 0.576328192983
   GM of first 200 Collatz: 0.580336872578
   GM of first 300 Collatz: 0.583024804016
   GM of first 400 Collatz: 0.573339865314
   GM of first 500 Collatz: 0.580592397566

Which is also somewhat stable although it bears no resemblence to that of the odd numbers. And yes, the AM is negative. Really, really, really negative.

   AM of first 100 Collatz: -1.15965183147e+116
   AM of first 200 Collatz: -5.79825915736e+115
   AM of first 300 Collatz: -3.8655061049e+115
   AM of first 400 Collatz: -2.89912957868e+115
   AM of first 500 Collatz: -2.31930366294e+115

But maybe the tree crawler algorithm wasn't the best choice for a Collatz sequence generator. A tree crawler creates a path that minimizes the factors of 2. Perhaps a similar magnitude number created from random decimal digits would be more representative.

No surprise, the AM seems meaningless for this one also:

   Now try a 119 digit random number
   170171216567461327555762455479240297769664115111878616708268
   24858491332473375089924042517307901176091503666104708437023

   AM of first  100 Collatz: -1.70171216567e+116
   AM of first  200 Collatz: -8.50856082837e+115
   AM of first  300 Collatz: -5.67237388558e+115
   AM of first  400 Collatz: -4.25428041419e+115
   AM of first  500 Collatz: -3.40342433135e+115
   AM of first  600 Collatz: -2.83618694279e+115
   AM of first  700 Collatz: -2.43101737954e+115
   AM of first  800 Collatz: -2.12714020709e+115
   AM of first  900 Collatz: -1.89079129519e+115
   AM of first 1000 Collatz: -1.70171216567e+115

Ah, but look at the GM.

   GM of first  100 Collatz: 0.046809670875
   GM of first  200 Collatz: 0.18287838408
   GM of first  300 Collatz: 0.296127794073
   GM of first  400 Collatz: 0.390788382319
   GM of first  500 Collatz: 0.443977997494
   GM of first  600 Collatz: 0.489583606479
   GM of first  700 Collatz: 0.531275542781
   GM of first  800 Collatz: 0.557564646428
   GM of first  900 Collatz: 0.572699420436
   GM of first 1000 Collatz: 0.587133849254

Makes you even wonder why we're making such a fuss over the heuristics, eh? --Mensanator 02:43, 26 January 2007 (UTC)

   # just how atypical was the tree crawler number?
   #
   import collatz_functions as cf
   #
   # the tree crawler number
   tc = 11596518314714582889138231827660399572141518294813905686625772398441281808105172818431359253618093491566168722452508153
   # by construction, tc should have EXACTLY 500 odd
   # numbers in it's Collatz sequence
   tc_stats = cf.collatz(tc,0)
   # returns [evens,odds] of sequence
   print tc_stats
   #
   # [1185, 500]
   #
   # the random number
   rn = 17017121656746132755576245547924029776966411511187861670826824858491332473375089924042517307901176091503666104708437023
   # had over a thousand, specifically
   rn_stats = cf.collatz(rn,0)
   print rn_stats
   #
   # [2000, 1014]
   #
   # the number of bits in each number was
   tc_bits = cf.gmpy.numdigits(tc,2)
   rn_bits = cf.gmpy.numdigits(rn,2)
   print tc_bits,rn_bits
   #
   # 393 393
   #
   # The heuristic of every odd number being followed
   # by an average of 2 even numbers coupled with the
   # mean 1.585 bits of carry per odd number means there
   # is a net loss of 0.415 bits per odd number.
   # Therefore, a random number of m bits should result
   # in a Collatz sequence containing m/0.415 or m*2.409
   # odd numbers.
   #
   # Or the actual odd number count divided by the
   # bit-length should be 2.409.
   #
   print float(rn_stats[1])/rn_bits
   #
   # 2.58015267176
   #
   # Hmm...close but not exact. Must have gotten lucky
   # with the random number generator. But the tree
   # crawler odd/bit ratio was extremely atypical:
   #
   print float(tc_stats[1])/tc_bits
   #
   # 1.27226463104
   #
   # That's not something you're likely to see by testing
   # random 119 digit numbers.

--Mensanator 07:49, 26 January 2007 (UTC)

Mensanator, thank you for running those tests. I also ran a few more tests too. Taking random odds n (instead of taking the first bunch of odds), I found that the AM of s(n)-n fluctuates quite wildly. Probably this is because of the fairly large standard deviation. The fact that is somewhat close to 1/3 when taking the first set of odds, may in fact be just a coincidence. In similar tests for the GM, I found less fluctuation, similar to what you found. I don't have a good explanation for any of this.

Anyway, back to the article. I don't think that the AM stuff needs to mentioned in the main article, and here's why. I went to Lagarias's annotated bibliography, and couldn't find mention of it. I then asked him. He responded quickly, saying he was unaware of people studying tha AM. Therefore, whether or not the AM is relevant, significant or interesting, it would be original research, which disqualifies form inclusion in a wikipedia article.

When I first read the article, I interpreted average to mean AM. There was no hint the average meant geometric mean of the ratios. Also, since there was no derivation of the 3/4 or supporting reference, I tried to derive the result myself, and got something different, because I naively used the AM. Only on reading your contributions to the discussion page, did I learn that what was meant was the GM. Since then, I've tried to clarify the article, at least to my satisfaction, by linking to Lagarias's derivation of the 3/4, and stating that the average in the sense of the geometric mean. DRLB 17:04, 26 January 2007 (UTC)

I agree, no point in discussing the AM. And the "getting something different" was my problem with your original posts, although I think we are now on the same page. And I have no problem with the way you edited the article. This has got to be a first for Wikipedia - a discussion where both parties end up agreeing. :-)

Oh, and I ran one more test to satisfy my curiosity. I mentioned that my tree crawler algorithm "minimizes the factors of 2". That wasn't a good way to put it since the tree crawler sequence had roughly twice as many evens as odds just like the random number. The significant difference between the two is how those factors are distributed. For a random number, we get a Geometric Distribution:

   # rn factor of 2 distribution (* scale = 8)
   #   1 (527) *****************************************************************
   #   2 (243) ******************************
   #   3 (117) **************
   #   4 ( 62) *******
   #   5 ( 36) ****
   #   6 ( 13) *
   #   7 (  6) 
   #   8 (  5) 
   #   9 (  3) 
   #  10 (  1) 
   #  11 (  1) 

But for the tree crawler sequence, the distribution is very different and probably explains the difference in the GMs of the two sequences:

   # tc factor of 2 distribution (* scale = 8)
   #   1 ( 98) ************
   #   2 (229) ****************************
   #   3 ( 63) *******
   #   4 (110) *************

--Mensanator 19:37, 26 January 2007 (UTC)

Collatz's Conjecture Proved!

A very simple and general solution to Collatz-type problems is presented here: [5]. It's worth looking into ...

I've seen it. It's rubbish.--Mensanator 18:37, 10 September 2006 (UTC)

Come back when this has been published in a mathematical journal. Fredrik Johansson 10:01, 10 September 2006 (UTC)

I concur. Sr13 01:52, 28 September 2006 (UTC)

LOL, the guy also claims to have proved P=NP on his website. Crackpots seem to prefer "proving" difficult conjectures in pairs ;)

Removing link

• Collatz Observations discusses observations about the Collatz Conjecture as it pertains to a bijection over the natural numbers.

I am removing the above link from the External links section because the page it links to is incorrect. It claims to present a breathtakingly simple proof of the conjecture which is, as it turns out, not a proof at all. I just thought I'd leave a note here in case there's any question. -GTBacchus^(talk) 22:27, 26 September 2006 (UTC)

Searching Collatz

When I type in Collatz, Wikipedia leads me to the conjecture rather than the person. Shouldn't there be a disambiguation page that links to both pages? Sr13 01:58, 28 September 2006 (UTC)

Like this: Collatz? -GTBacchus^(talk) 02:10, 28 September 2006 (UTC)

Thanks. Sr13 03:05, 28 September 2006 (UTC)

Another claim to a proof.

http://scitec.uwichill.edu.bb/cmp/journal/cadogan.pdf

In a mathematical journal this time, albeit an obscure one. AFAICT it's not verified independentl yet. Could someone take a look?

I haven't had time to look at in detail but my initial impression is mixed. The techniques used seem to be very elementary. However, the paper has no obvious gaps or crankyness. You may get a better response by posting to sci.math on usenet. JoshuaZ 22:04, 4 December 2006 (UTC)

I'm following it just fine until the bottom of page 7, where I'm stuck on the justification of (2.6). Is anybody else checking this out, for whom that step makes sense? -GTBacchus^(talk) 00:04, 5 December 2006 (UTC)

I'd like to see how his equations deal with -17. Yes, I know the conjecture is false in the negtive domain, but he has to show why his convergence method is a "proof" in the positive domain when it obviously isn't a proof in the negative domain.--Mensanator 13:03, 6 January 2007 (UTC)

I'm pretty confident that the line on page 7 where I was tripping up is actually a fallacy. He basically uses the following logic: X implies Y, X implies Z, therefore Y implies Z. He's also the editor-in-chief of the journal that published it, so I'm guessing the peer review was minimal at best. I'm pretty sure the Collatz conjecture is still open. -GTBacchus^(talk) 07:27, 8 January 2007 (UTC)

I just happen to read this post today --- the flaw in this "proof" is easily noticed …

It is true that j ~ 3j+1 for all odd j --- however, they first coalesce at 3j+1 > j and not at some 1 < k < j < 3j+1 (that is, the sequence with starting number 3j+1 is a subsequence of the sequence with starting number j).

Likewise, 4j+1 ~ 3j+1 for all j and they first coalesce at 3j+1 < 4j+1 --- that is, the sequence with starting number 3j+1 is also a subsequence of the sequence with starting number 4j+1.

Therefore, j ~ 4j+1 but the sequence with starting number j is not a subsequence of the sequence with starting number 4j+1, or vice versa, and they first coalesce at 3j+1 with j < 3j+1 < 4j+1.

In the assailed paper, Corollary 3.2 is true and, as stated, Lemmas 3.4 and 3.5 as well as Theorem 3.6 are true --- that is, the results are true but their alleged "proofs" (specifically, on "repeated application" on 4j+1 with supposedly descending coalescence points) are defective [we simply note that x ~ 1 and y ~ 1 by just generating their sequences so, by definition of "~", x ~ y for all positive integers x and y hence all "assertions" in the paper about "~" are "tautologous" --- to avoid this, all arguments in the paper should justify the existence of some _first_ coalescence number > 1 and then succeeding ones that converges to 1].

Lemma 3.4 is faulty in its attempt to prove the convergence of 4j+1 to 1 --- specifically, in this claim: "1 + 3j ~ t_k,l for some k >= 1 and l < j". Again, this claim is tautologously true because 1+3j ~ t_0,1 = 1. But the mistake in the paper's reasoning is in the fact that when j is even and 1+3j is odd, what is asserted is that 1+3j ~ 1+3j and so t_k,l = 1+3j > j. BenCawaling 03:27, 20 January 2007 (UTC)

Note to Jibbist:

If you actually ever do find a relevant link, it goes under References and External Links not See Also.

And tell Andy that a do..while loop isn't a recursive algorithm. --Mensanator 00:49, 9 March 2007 (UTC)

It's a stupid problem

I don't understand why anyone would even think they could prove this conjecture. To do this, they'd have to test every number out to see that it hits 1 eventually, but there's infinity numbers. They can check as many numbers as they want, but they'll never reach infinity. —The preceding unsigned comment was added by Logicker (talk • contribs) 22:52, 14 March 2007 (UTC).

The same might be said of proving something like "adding any number to itself gives you twice that number". Luckily, formal logic and the mathematical proof do indeed provide us with ways to determine and show the truth of such infinite classes of statements. Hv 23:19, 14 March 2007 (UTC)

Formal logic and mathematical proof may help you when you have tautologies like "adding any number to itself gives you twice that number" but doesn't help if you have to test every single number out and there's infinity of them.Logicker 01:47, 15 March 2007 (UTC)

Why do you think you have to test every number? That every 2**n-1 is divisible by 3 when n is even isn't a tautology and that can be proved without doing an infinity of tests. --Mensanator 04:30, 15 March 2007 (UTC)

When n is even, n=2k for some k, so 2^n-1 = 2^(2k)-1 = 4^k-1 = 1^k-1 = 0(mod 3). It's a tautology (true for any k), so you don't have to test every number. But with the Collatz sequence, you can't do this, which is why you have to test every number out. It's a stupid problem which only cranks work on.Logicker 16:01, 15 March 2007 (UTC)

You keep saying "you can't do this" but you've never explained why. That makes the statement a non sequitur, doesn't it? It's not stupid because I learned a lot while studying it. And it's not only cranks that work on it, it's only cranks that think they've proved it...or think it's unprovable.--Mensanator 20:59, 15 March 2007 (UTC)

Try starting the Collatz sequence with the variable x, which can represent any number. Then the next iteration is x/2 if x=0 (mod 2). And it's (3x+1)/2 if x=1 (mod 2). And the next iteration is either x/4, (3x+1)/4, (3(3x+1)/2+1)/2, or (3x/2+1)/2.

Why do you think that iteration is the only method available for proving the conjecture?

You can go on forever with this pattern,

And it can be proved that every possible pattern appears infinitely many times on the Collatz Tree (the union of all sequences). I do not have to actually trot out each pattern to prove it exists, no iteration necessary. Now explain how you know that there isn't a non-iterative proof.

but you'll never know if it goes to 1 unless you know the value of x. But there are infinity possible x's.

Which is only a problem for iterative proofs. Until you can prove that there can only be an iterative proof, the infinity of possible x's means nothing.

Now that's what I call "proof by hocus-pocus". Logicker 02:03, 16 March 2007 (UTC)

In other words, you can't prove that there can only be iterative proofs. And yet you cling to the notion that an infinite number of steps must be done. --Mensanator 19:37, 16 March 2007 (UTC)

So that's why the problem is a complete waste of time and energy for any serious mathematician.Logicker 22:50, 15 March 2007 (UTC)

So who's a serious mathematician? --Mensanator 00:35, 16 March 2007 (UTC)

Logicker, are you familiar with the idea of a proof by contradiction? Like, maybe someone could show that, if some starting number didn't eventually reach 1, then that would imply something that's clearly false, therefore there must be no such number? Lots of statements in "serious mathematics" have no proofs excepts proofs by contradiction; does that make all of those statements "stupid" as well? -GTBacchus^(talk) 00:51, 16 March 2007 (UTC)

When I was in high school, my math teacher explained the fifteen puzzle (with tiles 14 and 15 exchanged) to the class and why it couldn't be solved. Everyone was satisfied with the explanation except for one kid named Bradley. Bradley insisted that the teacher's explanation wasn't good enough because he thought he could get around the fact that the solution and the original configuration have different parities. Bradley, is that you? Logicker 02:03, 16 March 2007 (UTC)

There is a difference between "provably false" and "unproved". No one studying Collatz is trying to refute anything that's been proved. Sure, there are some cranks around who wrongly believe they have a proof. But so what? There are still cranks prattling on about FLT and that was settled years ago. The fact that Collatz hasn't been settled yet makes it a legitimate subject for research even if serious mathematicians don't care about it. --Mensanator 19:37, 16 March 2007 (UTC)

No, I'm not Bradley, and I understand why the fifteen puzzle is unsolvable from certain configurations, with differet parity, as you say. In fact, I used that puzzle as an example when I was teaching group theory, when we were talking about even and odd permutations. What on Earth has that got to do with the Collatz conjecture? Also, did you even read my question about indirect proof? What's your justification for ruling those out; are you a constructivist or something? -GTBacchus^(talk) 22:07, 17 March 2007 (UTC)

There is no reason why a Collatz sequence can't go to infinity or end up in a nontrivial cycle, so there can't be any proof by contradiction. The only reason why no such example has ever been found is because the odds of such happenning are so low. See http://hdebruijn.soo.dto.tudelft.nl/www/programs/collatz.htm. Also, this paper formally proves that it's unprovable, http://arxiv.org/abs/math/0312309. I don't think the author of that paper had to go through so much detail to get his point across, as it's so obvious that you have to test out every number to prove the conjecture. I knew it right away when I first heard of the conjecture.Logicker 04:41, 18 March 2007 (UTC)