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?

Clarifying Cycles[edit]

I'm confused by the section on cycles. It refers to increasing sequences of odd numbers as part of the definition, and yet it's impossible for there to be an increasing sequence of odd numbers since 3n+1 is always even for odd n. So if a_0 is odd, then a_1 will be even. If any subsequent a_i is odd, the next term will be even. So there is never a case where 2 odd numbers are adjacent; therefore, there can never be an increasing nor decreasing sequence of odd numbers. Additionally, adjacent even numbers will always be either in isolation or decreasing, so the use of the term decreasing there seems extraneous at best. Gramby (talk) 09:37, 6 January 2014 (UTC)

The shortened sequence where odd numbers (n) are replaced by (3n+1)/2 can have consecutive odd numbers. I think that's the context of the "cycles" section. — Arthur Rubin (talk) 17:27, 7 January 2014 (UTC)
Thanks Arthur. I'm not sure how I missed the first sentence introducing the (3n+1)/2 change. Gramby (talk) 13:13, 8 January 2014 (UTC)

Simplified construction[edit]

I removed a section which notes that, if the (3n+1)/2 process has k consecutive odd numbers, then the kth successive entry is:

\left(\tfrac 3 2\right)^k(n+1)-1.

Something like that might be said, if a reliable source can be found, but what was written was confusing. — Arthur Rubin (talk) 17:32, 7 January 2014 (UTC)

Yes, it can be concluded from the section you removed ;-) --Franz Scheerer (Olbers) (talk) 18:20, 8 January 2014 (UTC)
This is Wikipedia, not Wikibooks, Wikisource, Wikiversity, or Wiktionary. We need a reliable source for the information, and the websites using the name "Franz Scheerer" are not reliable. If you can find an actual reliable source, then the text description might be useful. The modified code is still not helpful, even if documented. — Arthur Rubin (talk) 21:22, 8 January 2014 (UTC)
I also removed the code change and the statements about 3n+1 ≈ 3n, as they are unsourced and do not seem helpful. — Arthur Rubin (talk) 01:03, 8 January 2014 (UTC)

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)

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)