Talk:Collatz conjecture

References in culture

There is a reference to this confusing mess in the popular webcomic XKCD. Someone should make a section in the article detailing all such references that pop up in culture. —Preceding unsigned comment added by 71.42.218.73 (talk) 17:19, 5 March 2010 (UTC)

No, somebody shouldn't make a pop culture section. In Pop Culture sections are lame and contribute nothing to the article. Go read this again: http://xkcd.com/446/. If you think you need to make a pop culture section, you're completely missing the point of that comic.192.104.39.2 (talk) 18:01, 5 March 2010 (UTC)

meat and potatoes

function collatz(n) show n if n > 1 if n is odd call collatz(3n + 1) else call collatz(n / 2). This program halts when the sequence reaches 1, ... 76.240.78.196 (talk) 17:57, 26 January 2010 (UTC)meami.org

Duh. Now try telling us something we don't know.--Mensanator (talk) 06:32, 30 January 2010 (UTC)

pls look at it...

This forum is for discussion of the Wikipedia article.

The appropriate place to discuss this is the Usenet group sci.math and I've transferred it there. You can reach it via Google Groups with subject Collatz Conjecture proof?

No link to "claimed proof by Peter Schorer"

E-Mail discussion with Jeff Lagarias:

---

---

Re: About the Collatz conjecture-reply‏
Von: 	Jeffrey C Lagarias (lagarias@umich.edu)
Gesendet: 	Dienstag, 9. Juni 2009 22:58:30
An: 	Mario (mario_***@hotmail.de)

Dear Mario,
    In reply to your query, various earlier versions of Peter Schorer's
papers-and I have seen several- were wrong: 
 they had gaps so the result is not proved. I have not looked
at any versions since 2008, he continually rewrites the proofs, so any
specific comments will be out of date. 

    In the 2008 versions mistakes were not in the lemmas, where most things were 
correct, but in the final proofs. The author's notation is designed to not
indicate clearly the dependence of quantities on earlier parameters.
This allows the mistake of treating some quantity as a constant, when in
fact it is variable, depending on earlier quantities. You only have to make
such a mistake once,  to derive anything. 

    General comment: In the methods this author uses, I don't see any
substantial new idea being introduced that will explain why the
result should be true (3x+1 Conjecture), if indeed it is true. Why can't there
be a finite cycle of period 10^{100}?

    I see the latest version gives three proofs of the final result. If
you have proved it, one proof will suffice.

   The 3x+1 problem is dangerous, it can be a colossal time sink.
 My advice: don't work on it unless you have a specific
 idea to test out. 

   sincerely yours,

    jeff lagarias

---

On Jun 8, 2009, at 6:22 PM, Mario wrote:

    Dear Jeffrey Lagarias,
    recently I've read some articles about the Collatz conjecture and played arround a little bit with it.

    Reading some further articles, I saw Peter Schorer's text linked at several pages (http://www.occampress.com/). He claims that 
he's solved the problem. Also I have seen a (scientific) review of his article 
(http://rolf.haynberg.de/wp-content/uploads/2009/03/collatzproof.pdf).

    As you have worked alot with the problem, and especially because of your two texts (The 3x + 1 problem: An annotated bibliography (1963–1999) and The 3x + 1 problem: An annotated bibliography, II (2000–)), I thought that you are the right mathematican to ask, whether the claimed proof of Peter Schorer is right or wrong - unfinished or conceptional wrong.

    I would be very happy to get an answere about that very interesting topic.

    kind regards,
    Mario

    PS: Sorry for my spelling, english isn't my native language.

---

---

Therefor, no link to peter Schorer's wrong article. Mario23 (talk) 21:32, 25 August 2009 (UTC)

A proof?

Here is an article detailing a proof of the Collatz conjecture.

Bruckman, P.S. "A proof of the Collatz conjecture". International Journal of Mathematical Education in Science and Technology. 39.3 (2008): 403-407. —Preceding unsigned comment added by 68.127.62.5 (talk) 01:33, 16 January 2010 (UTC)

No. Check discussion in /Archive_1#Evidence_that_the_conjecture_may_be_proved. -- Magioladitis (talk) 03:58, 16 January 2010 (UTC)

question about 100 million and 1 billion results in main article

The original article says:

"The number less than 100 million with the longest total stopping time is 63,728,127, with 949 steps."

and

"The number less than 1 billion with the longest total stopping time is 670,617,279, with 986 steps."

However I wrote a C program and the respective numbers came out to 950 and 986 respectively.

I get 950 & 987 in my program. But then again, my program counts the length of the sequence, not the number of steps. That means I include the starting number. Try your program with a more reasonable number like 16. The sequence will be 16, 8, 4, 2, 1 the number of steps is 4, the length of the sequence is 5. First, you'll want to check what your program is ACTUALLY doing, then decide if that's what you want it to do. Frankly, I don't see how you can get 950 & 986. A consistent answer would be EITHER 950 & 987 OR 949 & 986.

Not knowing whether I was right or wrong then I googled around and found some other web pages also with the same results as me: http://d.hatena.ne.jp/tamura70/20100116/collatz http://www.mathforum.org/kb/message.jspa?messageID=465161&tstart=0 http://blog.livedoor.jp/dankogai/archives/50564170.html

That will depend on what specifically they are counting, but 950 & 986 doesn't seem right.

So what's the story? Where did I -- and the other guys on the webpages listed above -- go wrong? Or are the figures in the quotations from the main article wrong?

I don't know C that well, but when I ran this through my Python library of Collatz functions, I got the wrong answer at first, seems I was including the start of the sequence but forgot to increment the odd count when I hit 1. Your answer seems inconsistent, so I can't guess what you're doing wrong.--Mensanator (talk) 21:12, 16 February 2010 (UTC)

BTW in case it's useful for anybody, here is my cross-platform (Windows, Linux) source code suitable for 64 bit systems:

/**
 * Copyright (c) 2010 Simon Hardy-Francis
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */

#include <assert.h> /* for assert() */
#include <stdio.h>  /* for printf() */
#include <string.h> /* for memset() */
#include <stdlib.h> /* for calloc() */

#define VERBOSE 0

#define CACHE_GLOBAL unsigned short * cache
#define CACHE_INIT(upper_bound) cache = ( unsigned short *) calloc ( upper_bound, sizeof ( unsigned short ));assert ( cache != NULL );memset ( cache, 0, upper_bound * sizeof ( unsigned short ) )
#define CACHE_LOOKUP(i) ((i) < upper_bound ? cache[i] : 0)
#define CACHE_STORE(n,steps) (cache[n] = steps)

CACHE_GLOBAL;

void
collatz ( size_t lower_bound, size_t upper_bound )
{
       unsigned short   steps_maximum = 0;
       unsigned short   steps;
       unsigned short   steps_cached;
       size_t           i_largest = 0;
       size_t           i;
       size_t           n;

       CACHE_INIT ( upper_bound );

       for ( n = lower_bound ; n <= upper_bound ; n ++ ) {
               steps = 1;

               for ( i = n ; i > 1 ;  ) {
                       if ( i & 1 ) {
                               i = i + ( i << 1 ) + 1; // i = ( 3 * i) + 1;
                               steps ++;
                       } else {
                               i >>= 1;
                               if ( steps_cached = CACHE_LOOKUP ( i ) ) {
                                       steps += steps_cached;
                                       break;
                               }
                               steps ++;
                       }
#if VERBOSE
                       if ( i_largest < i ) {
                               i_largest = i;
                               printf ( "n: %-8llu, i_largest: %-10llu\n", n, i );
                       }
#endif
               }
               CACHE_STORE ( n, steps );

               steps_maximum = steps > steps_maximum ? steps : steps_maximum;
       }

       printf ( "%llu %llu %llu\n", lower_bound, upper_bound, steps_maximum );
}

int
main ( int argc, char **argv )
{
       size_t lower_bound;
       size_t upper_bound;

       if ( 8 != sizeof ( size_t) ) {
               printf ( "Hint: Better to run this program on WIN64 systems\n" );
               exit ( 1 );
       }

       if ( argc <= 2 ) {
               printf ( "usage: e.g. collatz 1 10000\n" );
               exit ( 1 );
       }

       lower_bound = atoi ( argv[1] );
       upper_bound = atoi ( argv[2] );
       collatz ( lower_bound, upper_bound );
}

(Sorry this is the first time I've ever edited an Wikipedia talk page... please be kind to the newbie :-))

SimonHF (talk) 05:26, 16 February 2010 (UTC)

So I figured out what the problem is. I was working from two different sources; the Wikipedia Collatz acticle and this document: http://docs.google.com/View?id=dd5f3337_12fzjpqbc2 . One refers to 'steps' and the other refers to 'cycle length'... duh. This makes it a bit confusing... well for me anyway... :-)

SimonHF (talk) 03:28, 17 February 2010 (UTC)

Yeah, ya gotta be careful about what you read on the Internet. "Cycle length" is not the appropriate terminology, it is more appropriate to use "sequence length" or something similar. "Cycle" refers to that portion of the sequence that loops, i.e., 4, 2, 1. For 3n+1 in the positive domain, the "cycle" is always 4, 2, 1 although there is no limit on how long a sequence can be. In the negative domain of 3n+1 the are other cycles, @ -1, -5 and -17. Extending Collatz to use 3n+C, you can always choose a C to create an arbitrary cycle length.--Mensanator (talk) 05:43, 17 February 2010 (UTC)

As a corroboration, here is Mathematica code to verify, using the STEPS convention (that 16 is 4 steps).

collatzeStep[x_Integer?EvenQ] := x/2;
collatzeStep[x_Integer] := 3 x + 1;
collatzeStep[1] = 1;
collatzeStepCount[n_Integer] := Length[FixedPointList[collatzeStep, n]] - 2

And the results:

collatzeStepCount[16]
4

collatzeStepCount[63728127]
949

collatzeStepCount[670617279]
986

JonMcLoone (talk) 10:57, 5 March 2010 (UTC)

Practical applications?

If progress on the Collatz conjecture has practical applications or implications outside of mathematics, it should be mentioned in the article. ButOnMethItIs (talk) 12:16, 24 February 2010 (UTC)

What about practical applications inside mathematics?--Mensanator (talk) 19:18, 25 February 2010 (UTC)

So long as it's not original research and it speaks to the importance of the Collatz conjecture to the wider world, that would be most welcome. Presently, I don't see anything in the article that suggests such importance. ButOnMethItIs (talk) 13:47, 26 February 2010 (UTC)

That's too bad, I only do original research. (Why does this apply to math, which is self-evident?)

I assume it's not mentioned because it has simply never occured to anyone (except me) that Collatz can be exploited to solve problems beyond its domain that would certainly be of interest to the wider world.

Like factoring.

I have a feasability study that factors a series of composites from 5 to 200 digits. And does them all in about 8 seconds. But since it's not general purpose, RSA numbers are safe. For now.

There's nothing to cite yet, but practical applications DO exist.--Mensanator (talk) 21:06, 26 February 2010 (UTC)

Over 9000

Mad props to whomever snuck this in as a rational example! Metao (talk) 08:55, 5 March 2010 (UTC)

Came here to say the same thing. The beauty of it is that it is true, and un-arguable. It really goes up to OVER 9000! happypal (Talk | contribs) 09:09, 5 March 2010 (UTC)

Aye, that it is. But is it really necessary? Seems to detract from the overall theme of the article. I vote to remove it. I will not do so unless others agree. But still. It's win. Centrisian (talk) 12:30, 5 March 2010 (UTC)

There's no rule that says we can't have a sense of humor. There is a rule that says articles can't have random silliness in them. I think that since this is both correct and unobtrusive (someone unfamiliar with the meme will never even suspect that there's anything to read into), it can stay. Put another way, a good (if rough) test of this (in my opinion) is, "Is it plausible that this wasn't originally intended to refer to an Internet meme?" I think it is (especially the original edit was made on May 8, 2005), it can stay. (That being said, it might be possible to make it even less obtrusive; but in the interest of avoiding unwanted attention, we should probably just leave it alone until next Monday, when it comes off the front page of xkcd.) PhageRules1 (talk) 12:56, 5 March 2010 (UTC)

You're supposed to be professional, not put jokes in these articles. This isn't a linking page for your entertainment websites. No, no it's not. Stop thinking about replying with a psudo-twist of terrible logic. The answer is no. Patricoo (talk) 16:00, 5 March 2010 (UTC)

As a side note, I would love to know how many semi-protects have been as a direct response to treatment of a subject in xkcd. Dave (talk) 16:02, 5 March 2010 (UTC)

Can we at least make it a bit more subtle? I see no reason why we need have OVER 9000 in bold text. Theusernameiwantedisalreadyinuse (talk) 17:08, 5 March 2010 (UTC)

Ground Breaking?

You could always change 3x+1 to just n+1. Also try with 5n+1 instead.

In all, the Collatz conjecture can be Substituted with and odd number times n +1, and will eventually reach 1 with this formula. —Preceding unsigned comment added by JRoberts851 (talk • contribs) 16:02, 5 March 2010 (UTC)

Can you prove that?85.228.171.42 (talk) 17:58, 5 March 2010 (UTC)

5n+1 fails with 7 (7, 36, 18, 9, 46, 23, 116, 58, 29, 146... ) It appears to be a non-repeating, infinitely increasing series (at least through 1000 cycles which is where I cut it off).Laxrulz777 (talk) 19:36, 5 March 2010 (UTC)

Removal of program languages

I boldly removed a bunch of different "example programs" which calculated the Collatz conjecture. I feel that the pseudocode is more than sufficient to demonstrate the solution, and it seemed that the examples were not adding anything to the article. This is not an article to discuss the difference between various languages, it is to discuss the Collatz conjecture, and having a bunch of different languages only serves to distract the reader. --Shirik (Questions or Comments?) 18:07, 5 March 2010 (UTC)