Talk:Collatz conjecture

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, High-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
High Priority
 Field: Number theory
This article has comments.

pls look at it...[edit]

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?

Program to calculate Hailstone sequences[edit]

I am requesting some comment on the recently added "simplified" program. My comments:

  • The (3/2)k construction, although accurate, requires a reference.
  • The new (second) program is not "simplified".
  • The new program appears to display the last term of a (3n+1)/2 run twice. This could be fixed by moving the first "show n" outside of the while loop, but that produces a small anomaly if the input is "1".

Arthur Rubin (talk) 18:03, 9 January 2014 (UTC)

I think the calculation is simplfied, if considering n+1 instead of n, since the term +1 in the 3x+1 operation is avoided. (talk) 10:34, 29 January 2014 (UTC)

 g(n) = f(n-1) + 1 = \begin{cases} (3/2)n &\text{if } n \equiv 0 \pmod{2}\\ (n+1)/2 & \text{if } n\equiv 1 \pmod{2} .\end{cases}

Using g instead of f you see, it is growing as long as n is even or n-1 is odd. In binary representation n the number of left-most zeros are the number of upward operations.

The inverse relation is

 I(n)  = \begin{cases} (2/3)n &\text{if } n \equiv 0 \pmod{3}\\ 2n-1 & \text{for all } n.\end{cases} ,

meaning that there are two possible predecessors (2/3)n and 2n-1, if n is divisible by three and always an odd predecessor 2n-1. — Preceding unsigned comment added by (talk) 10:58, 29 January 2014 (UTC)

In other words, there is always a greater predecessor 2n-1 and smaller one if n is divisible by three. The predecessor 2n-1 also have a smaller second predecessor (predecessor of predecessor), if n \equiv 2 \pmod{3}. (talk) 11:09, 29 January 2014 (UTC)

At most, there are log(n)/log(3) downward operations in series of the inverse I.


This conjecture has an unusual property regarding possible counterexamples. Even if God said "Here's a number which diverges without cycles", this wouldn't really prove anything, because this number couldn't be checked in finite time. Normally, a counterexample instantly (well, at least reasonably quickly) disproves a conjecture, but here it is useless. Are there any other conjectures with this property? Are there any sources that discuss or least mention this? GregorB (talk) 20:29, 20 February 2014 (UTC)

If you ask whether there are any sources that mention this then I suspect you don't actually know whether it is true. Neither do I. Is there any known test which has been proven to determine in finite time whether n is a counter example? I have no idea. If n is a counter example then it obviously wouldn't work to compute the infinite sequence, but it doesn't seem impossible to me that somebody has found or will find a way to prove a sequence with certain testable properties must diverge, without knowing whether such a sequence exists. Many conjectures have the property you ask for, although the meaning of "counter example" may sometimes seem less specific than for the Collatz conjecture. For example, Polignac's conjecture states: "For any positive even number n, there are infinitely many prime gaps of size n". Suppose God claims n=2 is a counter example. Then God would be claiming the twin prime conjecture is false. Oh no, the alleged counter example is a more famous unsolved conjecture than we started with. By the way, last year it was finally proved by Yitang Zhang that there exists n which are not counter examples to Polignac's conjecture, but no specific n has been proven. As an example of how little we sometimes know about small numbers, Friendly number says: "No general method is known for determining whether a number is friendly or solitary. The smallest number whose classification is unknown (as of 2009) is 10". says: "It is believed that 10, 14, 15, 20, 22, 26, 33, 34, 38, 44, 46, 51, 54, 58, 62, 68, 69, 70, 72, 74, 76, 82, 86, 87, 88, 90, 91, 92, 94, 95, 99, 104, 105, 106, and many others are also solitary, although a proof appears to be extremely difficult." PrimeHunter (talk) 02:37, 21 February 2014 (UTC)
You can look at the position of the problem in the arithmetic hierarchy for some indication of the maximum degree of difficulty. The set of all numbers which converge to the 1(-4)-2 cycle here is \Sigma_0^1 (as you can code the entire the entire sequence as an number); so the Collatz conjecture is \Pi_0^2. Similarly, in regard Polignac's conjecture, the question of whether a number occurs infinitely many times as a prime gap is \Pi_0^2, so the conjecture is also \Pi_0^2. There are numerical conjectures at a higher level. — Arthur Rubin (talk) 21:00, 24 February 2014 (UTC)
It also depends on how you define the conjecture - there is an equivalent problem that looks at a map between infinite binary vectors to the 2-adics - depending on what maps to the rationals/integers/naturals determines the conjecture. In that case, you could specify a counterexample by considering the binary vectors also as 2-adics, then giving an irrational 2-adic that maps to a rational 2-adic. I'm not saying it would be easy to check, exactly, but it is a much more direct sort of thing logically speaking.Phoenixia1177 (talk) 04:31, 16 May 2014 (UTC)
Huh? Running the thing backwards, if x is rational, then neither 2x nor (x-1)/3 can be irrational, regardless of whether we're talking about real numbers or 2-adics. —David Eppstein (talk) 04:37, 16 May 2014 (UTC)
The parity of a 2-adic integer's trajectory gives an infinite binary word, that word can be taken as another 2-adic integer. Consider that as mapping 2-adic to 2-adic: if rationals map to rationals, then every rational number is eventually cyclic - on the other hand, if under the inverse map an irrational maps to a rational, then there is a divergent rational trajectory; which, in the case that the image is a natural number, means that the trajectory diverges off to infinity. Essentially, the digits of the image under the mapping encode the trajectory due to the close relation between Collatz trajectories and parity. --The observation is, obviously, fairly trivial - what makes it interesting is how simple it is to work out the form of the mapping.Phoenixia1177 (talk) 05:26, 16 May 2014 (UTC)
The conjecture (as with nearly all mathematics) requires proof. If you claim a number which cycles, you can prove your claim by writing down the sequence. If you show me a number which diverges forever, you obviously can't write the sequence down, so you must use math to show it. Imagine a machine which takes as input a number, and runs the collatz function on it. This function can return True, False, or run forever. The fact that you cannot know (just by running the machine) whether it will return a result (True/False), or if it will run forever, is known as the Halting Problem. It is well known in the field of computer science. — Preceding unsigned comment added by 2601:9:76C0:53:2D87:9BAD:A4D4:62AF (talk) 01:43, 23 October 2014 (UTC)
That's sort of right. There is no reason there can't be a condition equivalent to divergence that can be easily written and checked - for f(x) = x ^ 2, you can't write down the sequence, but |x| > 1 can be checked. There is nothing that has shown that the Collatz Conjecture trajectories reduce to the Halting Problem; if this had been shown, then the conjecture couldn't possibly be true. There is a result that shows that we can't know which functions, from a set of collatz generalizations, converge for all naturals because that would be equiv. the halting problem; but that doesn't really relate to anything being said here.Phoenixia1177 (talk) 08:42, 26 October 2014 (UTC)

References section[edit]

It is unusual to have a section "References and external links", especially when there is also one for "External links". I suggest a new subsection for "Preprints", and moving links to online preprints there; other links to web sites and online resources should go to "External links" and then the section should take the standard title "References" per WP:MOS. Deltahedron (talk) 09:02, 11 May 2014 (UTC)

Real and complex numbers[edit]

Please could somebody consider adding a derivation for the continuous function which appears to have been "pulled from thin air", or a link to another article where this is discussed.

I see the explanation at e.g. [1] and would do something myself, but I've never done any mathematical editing and really don't want to make a mess of somebody else's article. MarkMLl (talk) 07:55, 26 September 2014 (UTC)



if i wanna add alot of info about the Collatz conjecture that are not on the article what i need to do? do i first need to post in talk and then it will be posted in the article or what?

i have alot of stuff i was working on that are not showen in the article — Preceding unsigned comment added by Isaac.mor (talkcontribs) 10:19, 22 February 2015 (UTC)

If by "stuff I was working on" you mean things you have worked out yourself, then that should not be added to the article: see WP:No original research. Anything you add should be supported by reliable sources. AndrewWTaylor (talk) 18:31, 22 February 2015 (UTC)
Or, to put it more constructively: first get your work published in the usual way in a peer-reviewed mathematics journal, and then come back to this talk page with the publication information; we might or might not add it here but in any case it will be published in the journal for the world to see. —David Eppstein (talk) 19:44, 22 February 2015 (UTC)