Talk:Collatz conjecture/Archive 2

Archive 1

Archive 2

Archive 3

Collatz in Reverse

Hey everyone, I'm just going to throw out some ideas for topic 5.1. Working with the equation ${\frac {x-1}{3}}$ only equals an integer for results from $2(3x-1)$. There exist a full system of equations to explain how branching will occur (you'll have to excuse me, my area of greatest expertise is in graph theory so I treat it as such). Would these equations have to be published in a journal before posted to WP? Infonation101 (talk) 05:23, 11 April 2008 (UTC)

Yes, they would. See WP:NOR for details. That said, if your result is brand new, then you should publish it to get the credit you deserve. If not, then someone else has published it, and you can improve Wikipedia by finding the references and updating the article. So it's a really sensible policy, IMO.—GraemeMcRae^talk 14:05, 11 April 2008 (UTC)

Understood. I am writing a paper for a professor I know, but never considered myself someone able to develop equations that haven't already been discovered in an area under such scrutiny. I figured that someone had written about these, but I just hadn't been able to find them. For example, using the equations above if we insert $2(3x-1)$ in for $x$ in the equation ${\frac {x-1}{3}}$ the result is $2x-1$. A stupidly simple result to prove ${\frac {x-1}{3}}$ will only result in odd numbers. I'll keep digging for a paper written on this, and if I can't then I'll write something up myself. But if the latter is the case, the information will not be posted on WP for a while yet. Regardless, thank you for your response. I wasn't sure about the WP:NOR policy when making algebraic derivations. Infonation101 (talk) 18:59, 11 April 2008 (UTC)

Look at the main article under "As a parity sequence" and the related section "Iterating on rational numbers with odd denominators". The parity sequences discussed can, of course, be played in reverse giving you similar equations. Also, check the references for "Blueprint for Failure: How to Construct a Counterexample to the Collatz Conjecture". In that paper (by yours truly) is an equation system similar to the parity sequences. The elemnts are simply counts of n/2 operations, so the parity sequence {10100100010000} would be [1,2,3,4]. The equations happen to done from the reverse viewpoint. ALL sequences have the function g=(X*a - Z)/Y where, given the sequence sv,

 X = 2**sum(sv)
 Y = 3**len(sv)
 Z = sum of, (3**index(sv) * 2**sum(sv[:-(len(sv)-index(sv))])
 so [1]   is (2**1*a - 3**0*2**0)/3**1 or (2*a-1)/3
    [1,2] is (2**3*a - (3**0*2**1+3**1*2**0))/3**2 or (8*a-5)/9

Your exact function cannot be exactly described as you don't do a n/2 operation (required in my system). But in general, such reverse formulations have been studied before by myself and others. Perhaps this will give you something to look for ("Diophantine Equation" might be a useful keyword). --Mensanator (talk) 00:18, 12 April 2008 (UTC)

Thanks, I'll look into that. Infonation101 (talk) 22:03, 12 April 2008 (UTC)

What about changing the terminology from graph to digraph. It seems more appropriate and specific to the graph being created. Infonation101 (talk) 04:20, 15 April 2008 (UTC)

I don't know about that. All I know is that someone objected to the use of "tree" as a tree, by definition, is acyclic and that "graph" should be used. With "disconnected" in reference seperate components which comprise the graph. I assumed he knew what he was talking about. I certainly don't as I have no degree in graph theory.--Mensanator (talk) 06:35, 15 April 2008 (UTC)

Mensanator, you seem to be an expert in parity sequence. Honestly I don't understand how that works exactly, but graph theory and discrete modeling happens to be my strongest field of study. I would recommend that it is a digraph, and not just a graph. Graph can refer to one of many types of graphs, such as a pseudograph. If we were to exclude the {1,2,4} circuit then it could be considered a tree, but in reference to the entire structure that can't be done. If it matters, I could type up a prototype subarticle to explain the Collatz conjecture in terms of graph and set theory. Infonation101 (talk) 19:30, 15 April 2008 (UTC)

"Seem to be" is probably appropriate here as I'm self-taught about parity sequences (the theory (Sequence Vectors) is explained in the beginning of my paper I referenced earlier if you're interested). I was just pointing out that I won't object to calling it a digraph if that's the proper graph theory terminology. As long as the terminology relates to the case in point. For example, sometimes the graph shows only the odd integers, in which case the {1,2,4} cycle becomes a loop at {1}. This then becomes a pseudograph? And I would never exclude the cycle because that becomes extremely important when you use the negative domain or the 3n+C extensions. For that matter, I would like to know the proper terminology for when the graph components are unconnected (is even that the correct terminology?) as in the negative domain for 3n+1 or in then positive domain for 3n+5. And for the cycle of every component, is there a term for it's smallest magnitude node (such as 1 for {1 4 2 1 ...} or -17 for {-17 -50 -25 -74 -37 -110 -55 -164 -82 -41 -122 -61 -182 -91 -272 -136 -68 -34 -17 ...}? Someone I was working with used attractor although this isn't what is normally meant by that word. A subarticle spelling out proper graph theory terminology sounds like a good idea to me. --Mensanator (talk) 00:34, 16 April 2008 (UTC)

I'll get working on it. I'm in finals right now so it might take me a little while, also because I have OCD tendencies I'll revise it probably a dozen times. Doing this actually intrigues me because a general theory for the 3n+C could be created that would expand into the entire integer set. This could get intense. I'm going to revise your paper and use the equations there and in other reliably posted sources to define the graph. And I believe you would be correct about a loop at 1, from 1. As for the definitions, I'll make sure to explain each term I use so that there is no ambiguity. Infonation101 (talk) 02:05, 16 April 2008 (UTC)

Do you know that this is not the place for this discussion? Please use your talk page to write down calculations. Here are using this to improve the article by adding references, etc not by... solving the problem! -- Magioladitis (talk) 07:54, 16 April 2008 (UTC)

Forgive us. The calculations at the top of the section I was proposing to post in the article, and the later discussion has been how to improve the section of the article dealing with subsection 5.1. By no means are we attempting to solve the problem. We're both aware of the complexity of finding a solution to this problem, and only have we been discussing how to improve the explanation of the problem. Sorry you didn't see that. Hence the comments like, I could type up a prototype subarticle to explain the Collatz conjecture in terms of graph and set theory and What about changing the terminology from graph to digraph. Infonation101 (talk) 16:45, 16 April 2008 (UTC)

Invalid links

Hi, In the Syracuse function part, there are a few invalid links, like

http://www.geocities.com/dwakeel/syracuse.htm :

1, 3, 5, 7, and 9 are known to exist in E. Let k be an odd integer greater than 9. Suppose that the odd numbers up to and including k - 2 are in E and let us try to prove that k is in E. As k is odd, k + 1 is even, so we can write k + 1 = 2^ph for p ≥ 1, h odd, and k = 2^ph-1. Now we have:

• If p = 1, then k = 2h - 1. It is easy to check that f (k) < k , so f (k) ∈ E; hence k ∈ E.
• If p ≥ 2 and h is a multiple of 3, we can write h = 3h′. Let k′ = 2^{p + 1}h′ - 1; we have f (k′) = k , and as k′ < k , k′ is in E; therefore k = f (k′) ∈ E.
• If p ≥ 2 and h is not a multiple of 3 but h ≡ (-1)^p mod 4, we can still show that k ∈ E. (Cf.)

The problematic case is that where p ≥ 2 , h not multiple of 3 and h ≡ (-1)^p+1 mod 4. Here, if we manage to show that for every odd integer k′, 1 ≤ k′ ≤ k-2 ; 3k′ ∈ E we are done. (Cf.).

I don't understand why if p ≥ 2 and h is not a multiple of 3 but h ≡ (-1)^p mod 4, we can still show that k ∈ E. (Cf.)

And why if we manage to show that for every odd integer k′, 1 ≤ k′ ≤ k-2 ; 3k′ ∈ E we are done

Dave Couptily (talk) 21:47, 7 May 2008 (UTC)

a layman's presentation

I cannot claim a great insight in the conjecture, but on the first time I heard about it, it was presented as the simple formula below. I find it makes a much more intuitive presentation of the question. Could we consider stating the question in those terms in the introduction?

given a strictly positive integer I, consider the arithmetico-geometric sequence U defined by:

 U(0) = I
 U(j) = (3*U(j-1) + 1)
 Conjecture: there always exist two positive integers N and K such that 
 U(N) = 2**K

This presentation is incorrect. You're not doing any divisions by 2 until you reach N, thus, this algorithm is invalid.

(after you've reached N, then you can keep dividing by 2 until you reach 1, so the only difference is a permutation in the sequence of 3*n+1 and n/2)...

But you're not doing any n/2.

I don't do the divides by two because they are superfluous for stating the core issue, they are only here to make calculations tractable. My claim though, is that Collatz' (ungeneralized) original conjecture is thus not minimally formulated, which does not help making the problem accessible to a layman.

This formulation is strictly equivalent to the conjecture, but I find it much simpler and accessible to 12 year old students, as it does not reference a "if U(j) is odd then... else..."

Every problem has a solution that's simple, elegant and wrong.

by using the big "W" word, are you suggesting the conjecture above and Collatz' (ungeneralized) conjecture are not equivalent? If so, can you show why? It seems trivial to me that they imply each other. If it's not trivial to you, then I may expose a proof if you want (note: it just consists in rearranging the terms of the sequence to obtain the ai sequence mentioned in the article).

The correct equivalent sequence would be n -> 3n+2^k where 2^k is the highest power of 2 dividing n. As soon as you reach an even number (which is fast since your sequence alternate parities), your sequence becomes unrelated to the associated Collatz sequence.Idura (talk) 08:13, 3 July 2008 (UTC)

Sorry, indeed I mixed it up (shouldn't trust my memory, and still can't find my notes)! I still would like to get rid of the parity test, because I find it's just a convenience for calculation, not something actually needed to state the problem. Would this work out?

Idura's comment is incorrect also. What you want is

       U(j+1) = (3*U(j) + 1)/2^k

To avoid talk of "parity", simply define k as "the position of the Least Significant 1-bit of the binary representation of (3*U(j) + 1)". In Python, using the GMP math library, this is easier to implement than to state:

       # Python
       from gmpy import scan1 # find LS 1-bit
       ...
       U(j+1) = (3*U(j)+1) >> scan1((3*U(j)+1)) # >> means right shift 

Using the proper definition of k, all U(n) will be odd numbers, so there is no need to speak of evens. You don't even need the U(N) = 2^K as it is a special case of the above. Of course, you'll never see any power of 2 except 2^0. But you can say "there is an N such that U(N) has an alternating binary bit pattern (101010...10101)". All powers of 2 have such a number as their predecessor via (3n+1), which you'll always see even though you won't see the actual power of 2. Of course, only powers of two with even k can have such a predecessor. That doesn't invalidate the above, just a comment.

It is, however, still a non-rigorous definition since it only applies to 3n+1. The rigorous definiton would be something like:

    For any 3n+C system, there exists an N such that U(N) enters the trivial loop cycle {C, 4C, 2C, C}
    whose Sequence Vector is [2].
    Conjecture: the trivial cycle [2] is the only cycle in the positive domain

See? No mention of powers of two or stopping at 1. It applies universally. If you don't understand the above, you don't understand Collatz. And need I point out that the Collatz Conjecture is simply when C=1?

given a strictly positive integer I, consider the sequence U defined by:
 U(0) = I
 U(j) = 2*(3*U(j-1) + 2^(j-1))
Conjecture: there always exist two positive integers N and K such that 
 U(N) = 2^K

There are more iterations before reaching N in this sequence than in the equivalent Collatz sequence, because we multiply by 2 regardless of the parity of U(j), but I think this time it's correct...

It's still wrong, see above.

—Preceding unsigned comment added by 81.80.159.49 (talk) 09:13, 3 July 2008 (UTC) 

Also it indicates that the goal is to show that even though the powers of two are less and less dense as numbers increase, you'll eventually always reach a power of two by keeping the sequence 3N+1...

I am clear?

No. This "power of two" thing doesn't apply in the extension 3n+C (of which 3n+1 is a special case). To understand why & when Collatz works and why & when it doesn't, you need more rigorous (and correct) definitions. At least you're doing the right thing discussing it here before making any change to the main article. --Mensanator (talk) 00:11, 3 July 2008 (UTC)

Where in the article (or elsewhere) is this "3n+C" extension mentioned?

It's not in the article because Wikipedia has rules about "no original research". Haven't you noticed the banner at the top of the article complaining about lack of citations? You can't just shove stuff into the article unless you can give a proper citation. To me, this isn't necessary since math is self-evidently true and so doesn't depend on the Appeal To Authority Fallacy that Wikipedia is built on. But I don't make the rules here. To answer your question, see the References section. specifically, this one: * Paul Stadfeld: Blueprint for Failure: How to Construct a Counterexample to the Collatz Conjecture --Mensanator (talk) 17:24, 3 July 2008 (UTC)

—Preceding unsigned comment added by 86.67.3.169 (talk) 20:43, 2 July 2008 (UTC)

Another way to solve Collatz Conjecture

Well, I've found an alternative way to solve the conjecture, but I need some mathematic assistment to prove or deny it. If anyone is interested, you can contact me at my mail, (tukovial@hotmail.com), I'll be glad to answer you and receive your opinions.

Arturo Vial Arqueros. —Preceding unsigned comment added by 201.236.170.245 (talk) 03:16, 5 October 2008 (UTC)

Alan Tyte's "proof"

Discussion moved to Mugbuff's talk page. This is not a forum. Any discussion about the editor's ideas can be held there. Thanks for the understanding. -- Magioladitis (talk) 09:22, 27 March 2009 (UTC)

Further information: User talk:Mugbuff

Ultra Fractal formulas for those that want to play with the fractal version

Collatz_mandel { ;20081027
;Made by Mark Jeronimus [email address redacted]
;© 2008 Mark Jeronimus
global:
init:
  #z=#pixel
  if @optimized
    float mul = real(@muladd)
    float add = imag(@muladd)
  else
    float mul = real(@muladd) * 2
    float add = imag(@muladd) * 2
  endif
loop:
  complex p = #pi/2*#z
  #z = ( ((mul+1)*#z+add) - ((mul-1)*#z+add) * cos(p*2) )/4
bailout:
  |#z|<@bailout
default:
  title="Collatz Mandelbrot"
  center=(0,0)
  magn=0.3
  periodicity=0

  param muladd
    default = (3, 1)
  endparam
  param optimized
    caption = "Optimized version"
    default = true
  endparam
  param bailout
    caption = "Bailout"
    default = 1000
  endparam
switch:
  type = "Collatz_julia"
  start = #pixel
  optimized = @optimized
  bailout = @bailout
}

Collatz_julia { ;20081027
;Made by Mark Jeronimus [email address redacted]
;© 2008 Mark Jeronimus
global:
init:
  #z=@start
  if @optimized
    float mul = real(#pixel)
    float add = imag(#pixel)
  else
    float mul = real(#pixel) * 2
    float add = imag(#pixel) * 2
  endif
loop:
  complex p = #pi/2*#z
  #z = ( ((mul+1)*#z+add) - ((mul-1)*#z+add) * cos(p*2) )/4
bailout:
  |#z|<@bailout
default:
  title="Collatz Julia"
  center=(0,0)
  magn=0.3
  periodicity=0

  param start
    caption = "Perturbation"
    default = (0, 1)
  endparam
  param optimized
    caption = "Optimized version"
    default = true
  endparam
  param bailout
    caption = "Bailout"
    default = 1000
  endparam
switch:
  type = "Collatz_mandel"
  muladd = #pixel
  optimized = @optimized
  bailout = @bailout
}

Ultra Fractal version 4.0 or newer required. —Preceding unsigned comment added by 87.212.178.246 (talk) 15:56, 27 October 2008 (UTC)

Time

Is there also a table where not the stopping time but the time until a smaller number is reached is listed? Such a table would surely be quite useful, as this time obviously depends on congruencies (f.x. all even numbers have it at 1 and all numbers 1 mod 4 at 3). I think it's worth a try to search for dependancies between conguencies and this time. Another thing I'm interested in is the difference between the starting number and the first smaller number in the sequence(in the two listed cases above it obviously always grows by 1 with the next number)--Alexmagnus2 (talk) 11:53, 26 February 2009 (UTC)

Check out Eric Roosendaal's site. I don't quite remember his terminology and may be confusing someone else's (I appologize if I got some of this wrong), but there is stuff like

 '    excursion
 '       /\
 '      /  \
 'start/    \glide
 '           \
 '            \
 '             \/\
 '                \  /\
 '                 \/  \
 '                     stop

When considering only odd numbers in the sequence, the number of growth steps depends on how many contiguous 1 bits are in the binary representation. Thus, Mersenne numbers show spectacular growth before they ever hit a smaller number. But they decline almost as rapidly, such as the diagram I drew and thus, rarely becoming stopping time record setters. Although they have typically twice the mean stopping time per bit as that of a random bit pattern, actual record settters can achieve 10-12 times that of the random bit pattern. For example, the Mersenne number 2**177149 - 1 will diverge for 177149 consecutive odd values at which point the excursion is reached (and the excursion's bit count can be predicted). And you can predict how long the glide will last (at which point the number falls below it's initial value). Of course, bit patterns other than all 1's behave differently. Stopping time record setters typically have less intense growth and less intense declines (the graph has a shallower slope). So although the excursion tends to be lower, the glide tends to me much longer producing a larger total stopping time. A lot of interesting facts can be gleaned from studying Collatz in binary. --Mensanator (talk) 00:08, 27 February 2009 (UTC)

The glide times is what I need. On the page I see the glide records but not the glide times for each number...--Alexmagnus2 (talk) 14:05, 28 February 2009 (UTC)

My guess is that he has a database with the Glide values for all the n he has tested. It certainly doesn't surprise me that he doesn't make such data available. If _I_ were running such a project, I would reward the volunteers with access to that data. Maybe you should write him and ask (you may have to join his project and do work). The worse that can happen is he'll say no. And I have reason to believe, from the testing I've done, such data won't reveal any magic formula that will tell you the Glide for a given number. --Mensanator (talk) 01:54, 1 March 2009 (UTC)

Oneness

Oneness (mathematics) redirects to this article. Why? --HelgeStenstrom (talk) 08:07, 16 March 2009 (UTC)

See this content before redirection, and see Wikipedia:Articles for deletion/Oneness (mathematics). PrimeHunter (talk) 13:04, 16 March 2009 (UTC)

Is it of interest that if you start with (2^j)*k-1 the sequence of odd integers increases for j-1 steps before a decrease occurs, thus a glide as long as you want can be created by making j large enough ? Mugbuff (talk) 20:22, 21 May 2009 (UTC)

Sure, it's of interest, although you've only given the number of steps to the excursion. To get Oneness, you also need to know how long the glide actually is. For example, using k=1 (such that we're talking about a Mersenne Number), the bits remaining at the excursion have a Negative Binomial (Geometric) distribution of ones & zeroes, just as a random binary pattern does and the glide will behave statistically like that of a random pattern. And such a pattern is predicatble because the mean of a Geometric distribution is the inverse of its probability. Thus, at the excursion, the number of bits will be j*1.585. Summing the length of the excursion + glide means you can predict the Oneness of a Mersenne Number: [1] (here, "Cycles" means count of odd numbers, to get Oneness, you have to also count how many evens, one for each odd in the excursion plus two for each odd in the glide). As you can see from the graph, statisics rarely gives you exact results, but it does exhibit punctured equilibrium and tracks the red curve. When j is large, say 177149, the prediction is acurate to 2%.

So the criticsm here (from the above mentioned redirection discussion): <quote> What's described here as "oneness" is the number of steps it takes to reach the number 1, and a link is given to suggest that that pattern can't be predicted. </quote> is a bit naive.

Furthermore, Oneness doesn't apply to Collatz extentions 3n+C, where the loop cycle is 4C, 2C, C. --Mensanator (talk) 17:23, 23 May 2009 (UTC)

Buggy C++ code not needed

Has anyone actually tested the C++ code in the article? The test,

num = (num % 2)?

looks like an assignment rather than a test to me, and even if it were changed to

num == (num % 2)?

it wouldn't test the right thing. To my eye, it looks like that test should be changed to

num == (num % 2)*2?

Even if the C++ program that is provided here works, isn't it original research? Also, if some random C++ coder can update this article to provide C++ code (even if it works), doesn't that mean it's not really necessary, given the pseudocode is already in the article, and explains the algorithm pretty clearly?

It is my understanding that it's a Wikipedia policy to present such algorithms in pseudocode, although I don't remember where I read that. --Mensanator (talk) 17:29, 21 June 2009 (UTC)

Not being sure of the answers to these questions, I'll leave the article alone for now. If someone is more sure (and agrees with me that the whole C++ stuff should be deleted) then I'll look forward to a WP:Bolder person than me removing that part of the article! Thanks.—GraemeMcRae^talk 16:05, 21 June 2009 (UTC)

It's an assignment but you are only quoting part of the expression in the assignment:

num = (num % 2)? (3*num + 1) : (num / 2)

?: has higher precedence than = so it's equivalent to:

num =((num % 2)? (3*num + 1) : (num / 2))

In other words: If num % 2 is non-zero (meaning that num is odd) then assign num = 3*num +1, else assign num = num/2. See ?:#Conditional assignment. PrimeHunter (talk) 16:38, 21 June 2009 (UTC)

Ahh! I get it now. Thanks, PrimeHunter. My question remains about whether C++ code is really needed in this article. The Pseudocode explains the algorithm clearly, and as my misunderstanding of the C++ shows, the C++ code is a bit harder to fathom, and seems a lot like original research.—GraemeMcRae^talk 17:24, 21 June 2009 (UTC)

Removing the C++ code would be OK by me, but the connection to the halting problem seems better when an actual program is given. PrimeHunter (talk) 23:18, 21 June 2009 (UTC)

Unclear Formulas

In section "Other formulations of the conjecture" there is "2n,(n+1)/3" what does the comma mean? —Preceding unsigned comment added by 75.196.98.221 (talk) 19:12, 19 August 2009 (UTC)

I don't know whether it's common notation for relations but here it means that n has incoming edges from both 2n and (n+1)/3 in the collatz graph. PrimeHunter (talk) 00:31, 20 August 2009 (UTC)

Oh, you must have made a typo as there is no "2n,(n+1)/3". There couldn't be, as "(n+1)/3" is not the inverse of "3n+1". Obviously, you meant "2n,(n-1)/3", which is what's actually written in the article. --Mensanator (talk) 01:24, 20 August 2009 (UTC)

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)

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)

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)

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)

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)

That brings up the issue of which language to use. Since there can be no agreement, should we just include one of each? No. Read the guidlines of Wikipedia. It says somewhere (I don't recall exactly where) that code examples should always be in pseudocode. And I looked up a pseudo-code standard before posting that version.--Mensanator (talk) 00:55, 6 March 2010 (UTC)

Implementing the calculation in a bunch of different languages is very much on topic on Rosetta Code, so I've copied the programs to a page for the Collatz conjecture there. I notice that since the removal, 66.223.56.164 has (without attention to markup) restored the programs and added a bash version. Perhaps a link to the programs on Rosetta Code would be a good compromise? — Kevin Reid | 72.228.72.196 (talk) 19:07, 6 March 2010 (UTC)

No, it wouldn't add value to the article. Also, i'ts only indirectly related to this subject. → Adrian Lozano (talk) 23:48, 6 March 2010 (UTC)

Is convergence the right word?

Actually, the series can not converge to 1. 1 ist odd, so after 1 follos 4, 2, 1, 4 ..., what means that the series does not converge, but only that 1 (an 2 and 4) is a accumulation point of the series. 84.176.188.98 (talk) 14:17, 6 March 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)

It wasn't bold when I originally found the article. It certainly shouldn't be bold. Metao (talk) 06:54, 8 March 2010 (UTC)

This article has been hit pretty hard in the last few days, hasn't it? Personally, I see no reason to even mention the phrase "over 9000," since it's just an internet meme and not at all relevant to the article, but I don't see anything wrong with saying that the maximum value it reaches is 9232 (or to put that term in bold). 67.162.113.118 (talk) 02:33, 7 March 2010 (UTC)

collatz for negative integers

Given that collatz works for positive integers by using 3n+1, then shouldn't collatz for negative integers be 3n-1?

No. Collatz states the sequence always reaches +1. Negative numbers in 3n-1 always reach -1, not +1.

If you do positive integers with this version (i.e. f(odd n) = 3n+sgn(n)*1 ) your numbers would fall into the same patterns as the stated generalized corollary for negatives, but positive.

That's why we don't say "always reaches +1", we say "always reaches the Sequence Vector [2]" which is invariant, structure-wise. Thus, with 3n+1 we say the loop cycles are at:

 negative domain                   positive domain
 [1] [1,2] [1, 1, 1, 2, 1, 1, 4]   [2]

whereas in 3n-1 the loop cycles are at

 negative domain                   positive domain
 [2]                               [1] [1,2] [1, 1, 1, 2, 1, 1, 4]

Note that the loop cycles are always the same structure, but [2] is only a loop cycle in the positive domain of 3n+1 OR in the negative domain of 3n-1.--Mensanator (talk) 00:43, 9 March 2010 (UTC)

—Preceding unsigned comment added by 174.46.204.210 (talk) 19:44, 8 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)

I checked this for over 1,000,000 iterations and it just kept getting larger (still doesnt prove it diverges though (and yes i realize theres a counterexample below this, i was just curious))M00npirate (talk) 05:25, 11 March 2010 (UTC)

One way to look at it is the fact that even numbers have a Negative Binomial (Geometric) distribution. The mean of a Geometric distribution is the inverse of the probalility, therefore, even numbers will have a mean of two n/2 operations between odd numbers. That results in division by 4 which cannot overcome the multiplcation by 5, so the series tend to diverge. By the same argument, we expect 3n+1 to converge since division by 4 overcomes multiplication by 3, it's just we have to prove there's no case where it hits a loop cycle other than 4-2-1-4. There's no point in making that check for 5n+1 since we have examples that run off to infinity.--Mensanator (talk) 01:17, 6 March 2010 (UTC)

That's not quite right.

It doesn't have to be. Read the article, that's what "A probabilistic heuristic" means. It's still valid even though it makes no sense when considering loop cycles.

You'd still have to show that 5x+1 didn't inevitably hit 2^y power (where y is arbitrary).

And that would be a problem to prove 5x+1 True. But it suffices to show a single counterexample to demonstrate it's False.

This would instantly result in the number going straight to 1. It's not impossible that 5x + 1 has some law that makes it always pass through 2^y

Yes, it is quite impossible for such a law to exist.

(I feel pretty comfortable that it doesn't).

Here's the counterexample: 5 26 13 66 33 166 83 416 208 104 52 26

QED

--Mensanator (talk) 01:58, 9 March 2010 (UTC)

216.136.12.169 (talk) 14:05, 8 March 2010 (UTC)

Proof of Collatz?

http://arxiv.org/PS_cache/arxiv/pdf/1002/1002.3973v1.pdf

Abstract: It is shown that there is no non-trivial cycle and divergent cycle in the Collatz sequences, or frequently called 3x + 1 mapping . This proves that the conjecture by Collatz is true.

Can anyone verify this? —Preceding unsigned comment added by 82.44.152.23 (talk) 23:56, 6 March 2010 (UTC)

No.--Mensanator (talk) 02:10, 7 March 2010 (UTC)

in news:sci.math I have recently shown an error in lemma 2.4. A formula, from which he derived the argument for impossibility of a loop was wrong, so this whole approach was insufficient to disprove the possibility of a cycle. (don't have the link for google-groups at hand, look for "helms" and "collatz" in a thread initiated by gerry myerson) Gottfried Helms --Gotti 08:33, 11 March 2010 (UTC)

How to insert reference fom google-groups?(Steiner-"fact")

Hi -

today I observed, that my remark concerning R.Steiner's m-cycle-theorem needs verification by some tag: "((fact))" I've found the msg in sci.math.research using google-groups. Here is the link of the article: http://groups.google.de/group/sci.math.research/msg/d40067154180694f?hl=de which was part of a thread of mine.

Don't know how to supply that link in the article. (Also I corrected: in that msg Steiner claims to be able to disprove m=71-cycles, (not m=72 as I wrongly wrote))

(update: in an update-article (online, not known whether it is published) Simons/deWeger extend their proof to m=76 due to new numbers a0 shown to be converging by computer-aided numerical checks)

Gottfried Helms —Preceding unsigned comment added by Druseltal2005 (talk • contribs) 13:41, 10 March 2010 (UTC)

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)

No. You just want an excuse to put the xkcd strip on this article. There is no reason to add a "references in pop culture" section just for that. Xkcd fans are already a plague that attempts to include a strip in every Wikipedia page. Flintmecha (talk) 20:28, 12 March 2010 (UTC)

Agree. Xkcd should be blacklisted, and only whitelisted by request. OhNoitsJamie ^Talk 20:44, 12 March 2010 (UTC)

"Xkcd fans are already a plague that attempts to include a strip in every Wikipedia page."? That's a lazy generalisation, at best. Julianhall (talk) 12:14, 15 March 2010 (UTC)

I'm not sure I agree with the absolute nature of that statement. xkcd isn't inherently bad or un-notable. The issue arises where people who read xkcd automatically jump to Wikipedia to find the definition of something they had never heard of before, and then decide to add the xkcd reference either because they believe it merits mention or because they honestly believe that it is the most notable thing to ever happen to something (see page histories and discussions over topics ranging from the Voynich manuscript to the fast inverse square root to the article on wood (note also that the comic focus shifts on them: Voynich was the entire point of an xkcd comic, whereas InvSqrt() was apparently a title tag attribute on one of the comics, and the wood one doesn't really need to be explained except to say that when xkcd shows a Wikipedia page, expect that page to actually look like that for a couple of seconds at least). I don't love the "In Popular Culture" sections at all, but there are a small few instances where xkcd should be mentioned. This isn't one of them: believe it or not, the best thing that ever happened to the Poisson distribution or Fermat's Last Theorem wasn't being mentioned by xkcd. 67.162.113.118 (talk) 05:14, 15 March 2010 (UTC)

I totally agree with this comment. Julianhall (talk) 12:14, 15 March 2010 (UTC)

On "Iterating on all integers"

Is the sequence 0 -> 0 properly a "cycle"? I don't consider it as such because it does not contain an odd number.

Furthermore, that notation [7](18) seems worthless to me, i.e., has no value. Simply knowing how many evens there are isn't good enough, you need to know the distribution of the evens. For instance, there are a lot of ways to partition 11 evens amongst 7 odds, but only [1, 1, 1, 2, 1, 1, 4] (or one of its cyclic permutations) will give you a loop cycle. Of course, you would need to know how to exploit the distribution to learn anything, but that's easily doable. Note that [1, 1, 1, 2, 1, 1, 4] has 7 numbers that sum to 18. One can do calculations similar to the Parity Vector (this notation is just a compact version with the restriction that the sequence must begin with an odd number). And once we have the resulting function, we can determine whether the partition is a loop cycle without needing to evaluate the sequence. Can't do that with [7](18). I would like to change that to make it useful. Any support?--Mensanator (talk) 00:37, 21 March 2010 (UTC)

m-cycles

These edits are invalid. Although true that "there is a finite number of integers with infinite divergent trajectories", the finite numer has to be 0. Necessary But Not Sufficient. Likewise, for "there is a finite number of integers with cyclic trajectories", it is only sufficient if that finite number is EXACTLY 1. --Mensanator (talk) 23:32, 14 April 2010 (UTC)

Should M. Brushi article be removed?

The article by M. Bruschi is short, doesn't really add much, and is self-published on Xarchive, not reviewed and published in a journal. —Preceding unsigned comment added by 77.212.188.168 (talk) 23:46, 17 April 2010 (UTC)

On the almost sure convergence of Syracuse sequences

This paper is bogus. The statement "our main assumption here is that, at each play, the Syracuse gambler has equal chances of winning or losing a bet," is outright false. Even numbers do indeed always follow odds, but NOT with equal probability. Even numbers follow the odd integers in a Negative Binomial (Geometric) distibution so the mean number of consecutive evens wiil be the inverse of the probability, therefore, the mean count of consecutive evens will be 2, and thus, not equal to the odds. There is no point continuing any further since all subsequent calculations are based on a fallacy. Links should be deleted.--Mensanator (talk) 17:26, 9 April 2010 (UTC)

After reading the paper (see Discussion section),

This IS the discussion section. What are you talking about?

I was talking about the discussion section in the paper

I find that the assumption can be justified. The assumption has been made taking into account the fact that if one starts at a random point (a number n), there is a 50% chance that this number is even and a 50% chance that it is odd. In other words, if N is the set of natural numbers, the assumption was made so that if one selects a number n, it is equally likely to be even as to be odd.

Ok.

From there,

...you get in trouble.

n will either undergo the operation of 3n+1 or the operation of n/2 (depending on whether it was even or odd). There is therefore a 50% chance that a_n will become n/2 and 50% chance that it becomes 3n +1.

False. The SUCCESSOR does NOT have the same probability as N. Is there a 50% probability that the successor of an odd number will be even? No, the probability is 100%. Is there a 100% probability that the successor of an even number will be odd? No, sometimes, but not always. If you don't understand this, you are a sucker for any crackpot who posts a bogus paper.

There is no reason to insult me I am only discussing the paper and giving my point of view.

Sorry, there is a subtle distinction between ignorance and stupidity and my intent doesn't always come across (ignorance is not an insult).

From what I understood is that if we pick a number N and given the fact that it is equally likely to be even as it is to being odd, there is therefore 50% that the next number will be n/2 and 50% chances that it will be 3n+1 (we pick a random number, it is either even or odd. If it is even it will become n/2 if it is odd it will become 3n+1). Now maybe I'm wrong and there is no problem with that.

Yes, you are wrong. The FIRSTnumber may be chosen randomly, but to be a sequence that converges, the subsequent numbers are NOT random. Random(n),Syracuse(n),Random(n),Syracuse(n),Random(n),Syracuse(n),Random(n),Syracuse(n),Random(n),Syracuse(n) is not a Syracuse SEQUENCE, let alone converges. And even if it was, you wouldn't end up with a 50/50 split. 50% of the Random(n) are even, but not 50% of the Syracuse(n) are even. It doesn't work even when you do it wrong. To get a converging Syracuse sequence, the terms would be Random(n),Syracuse(n),Syracuse(Syracuse(n)),Syracuse(Syracuse(Syracuse(n))),etc. And you STILL won't get a 50/50 split. You cannot make it work whether you do it correctly or incorrectly. And yes, there is a problem with that.

I did not publish the paper and I am in no way related to the person who did. So please be more respectful.

Ok, I apologize. But it's just as easy to get this right, you know.--Mensanator (talk) 18:31, 15 May 2010 (UTC)

In the discussion, it has even been shown that the results remain the same if we change the probability of having an even number and having an odd number.

Nothing of the kind has been shown. What's been shown is that a Collatz sequence will always have more even numbers than odd.--Mensanator (talk) 23:08, 14 May 2010 (UTC)

Function at the bottom

The last section is about the Syracuse function, but provides no explanation of context. According to the link, it will, if I read the inline linked source correctly, produce the number or iterations taken for odd number N. Maybe we should explain that, and possibly state how many iterations it must go out to before it becomes efficient to take N mod 2 of every number.

Oh, and am I going blind, or does it contain the Mandelbrot set? Do all fractals do that, or is it worth noting?

71.234.123.137 (talk) 22:18, 23 May 2010 (UTC)

better psudo-code?

function collatz(n)
  while true
    show n
    if n is odd then
      if n = 1 then endwhile
      set n = 3n + 1
    endif
    set n = n / 2
  endwhile
  show n

checking if it's 1 when it's even is pointless, also, no matter what, when it's odd, it's going to be even after, so it should fall through to the even operation. --96.237.247.231 (talk) 01:10, 17 July 2010 (UTC)

These are optimizations. They are not particularly relevant to the explanation of the algorithm. We should present the pseudo-code that best describes the algorithm, not necessarily the most optimized version. Cheers, — sligocki (talk) 05:24, 17 July 2010 (UTC)

Personally I'd prefer:

function collatz(n):
  while n != 1:
    show n
    set n = collatz_step(n)
  endwhile
  show n

function show(n):
  if n is odd then:
    return 3n + 1
  else (if n is even):
    return n / 2
  endif

because it delineates the fact that we are applying a step function repeatedly until we reach 1, but it's just an opinion. Cheers, — sligocki (talk) 05:31, 17 July 2010 (UTC)

Section "Iterating on all integers"

Why omit the even numbers and have lots of blurb explaining it? It strikes me that for the few numbers required, a simple list is easier to understand and doesn't really take up much space. I offer the section as an example below.

An obvious extension is to include all integers, not just positive integers. Interestingly, there are in this case a total of 5 known cycles, which all integers seem to eventually fall into under iteration of f. These cycles are listed here, starting with the well-known cycle for positive n.

Odd values are listed in bold. Each cycle is listed with its member of least absolute value first - which value is always odd. We follow each cycle with …, its [odd value cycle length] in square brackets and its (full cycle length) in parentheses.

1. 1 → 4 → 2 → 1 … [1] (3)
2. 0 → 0 … [0] (1)
3. −1 → -2 → −1 … [1] (2)
4. −5 → -14 → −7 → -20 → -10 → −5 … [2] (5)
5. −17 → -50 → −25 → -74 → −37 → -110 → −55 → -164 → -82 → −41 → -122 → −61 → -182 → −91 → -272 → -136 → -68 → -34 → −17 … [7] (18)

The Generalized Collatz Conjecture is the assertion that every integer, under iteration by f, eventually falls into one of these five cycles.

- - - - - - -- SGBailey (talk) 14:44, 4 June 2010 (UTC)

Dubious proofs added

This section will be for any "proofs" added or argued for being in the article. If the proposal doesn't exist in academia, the discussion may be better sent to the mathematics Reference Desk.

A proof by Meier Franz-Xaver was added and reverted three times by User:Rudiwiki1234 without source. The proof paper is linked in the edit at a sites.google page. A simple Google/Google Scholar search indicates that Meier Franz-Xaver does not seem to exist, on general internet mathematics or in academia. Of course, he may simply be a brilliant Ph.D. student or dropout somewhere - the paper, despite being six pages, uses grad-level mathematics concepts, it seems. Discussion moved to RefDesk. SamuelRiv (talk) 05:20, 16 June 2010 (UTC)

I've removed as WP:Original research, it doesn't matter if it is correct or not. Dmcq (talk) 09:18, 16 June 2010 (UTC)

The first numbered equation looks wrong to me. I have, somewhere, an extensive bibliography of the subject. Rich Farmbrough, 14:06, 16 June 2010 (UTC).

In the past we had a published proof in the article which I reverted because the magasine wasn't a proper scientific magasine on the area. From Wikipedia:Verifiability#Exceptional claims require exceptional sources:

• "Certain red flags should prompt editors to examine the sources for a given claim:
  • surprising or apparently important claims not covered by mainstream sources;

So any attempted proof has to be immediately removed until the scientific society accepts it. This is an encyclopedia, not the news nor place to upload original research. -- Magioladitis (talk) 14:35, 16 June 2010 (UTC)

A little research finds a serious error on page 1. There is no claim nor proof that the relations (1) through (6) generate all the relationships between the named maps. (Contrary to Rich's assertion, I believe them to be correct.) That's another reason why we should wait for a surprising result to be published in a peer-reviewed journal. — Arthur Rubin (talk) 15:21, 16 June 2010 (UTC)

Does the paper explicitly claim they do? I scanned through the thing, and it looked to me like too much work to verify all the claims that are given without proof. I also thought about the likelihood of additional relations on the generators, but the paper never seemed to mention it explicitly. The first place I was concerned was on p. 2 when the author claims the length of an element is well defined: that seem to require characterizing all the relations on the monoid. — Carl (CBM · talk) 15:29, 16 June 2010 (UTC)

That those are the only relations is implicit in the claim of the monoid involution.

The length of an element is well-defined; any monoid element corresponds to a function of the form n → A n + B, where A = 2^a3^b, (with a and b nonnegative) and 0 ≤ B < A. The length of any such element is a+b.

For any such function, and any choice of the order of b α/β/γs, and a φ/ψs, there is a representation in terms of the base functions, related to the mixed radix representation of B. It may be that the involution takes (n → A n + B) to (n → A n + (A−1−B), so that we could still continue the proof, but such a patch doesn't lend credibility. — Arthur Rubin (talk) 15:56, 16 June 2010 (UTC)

I think we agree that the main concern is the large amount of "implicit" material that would have to be checked carefully. — Carl (CBM · talk) 16:11, 16 June 2010 (UTC)

I didn't see any distinguishing of positive and negative numbers in it so it should have led to the generalize Collatz sequences instead shouldn't it? Dmcq (talk) 18:17, 16 June 2010 (UTC)

The relations (1)–(6) do generate all relationships between the maps. Using (1)–(6), every element can be represented as a product of α/β/γs followed by a product of φ/ψs, and this representation is unique: the element of M is a function of the form 2ⁿ3^mx + a where 0 ≤ a < 2ⁿ3^m; the number of φ/ψs and α/β/γs are determined by n and m, respectively, the sequence of γ/α/β is determined by the ternary representation of a mod 3^m (with most significant digit on the right), and the sequence of ψ/φ is determined by the binary representation of $\lfloor a/3^{m}\rfloor$. The definition of τ, as well as the homomorphism in Lemma 2.2, is thus correct. There are, however, other problems elsewhere, see the Ref Desk (in the updated version of the paper, the problem shifted to Step 4).—Emil J. 14:08, 17 June 2010 (UTC)

Reference for Syracuse function

Can someone give a reference where to find more information about the syracuse function? I would be especially interested in a proof of the last statement

If p ≥ 2 and h is not a multiple of 3 but h ≡ (−1)p mod 4, we can still show that k ∈ E --95.17.70.203 (talk) 22:27, 24 October 2010 (UTC)

BOINC Collatz Conjecture

We should mention that there is a distributed computing project focused on this conejcture. http://boinc.thesonntags.com/collatz/ —Preceding unsigned comment added by 99.225.34.167 (talk) 19:38, 2 August 2010 (UTC)

I agree, the article/s on gravity waves/pulsars mention einstein@home, as do articles on protein folding mention folding@home & rosetta@home. —Preceding unsigned comment added by 220.239.225.85 (talk) 11:38, 7 August 2010 (UTC)

Under 'experimental evidence' it is stated that about 10^18 numbers have been checked, but haven't some 10^21 numbers been checked by the BOINC project? http://boinc.thesonntags.com/collatz/highest_steps.php 24.91.31.97 (talk) 03:26, 11 December 2010 (UTC)

I don't quite understand the table you linked to. What I can see from it is that the project tested some numbers > 2·10²¹, but it gives no indication whether they have tested all numbers below some bound of such magnitude. I couldn't find this information elsewhere on their web page either. They give all kinds of irrelevant technical details, but strangely enough, this basic information is nowhere to be found.—Emil J. 13:40, 13 December 2010 (UTC)

My guess is that the project (analogous to the Great Internet Mersenne Prime Search and more loosely to SETI@home) assigns each participant a block of numbers to be tested. Presumably these blocks are assigned in order. —Tamfang (talk) 19:17, 13 December 2010 (UTC)

It's quite possible that they assign blocks in order, but if we are to report it as a claim, we need them to explicitly state it instead of guessing it. However, rather than the order of blocks, I'm rather more worried about the starting point of their search. Even assuming the intervals are assigned in order, the table suggests that they could have done roughly the interval [2.361·10²¹,2.365·10²¹] in something over 1 year. That's on the order of 4·10¹⁸ distinct numbers. How long has the project been running? I could not find it either, the only information is that they "continue the work of the previous 3x+1@home BOINC project which ended in 2008". But I think that if I assume that both projects together were running for 10 years, I'm probably being generous. Since hardware gets faster, software gets more optimized, and the number of people involved also tends to increase, it's unlikely that they were going at a faster rate before than they do know. Hence the project may have checked less than ~ 40·10¹⁸ numbers in total (and that's probably a gross overstatement). That's nowhere near 10²¹. A more probable conclusion is that either they only started the search at a number of order 2·10²¹, or they only check sparsely distributed intervals, and either way the vast majority of numbers below 10²¹ remains unchecked. In any case, we need more information.—Emil J. 20:04, 13 December 2010 (UTC)

Optimizations wrong

The section on Optimizations looks completely wrong.

For example, k=5, a=b=1; the right answer is f^5(33)=38, but the formula using the c and d arrays gives 3^3+2=29.

Furthermore, taking a=1, the formula would imply that f^5(2^k+b)-f^5(b)=3^c[b]; i.e. always a power of 3, which is not the case. What does seem to be true is that the difference is always a multiple of 3.

193.113.37.7 (talk) 12:39, 19 November 2010 (UTC)

You are apparently using a wrong definition of f. The section tells you to use the definition from the "As a parity sequence" section, which is

$f(n)={\begin{cases}n/2&{\mbox{if }}n\equiv 0\\(3n+1)/2&{\mbox{if }}n\equiv 1,\end{cases}}{\pmod {2}}$

and then the formula works out correctly. (Well, actually, it refers a bit vaguely to the "parity" section, I guess I'll clarify it.)—Emil J. 13:37, 19 November 2010 (UTC)

Following on from Emilj, in your case the answer will be got after 5+c[b] = 8 normal steps. This is the number of steps to do 5 divides by 2. Dmcq (talk) 13:59, 19 November 2010 (UTC)

Ok thanks. I think it's correct with the non-parity f if you use 6^c instead of 3^c. Anyway, I'm not so sure it really speeds things up, because it trades small-integer operations for bigger ones.

193.113.37.7 (talk) 16:50, 19 November 2010 (UTC)

No you'd have to use different tables if you wanted it to work for k normal steps. With k=16 it speeds up things by a factor of 16 or more and it removes the conditional. The other optimisation as far as I can see speeds the testing of large numbers up by chopping out nearly 99% of them per step so it is extremely effective. Dmcq (talk) 17:56, 19 November 2010 (UTC)

Image "Directed Graph" with crossing lines

At the top of the article, there is an image of a directed graph. I believe this graph is a tree and can be rendered without any intersecting lines, yet the image has many edges that cross each other. Does this serve any special purpose, or is is just suboptimal or even slightly wrong? --Prauch (talk) 09:08, 10 August 2010 (UTC)

• I assume it's so that the image fits into a narrow space. --70.26.56.185 (talk) 05:46, 19 December 2010 (UTC)

Error in Syracuse function section

This section makes the statement "For all odd h, f (2h − 1) ≤ (3h − 1)/2". This is clearly wrong, since:

$f(2h-1)=[3(2h-1)+1]/2^{a},a\geq 1=(6h-2)/2^{a}=(3h-1)/2^{a-1}$

Since $2^{a-1}\geq 1$, then $f(2h-1)\leq (3h-1)$. This invalidates a later point in the proof sketch.

Noldorin (talk) 23:40, 26 January 2011 (UTC)

If h is odd, then 3h − 1 is even, hence a ≥ 2.—Emil J. 11:45, 27 January 2011 (UTC)

Ah, fair enough. That should probably be stated explicitly, since it's not 'self-evident'. Noldorin (talk) 22:20, 29 January 2011 (UTC)

Add discussion of why you need to triple odd numbers

I don't see where the article explains why you need to triple the odd numbers before you add 1--or at least give an example of a number that HAS to be tripled to make it work. The article gives examples using 11 and 27, but both of those numbers can lead to 1 by performing the series without tripling the odd numbers. Aristophanes68 (talk) 18:15, 28 January 2011 (UTC)

If you don't triple, it's, well obvious that the series lead to 1. I can't calculate it exactly, but the number of steps is less than twice the number of binary "digits". — Arthur Rubin (talk) 18:30, 28 January 2011 (UTC)

I'm still not sure why we care that you can triple a number, etc., and get back to one. At some point, there has to be a danger that we might NOT get back to one, but I can't tell from the article why Collatz et al. had reason to be worried about that. Are we simply trying to prove that multiplying odd numbers will always lead to an even number, from which we can always get back to one? Aristophanes68 (talk) 18:54, 28 January 2011 (UTC)

There is no a priori guarantee that we can get from an even number to one, we only get to another odd number, at which point we have to triple it again and so on. Since these repeated tripling steps increase the number, there is a very real danger that we might not get back to one.—Emil J. 19:12, 28 January 2011 (UTC)

To continue, although it's original research on my part.

• 1. Obvious
• 3. Interesting, seems to be true, but not obvious. <added 00:21, 6 May 2011 (UTC)> The probabilistic heuristic suggests that large odd numbers, on average, are multiplied by 3/4, but the law of small numbers makes it clear that the heuristic was not adequate for a proof. </added>
• 5. Almost certainly goes to infinity for some (almost all?) numbers. The probabilistic heuristic would suggest that odd numbers, on the average, are multiplied by 5/4.

— Arthur Rubin (talk) 19:27, 28 January 2011 (UTC)

Collatz the conjecture not the series?

If Collatz is indeed the name of the conjecture and not the name of the series - as the opening para states, then why redact a series of changes aimed at making the page more consistent? Why perpetuate those errors with a pointer to WP:STABILITY, surely it's not what that is for? --Paddy (talk) 18:04, 25 May 2011 (UTC)

I'll reinstate the edits if there is no reply in a day or so from the redactor. --Paddy (talk) 18:04, 25 May 2011 (UTC)

I took another look at WP:STABILITY, and that doesn't seem to apply as it is a matter of what is correct rather than a page 'style'. I've re-instated my edits. --Paddy (talk) 18:21, 25 May 2011 (UTC)

Collatz Conjecture has been proven (maybe)

by Gerhard Opfer:

http://preprint.math.uni-hamburg.de/public/papers/hbam/hbam2011-09.pdf

I guess the wiki page on the conjecture is going to be in need of a major overhaul pretty soon. — Preceding unsigned comment added by 83.22.3.178 (talk) 06:36, 2 June 2011 (UTC)

If the proof checks out. Until such time, it probably merits a mention, but I know people around here often don't like even adding that until the proof has been at least initially checked, so I'll wait before doing so. Mathboy0 (talk) 16:38, 2 June 2011 (UTC)

The proof should be treated with caution: The Collatz conjecture is safe (for now) - it seems that it lacks the proof of a central claim (the linked statements on the website are going more in detail).--91.34.225.251 (talk) 10:16, 5 June 2011 (UTC)

I would definitely suggest to remove the mention given the above information. 134.147.182.89 (talk) 16:18, 6 June 2011 (UTC)

The conjecture has been subjected to numerous failed proof attempts. This should warrant no more attention than the rest of them, until it is shown to be valid. I suggest the mention is removed until that happens, especially considering that indications so far are that the proof is invalid. 129.241.126.215 (talk) 13:07, 7 June 2011 (UTC)

And, indeed, Opfer withdraw his claim. See the current form of the above cited preprint, page 2. Kope (talk) 05:08, 24 June 2011 (UTC)

On the statement of the problem

It is not self-evident to me that the definition of the sequence can be given this way:

${a_{i}}={\frac {1}{2}}{a_{i-1}}-{\frac {1}{4}}(5a_{i-1}+2)((-1)^{a_{i-1}}-1)$

It might be useful, I belive, to say something more about how this equivalence is obtained. —Preceding unsigned comment added by 87.9.239.90 (talk) 13:39, 2 February 2011 (UTC)

The key-idea is always, to find (and make use) of some algebraic expression s(n) as a "switch"-function, which evaluates to two different values when n is odd or n is even. That may be done by $s(n)=(-1)^{n},s(n)=\cos(\pi *n)$ or something else.

In the above formula we find :$s(n)=(-1)^{n}-1$ which gives 0 or -2 depending on the oddness of n. A bit better is to normalize s(n) to give only 0 and 1 instead, so :$s(n)={\frac {1-(-1)^{n}}{2}}$

Finally observe that then s(n) and 1-s(n) have complementary evaluation to 0 and 1.

After this, combine the two alternative steps of the Collatz-transform

$a_{i+1}=s(a_{i})*{\frac {3a_{i}+1}{2}}+(1-s(a_{i}))*{\frac {a_{i}}{2}}$

and collect terms to get the most-pretty, or your favorite, form for the expression. Gotti 08:02, 8 June 2011 (UTC) — Preceding unsigned comment added by Druseltal2005 (talk • contribs)

I have stuck a citation needed on this. It may be true but is it really how somebody has formulated the problem? Dmcq (talk) 08:47, 8 June 2011 (UTC)

Hmm, I've seen this (or similar versions using sin/cos et al) occasionally in articles without noting the source. It is - as idea how to approach the problem of finding such a "continuous version" - sufficiently obvious in my opinion (I just wanted to give an idea how to do and did not check, whether the explication of my example matches exactly the given version of the formula). If this is really of interest I'd suggest to look in some article of the continuous version with the cos-function (I expect this in the material around the Collatz-fractal) --Gotti 12:56, 8 June 2011 (UTC)

Attribution for credit to Collatz and 1937 date

The first sentence of the article contains the claim that Collatz formulated the conjecture in 1937, but there is no citation. This claim was added, together with a link to MathWorld (which has an identical unsupported claim) on 7 September 2004. In fact, the 1985 AMM paper by Lagarias has a note in citation 24 (which points to letters by Collatz to some mathematicians) pointing out that in his letters, Collatz never claimed to have originated the 3x+1 conjecture. The Mathematical Gazette paper by Brian Thwaites does contain a claim of priority dating to 1952, and none of the other historical papers cited in this article contradict that claim. If there is no evidence that Collatz actually originated this conjecture, perhaps it would be safest to follow Lagarias, and say that the origin of this precise conjecture is not completely settled. — Preceding unsigned comment added by 157.82.226.85 (talk) 05:05, 28 May 2011 (UTC)

It's me again. Lagarias's annotated bibliography (http://arxiv.org/abs/math/0309224) has two relevant pieces of information (see the introduction, and the entries for Collatz, Shanks, and Trigg): First, Collatz mentioned this conjecture in an informal talk during the 1950 ICM in Cambridge, and more than one mathematician has attested this in writing. Second, in his own paper from 1986, he said that he had been thinking about similar problems since 1928, but didn't publish them, since he couldn't solve them. This does not give anything like a solid date, so the 1937 figure remains in doubt. — Preceding unsigned comment added by 157.82.226.85 (talk) 08:49, 30 May 2011 (UTC)

Kurtz and Simon's Generalization

I was disappointed that there is currently no discussion of Kurtz and Simon's generalization besides the short paragraph in the lede that they used "a generalization" and that generalization is undecidable. After encountering that in the lede, I was hoping to see more information on *what* the generalization was, and what about it makes it undecidable (if that can be summarized briefly). -- 174.31.219.218 (talk) 16:18, 5 June 2011 (UTC)

There is a reference to Kurtz and Simon's paper - you can just look it up. (And if you feel like it, include a short summary in the article!) AmirOnWiki (talk) 18:57, 18 August 2011 (UTC)

prize

"Paul Erdős said about the Collatz conjecture: "Mathematics is not yet ready for such problems." He offered $500 for its solution.[6]"

Excuse me, but who offered prize - Erdős or Collatz? --Dennis714 (talk) 04:14, 25 June 2011 (UTC)

Erdős, although I don't know what reference [6] says about it. — Arthur Rubin (talk) 09:06, 25 June 2011 (UTC)

Reference [6] says that someone else (not Guy) had attributed the saying "mathematics is not yet ripe for these problems" to Erdős. I tried to rephrase so it will be clearer. AmirOnWiki (talk) 18:57, 18 August 2011 (UTC)

In reverse

I changed the formulas in the 'In reverse' section. The first formule was:

$R(n)={\begin{cases}2n&{\mbox{if }}n\equiv 0,1,2,3,5\\(n-1)/3&{\mbox{if }}n\equiv 4\end{cases}}{\pmod {6}}.$

This is wrong, since it is always possible to multiply the number by two in the reverse Collatz process. I changed it into:

$R(n)={\begin{cases}\{2n\}&{\mbox{if }}n\equiv 0,1,2,3,5\\\{2n,(n-1)/3\}&{\mbox{if }}n\equiv 4\end{cases}}{\pmod {6}}.$

I don't know if this is the best way to write the reverse function. Maybe someone knows a better way to write it or explain it. 130.89.160.202 (talk) 17:35, 1 September 2011 (UTC)

Perhaps as a multi-function

$R(n)={\begin{cases}2n&\\(n-1)/3&{\mbox{if }}n\equiv 4{\pmod {6}}\end{cases}}.$

— Arthur Rubin (talk) 18:22, 1 September 2011 (UTC)

Reason for spike in views

Oh, by the way, in case anyone noticed or wants to be amused, check out the views per day (http://stats.grok.se/en/201109/Collatz_conjecture). The reason behind the massive spike is mostly likely due to Notch posting about it on his blog (http://notch.tumblr.com/post/10309613883/the-solutions-to-a-few-unsolved-problems)

Just FYI for the curious. :D Jessemv (talk) 04:19, 2 October 2011 (UTC)

Syracuse function

Where can I find some info about this approach? In paticular, I am interested in the proof for the h ≡ (−1)^p mod 4 case. Thanks! 93.92.134.38 (talk) 10:30, 25 November 2011 (UTC)

Collatz proof?

Hi, The article is right : no matter what number you start with..... But with specifics values,we found, you will always reach 1. The values can be write in 3x+1 form so it' s necessary that the polynome give a such value Repeat the process (which has been called "Half Or Triple Plus One", or HOTPO) indefinitely. It's false you repeat the process until you get specific valuesThe number of repeat give you the size. It 's trivial to get the complementary size from this point to 1. An addition give you the total size

The values cannot be reach with X/2 only with odd polynome It seems that the total size have a link with X and the specific vales

---

Jérôme 012812 12:00 CET

Tanks for your necesary critics — Preceding unsigned comment added by 88.189.253.171 (talk) 10:29, 28 January 2012 (UTC)

unusable link

http://people.cs.uchicago.edu/~simon/RES/collatz.pdf is an unusable draft lacking the main result. Can someone post the final draft? — Preceding unsigned comment added by 188.153.15.239 (talk) 13:58, 6 March 2012 (UTC)

Optimizations part needs update

Hello,

I am new to Wiki editing and I hope this is the best place for writing on this topic.

After doing some minor research I came to the conclusion that the optimizations part needs some update (or that the following comments also need to be included in the overall presentation): the quoted optimization seems (for me at least) not to be a credit of Tomás Oliveira e Silva, but a direct result of correctly applying the theorem of Riho Terras (for whom an article is also missing on English Wiki), see here for a less-than-formal introduction. This is important information that should be included here as it shows that, for example, 99.976132% numbers under 2¹⁰⁰ can be proven via this theorem to have finite stopping times (or 99,999995% numbers under 2³⁰⁰), values which are far higher than any current raw verification progress (currently between 2⁶⁰ and 2⁷⁰ from various sources).

--Dameniphel (talk) 09:33, 24 April 2012 (UTC)

I can't find anything recent which is from a reliable source; you may be right. As for your source, there is an error in finding the conclusion of Lemma 5: It does not follow directly from "For each k, that only finitely many numbers with convergence time k do not have stopping time k." that "There are only finitely many numbers with convergence time different from stopping time." The resulting theorem is still valid, and I don't see any reason why Terras's theorem shouldn't be in the "Supporting arguments" section. Perhaps I can find a copy of his paper in Acta Arithmetica the next time I do research at a university library.

As for the 3^k/2 in that section, it seems unlikely, but it's

$\sum _{i=0}^{\left\lfloor k\cdot {\frac {\log {3/2}}{\log 3}}\right\rfloor }{\begin{pmatrix}k\\i\end{pmatrix}}$

which I can't approximate in closed form at the moment. — Arthur Rubin (talk) 16:13, 24 April 2012 (UTC)

Terras's theorem seems to be that for almost all n, the sequence starting with n goes below n. An appropriate generalization, that for any λ for almost all n, the sequence starting with n goes below n/λ, which all follows from Terras's analysis. Both definitely belong in "supporting arguments". — Arthur Rubin (talk) 16:27, 24 April 2012 (UTC)

generalizations

Maybe this should be added?

Let x be an integer. Let the function T_5(x) be equal to x/2 if x is divisible by 2, equal to x/3 if x is divisible by 3 but not by 2, and equal to 5x+1 otherwise. In a similar way, let the function T_7(x) be equal to x/2 if x is divisible by 2, equal to x/3 if x is divisible by 3 but not by 2, equal to x/5 if x is divisible by 5 but not by 2 and 3, and equal to 7x+1 otherwise. Just like the 3x+1 function, it appears that, starting from any positive integer, the repeated iteration of the T_5(x) and T_7(x) functions eventually reach the integer one, after which the iterates enter a cycle. These are the 5x+1 and 7x+1 conjectures. (The 5x+1 conjecture was suggested to me by Eric Roosendaal.)

— http://www.ieeta.pt/~tos/px+1.html

--Dennis714 (talk) 23:17, 25 May 2012 (UTC)

Function

Here is a trivial function (in one part rather than two) to calculate the next integer in the series, I am not sure where to add it to the article though. $f(n)=(n\%2)*(1+n*3)+(1-(n\%2))*(n/2))$

--gbaddorf 18:57, 28 June 2012 (UTC)

Other Formations?

Just looking at the conjecture, but seeing it as an information processing instead of a mathematical problem (I'm a programmer not a mathematician), several things seem kind-of evident.

First, though "oneness" is very popular in maths, it seems to be something of noise in the conjecture. (discounting the number as the starting condition) The only way to reach 1 is to reach 2 first, so programatically this is really a "twoness" probem expanded to include the numbers zero and one. Likewise to reach two (2) you must first reach four (4), so how about "fourness"? To reach four (4) you must first reach eight (8), so "eightness?". Indeed the first point of covariance is reaching the value sixteen (16) which can be guessed, reached from thirty-two (32) or reached from five (5).

The entire devide by two term, and the reaching one requirement are just noise, present to complicate at one level and to "keep numbers reasonably representable and workably small".

The conjecture can be simplified, unless I am missing something, as "starting with any non-negative whole number, repeatedly applying the mathematical operation n=3n+1 will eventually result in a term which can be expressed as a power of two."

This could be proven because n/2 is computationally identical to a left-shift operation and the constraint on its application requires the least significant bit be zero (e.g. the number is even), so the left-shift never discards real information, so skipping the left-shift and assuming an infinitely wide register, the conjecture is that eventually only one bit will be set at some point after an unknown number of applications of "multiply r1 by 3; increment r1".

In this formulation, skipping all the _complicating_ mathematical noise of the n/2 and the two-phased function; or the bizarre-to-me equivelant long-form polynomial, the conjecture should be infinitely easier to prove or disprove.

Doing this "all mathy" I suspect the alternate rewrite would involve a whole number term to the natural log or some such. Basically 3n+1 must, for all n, cross, intersect, or land on or something math-speak, a value that is also in 2^x where x is a natural number.

How about, there is a non-empty intersection between the set of all numbers 2^x and any set of 3n+1 for any natural starting number n.

Again, not a mathematician, so I don't know how to write out the simplification in official math-talk.

Sinerely Rob White. IBitOBear (talk) 13:22, 26 November 2012 (UTC)

As a matter of fact, if you don't stop the computation at one in the original formulation you eventually get the repeating sequence {1,4,2,1,4,2,1...} so the simplist formulation is "3n+1 always converges on 2^x", or something. IBitOBear (talk) 13:31, 26 November 2012 (UTC)

I'm afraid that's wrong. It's important to the conjecture that you remove as many /2s as you can, as 3n+1, itself, can hit a power of two for only a small set of numbers. — Arthur Rubin (talk) 14:53, 26 November 2012 (UTC)

I ran the sequence... I was actually wrong because I failed to account for the changing significance/magnitude of "+1" (and I should have said right-shift, doh!) when you remove the bit-shifting effect of the n/2 you have to compensate by left-shifting the one (1). So looking at the base form the n/2 term repeatedly coerces oddness in the term, while the +1 returns it to even-ness by rounding up the the next even number. So the right-shift of n/2 serves to magnify the impact of the increment. In binary the plus-one and the right shift serve to reduce the span between the lowest and highest set-bit. In short, the binary sequence correction is to right-shift until odd, multiply by three (which preserves "oddness" as in the lowest-order bit remains set), then coerce away the lowest-order series of set-bits, effectively replacing the lowest order sequence of powers-of-two with the next higest power of two.

So ten (10) 1010 -> (right-shift => 5) 101 -> (*3 => 15) 01111 (+1 => 16) 10000 (right => 8, right => 4, right => 2, right => 1) 1.

Which is classic bit-shift simplification or rounding. Shifting right is then adding one is identical to finding the magnitude of the lowest set bit and adding it back in.

So ten (10) 1010 -> (*3 => 30) 11110 -> (plus lowest order power of two e.g. 2 e.g. xxxxx10 => 32) 00100000 ... right-shift this the same five times as before and you get 1.

Take any term, say the tirty, and put a bit in front of it (think if this as a new starting N) 10011110, add the lowest-set-bit in again (+10), get 10100000.

So this is really simple in binary. You multiply by three and then shave-off the least significant bits and toss in the next power of two, effectively rounding up the post multiplicatoin value.

Once you reach a base power of two each itteration is just multipy by four. e.g. 0001000 => 0011000 -> 0100000, hence the repeating pattern 1,4,2,1,4,2,1 if you don't stop processing in the original formulation.

Viewed in base-two (binary) this is just an exercise in "rounding up" and is inevetably true for all natural numbers. IBitOBear (talk) 00:25, 27 November 2012 (UTC)

From a pure computation perspective, this conjecture reads: If you keep throwing away information by rounding up, eventually you will have no useful informaton left. That's kind of a tautology. IBitOBear (talk) 00:49, 27 November 2012 (UTC)

By the way, if you care, I just saw the name of this conjecture on the XKCD store page last night, then I recognized the graphs as a binary progression distorted by projection onto a curved surface. If you constantly multiply by three and then throw away the same bits or more bits than you create by extension (1*3+1 is two bits, converting 011 to 0100 throws away two bits, but converting 0111 to 01000 throws away three bits, etc.) you _must_ eventually be left with only one bit set. It just requires letting go of the math to see the numbers. 8-) IBitOBear (talk) 03:03, 27 November 2012 (UTC)

Another version that might be useful in the proof is to imagine a finite state atomnita (such as Conway's Life) played on a one-dimensional board. The leading bit pattern increases by a first-order polynomial (e.g. 3n, which can only add a maximum of two bits at that end, e.g. 010xxx... becomes 110xxxx, adding one bit, but 0110xxxx becomes 01000xxxx adding two bits, which is the max extension of the leading edge) but the tail of zeros advances by an unconstrained second order polinomial 2^x where x is, must be at least two, because it always eats at least 01 and can eat as much as 01111111(repeating forever). So if it were a barrel rolling away leaving a trail of gunpowder, the fuse always burns no slower than the barrel can lay down more fuse _and_ sometimes it burns faster. So eventually the fire must reach the barrel. Using base-2/binary just makes the ln(x) nature of the advancement obvious in linear visuals. The n/2 just represents the observer walking along next to the buring fuse (e.g. correcting the point of observation.)

Sorry to keep adding stuff, but I don't know how clear I am being... Rob White. IBitOBear (talk) 03:19, 27 November 2012 (UTC)

I keep messing up the explanation so here is the visualizer...

 //License: GNU GPL V3 (or later at your option)
// © Robert White <rwhite at pobox.com> 2012
#include <iostream>
#include <sstream>
#include <iomanip>

using namespace std;

ostream & visualize(int divides, int value, const char * tag, ostream & os)
{
  char scratch[100];
  char *cursor = scratch;
  unsigned temp = value;
  while (temp) {
    *cursor++ = '0' + (temp & 1);
    temp >>= 1;
  }
  *cursor++ = '0';
  *cursor++ = '\0';
  int times = divides;
  while (times--) {
    os.put('.');
  }
  os << scratch << ' ' << value << ' ' << tag << "[" << divides << " total divisions by 2]" << endl;
  return os;
}

int
main(int argc, char *argv[])
{
  int counter;
  for (counter = 1; counter < argc; ++counter) {
    int divide_events = 0;
    istringstream Arg(argv[counter]);
    int value;
    Arg >> value;
    visualize(divide_events,value,"(Start)",cout);
    while (value > 0 && value != 1) {
      if (value % 2) {
        value *= 3;
        visualize(divide_events,value,"(after n*3)",cout);
        value += 1;
        visualize(divide_events,value,"(after n+1)",cout);
      } else {
        ++divide_events;
        value /= 2;
        // optionally comment out this next line for a slightly different perspective...
        visualize(divide_events,value,"(after n/2)",cout);
      }
    }
    visualize(divide_events,value,"(Done)",cout);
  }
  return 0;
}

and some output

./Collatz 30
011110 30 (Start)[0 total divisions by 2]
x11110 15 (after n/2)[1 total divisions by 2]
x1011010 45 (after n*3)[1 total divisions by 2]
x0111010 46 (after n+1)[1 total divisions by 2]
xx111010 23 (after n/2)[2 total divisions by 2]
xx10100010 69 (after n*3)[2 total divisions by 2]
xx01100010 70 (after n+1)[2 total divisions by 2]
xxx1100010 35 (after n/2)[3 total divisions by 2]
xxx10010110 105 (after n*3)[3 total divisions by 2]
xxx01010110 106 (after n+1)[3 total divisions by 2]
xxxx1010110 53 (after n/2)[4 total divisions by 2]
xxxx111110010 159 (after n*3)[4 total divisions by 2]
xxxx000001010 160 (after n+1)[4 total divisions by 2]
xxxxx00001010 80 (after n/2)[5 total divisions by 2]
xxxxxx0001010 40 (after n/2)[6 total divisions by 2]
xxxxxxx001010 20 (after n/2)[7 total divisions by 2]
xxxxxxxx01010 10 (after n/2)[8 total divisions by 2]
xxxxxxxxx1010 5 (after n/2)[9 total divisions by 2]
xxxxxxxxx11110 15 (after n*3)[9 total divisions by 2]
xxxxxxxxx000010 16 (after n+1)[9 total divisions by 2]
xxxxxxxxxx00010 8 (after n/2)[10 total divisions by 2]
xxxxxxxxxxx0010 4 (after n/2)[11 total divisions by 2]
xxxxxxxxxxxx010 2 (after n/2)[12 total divisions by 2]
xxxxxxxxxxxxx10 1 (after n/2)[13 total divisions by 2]
xxxxxxxxxxxxx10 1 (Done)[13 total divisions by 2]

By justifying/padding the binary number with a period "." for every bit consumed from the marching buffer, the patern becomes more clear, but less wiki friendly.

Run it with some realy big numbers, like a large prime, and you can see the lines converge.

It's also notably impossible to ever execute n=3n+1 twice in a row since the result is alwyas even, so the bit discarding n/2 must dominate.

notice how the plus-one keeps making one-or-more zeros on the least significant bit(s) and then the n/2 just eats them? The ability of the n/2 to eat zeros from the left will always overpower the ability of the *3 to make ones on the right because the plus-one is a dominant force at the low end of the curve. It always makes zeros. IBitOBear (talk) 05:05, 27 November 2012 (UTC)

Playing with the visualizer reveals that there is no real magic to the three (3) or the two (2), its all tied up with the multiply by odd when odd then coerce to even by adding one.

For any pair of numbers {A,B} where A is odd and B is even, and A is less than 2B, applying n=An+1 when n is odd, and n/B when n is even, will converge on the value 1. Some cases outside this are seemingl true as well. I had good luck with 29n+1 and n/8, which lands outside the 2B rule.

This is all tied up with evenness and the domination of evenness when you apply an evenness-corercing term to an odd number, and an even devisor to an even number, and the dominance of even terms occuring in the results. As long as the scaling term isn't too big for the consuming term, you converge on 1.

IBitOBear (talk) 13:34, 27 November 2012 (UTC)

Another observation (I can't sleep 8-) is that you always perform (3n+1)/2 when the number is odd, and n/2 when the number is even. That is (3n+1) is invariably even so the first n/2 is inevetable after each 3n+1. Since the probability of a any number devided by two producing an even number is .5, at least half the time you will end up with (3n+1)/4, and half the time you do that you end up doing (3n+1)/8 and so on. I know there is math-speak for this sort of probability series. The probability of (3n+1)/2 is 1, (3n+1)/4 is .5 and (3n+1)/8 is .25 and so on. Since all terms but the first diminish n, well throw the right magic statistical constant (the golden ratio?) and you have the reverse of compound interest. IBitOBear (talk) 13:50, 27 November 2012 (UTC)

You should better study the article carefully before overloading this page with your insights. The heuristic argument that you are trying to come up with is being described in this section of the article. Nageh (talk) 13:58, 27 November 2012 (UTC)

More than half the time you are multiplying by three and deviding by four-or-more. It's not magic. Did you run the visualizer? I know I am not offering it up in sufficently mathish words, but prodedurally its demonstrable. But sure, I have got it out of my system I think... So I will stop. IBitOBear (talk) 14:09, 27 November 2012 (UTC)

I want to second Nageh, and remind you that:

1. Until you're published, this is original research, and cannot be in the article.
2. If I'm not mistaken, there's a significant monetary prize for solving the problem. If you think you have a solution, why are you here?

— Arthur Rubin (talk) 14:11, 27 November 2012 (UTC)

Like I said, I'm not a mathematician. And I do recognise that my "visualizer" is basically the Hailstone sequence. But it is also an argument to rewrite the conjecture as an equivelant process as a game-of-life/conway simulation. If you use the rule for finding the least significant set bit and drop the divid by two noise and the pretty pictures, you get a stable atomnita that must terminate. Run the visualizer and then replace "." with "0" to see the very-large-number simplified version. Proving the two representations as covariant is right there in the induciton. This is so "computational" that some modern processors have native instructions for "find the lowest set/unset bit". I just don't happen to have a machine wiht infinitely wide registers. This is the same as using the /2 term to keep the numbers reasonable. I know its not the pretty you are expecting, but it is the same thing.

I din't know about the prize... IBitOBear (talk) 14:19, 27 November 2012 (UTC)

Your "visualizer" is nothing but the pictures you can already find in the article. They may provide you insight and indication for the conjecture's validity, but they are not proofs. You cannot take a finite number of start values, run them through your program, and then conclude that the conjecture holds for all numbers. Nageh (talk) 14:26, 27 November 2012 (UTC)

okay, so you didn't run it. The thing is it "proves" (for shallow definitions of that word) that if you delay all the n/2s till after you have only one bit set in the sequence, and symmetrically extend the "+1" by all those powers of two, you still converge. If you run the visualizer and then do a global search and replacd of the pading character wiht zero you get the visual effect more clearly. In computer sicence we call that "a pahtological rounding problem". The dominance of the "+1" is there by demonstrated and the "big numbers might be different" issue is debunked. That is _not_ in the article. Think of it as pure associativity between the division and the adjusted power of the "+1" to select away oddness in the result set. Sure lots of people have spent lots of time on it, but it's not that hard to see if you lay it out correctly.

so rounding up after multiplication bad, and that's all this really is. The conjecture was formalized before people commonly thought in binary, but done entirely in binary, its not very complex. The divide by two while even construct can be restated shift-right while even, or "throw away the least significant zeros" a la Hailstone, but now the 3n+1 term is "multiply by three then round up to the next even number".

e.g. this conjecture is "if you keep rounding in one direction you will eat your data"... just hidden behind smoke and mirrors. Viewed in base 2 and left in-place instead of being sucked rightwards, you see that each application of the "+1" is really an application of an increasingly dominant power of two. Sure its the Hailstone series at one level, he just formated it unhelpfully. Sorry I don't see why this is hard but I live with it every day in practical coding. IBitOBear (talk) 15:06, 27 November 2012 (UTC)

Sigh. I will just refer you to what Arthur Rubin said now. And now go get the prize and don't bother us anymore. Nageh (talk) 15:18, 27 November 2012 (UTC)

(for those listening along at home, the differnce between my graph and the one in the article is that I call out the "plus one" as a separate step so you can see its literal effect instead of just the the blind results in the Hailstone series. I also fromat in bit/register/serial-transmission order to make the series more english-reader friendtly. That's what it's intended to let you visualize. You can convert from the /2 to the add-in-least-significant-bit layouts by pure text substitution.)

Were is this prize gone to get? Seriously. You assume I just couldn't be right in a classic plead to authority. You didn'e even look at the output nor probably even do more than weigh my words by raw count. So where is this prize to be had from? There is no prize mentioned in the article or google. IBitOBear (talk) 15:31, 27 November 2012 (UTC)

A prize is mentioned in the lead section of the article. Seriously, Wikipedia talk pages serve solely for the purpose of coordinating changes to the article. They are not a general discussion forum about the subject of the article, and especially they are not a venue to propose your ideas about solving open problems. See WP:TALK and WP:FORUM. These are the rules here, so be that kind and find a more appropriate forum.—Emil J. 16:25, 27 November 2012 (UTC)

Methods of proof

In section "Methods of proof" was said, that "For large cycles the fraction 3^A/2^B would be expected to tend to 1". But I think, it is not obviously. How can one to prove this conjecture? And where is the source of this information? — Preceding unsigned comment added by 95.25.29.249 (talk) 16:42, 5 December 2012 (UTC)

In reality, next number in series either x/2 or (3x/2 + 1/2)..... not x/2 or (3x + 1)

Considering that if parity is odd, then the next number will definitely be even. And in this case it will surely be halved next. So in reality, next number is x/2 or (3x/2 + 1/2). Instead of x/2 or (3x + 1).

And given this, the series will be convergent. Unless one assumes that for a random number the probability of odd parity is higher than of even. Which is false, given the definition of a random number.

A layman's 2 cents.. hoping not to get beaten too much!! :)

122.176.144.169 (talk) 16:32, 20 April 2013 (UTC) Tej

Trivial cycle

Why is the trivial cycle represented as (1, 2) instead of (1, 4, 2)? 76.169.154.92 (talk) 05:26, 16 February 2013 (UTC)

It's the "shortcut" definition $f(n)=(3n+1)/2$ for odd n in Collatz conjecture#Notation. PrimeHunter (talk) 05:48, 16 February 2013 (UTC)

This "shortcut" definition is introduced almost halfway into this article. It appears that all the sequences prior to the introduction of this definition (such as those in the subsection Collatz conjecture#Examples) use the original definition, while the sequences after the introduction of the shortcut definition use the new version. This seems like a bad way to arrange the article, because someone who reads the first 25% of the article very carefully, and then skims the rest, won't realize that you have redefined the rule for f(n) halfway through the page. That would be like a Wikipedia article using the name "Clinton" to indicate Bill Clinton during the first half of the article, but then using the name "Clinton" alone to indicate Hillary Clinton in the second half. This should be fixed. — Lawrence King ^(talk) 23:11, 3 June 2013 (UTC)

Misleading graph

This graph: [2] is misleading. There are many dots that should appear above the 1,000,000 mark but are truncated. In particular, initial numbers of 1819 and above can produce highest values greater than 1,000,000 (1819 itself produces a maximum of 1,276,936). --pgimeno (talk) 10:01, 9 May 2013 (UTC)

Kurtz proof

The introduction mentions a result by Kurtz & Simon. This result should be described in the body of article, because (1) it is clearly important, (2) it is interesting, and (3) Wikipedia policy s doesn't support including major substantive facts in an introduction unless they appear in the body of the article as well.

In particular, it should be made clear whether the "natural generalization of the Collatz problem" investigated by Kurtz and Simon is the same as the "Generalized Collatz Conjecture" described later in the article. — Lawrence King ^(talk) 23:18, 3 June 2013 (UTC)

Proof of Collatz Conjecture Using 100 State Deterministic Finite State Machine

There is a draft proof of the Collatz Conjecture at http://collatzconjecture.blogspot.com/. The essence of it appears to be that the conjecture can be reduced to a 100 state deterministic finite state machine. There are only two loops, the 4-2-1 loop and a "00" loop, both of which converge to 1. The proof seems to address quite clearly the Steiner/Simons/deWeger theorems and others related to the number of "cycles" necessary to show convergence. This should be added to the main article under either the Theorems section or Finite State Machine section.

216.201.245.6 (talk) 14:57, 2 July 2013 (UTC)

The proof uses something it calls "principle 1", and this is obviously false. --Daniel5Ko (talk) 22:57, 2 July 2013 (UTC)

Could someone please clarify

The phrase "Here, if we manage to show that for every odd integer k′, 1 ≤ k′ ≤ k − 2 ; 3k′ ∈ E we are done." at the end of the section concerning syracuse functions is fit for a math classroom. On wikipedia, it could benefit from a little expounding for the non-math dumbasses such as yours truly, to whom this might seem rather cryptic gobbledygook. Inquiring minds want to know... Kleuske (talk) 16:05, 24 July 2013 (UTC)

Why is the Bruckman proof not mentioned?

Bruckman published a proof of the Collatz Conjecture in the peer-reviewed International Journal of Mathematical Education in Science and Technology (Paul S. Bruckman (2008) A proof of the Collatz conjecture, InternationalJournal of Mathematical Education in Science and Technology, 39:3, 403-407, DOI:10.1080/00207390701691574). Shouldn't this proof be mentioned in the proofs section of this Wikipedia page?

Cobalt60blue (talk) 01:47, 6 August 2013 (UTC)

See Talk:Collatz conjecture/Archive 1#Evidence that the conjecture may be proved. Five years later there is still no sign anyone takes the alleged proof seriously. PrimeHunter (talk) 04:09, 6 August 2013 (UTC)

Methods of Proof

STBPB (Sorry to be pedantic but) This section contains the statement

Rearranging shows that the lowest number in the cycle satisfies: x \ge \frac{3^{A-1}}{2^B-3^A} which gives a lower bound for the lowest number in a cycle for a given cycle length. For large cycles the fraction 3^A/2^B would be expected to tend to 1, so that the lower bound would be large.

It's the "would be" that irks. Since A and B are not independent but are defined by a process that produces a (yet unknown) collatz cycle, we don't know what the fraction would be. If 2^B is always much greater than 3^A (it has to be greater) then it will tend towards zero for large exponents. If it so happens that B is always the smallest B that makes 2^B just greater than 3^A then the fraction does not appear to want to converge, oscillating wildly between .5 and .95 over the range 10^10 to 10^100 (when it is 0.864, and so we can deduce that x >= 2.12).

Suggest remove the last sentence.

A1jrj (talk) 15:05, 1 October 2013 (UTC)

Methods of proof

The section currently named "methods of proof" consists of a description of one "methods of attack" that obviously doesn't work (since the conjecture has not been proved). Should it be part of the article? I doubt it. Please discuss (there is no source for it, either). AmirOnWiki (talk) 18:20, 11 October 2013 (UTC)

Highest power of 2

It's plain obvious that if the hypothesis of the sequence always terminanting in 1 is correct, it reaches a power of 2 somewhere. But: is there any explanation why it seems that if you pick a random number, the probability is quite high that the highest power of 2 in the process will be 16? That is, for most numbers the sequence seems to end 5, 16, 8, 4, 2, 1. --92.224.108.169 (talk) 18:11, 11 November 2013 (UTC)

An Additional idea to this comment by Chris Bernardini. more of a confirmation of the logic however useless this is.

Because there are infinitely many N for 2^n and the fact is that every even power 2^(2a) so that 2^2=1*3+1 2^4=5*3+1 2^6=21*3+1 etc... where each term progresses in a manner of the previous odd integer that is being multiplied by 3 is multiplied by 4 then 1 is added for the next odd number that produces the next even power as *3+1. for ex. if y =*4+1 then 1y = 5, 5y=21 ,21y=85 etc... and 2^(2a-1) can only ever come from a value of 2^(2a)

because of this simple fact saying most numbers travel through 16 to five is absolutely true(for all cases excepting if you choose 1), this is because because 16 is the lowest possible even number of the form 2^n that can be created aside from having already reached a value of 1 which allows you to reach a value of 4.

Basically all this says about the problem is:

if they all reach one then they will ALL attain 16 at some point before reaching one excepting that one be the chosen number.

This type of pattern follows through all strings of odd numbers excepting those 0 mod 3 as they can only appear by being chosen. Jeff Lagragias has done work that is equivalent to all mine and greater as well. however more complicated to understand my terminology and notation is anything but professional quality. — Preceding unsigned comment added by 207.210.136.250 (talk • contribs) 21:54, November 14, 2013‎

Relevance of this to potential solutions of the problem is questionable. — Arthur Rubin (talk) 18:25, 17 November 2013 (UTC)

Why "Syracuse problem"?

Why is this unsolved puzzle in mathematics also known as the "Syracuse problem"? Thanks for any insights on this. Kind regards, DA Sonnenfeld (talk) 16:26, 17 November 2013 (UTC)

Y Solved; documentation added to article. DA Sonnenfeld (talk) 21:56, 5 December 2013 (UTC)

Kurtz/Simon work is irrelevant.

The article currently says:

"In 2007, researchers Kurtz and Simon, building on earlier work by J.H. Conway in the 1970s, proved that a natural generalization of the Collatz problem is algorithmically undecidable."

This is false. Conway already proved the generalized Collatz problem undecidable in 1972 in the very paper Kurtz and Simon reference. Conway states a theorem about computable functions, and then states the corollary which would follow from the theorem: GCP is undecidable. This is the motivation for the theorem in the first place.

Kurtz and Simon mistakenly think that because the theorem only concerns GCP x values of the form 2^k, that it wouldn't follow that GCP is undecidable. However, showing GCP is undecidable for even a single x clearly proves it undecidable for all of ω (this is not the same as "for each member of ω"). Besides which, the corollary is right there in black and white on the first page of Conway's paper: GCP is undecidable, 1972.

I'm changing it and removing the reference to Kurtz and Simon. I have spent time reviewing their paper, and while it is an interesting piece of work, I'm not tracking why they think they are proving anything at all with it.TricksterWolf (talk) 16:08, 9 December 2013 (UTC)

Mandelbrots

Is it just me, or is the Collatz fractal full of Mandelbrots? I wonder if someone can explain why... 103.1.70.97 (talk) 02:00, 23 October 2013 (UTC)

infinite strings of mandelbrot sets that collapse to 1. its a good visual "proof" — Preceding unsigned comment added by The ChrisB Pi (talk • contribs) 21:56, 14 November 2013 (UTC)

No, it's just you. It's a fractal, not a "Mandelbrot". And the relationship between the Collatz fractal and the Collatz problem is unrelated to properties of the fractal. — Arthur Rubin (talk) 18:24, 17 November 2013 (UTC)

This is a fair question. Clearly, 103.1.70.97 means, "Why does the Collatz fractal resemble the Mandelbrot set fractal?", and the article does not address the similarity. I wondered the same thing myself when I first viewed the image.TricksterWolf (talk) 16:22, 9 December 2013 (UTC)

Clarifying Cycles

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

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

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. 178.201.250.13 (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 178.201.250.13 (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}}$.178.201.250.13 (talk) 11:09, 29 January 2014 (UTC)

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

References section

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

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. [3] 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)

Counterexample

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". http://mathworld.wolfram.com/SolitaryNumber.html 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)

Assessment comment

The comment(s) below were originally left at Talk:Collatz conjecture/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Comment(s)

Press [show] to view →

In the course of investigating the number of steps it takes various integers to converge to 1 , I was extremely surprised by some results. I was counting as steps each iteration of (3x+1)/2^n. My start values were of the form 2^k+c. For different values of c, I printed out the counts for k = 1 to 100. Certain counts occurred much more frequently than others. At low values of k , counts of 32, 44, and 56 appeared more often than I expected. At high values of k the predominance of certain counts was even more marked and the counts 109, 162, 191 and 210 almost excluded other values over consecutive values of k. Could anyone confirm these results and, if confirmed, give a reason ?Mugbuff (talk) 03:22, 24 December 2007 (UTC) Look at the numbers in binary. C's bit pattern will generally remain unchanged by adding a large power of 2. The LSB solely determines the Collatz iterations, so all your numbers will have the same iteration counts up to the point where c converges to 1. Although what happens next depends on what has ahppened to that initial MSB, getting similar counts of (3n+1 is not that surprising. In my tests, I had many sequences with 56 odd numbers, but with diffent even counts. In general, looking at the beaviour in binary is a fascinating study. In binary, to multiply by three you just need to left shift the number and add it to the unshifted value. And if you preset the carry before doing the sahift, you'll automatically get the +1 when you add the unshifted value. Once you have this, there are all kinds of fascinating phenomena associated with the interactiions of bits.One of such is the property of resonance. That's where the bit pattern remains the same (albeit shorter) as the sequence progresses. Remember, Collatz iterations are determined by the LSB, so resonance often affects ieration counts.76.214.209.209 (talk) 05:59, 7 March 2011 (UTC)

Last edited at 05:59, 7 March 2011 (UTC). Substituted at 21:14, 4 May 2016 (UTC)

Question

hi

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 (talk • contribs) 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)

What exactly IS "the real extension of the Collatz map optimized by replacing 3n+1 by (3n+1)/2" ?

Picture caption:

"Cobweb plot of the orbit 10-5-8-4-2-1-2-1-2-1-etc. in the real extension of the Collatz map (optimized by replacing "3n + 1" with "(3n + 1)/2")"

Since there is nothing in the article that refers to a "real extension" of the Collatz map (no less an "optimized" one) — and the caption doesn't go to any trouble to explain what it might be trying to say — can we please remove this picture and its unhelpful caption? (Sorry, but I have zero patience for nonsense posing as editing.)Daqu (talk) 01:41, 12 March 2015 (UTC)

I'm having difficulty understanding, the real extension is right next to the picture in the section "Iterating on real or complex numbers", and it says, right in the caption, what the optimization is (despite being a rather trivial one).Phoenixia1177 (talk) 15:00, 31 March 2015 (UTC)

Ok, but why this particular real function among so many others? Do we have a source for this? Does this offer any actual insight into the Collatz conjecture? As it is, it looks like unsourced original research and as such should be removed. —David Eppstein (talk) 17:31, 31 March 2015 (UTC)

I have no idea why this particulair one, I didn't put it there nor argue that it is the right one. That said, it is an obvious one and I've seen it more than once, but there are others that have been employed, and of equal to greater use - moreover, it is trivial to add terms to the one in the article to get something more general. I don't really see the point in removing it as it is, essentially, a really obvious extension of the parity function, but I would downplay any emphasis that makes it sound like it is the "standard" or "right" real version of the Collatz function (but does serve as a reasonably simple example of an extension, basic enough that I don't think it is OR).Phoenixia1177 (talk) 01:41, 26 May 2015 (UTC)

Artistic visualizations

Note that on https://mathematica.stackexchange.com/questions/85718/trying-to-visualize-a-collatz-the-collatz-conjecture are some beautiful pictures generated from 3n+1 sequences, maybe some of them should be included in the article? — Preceding unsigned comment added by 87.173.4.44 (talk) 10:26, 27 September 2015 (UTC)

Not clear

It is not clear to me why anyone wants to study this conjecture. Any other recursion could be used. — Preceding unsigned comment added by 81.149.226.23 (talk) 14:42, 30 December 2015 (UTC)

Well, this is mathematics. We study it because it is there, and curious. Much of today's computing is based on mathematical research from the 50s that made no business sense whatsoever. --WiseWoman (talk) 12:30, 21 March 2016 (UTC)

This isn't a discussion forum about the Collatz conjecture or why people might or might not be interested. The topic of the talk page is to discuss the state of the article. From WP:TALK#USE:

Stay on topic: Talk pages are for discussing the article, not for general conversation about the article's subject (much less other subjects). Keep discussions focused on how to improve the article. If you want to discuss the subject of an article, you can do so at Wikipedia:Reference desk instead. Comments that are plainly irrelevant are subject to archival or removal.

— 64.134.181.228 (talk) 21:15, 24 March 2016 (UTC)

Histogram is misleading

The histogram on stopping times is very misleading.

While "valid" as stated, it is inappropriate for the distribution.

The underlying distribution has no mean (like an exponential distribution).

In fact, the actual distribution can be ( with difficulty) computed.

The essential point is the number of integers with stopping time n is a non-decreasing function of n (which is easily shown without the need to a difficult computation).

At the very least, the histogram should be complimented with the actual distribution (say though the same domain).

This would not only be illuminating, but would be a nice illustration of some subtle, yet key points about distributions (i.e. histograms are only useful with distributions with means and "small" tails). — Preceding unsigned comment added by 108.227.46.153 (talk) 15:59, 6 September 2015 (UTC)

You are certainly right in saying that the number of integers with stopping time n is a non-decreasing function of n, and the histogram clearly gives a very different impression, so I shall remove it. If you or anyone else can do put more accurate information about the distribution into the article, that will be very helpful. The editor who uses the pseudonym "JamesBWatson" (talk) 12:40, 22 March 2016 (UTC)

The number of all integers with stopping time n is equal to the number of nodes at the n-th level of the Collatz graph, which is approximately aⁿ, where 1 < a < 2, as expected from an "average" infinite tree whose nodes have one or two children.

Although this result may be interesting, it does not say anything about the expected stopping time of an integer chosen at random from a fixed interval. And that is the purpose of the removed histogram, which illustrates an important aspect of the Collatz sequence behavior. Petr Matas 19:01, 25 March 2016 (UTC)