Talk:Collatz conjecture/Archive 1
 | This is an archive of past discussions about Collatz conjecture. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
| Archive 1 | Archive 2 | Archive 3 |
A query
Has anyone ever noticed that always leads to , and does it in exactly 2n steps? I have a proof of this, but I'll just give two examples instead.
- Yes, it's well known. At least to me. --Mensanator 01:03, 12 October 2007 (UTC)
- Indeed, it is easy to see that (i * 2^n -1) yields (i * 3^n -1) in n half-tripling steps
- Note that every non zero integer is uniquely written in the first form above, with i odd and n postive or zero. The resulting integer after the n steps above is even, so that one or more halving steps will follow, the number of which it is interesting to study as a function of (i,n). I call the preceding collapsed (pun intended) steps from an odd to an odd "a Collatz round"... Ninho (talk) 17:11, 19 February 2008 (UTC)Ninho
Example 1. , done in 2*4 = 8 steps
Example 2. , done in 2*5 = 10 steps
- 2n-1 is commonly known as a Mersenne Number (not to be confused with Mersenne Primes). In binary, such numbers always consist of n 1-bits. Thus, 31 is 25 or 111112. Contiguous 1-bits at the Least Significant Bit positions invoke mono-stable binary resonance in Collatz. The Least Significant Bit is consumed and because of the contiguous remaining bits, the carry progogates all the way past the Most Significant Bit position. This resonance lasts as long as the length of the original pattern of 1-bits. You can see an example of this here: [1] Scroll to the bottom, past the pictures. --Mensanator 01:03, 12 October 2007 (UTC)
Note that up until the sequence equals it toggles between odd and even n times.
- While resonating, the pattern can never create more than one 0-bit at the LSB. Thus, during resonance, odds & evens lock-step until the initial pattern (called the Core) is consumed. But only bits at the LSB are consumed in this process. The whole time it's resonating, carry bits are accumulating (called the Nebula) past the original MSB (called the Event Horizon). For an example, see [2] --Mensanator 01:03, 12 October 2007 (UTC)
When the sequence equals we finally see the first repeated division by two since so that the sequence is even for the second term in a row.
- Another thing to note is that although the Nebula appears to be random patterns in base 2, they are a constant pattern in base 3. At the moment the resonance halts (and all that is left is the Nebula), you'll see that the Nebula consists of n 2's in base 3. Thus, 111112 -> 222223 --Mensanator 01:03, 12 October 2007 (UTC)
In certain (rare) cases this lets us predict the sequence many terms ahead. For example, we know that if we start at then in 20 steps we will arrive at
- 310-1 is, of course, 22222222223. And not in rare cases, in all cases. But you can do much better than that. I noted that the bit patterns of the Nebula appear random. They aren't, of course, but they tend to have a Negative Binomial distribution in the patterns of contiguous 1 or 0-bits. And so does a number where the bits are chosen randomly. Since it's only the pattern that controls how Collatz sequences, we can pretend that the Nebula created by a Mesenne Number is random. Thus, we can calculate not only how long the Mesenne Number takes to reach 3n-1 but how long it takes to reach 1! If we define Cycle to mean the transition from one odd number to the next, the formula is
The stopping time (in Cycles) for Mersenne Numbers (2^m-1) is predicted to be: m+(1.585*m)/0.415 or 4.819*m
- Keeping in mind that these are statistical (the mean of a Negative Binomial is the inverse of the probabilty. Thus, a "random" pattern of bits yields sequences in which there are a mean of 2 Least Significant zeros). See [3] for small values of m. For really large m, say for the 1st, 6th Generation Type [1,2] Mesenne Hailstone, the prediction is pretty good. This number is 2177149 - 1 (53338 decimal digits). The formula predicts 853681.031 cycles vs. 854697 actual or 99.88%. --Mensanator 01:03, 12 October 2007 (UTC)
Is this worth noting? Am I hitting on something here? Have others noted this before?
- Yes, yes and yes. And that's just the tip of the iceberg. There are many patterns that produce binary resonance. Examples exist of mono-stable, bi-stable, tri-stable and quadra-stable (all of which have their own run-time calculation formulae). One of the most bizarre is the 6th Generation Quadra-cycle Pulsar with 4-bit Rep-unit & 2-bit Resonator. This requires 4098 bits to construct. It has the amzing ability to not simply generate a "random" Nebula, but to actually create a Nebula that rebuilds the Rep-units consumed in the resonance. The only thing that keeps this particular beast from going off to infinity is the fact that Rep-units are consumed faster than they are re-created, so the pulsating resonance is always finite. Picture that Big Bang animation where after the Core is consumed, it re-appears at 1/4 it's previous size, repeating over and over until it ultimately vanishes, leaving behind another "random" Nebula which then collapses to a singularity. --Mensanator 01:03, 12 October 2007 (UTC)
- To me, that sounds very interesting and I can't think having ever seen this observation before. Though I'm a little skeptical and will work out a few examples for myself. But you should scour as many math journals for articles on the Collatz sequence and see if they mention this at all. If they don't, then seriously think about writing up a paper on this and submitting it to the Journal of Integer Sequences. Anton Mravcek 23:04, 8 October 2007 (UTC)
- The OP is definitely spot on, so your tests should confirm it. Other than my own work, I can't say for sure, but I'm fairly certain this has come up before, as it's one of those things that become very obvious in Collatz research if you look at the numbers the right way. I first noted it simply by printing a Collatz sequence in base 2. --Mensanator 01:03, 12 October 2007 (UTC)
Bottom-up Collatz Graph Section
I have several objections to this section:
<quote>
There is another approach to prove the following conjecture, which considers the bottom-up method of growing Collatz graph. Collatz graph is defined by an inverse function,
if
if
Thus looking from this perspective, we have the problem redefined in the following way. The Collatz conjecture states,
- The inverse function forms a tree except for the 1-2 loop.
- All integers are present in the tree.
</quote>
First of all, it is wrong. It should be
if
if
If n=7 then the original rule would have 7 branch to 14 and 13/3 which is not an integer and thus, invalid. The second rule is invoked ONLY when n == 2 (mod 3). Or -1 if you prefer.
Second, it is implied, but not specifically stated, that the rules that are being
inverted are not the same as given in the top of the article. This inverse tree
modifies the odd number rule to be (3n+1)/2. This modification changes the sequence
to
3 -> 5 -> 8 -> 4 -> 2 -> 1 -> 2 -> 1 ...
Whereas the sequence under the original 3x+1 rule is
3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 ...
From the modified rule, you get a "V" tree:
32 10 3 | | / | |/ 16 5 | / |/ 8 | | 4 [1] | / |/ 2 | | [1]
The original rule produces an "inverted L" tree:
32 10__3 | | | | 16_5 | | 8 | | 4__[1] | | 2 | | [1]
Generating an "inverted L" tree is a bit trickier, but the rules would be
if
if
Lastly, why is the 1-2 loop not considered part of the tree? And when saying that
all numbers are on "the tree", I think it should be specifically pointed out that
the conjecture being true implies that there is only one tree. The reason is that
there are other systems, such as 3x+5 or 3x+1 with negative numbers, in which case
there is more than one tree (and thus the conjecture fails for such systems).
--Mensanator 21:47, 3 Feb 2005 (UTC)
Where is a proof? -- Taku 03:13, Mar 23, 2005 (UTC)
Proof of what? What are you asking about? Proof that the bottom-up method described is wrong? Proof that other systems fail the conjecture? I'll be happy to back up my claims if you tell me what you object to.
--Mensanator 23:27, 25 Mar 2005 (UTC)
Well, by a proof I meant a proof of this conjecture. But sorry, I missed this in the article: "The conjecture has been checked by computer for all start values up to 3 × 253 = 27,021,597,764,222,976, but a proof of the conjecture has not been found." -- Taku 00:25, Mar 26, 2005 (UTC)
Would somebody double check the recent anon changes?
Thanks. Oleg Alexandrov 23:48, 30 Mar 2005 (UTC)
I'm going through this article slowly; so far I've added a stub article about Collatz and added a clear statement of the conjecture itself; also I've made the unproven status of the conjecture clearer (responding to the fact that Taku was able to be confused). I'll be double checking everything, so I imagine I will be checking the anon changes. ACW 18:55, 12 May 2005 (UTC)
Rewrite pass
As I mentioned in the last item, I've started a fairly careful rewrite pass, trying to tighten and clarify, and check for accuracy. I don't know exactly how long it'll take; of course anybody is free to help. I've gotten up through the "Examples" section so far. My most major change is to merge the first two sections; the distinction between the "halting" and "non-halting" formulation seemed not worth the trouble to maintain, and could easily confuse the reader.
I mostly decided to use the "non-halting" formulation; the conjecture states that each sequence reaches 1, and doesn't say anything about halting there. This formulation is more amenable to formal rigor, since you can say a[i] = f(a[i-i]) for all i > 1 (and not have to jump through hoops to forbid extension past the first occurrence of 1).
I also adopted a style in which I state things in informal English, followed by a rigorous formula. The non-expert can read just the informal descriptions, and not miss anything. Please read what I've got so far and see what you think. I'd love in particular to hear from Taku to see if it's now clearer that the conjecture is unsettled.
I am strongly tempted to remove the two sections, "Other ways of looking at it" and "Optimizations". A reader who has read down to this point now knows everything about the conjecture that a non-specialist could be expected to know. A reader who is tempted to actually try to solve the problem has been given the basics, and can now be directed to the masterful summary by Lagarias. Somebody should convince me that we need to do more here. "Other ways of looking at it" discusses a small handful of the isomorphism-based approaches that have been tried; "optimizations" might help you make a program for computing Collatz sequences run faster. Both topics are treated with more care in Lagarias.
Without these two sections, the article will be clear, tight, and to the point. With them, it trails off into vague observations of questionable value. Is there any real objection to cutting them? ACW 20:04, 18 May 2005 (UTC)
review/shortening of the entry
Hi -
just stepped in and nearly was to add some contributions - now that discussion says me, that this would be obsolete.
Few comments to the arguments above:
- the Lagarias-article is a deep resource. But for me, as an amateur, it was difficult to understand more than a handful of arguments. If you think of reducing topics like "optimizations" and "other views", then you should at least mention the article of Peter Schorer(*1), which is also concise and deep, but much more readable for a beginner of that subject (Don't forget that especially the Collatz-Problem is a hobby for amateurs).
- There were some definite findings in the Collatz-research, worth to be noted. Those I know are results concerning loops.
Now, why are loops of interest?
a) Finding a loop *disproves* the Collatz-conjecture with one counterexample
b) Proving the non-existence of a loop is half of a proof of the whole conjecture:
- if no divergent trajectory exists AND - if no loop exist then the Collatz-conjecture is settled.
A general loop is still not disproven, but Ray Steiner (1978) and Benne de Weger/John Simons(2000 and 2002) succeeded in disproving certain types of loops (called 1-cycle (Steiner) resp. m-cycle with m=1 to 68 (deWeger/Simons)). The deWeger/Simons-paper was recently online and is possibly still available.
- Reading the above discussion, I think, I better do not involve in that subject myself. But keeping in mind that we have an open question here which attracts many amateurs and has the power to lead them to deeper aspects of number-theory, I'd guessed it a somehow paedagogic aspect to adress accessible subtopics for some cursory num-theory-engaged reader. In my own attempt of the disproof of a 1-cycle-loop I found important connections to the still not completely settled question of bounds of the approximation of m*log(2) to n*log(3) and to the (also not completely solved) waring-problem (see chapter of power-fractions in mathworld.wolfram.com).
But surely - that's a matter of the preferences of a wikipedia and of the intentions of the project-team, where I could not involve myself due to lack of time and intensity.
Kind regards (and thanks for your engagement anyway) -
Gottfried Helms
(*1) In his online-article he even announces a (small) price for some findings. (Don't have the url available at the moment)
--Gottfried 20:06, 1 Jun 2005 (UTC)
The recent work is interesting to me ... I can't think of any reason not to add a link to the Schorer work: please do!
It's a difficult question of policy how much information to put here. I have not yet looked at the page on the Four-Color Theorem, but I would wager that it does not contain a proof! My feeling is that we should provide elementary information, enough for readers to decide whether they are interested, and then appropriate links to the outside world. Wikipedia is not the Internet. Lagarias, Schorer, Erik Weisstein ... that would probably be enough.
ACW 03:33, 2 Jun 2005 (UTC)
Would it be appropriate to balance the "evidence" by pointing out that evidence is not proof? Say, by adding a link to The Law of Small Numbers showing that no matter how many numbers are tested, it will never be enough. And speaking of loops, the "probablistic evidence" falls apart when loop sequences are encountered.
As far as having too much, I don't think there's a problem there. Look up something silly like Andre The Giant. Stupid articles ramble on endlessly. I am in favor of cutting The Abstract Machine because it is terse to the point of being wrong and its author won't budge on that issue. He should make a seperate article where he has the space to give it a proper treatment and then link to it. Otherwise, lose it.
--64.144.30.11 00:50, 16 July 2005 (UTC)
Review/ add. links
The site of P.Schorer is http://www.occampress.com it contains several articles; the introductory is: http://www.occampress.com/intro.pdf
I'm a bit surprised: today I find it not so readable as I recalled from my last visit (about 2003) - maybe it is due to new versions and more abstraction, but he is linked in many pages.
[No: the reason you didn't find it as readable was because you were linked to the paper containing all proofs, instead of to the introductory paper. The above is now the correct link. (Actually, the introductory paper consists of two files. I have linked to the first.) -- Peter Schorer, 8/11/05]
The B. de Weger-article about the loops ("m-cycles") is in http://www.win.tue.nl/~bdeweger/3n+1_v1.33.pdf
The Steiner-article of 1978, which was the first proof in the study of loops (to prove or disprove), disproving the most simple type, called "1-cycle", has never been online, but is referred by the de Weger/Simons - article.
Pls excuse I didn't place the links directly to the right place in the wiki-article: I don't want to possibly damage its html.
Regards -
Gottfried
Gottfried: I was going to do this, but then I had second thoughts. You should do it. You found the references. Don't worry about messing up the wiki. If you mess it up, somebody will fix it. You should just jump in and do it without fear! ACW 00:11, 4 Jun 2005 (UTC)
Ways for the conjecture to be false
I don't think it's possible for it to fall into a loop that excludes 1. For that to happen, would have to equal x, where x is a number in the loop. n = 1 and n >= 3 are obviously not possible if x is a positive integer, so n must equal 2. If equals x, then x must equal 1, so the only possible loop contains 1. --Bart133 (t) 15:12, 25 August 2005 (UTC)
- Why do you think "x: (3x+1)/2n = x" is required for a loop that excludes 1? Isn't the whole point that n/2 and 3n+1 operations are interleaved, seemingly at random? --noösfractal 17:25, 25 August 2005 (UTC)
Bart133: Your reasoning doesn't cover the cases where a loop contains more than one -step. I think you have successfully proven that the 4-2-1 loop is the only one with exactly one tripling step. ACW 16:04, 27 August 2005 (UTC)
Unless you also include the negative integer domain. Here you will find the sequence -1 -2 -1 which also contains exactly one tripling loop. All issues of structure based on patterns of halving and tripling span the entire integer domain, not just the positive integers. In fact, the conjecture is simply false in the negative integers and is usually not discussed. Nevertheless, to properly understand the patterns, you cannot ignore the negative integers because the math takes you there whether or not you want to go there. Every possible pattern of halving and tripling occurs infinitely many times on the Collatz tree and from those patterns one can derive a formula that determines whether of not said pattern forms a loop. But that loop can be either positive or negative. It would be better to say that has only one positive loop. And you should leave 1 out of it since in the generalization to (C a positive odd integer) you'll find that the sequence [3x+C][x/2][x/2] always loops at C, not 1. Of course, the conjecture is provably false for any C not a power of 3, but if one is actually interested in learning "ways for the conjecture to be false" then can be a useful study. --Mensanator 20:49, 3 September 2005 (UTC)
Mensanator: In this case I think we should cut Bart133 some slack, since he did specify "positive" when he stated what he was trying to prove.
Now, continuing just for fun down the path you mention: it turns out that some patterns of halving and tripling can only occur in loops if you generalize to rational numbers. Here, you have to regard a fraction as being even if its numerator is even, and odd if the numerator is odd. So, for example, 1/5 -> 8/5 -> 4/5 -> 2/5 -> 1/5, thus realizing the pattern THHH. Ah, you are actually getting the same generalization by replacing 1 with C above. Excellent. ACW 23:57, 3 September 2005 (UTC)
Sure, Bart133 can have all the slack he needs. I was just trying to point out that things are sometimes clearer when you look at the whole picture. The loop function I refered to is (Z*C)/(X-Y) where X is a power of 2 (and is the number of halving steps) and Y a power of 3 (the number of tripling steps). The sequence is trivially an integer (and thus a loop) if X-Y is 1 or -1. Now the only places where a power of 2 differs from a power of 3 by 1 are {2,3}, {4,3} and {8,9} which give you loops at -1, +1 and -5. If you restricted your research to positive integers, you may not ever discover that interesting bit. Any additional loops would be non-trivial. But it would be wrong to think that there are no non-trivial loops in . A non-trivial loop exists at -17. Sure it's negative, but the very fact it exists means we can't conclude that non-trivial loops are impossible.--Mensanator 01:22, 4 September 2005 (UTC)
dcorradini_argentina
Algoritmo de Syracuse _ Demostración 05/02/06
Terminología:
Impar: x
Par: y
Nº: Números naturales positivos
Impar: 2n-1
Par: 2n
A) Primero quiero demostrar que la ecuación 3x+1 da como resultado siempre un Nº par.
• 3 x + 1 = y = 2n • 3(2n-1)+1 • 6n – 2
- 2 (3n-1) (tiene la forma 2 n, por lo tanto es par para cualquier Nº Natural positivo)
B) Segundo quiero demostrar que la ecuación 3x+1 es una sucesión convergente al Nº 4, tenemos como surge en A lo siguiente:
2 (3n - 1) =
2 [3n1-1, 3 n2-1, 3 n3-1,…….3nn -1]
Lim 2 ((3n1-1), (3 n2-1), (3 n3-1),…….(3nn -1)] = 4
N (n1…nn)==> 1
C) Tercero, demuestro que un Nº par que se divide por 2 es una sucesión convergente al Nº 1.
Y = 2n, por las reglas impuestas, tenemos que a todo N° par se lo debe dividir por 2
Y= 2n/2 = [2 (N1, N2, N3……Nn) / 2] = (2/2) (N1/2, N2/2, N3/2, ……Nn/2)
Lim. (2/2) (N1/2, N2/2, N3/2, ……Nn/2) = 1
N (n1 …nn) ==> 2
Complementando a esto, tenemos el siguiente teorema, que se desprende de las propiedad de los números naturales=
[ (2n1/2) < (2n2/2) < (2n3/2) < ……..< (2nn/2) ]
Por lo tanto tenemos que la sucesión de cualquier N° Natural positivo, donde se aplique las dos reglas del algoritmo de Syracuse/Collatz, siempre que sea un N° positivo so obtendra un N° par y todo N° par se dividira por 2, llegando siempre al N° 1 (después de sucesivas factorizaciones del N° par), a partir de este momento se repite el ciclo por la ecuación 3x+1.
Diego Corradini Buenos Aires Argentina
Obtenido de "http://es.wikipedia.org/wiki/Usuario:Dcorradini"
I was wondering if somebody could add some research paths that people have taken to try to prove it. --yoshi 19:04, 17 February 2006 (UTC)
Why did you post the Spanish version here when you have an English translation at "http://es.wikipedia.org/wiki/Usuario:Dcorradini"?
And speaking of translating, even I know better than to use "Y" as a variable if I'm translating Spanish to English (you might want to go patch up your translated equations).
As to content, is that supposed to be some kind of proof? Aren't you using circular logic? Don't the convergences you speak of assume the conjecture is true? Try the convergences in the negative numbers, specifically, -17. Don't work, do they? You are assuming, without proof, that there are no non-trivial loops in the positive integers. Don't you need to prove that before you can trot out the convergences?
Or did I not understand what you're saying (quite possible since I don't speak Spanish and am relying on the dubious translation). --Mensanator 05:59, 22 February 2006 (UTC)
La demostración esta dada para numeros naturales, no enteros, es decir mayor a cero. en el link de wikipedia vas a encontrar las formulas mejor expresadas, y por cierto no tomo que la conjetura es verdadera, en cambio SI surge que es verdadera por la demostración.-
Saludos cordiales
Diego
Syracuse funcion?
It is not clear what is the relation between syracuse function/conjecture and the collatz conjecture.--Pokipsy76 09:34, 1 March 2006 (UTC)
The problem of Syracusa or Conjecture of Collatz (he/she also has other names) it is the same thing: 3x+1
Greetings
Diego
Re: Syracuse conjecture concerns only odd numbers, so Syracuse function f is the main tool for the Syracuse conjecture, it is the same as the function f defined in [[4]],To prove the Syracuse Conjecture, is to show that for all k ∈ I , there exists an integer n ≥ 1 such that : f n(k) = 1.
greetings
Samiciel
Just looked at your link and I have one question: have you tried making the graph G using negative integers? You say that
The only possibilities for this would be that a cycle exists somewhere in the tree and forms a "whirlpool" which integers cannot leave.
but if you look at -17, you will find just such a "whirlpool". Yes, it's in the negative domain instead of the positive, but the underlying cause of such "whirlpools" is independent of the domain. So there is nothing preventing such a "whirlpool" from occuring in the positive domain.
The fact that integers are determined by their leaving connection, which is oriented toward 1, seems to provide an argument against the existence of such cycles.
The argument is false. The "whirpool" at -17 is the counter-example.
--Mensanator 08:44, 9 March 2006 (UTC)
I think there's an error about de Syracuse function : It is said
Some properties of the Syracuse function are:
- f (4k + 1) = f (k) for all k in .
But so I would say f (4k + 1) = f ( 3k + 1)
Dave Couptily (talk) 13:35, 2 May 2008 (UTC)
- But is an even number. Doesn't the Syracuse function only deal with odd numbers? And why do you claim said property is false? it's easy to see that given any branch, k can attatch at either an odd number of evens above the ood or an even number, essentially:
4k+1___even
|
4k+1___even even
| |
even k___even
| or |
k___even even
| |
odd odd
- Both k and 4k+1 must be odd and both always reduce to the same odd number, so f (4k + 1) = f (k). --Mensanator (talk) 21:49, 2 May 2008 (UTC)
- I'm sorry, I didn't saw that k was an antecedent of 3k+1 by the Syracuse function, so I didn't understood why it was on the same branch. You're right. Thank you for your explanations. Dave Couptily (talk) 13:05, 3 May 2008 (UTC)
Sequences in the Collatz 3x+1 problem
moved:
It has been shown that a binary tree can be used to find infinite sequences of numbers that definitely satisfy the Collatz conjecture ([5] Sequences in the Collatz 3x+1 problem).
Original reasearch violates Wikipedia's rules.
And there is a reason for this: the paper is flawed.
Program 2.1 (edited to show entire tree on one line) zack's 'tree' (Program 2.1) [1] [2] [4] [1, 8] [2, 16] [4, 5, 32] [1, 8, 1, 10, 64] [2, 16, 2, 3, 20, 21, 128] [4, 5, 32, 4, 6, 40, 42, 256] [1, 8, 1, 10, 64, 1, 8, 1, 12, 13, 80, 13, 84, 85, 512] [2, 16, 2, 3, 20, 21, 128, 2, 16, 2, 3, 24, 26, 160, 26, 27, 168, 170, 1024]
Whoa, dude, you got a serious problem. What's with all the repeated values? Why do I see 27 on the 11th level? Because in this line,
if (old_tree[n]-1)/3 % 2 == 1:
you didn't check to see if (old_tree[n]-1)/3 is an integer! For 84, it's not, so you should NOT append 27 to your tree at this point.
And why the infinite recursion? There's no need for that, but I won't quibble about that absurdity.
Here is the proper way to generate the binary tree:
def numerical_tree(tree):
print tree
old_tree = tree
tree = []
# zack's algorithm
# for n in range(len(old_tree)):
# print old_tree[n],
# if (old_tree[n]-1)/3 % 2 == 1:
# tree.append((old_tree[n]-1)/3)
# tree.append(old_tree[n]*2)
#
# the proper way to do it
#
for n in range(len(old_tree)):
tree.append(old_tree[n]*2)
if (old_tree[n] != 4) and (old_tree[n] % 6 == 4):
# # an odd number can't spawn a new branch
# # old_tree[n] % 6 == 4 ensures that only
# # even numbers divisible by 3 after subtracting 1
# # spawn new branches of the binary tree
tree.append((old_tree[n]-1)/3)
numerical_tree(tree)
numerical_tree([1])
My tree, formated to show proper binary relationship
[1] [2] [4] [8] [16] [32, 5] [64, 10] [128, 21, 20, 3] [256, 42, 40, 6] [512, 85, 84, 80, 13, 12] [1024, 170, 168, 160, 26, 24] [2048, 341, 340, 336, 320, 53, 52, 48] [4096, 682, 680, 113, 672, 640, 106, 104, 17, 96]
That's as far as I got in your paper, but I think it's enough to disqualify its inclusion in the Wikipedia. What you should do is fix up that paper so that it actually accomplishes something, submit it to a journal for publication (and don't be surprised when it's rejected), and then you can reference it here.
--Mensanator 00:35, 29 March 2006 (UTC)
"you didn't check to see if (old_tree[n]-1)/3 is an integer! For 84, it's not, so you should NOT append 27 to your tree at this point."
(84-1)/3 % 2 != 1. 27 comes from (82-1)/3. There are going to be repeated values. This simple algorithm is not the focus of the paper; it's just an example from which the paper branches. Don't worry and just keep reading.
Why do you think the 27 comes from 82? There's no 82 in the previous tree. If you line up the numbers, you'll see that 27 is a left child of 84.
[1, 8, 1, 10, 64, 1, 8, 1, 12, 13, 80, 13, 84, 85, 512] [2, 16, 2, 3, 20, 21, 128, 2, 16, 2, 3, 24, 26, 160, 26, 27, 168, 170, 1024]
Are you aware that Python does integer division? That it simply discards the remainder?
>>> print (84-1)/3 27
If you don't know what you're doing, use divmod:
>>> print divmod(84-1,3) (27, 2)
then you can see that your division was invalid.
Look at my tree. There are NOT supposed to be repeated values. You say in your paper
the program actually generates the Collatz tree level by level
But your program doesn't do that, does it? How did you come to the conclusion that Program 2.1 was generating the Collatz tree level by level? Do you acually think numbers appear on the Collatz tree more than once? Is there any point in reading the rest of the paper having demonstrated that a) you don't understand how to program, b) you don't understand the Collatz problem and c) you make no effort at quality control? What do you think an actual peer reviewer would do with your paper?
27, by the way, properly appears on level 112, which cannot be reached by your program even if you take out the silly infinite recursion. If you do it properly and save your trees into text files to prevent running out of memory, you'll find that the files are 3 GB by the time you reach level 84. That's where I stopped because the level files exceeded the capacity of a CD even when zipped.
And why not register with Wikipedia and get a user account. Then you can sign your posts. Right now I'm just talking to an IP address.
--Mensanator 05:42, 29 March 2006 (UTC)
Ok, I read the rest of the paper. Program 4 & 5 basically do the same thing, so I'll only make a distinction when necssary.
First of all, Programs 4 & 5 appear to work better than Program 2 (possibly because they don't use division).
They are, however, incomplete. You state that they "creates and follows a general binary tree". Your programs do NOT create a binary tree. They don't even create any Collatz numbers because you neglected to assign any values to "n" in
(2**(i+r*n)-a)/3**b
All your programs do is create the parameters a,b,i,r. This can be easily rectified by wrapping a,b,i,r in a for loop once a,b,i,r are calculated:
for n in range(0,10): p = (2**(i+r*n)-a)/3**b print 'n: %2d %d' % (n,p)
from which we get:
1 1 0 2 n: 0 0 n: 1 1 n: 2 5 n: 3 21 n: 4 85 n: 5 341 n: 6 1365 n: 7 5461 n: 8 21845 n: 9 87381
Oh dear, 1,1,0,2 produces a 0 for n=0 and 0 isn't on the Collatz tree (other a,b,i,r sets give negative numbers). Should I start the n-loop at 1? No, because some a,b,i,r sets require n=0.
Ignoring that, let's look at the numbers actually produced. Plotting the numbers on the Collatz tree:
a b i r
1 1 0 2
87381-----x
x
21845-----------x
x
5461-----------------x
x
1365----------------------x
x
341---------------------------x
x
85-------------------------------x
x
21----------------------------------x
x
5-------------------------------------x
x
x
x
1
shows that they are all on order 1 branches. But not the entire branch, just the first element. To see the second element, we have to re-calculate a,b,i,r:
2 1 1 2
n: 0 0
n: 1 2
n: 2 10
n: 3 42
n: 4 170
n: 5 682
n: 6 2730
n: 7 10922
n: 8 43690
n: 9 174762
a b i r
2 1 1 2
174762
x------x
43690 x
x------------x
10922 x
x------------------x
2730 x
x-----------------------x
682 x
x---------------------------x
170 x
x-------------------------------x
42 x
x-----------------------------------x
10 x
x---------------------------------------x
x
x
2
x
Uhh...this isn't exactly a binary tree. The numbers created by any given set of a,b,i,r are cousins, not children.
How does it follow from this that EVERY node on the tree is generated? Program 2 (when done correctly) generates every child of every element of a given level. By induction, all nodes are created.
And even if I discount the 0's and negative numbers, there's another problem: duplicates. If you are properly generating a Collatz tree, there won't be any duplicate values. Yet, a=38 b=2 i=1 r=6 n=1 evaluates to
(2**(1+6*1)-38)/3**2 = (2**7-38)/3**2 = (128-38)/9 = 10
as does a=2 b=1 i=1 r=2 n=1
(2**(1+2*2)-2)/3**1 = (2**5-2)/3**1 = (32-2)/3 = 10
Furthermore, both a=67 b=2 i=2 r=6 n=1 and a=1 b=1 i=0 r=2 n=3 evaluate to 21. Did you even know this was happening? Do you want to know why?
a=1 b=1 i=0 r=2 n=3 is the "correct" answer. Since b corresponds to the number of 3n+1 steps in a sequence, that set of parameters corresponds to the actual sequence from 21:
21--64
32
16
8
4
2
1
So where does the other 21 come from?
Note that it has b=2. But also note that (i+r*n) corresponds to the number of n/2 steps in a sequence. If we start at 21 and do 8 even steps and 2 odd steps instead of 6 evens and 1 odd, we get:
21--64
32
16
8
4
2
1--4
2
1
Thus,
(2**(2+6*1)-67)/3**2
defines the sequence if you MAKE TWO LOOPS AROUND THE ROOT.
Finally, to reach 27 with this "sieve", the b lookup table needs 2*3**40 or 2199023255552 entries. I doubt this will be of any use to push the research limit past 6*2**58.
Oh, and by the way, there's nothing inherrently wrong about the ideas presented in Program 5, I use a similar technique in my own programs. But I don't claim it's something it's not.
--Mensanator 02:34, 31 March 2006 (UTC)
Obvious Optimization
Wouldn't the most obvious optimization be to stop if the current value of the function is less than the original input, since all numbers below the input must have terminated, or the program would have screamed, "i've found a counterexample!"? If so, perhaps it should be added? or was it perhaps considered too obvious to do so?
- Hmmm, I thought it was there. I'll check soon, unless somebody else beats me to it. You're right, though: if a starting value has a smaller iterate, the search program should immediately proceed to the next starting value; and if all starting values could be shown to have smaller iterates, the conjecture would be established. ACW 04:48, 23 August 2006 (UTC)
Pseudocode Standard
I used the standard found here: [6] What standard are you referencing? --Mensanator 22:39, 24 August 2006 (UTC)
Probabilistic evidence
The statement "A rebuttal by contradiction would be the number 3 : 3 10 5 16 8 4 2 1" is not a rebuttal because it clearly says average and about. Rolling snake-eyes on a pair of dice does not rebut the claim that the average outcome of a roll of dice is 7.
One can always find an example of a sequence of n consecutive increasing odd numbers simply by starting with a Mesenne Number (2**n-1) or any number having n consecutive 1's at the least significant bit position of the number when represented in binary. But such patterns are not representative of the average.
For a binary number of n bits chosen at random, the distribution of consecutive 1's will be a Negative Binomial, specifically, a Geometric Distribution. In such a distribution, there will be twice as many 1-bit patterns as 2-bit, twice as many 2-bit as 3-bit, twice as many 3-bit as 4-bit, etc. The mean of a Geometric Distribution is the inverse of the probability. Thus, for such a randomly chosen number the mean bit pattern length will be 2 regardless of how large n is. And a mean of 2 consecutive 0's at the least significant bit position implies that the mean number of consecutive n/2 operations will be 2 for every 3n+1 operation resulting in the consecutive odd numbers being about 3/4 on average.
For example 2**177149-1 has 177149 consecutive increasing odd numbers. But the last of those odd numbers has 177149*1.585 bits whose pattern is a Geomtric Distribution (the result of converting 3**177149-1 to base 2) from which point on the sequence will indeed average 3/4. From this relationship we can predict that there will be
n + (1.585 * n)/0.415 or 4.819 * n
odd numbers, where n is the number of bits in the Mersenne Number.
Therefore, the sequence should have
4.819*177,149 or 853,681
odd numbers. It actually has
854,697
making the prediction accuracy 99.88%.
So the probalistic evidence is still correct despite the sequence beginning with 177149 consecutive increasing odd numbers. --Mensanator 18:14, 26 August 2006 (UTC)
Suppose n is odd. Then 3n+1 is even. With probability 1/2 the next odd number is (3n+1)/2;
- So half of all even numbers have a single factor of 2.
with probability 1/4, the next odd number is (3n+1)/4;
- So half the remaining even numbers have 2 factors of 2.
with probability 1/8, the next odd number is (3n+1)/8;
- So half the remaining even numbers have 3 factors of 2.
and so on.
- Making the factors of 2 a Geometric Distribution with probability 1/2.
Of course, these probabilities are only heuristic.
- And the mean of a Geometric Distribution is the inverse of the probability.
Anyway the expected size of the next number is
- (3n+1)/(2*2)
- I'm not sure about this. Where's the error in my derivation? See below for further thoughts. DRLB 22:42, 18 January 2007 (UTC)
therefore
- .
In other words, the probabilistic evidence suggests that the next odd number should be slightly larger.
- Then we would expect to see sequences diverging to infinity, but we don't see that.
Please correct me if I'm wrong.
- Sequences do NOT diverge to infinity, they converge to 1.
Assuming I'm right,
- I don't see how.
for now, then I'd guess that there may be still be a strong heuristic probabilistic argument that the sequence will hit 1 in general. I estimate the standard deviation to be about , and perhaps this is large enough that one can argue heuristically the sequence will decrease sufficiently often to eventually hit 1.
- Have you tried this with, say, numbers with 53000 decimal digits? Think your standard deviation covers that case? Or did I just get lucky? --Mensanator 06:06, 18 January 2007 (UTC)
DRLB 20:07, 16 January 2007 (UTC)
Hmm ... I checked one of the references and found a page [7] on this heuristic argument.
I don't exactly agree with Mensanator or this page (which are essentially the same argument), but the disagreement is over a technicality. Expectation must be calculated as a sum of the possible outcomes weighted by their probabilities.
My calculation, according this rule, gives n+1/3. The other arguement uses a product of the outcomes, weighted by the probalities (using power to define the weight). Formally speaking, this is not expectation, per se. But of course it has meaning, and is good heuristic evidence.
Of course, it can be converted to an expectation by applying a logarithm. So, the expected value of the logarithm can the ratio of consecutive odd numbers is log (3/4).
Note that the logarithm of expectation is not the same as expectation as the logarithm. In other words, we're both right.
I think the article could be corrected to avoid this confusion from arising again. DRLB 22:42, 18 January 2007 (UTC)
- Ok, so expectation isn't the same as heuristics. So what? The point being discussed here is heuristics. And if we're both right, then one of us is more right than the other. The article should remain as it is. Any confusion on your part is not Wikipedia's problem as long as the point it's making is made correctly, which it is.
- And even if your Great Expectations are correct, what good are they? How does "the expectation that the odd successor of an odd number is slightly larger" provide any insight into why Collatz sequences always converge to 1?
- In contrast, look at how useful the heuristic is: every odd number in a Collatz sequence will be succeeded by a mean of two even numbers. Earlier, I showed how to predict the number of odd numbers in the Collatz sequence of 2**177149-1 and got an answer (853681) that was within 0.12% of the actual result of 854697. By the heuristic, the number of evens should then be 2*853681 or 1707362. It actually has 1531812, only 89.7% acurate.
- Oops, in my haste I miscalculated the even number prediction. Because the seed of the sequence in question is a Mersenne Number, the heuristic is not applicable until after the first 177149 odd numbers of the sequence. The correct calculation is 177149+(853681-177149)*2 = 1530213 or accurate to 99.9%. --Mensanator 18:08, 19 January 2007 (UTC)
- Not as good, but these calculations are based on statistics, so your mileage may vary. I don't see how n+1/3 provides any clue at all as to how to figure sequence length. As evidenced by this discussion, you seem to be introducing confusion as opposed to reducing it.
- If you can justify the expectation (assuming you have a citation), then go ahead and add it as further probabilistic evidence, but leave the discussion of the heuristic alone. --Mensanator 07:19, 19 January 2007 (UTC)
Just to be sure, I ran some tests on the first 20,000 odd numbers. The average difference between the next odd number and the current for these was 0.6987. In particular, note that, the next odd was slightly larger, on average. Indeed, it is even larger than the 1/3 difference that I heuristically estimated. However, exponentiating the average logarithm of the ratio of the next odd to the current odd gave 0.7500979897, which is about the 3/4 one expects heuristically, suggesting that the next odd should be considerably smaller, on average. This difference arises because of different meanings of average. Maybe this is worth adding to Paradox, provided that there is some published literature about such kinds of counterintuitive phenomena, which is surely more general than the Collatz problem. Then again, maybe it's not worth it. DRLB 23:21, 18 January 2007 (UTC)
- Questions: [1] How are you actually calculating this? My two attempts at figuring out what you meant produce results nothing like yours. [2] How did you decide that 20000 was statistically significant? [3] Why did you use the first 20000 odd numbers as opposed to 20000 random odd numbers or 20000 odd numbers having 50000 bits each? [4] Can you re-run this test using 20000 consecutive odd numbers from an actual Collatz sequence? Otherwise, I'd say your test is pretty meaningless since consecutive odd numbers do not form a Collatz sequence. --Mensanator 07:19, 19 January 2007 (UTC)
Here's a smaller example of what I did. Take the first four odd numbers: 1,3,5,7. For Collatz sequences beginning with these numbers, the next odd number is 1,5,1,11, respectively. The differences are (1-1),(5-3),(1-5),(11-7), that is, 0,2,-4,4. The average difference is (0+2-4+4)=1/2. More precisely, the arithmetic mean of the difference is 1/2. The other sense of average growth, the sense in probabilistic evidence of the article, can be expressed as the geometric mean of the ratios, (1/1),(5/3),(5/1),(11/7), which is the fourth root of 11/21, or about 0.85. DRLB 18:07, 19 January 2007 (UTC)
- No, the differences are (1-1), (3-5), (5-1) and (7-11), that is, 0,-2,4,-4. The average difference is (0-2+4-4)/4=-1/2. And your ratios are also wrong. Should be (1/1),(3/5),(5/1),(7/11) so the geometric mean would be 4th root of 105/55, or about 1.175. And even the wrong ratios you gave don't have a product of 11/21, the product would be 275/21 whose 4th root is about 1.9. Now I understand why I couldn't figure out how you came up with that goofy result from the 1st 20000 odd numbers. Perhaps you should re-think your role as a Wikipedia contributor until you learn how to use your calculator. --Mensanator 00:53, 20 January 2007 (UTC)
- Mensanator, you negated the differences I used. The next odd number after 3 is 5, because 3(3)+1 = 10, and 10/2=5. 3 has increased by 2, that is to 5, so the difference I gave was correct. Also, the ratios I gave had an glaring typo, 5/1 should have been 1/5. My apologies. Again, once corrected, these are exactly the inverses of the ratios you gave. Anyway, their product (after correcting the typo) is 55/105 = 11/21, the inverse of the ratio that you give, because you again divided the previous odd by the next. We both can calcuate fourth roots, it seems, since 0.85 * 1.175 = 0.99875, which is close to 1, as it should be since we used inverse values. Clearly, we can use both calculators, unless you calculated the fourth root by hand. Finally, this is a talk page, so we ought to be more forgiving, don't you agree? DRLB 17:12, 24 January 2007 (UTC)
- Ok, I can be more forgiving. Provided you make an effort to see the forest instead of the trees. It doesn't matter whether you use n/succ(n) or succ(n)/n. The geometric mean of n/succ(n)=1.175 implies that the next odd number will be slightly smaller. The geometric mean of succ(n)/n=0.85 implies that the next odd number will be slightly smaller, which is exactly the same conclusion as the other ratio. In neither case is the implication that the next odd number will be slightly larger as you originally claimed. You have more than just your values inverted, your whole argument is inverted and thus wrong and the original Wikipedia article is correct. Oh, and your claim of n+1/3 was bogus also. When you use the wrong ratios like you did, you get 4/3 or 1.333... decimal, so the correct thing is 1+1/3, not n+1/3. --Mensanator 06:37, 25 January 2007 (UTC)
- Finally, we agree on the geometric mean. All I've trying to say here is that, in the geometric mean, the next odd is smaller. This is the forest that you allude to, and I see it. I was never claiming that the article was wrong, rather imprecise on what is meant by average. Maybe I'm being pedantic, but to me the default meaning of average is arithmetic mean, so a clarification was in order. I maintain that, in the arithmetic mean, the next odd is larger, by a difference of 1/3. This presumes that one takes a random odd starting value. Earlier, however, you asked me compute the arithmetic mean (of the difference between successive odds) for the odd numbers in a Collatz sequence. If you run the sequence until it hits 1, then it will be negative, i.e. not positive 1/3. Thus the heuristic that the odd number in a Collatz sequence have the same distribution as uniform seems to fail (by the way, the evidence of a geometric mean of 3/4 for suggesting convergence to 1 depends on the very same heuristic, that odd numbers in a Collatz sequence behave as uniform odd numbers). Anyway, this is a curious phenomenon, perhaps worth mentioning, but obviously not in a way that distracts from the main point. It's interesting to me that the geometric mean predicts a decrease while the arithemtic mean predicts an increase, but maybe I'm just goofy in general. Again, I'd be surprised if all this was not noted somewhere else. DRLB 15:39, 25 January 2007 (UTC)
At least we are slowly starting to communicate. I've obviously not been understanding some things you said, BOTOH, I think you were not very clear. In the following, I've made sure I used the same thing you did, succ(n)-n and succ(n)/n for Arithmetic Mean (AM) and Geometric Mean (GM). But I'm still confused.
You said the AM of the first 20000 odd numbers is 0.6987. I get that now also, but I fail to see what the significance is.
AM of 100 odd numbers: 0.56 AM of 200 odd numbers: 0.77 AM of 300 odd numbers: 0.34 AM of 400 odd numbers: 0.64 AM of 500 odd numbers: 0.48 AM of 600 odd numbers: 0.753333333333 AM of 700 odd numbers: 0.394285714286 AM of 800 odd numbers: 0.6925 AM of 900 odd numbers: 0.544444444444 AM of 1000 odd numbers: 0.806 AM of 1100 odd numbers: 0.376363636364 AM of 1200 odd numbers: 0.585 AM of 1300 odd numbers: 0.507692307692 AM of 1400 odd numbers: 0.734285714286 AM of 1500 odd numbers: 0.433333333333 AM of 1600 odd numbers: 0.66 AM of 1700 odd numbers: 0.581176470588 AM of 1800 odd numbers: 0.787777777778 AM of 1900 odd numbers: 0.357894736842 AM of 2000 odd numbers: 0.62
The AM is completely unstable for the odds, so of what use is this when comparing to the AM of a Collatz sequence?
The GM of the odds at least is somewhat stable:
GM of 100 odds: 0.763088110546 GM of 200 odds: 0.75433373718 GM of 300 odds: 0.749584108063 GM of 400 odds: 0.75368585376 GM of 500 odds: 0.751960072532 GM of 600 odds: 0.753409836832 GM of 700 odds: 0.749230723047 GM of 800 odds: 0.751297997523 GM of 900 odds: 0.751170047199 GM of 1000 odds: 0.751586927746 GM of 1100 odds: 0.750506937857 GM of 1200 odds: 0.750040383186 GM of 1300 odds: 0.750845232813 GM of 1400 odds: 0.751163263524 GM of 1500 odds: 0.75074441619 GM of 1600 odds: 0.751028202758 GM of 1700 odds: 0.75158478744 GM of 1800 odds: 0.750922077419 GM of 1900 odds: 0.750329418241 GM of 2000 odds: 0.750576235761
Although the GM of an actual Collatz sequence looks more like this:
An actual Collatz sequence (built by tree crawler) from: 115965183147145828891382318276603995721415182948139056866257 72398441281808105172818431359253618093491566168722452508153
GM of first 100 Collatz: 0.576328192983 GM of first 200 Collatz: 0.580336872578 GM of first 300 Collatz: 0.583024804016 GM of first 400 Collatz: 0.573339865314 GM of first 500 Collatz: 0.580592397566
Which is also somewhat stable although it bears no resemblence to that of the odd numbers. And yes, the AM is negative. Really, really, really negative.
AM of first 100 Collatz: -1.15965183147e+116 AM of first 200 Collatz: -5.79825915736e+115 AM of first 300 Collatz: -3.8655061049e+115 AM of first 400 Collatz: -2.89912957868e+115 AM of first 500 Collatz: -2.31930366294e+115
But maybe the tree crawler algorithm wasn't the best choice for a Collatz sequence generator. A tree crawler creates a path that minimizes the factors of 2. Perhaps a similar magnitude number created from random decimal digits would be more representative.
No surprise, the AM seems meaningless for this one also:
Now try a 119 digit random number 170171216567461327555762455479240297769664115111878616708268 24858491332473375089924042517307901176091503666104708437023
AM of first 100 Collatz: -1.70171216567e+116 AM of first 200 Collatz: -8.50856082837e+115 AM of first 300 Collatz: -5.67237388558e+115 AM of first 400 Collatz: -4.25428041419e+115 AM of first 500 Collatz: -3.40342433135e+115 AM of first 600 Collatz: -2.83618694279e+115 AM of first 700 Collatz: -2.43101737954e+115 AM of first 800 Collatz: -2.12714020709e+115 AM of first 900 Collatz: -1.89079129519e+115 AM of first 1000 Collatz: -1.70171216567e+115
Ah, but look at the GM.
GM of first 100 Collatz: 0.046809670875 GM of first 200 Collatz: 0.18287838408 GM of first 300 Collatz: 0.296127794073 GM of first 400 Collatz: 0.390788382319 GM of first 500 Collatz: 0.443977997494 GM of first 600 Collatz: 0.489583606479 GM of first 700 Collatz: 0.531275542781 GM of first 800 Collatz: 0.557564646428 GM of first 900 Collatz: 0.572699420436 GM of first 1000 Collatz: 0.587133849254
Makes you even wonder why we're making such a fuss over the heuristics, eh? --Mensanator 02:43, 26 January 2007 (UTC)
# just how atypical was the tree crawler number? # import collatz_functions as cf # # the tree crawler number tc = 11596518314714582889138231827660399572141518294813905686625772398441281808105172818431359253618093491566168722452508153 # by construction, tc should have EXACTLY 500 odd # numbers in it's Collatz sequence tc_stats = cf.collatz(tc,0) # returns [evens,odds] of sequence print tc_stats # # [1185, 500] # # the random number rn = 17017121656746132755576245547924029776966411511187861670826824858491332473375089924042517307901176091503666104708437023 # had over a thousand, specifically rn_stats = cf.collatz(rn,0) print rn_stats # # [2000, 1014] # # the number of bits in each number was tc_bits = cf.gmpy.numdigits(tc,2) rn_bits = cf.gmpy.numdigits(rn,2) print tc_bits,rn_bits # # 393 393 # # The heuristic of every odd number being followed # by an average of 2 even numbers coupled with the # mean 1.585 bits of carry per odd number means there # is a net loss of 0.415 bits per odd number. # Therefore, a random number of m bits should result # in a Collatz sequence containing m/0.415 or m*2.409 # odd numbers. # # Or the actual odd number count divided by the # bit-length should be 2.409. # print float(rn_stats[1])/rn_bits # # 2.58015267176 # # Hmm...close but not exact. Must have gotten lucky # with the random number generator. But the tree # crawler odd/bit ratio was extremely atypical: # print float(tc_stats[1])/tc_bits # # 1.27226463104 # # That's not something you're likely to see by testing # random 119 digit numbers.
--Mensanator 07:49, 26 January 2007 (UTC)
Mensanator, thank you for running those tests. I also ran a few more tests too. Taking random odds n (instead of taking the first bunch of odds), I found that the AM of s(n)-n fluctuates quite wildly. Probably this is because of the fairly large standard deviation. The fact that is somewhat close to 1/3 when taking the first set of odds, may in fact be just a coincidence. In similar tests for the GM, I found less fluctuation, similar to what you found. I don't have a good explanation for any of this.
Anyway, back to the article. I don't think that the AM stuff needs to mentioned in the main article, and here's why. I went to Lagarias's annotated bibliography, and couldn't find mention of it. I then asked him. He responded quickly, saying he was unaware of people studying tha AM. Therefore, whether or not the AM is relevant, significant or interesting, it would be original research, which disqualifies form inclusion in a wikipedia article.
When I first read the article, I interpreted average to mean AM. There was no hint the average meant geometric mean of the ratios. Also, since there was no derivation of the 3/4 or supporting reference, I tried to derive the result myself, and got something different, because I naively used the AM. Only on reading your contributions to the discussion page, did I learn that what was meant was the GM. Since then, I've tried to clarify the article, at least to my satisfaction, by linking to Lagarias's derivation of the 3/4, and stating that the average in the sense of the geometric mean. DRLB 17:04, 26 January 2007 (UTC)
- I agree, no point in discussing the AM. And the "getting something different" was my problem with your original posts, although I think we are now on the same page. And I have no problem with the way you edited the article. This has got to be a first for Wikipedia - a discussion where both parties end up agreeing. :-)
- Oh, and I ran one more test to satisfy my curiosity. I mentioned that my tree crawler algorithm "minimizes the factors of 2". That wasn't a good way to put it since the tree crawler sequence had roughly twice as many evens as odds just like the random number. The significant difference between the two is how those factors are distributed. For a random number, we get a Geometric Distribution:
# rn factor of 2 distribution (* scale = 8) # 1 (527) ***************************************************************** # 2 (243) ****************************** # 3 (117) ************** # 4 ( 62) ******* # 5 ( 36) **** # 6 ( 13) * # 7 ( 6) # 8 ( 5) # 9 ( 3) # 10 ( 1) # 11 ( 1)
- But for the tree crawler sequence, the distribution is very different and probably explains the difference in the GMs of the two sequences:
# tc factor of 2 distribution (* scale = 8) # 1 ( 98) ************ # 2 (229) **************************** # 3 ( 63) ******* # 4 (110) *************
Collatz's Conjecture Proved!
A very simple and general solution to Collatz-type problems is presented here: [8]. It's worth looking into ...
I've seen it. It's rubbish.--Mensanator 18:37, 10 September 2006 (UTC)
- Come back when this has been published in a mathematical journal. Fredrik Johansson 10:01, 10 September 2006 (UTC)
- You might want to view my "Collatz 3x+1 Conjecture Proved!" publication submissions history at http://www.geocities.com/collatz_conjecture_proved/ then YOU DECIDE! For aspiring authors in mathematical journals, there are plenty of lessons to be learned.
- Geocities.com websites from Yahoo.com that are free have limitations such as a maximum of 4.2 MB data transfer per hour -- basically, with the large count of "screen shots" for the ../collatz_conjecture_proved/index.htm file, this allows only 1 user access per hour. I posted them in a public website because I am sure that they will survive me (without any maintenance from me). BenCawaling 08:36, 6 June 2007 (UTC)
- What a shame. I would have thought something as important as a proof of the Collatz Conjecture rates more than a lame-ass free website. I noticed you removed my paper from your list of references. You didn't steal any of my intellectual property, did you? --Mensanator 20:56, 9 June 2007 (UTC)
- Tsk, tsk. Sorry, this GeoCities site is currently unavailable.The GeoCities web site you were trying to view has temporarily exceeded its data transfer limit. Please try again later. Are you the site owner? Avoid service interruptions in the future by increasing your data transfer limit! Find out how. Learn more about data transfer. I guess I'll just have to write you off as a crank.--Mensanator 01:19, 7 June 2007 (UTC)
- Finally got through and it was well worth it! Almost as funny as James Harris. I guess I'm not the only one who thinks it's rubbish. --Mensanator 05:32, 7 June 2007 (UTC)
I concur. Sr13 01:52, 28 September 2006 (UTC)
LOL, the guy also claims to have proved P=NP on his website. Crackpots seem to prefer "proving" difficult conjectures in pairs ;)
Removing link
- Collatz Observations discusses observations about the Collatz Conjecture as it pertains to a bijection over the natural numbers.
I am removing the above link from the External links section because the page it links to is incorrect. It claims to present a breathtakingly simple proof of the conjecture which is, as it turns out, not a proof at all. I just thought I'd leave a note here in case there's any question. -GTBacchus(talk) 22:27, 26 September 2006 (UTC)
SYNOPSIS OF SIMPLE PROOF
The streamlined Collatz 3x+/-1 sequences —
Cn = <n, (3n+/-1)/2i, {3[(3n+/-1)/2i]+/-1}/2j, ...>
-involve only positive odd integer terms. The 3x+1 sequences in the negative integers domain are equivalent to the 3x-1 sequences in the positive integers domain.
The rigorous proof that there is no divergent 3x+/-1 sequence Cn in the positive integers domain follows from the fact that there is none in the positive rational numbers domain where each 3x+/-1 cycle-equations for any positive integer cycle-length > 1 has valid solutions — thus, any Cn is either fully cyclic or converges to some cyclic subsequence (there is only one respective cyclic subsequence for each not fully cyclic Cn).
The rigorous proof that any valid cycle-length h+1 > 1 cyclic preferred 3x+/-1 sequence Cx0 <(x0, x1, x2, x3, ..., xh)> [that is, the exponents of 2 in the denominators i = j = ... = 1 so that some of the sequence terms xi are positive even integers] could only have relatively small finite values follows from Marc Chamberland’s and Kenneth Monks’ independently proven assertion that the sum of the even cycle-terms xi is equal to the sum of the odd cycle-terms xi +/- the count of the latter.
[These rigorous proofs are presented in my unfinished manuscript “3x+1 problem solved, 3x+1 conjecture proved!” — unfortunately, I have been suffering from extreme blurred vision due to my persistent exploding optical nerves brought on by my uncontrollable diabetes so I am rarely able to work on my computer; indeed, I have had only about 30 days of barely productive time in the last 369 days so if my health prevents me from completing the said paper, I just hope others interested in the Collatz 3x+1 problem or conjecture might find the proof useful now].
The following assertions are easily proved (the rigorous proofs are also included in my aforementioned unfinished paper):
- C1 = <(1)> = <1, 1, 1, ...> is a trivial streamlined 3x+/-1
cyclic sequence.
- Every positive odd integer n has the form 4p+/-1 for some
nonnegative integer p.
- For the streamlined 3x-1 sequences, any term with the form
4p+1 has the successor term [3(4p+1)-1]/2k = 6p+1 > 4p+1
[for k = 1, 6p+1 is already odd — this means that the
streamlined 3x-1 iterates increment by only about half of
the current term] while any term with the form 4p-1 has the
successor term[3(4p-1)-1]/2k = (3p-1)/2k-2 < 4p-1
for all k >= 2 [this means that the streamlined 3x-1
iterates may decrement drastically — by about 1/4, 3/2, 13/4,
... of the current term and even immediately down to some
minimum cycle-term such as 1, 5, or 17]. Thus, any valid
streamlined 3x-1 cyclic sequence with cycle-length > 1 has at
least one increasing (that is, it has a larger
successor-term) and a minimum cycle-term with the form 4p+1
as well as at least one decreasing (that is, it has a smaller
successor-term and a maximum cycle-term with the form 4p-1.
- For the streamlined 3x+1 sequences, any term with the form
4p-1 has the successor term [3(4p-1)+1]/2k = 6p-1 > 4p-1
[for k = 1, 6p-1 is already odd — this means that the
streamlined 3x+1 iterates increment by only about half of
the current term] while any term with the form 4p+1 has the
successor term [3(4p+1)+1]/2k = (3p+1)/2k-2 < 4p+1 for all
k >= 2 [this means that the streamlined 3x+1 iterates may
decrement drastically — by about 1/4, 5/2, 13/4, ... of the
current term and even immediately down to some minimum
cycle-term such as 1]. Thus, any valid streamlined 3x+1
cyclic sequence with cycle-length > 1 has some increasing
and a minimum cycle-term with the form 4p-1 as well as some
decreasing and a maximum cycle-term with the form 4p+1.
- Each n that is not divisible by 3 [if n is a multiple of 3
then 2kn+/-1 is not divisible by 3 for any positive integer k]
has potentially infinite streamlined-3x+/-1-sequence-
predecessor terms (2kn+/-1)/3 [in this presentation, the top
and bottom signs of “+/-� correspond to the top and bottom
signs of “3x+/-1” except here where it should be reversed]
which form some 4p+/-1-recursive sequence <p1, p2 = 4p1+/-1,
p3 = 4p2+/-1 = 4(4p1+/-1) +/-1, ...> with a positive odd
integer first term p1 — for the 3x-1 sequences, p1 = 4a-1
with a even or p1 = 4a+1 with a either odd or even while for
the 3x+1 sequences, p1 = 4a+1 with a even or p1 = 4a-1 with
a either odd or even.
- Only 1 term of a 4p+/-1-recursive sequence <p1, p2, p3, ...>
could be in the same valid streamlined 3x+/-1 cyclic sequence
since the forward streamlined 3x+/-1 iteration function always
returns only one successor-term value.
- The successive terms of a 4p+/-1-recursive sequence <p1, p2,
p3, ...> have periodic residues modulo 3 — that is, one of
these forms:
(1) p1 == 0, p2 == 1, p3 == 2, p4 == 0, p5 == 1, p6 == 2, ...
(2) p1 == 0, p2 == 2, p3 == 1, p4 == 0, p5 == 2, p6 == 1, ...
(3) p1 == 1, p2 == 2, p3 == 0, p4 == 1, p5 == 2, p6 == 0, ...
(4) p1 == 1, p2 == 0, p3 == 2, p4 == 1, p5 == 0, p6 == 2, ...
(5) p1 == 2, p2 == 0, p3 == 1, p4 == 2, p5 == 0, p6 == 1, ...
(6) p1 == 2, p2 == 1, p3 == 0, p4 == 2, p5 == 1, p6 == 0, ...
- Each of the higher monotone increasing 4p+/-1-recursive-
sequence terms p2 < p3 < p4 < ... has the same immediate
streamlined-3x+/-1-sequence-successor term n = (3p1+/-1)/2k-2
< 4p1+/-1 (for k >= 2) as p1.
- Any valid streamlined 3x+/-1 sequence cycle-term is not
divisible by 3. Thus, any Cn with n a multiple of 3 converges
(every Cn is convergent) to some proper cyclic subsequence
(that is, n is not a cycle-term but some of the streamlined-
3x+/-1-sequence-successor terms of n form a loop).
- If p1 is a cycle-term and p2 is divisible by 3, then Cp2 as
well as Cp3, Cp4, Cp5, ... all converge to the same valid
proper streamlined 3x+/-1 cyclic subsequence Cp1.
- If p1 or p2 is a cycle-term and p3 is divisible by 3, then
Cp3 as well as Cp4, Cp5, Cp6, ... all converge to the same
valid proper streamlined 3x+/-1 cyclic subsequence Cp1 or Cp2.
Only p2 > p1 is a possible maximum cycle-term.
To determine all the valid nontrivial (with cycle-length > 1) cyclic
sequences of the streamlined 3x+/-1 sequences, it is sufficient to
verify the possibility as a maximum cycle-term of just the first 2
terms p1 and p2 of merely a few 4p+/-1-recursive sequences <p1, p2,
p3, ...> — that is, taking p0 = p1 when p1 = 4a+1 and p0 = a when
p1 = 4a-1 for the 3x-1 sequences or p0 = p1 when p1 = 4a-1 and
p0 = a when p1 = 4a+1 for the 3x+1 sequences, then only those with
p0 in {1, 2, 3, ..., z} for some small positive integer z are
significant.
- For the streamlined 3x-1 sequences, any possible maximum
cycle-term is not divisible by 3 and has the form 4p-1.
It suffices to simply consider the possible p1 = 4p-1 with
p = 2r and their respective 4p-1-recursive sequence <p1, p2,
p3, ...> where p2, p3, p4, ... all have the form 4p-1.
Thus, p1 = 24a+7 (for r = 3a+2) with p2 = 4(24a+7)-1 = 96a+27
or p1 = 24a+23 (for r = 3a+3) with p2 = 4(24a+23)-1 = 96a+91.
Case 1: m = p1 = 24a+7
The streamlined-3x-1-sequence-successor-term m’ to m = 24a+7 is
m’ = (3m-1)/2i = [3(24a+7)-1]/2i = (72a+20)/2i = (18a+5)/2i-2
for i >= 2.
Since m’ = 18a+5 is already odd for i = 2, then the streamlined-3x-1-
sequence-successor-term m’’ to m’ = 18a+5 is
m’’ = [3(18a+5)-1]/2j = (54a+14)/2j = (27a+7)/2j-1 for j >= 1.
If a = 0, then we obtain the streamlined 3x-1 cyclic sequence
C7 = C5 = <(7, 5)> with cycle-length = 2.
If a = 2b > 0, then m = 24a+7 = 24(2b)+7 = 48b+7,
m’’ = [27(2b)+7)/2j-1 = (54b+7)/2j-1 for j >= 1.
Since m’’ = 54b+7 is already odd for any integer b for j = 1
and m = 48b+7 < 54b+7 = m’’, then m = 48b+7, for any integer b > 0,
cannot be a valid maximum cycle-term.
Thus, a ¹ 2b for any integer b > 0.
If a = 4b+3, then m = 24(4b+3)+7 = 96b+79,
m’ = 18(4b+3)+5 = 72b+59 = 4(18b+15)-1.
Since p1 = 18b+15 is odd and divisible by 3 for any integer b, then p2 = 4p1-1 = 4(18b+15)-1 = 72b+59 = m’ cannot be a cycle-term because C72b+59 converges to the same proper streamlined 3x-1 cyclic subsequence of C18b+15. Hence, m cannot also be a (maximum) cycle-term.
Thus, a ¹ 4b+3 for any integer b >= 0.
If a = 4b+1, then m = 24(4b+1)+7 = 96b+31, m’ = 18(4b+1)+5 = 72b+23. The 4p-1-recursive-equence-successor-term p2 to p1 = 72b+23 = m’ is p2 = 4p1-1 = 4(72b+23)-1 = 288b+91 = 96(3b)+91 which has the form 96c+91 so C96b+31 = <96b+31, C72b+23> converges to the same cyclic subsequence to which some streamlined 3x-1 sequence C96c+91 converges (these are analyzed in case 4).
Case 2: m = p2 = 96a+27
Since m = p2 = 96a+27 = 4(24a+7)-1 = 4p1-1 is divisible by 3 for any integer a, then m = p2 = 96a+27 is not really a valid cycle-term - indeed, Cp2 = C96a+27 as well as Cp3, Cp4, Cp5, ... all converge to the same valid proper streamlined 3x-1 cyclic subsequence C7 (from case 1) or C91 (from case 4) of Cp1 = C24a+7.
Case 3: m = p1 = 24a+23
The first term q1 of the 4p-1-recursive sequence <q1, q2, q3, ...> of streamlined-3x-1-sequence-predecessor-terms to p1 = 24a+23 is q1 = [2k(24a+23)+1]/3 = 32a+31 for k = 2 — because, for k =1, q1 = [2(24a+23)+1]/3 = (48a+47)/3 is not an integer for any integer a since the numerator 48a+47 is never divisible by 3.
Since, for any integer a >0, q1 = 32a+31 > 24a+23 = p1 then p1 = 24a+23 cannot be a valid maximum cycle-term.
Case 4: m = p2 = 96a+91
If a = 0, then we obtain the streamlined 3x-1 cyclic sequence
C91 = C17 = C25 = C37 = C55 = C41 = C61 = <(91, 17, 25, 37, 55, 41, 61)>
with cycle-length = 7.
If a = 4b > 0, then
m = 96(4b)+91 = 384b+91 = 4(96b+23)-1 = 4[4(24b+6)-1]-1.
If we replace b by b+1 then
384(b+1)+91 = 384b+475 = 4(96b+119)-1 = 4[4(24b+30)-1]-1.
If a = 4b+1, then
m = 96(4b+1)+91 = 384b+187 = 4(96b+47)-1 = 4[4(24b+12)-1]-1.
If we replace b by b+1 then
384(b+1)+187 = 384b+571 = 4(96b+143)-1 = 4[4(24b+36)-1]-1.
If a = 4b+2, then
m = 96(4b+2)+91 = 384b+283 = 4(96b+71)-1 = 4[4(24b+18)-1]-1.
If we replace b by b+1 then
384(b+1)+283 = 384b+667 = 4(96b+167)-1 = 4[4(24b+42)-1]-1.
If a = 4b+3, then
m = 96(4b+3)+91 = 384b+379 = 4(96b+95)-1 = 4[4(24b+24)-1]-1.
If we replace b by b+1 then
384(b+1)+379 = 384b+763 = 4(96b+191)-1 = 4[4(24b+48)-1]-1.
Thus, we could invoke the principle of mathematical induction on b for a sound generalization argument that the sole valid streamlined 3x-1 cyclic sequence in this case is C91 = C17 = C25 = C37 = C55 = C41 = C61 = <(91, 17, 25, 37, 55, 41, 61)>.
Alternatively, we could invoke the principle of complete induction on
p0 in {1, 2, 3, ..., 24} to establish that the sole valid streamlined
3x-1 cyclic sequence in this case is C91.
- Basis: For p0 in {1, 2, 3, ..., 24}, or
n = p0|4p0+1|4p0+2|4p0+3 jn {1, 2, 3, ..., 96}, every
streamlined 3x-1 sequence Cn converges to one of the cyclic
subsequences C1, C5, or C17 (here, a fully cyclic sequence
converges to itself or has itself as a subsequence).
- Induction step: It is easily established that if for each
p0 = 24a+23, with a > 0, Cn converges to C1 or C5, or C17
then so does Cm for m = 4p0|4p0+1|4p0+2|4p0+3 with
p0 = 24(a+1)+23 = 24a+47 = 4(6a+12)-1.
Therefore, there are only 3 (unique uo to cyclic permutations) valid streamlined 3x-1 sequences — C1 = <(1)>, C5 = <(5, 7)>, and C17 = <(17, 25, 37, 55, 41, 61, 91)>.
- For the streamlined 3x+1 sequences, any possible maximum
cycle-term is not divisible by 3 and has the form 4p+1.
It suffices to simply consider the possible p1 = 4p+1 with
p = 2r and their respective 4p+1-recursive sequence <p1, p2,
p3, ...> where p2, p3, p4, ... all have the form 4p+1.
Thus, p1 = 24a+1 (for r = 3a) with p2 = 4(24a+1)+1 = 96a+5
or p1 = 24a+17 (for r = 3a+2) with p2 = 4(24a+17)+1 = 96a+69.
Case 1: m = p1 = 24a+1
If a = 0, then we obtain the trivial cycle-length = 1 streamlined 3x+1 cyclic sequence C1 = <(1)>. The first term q1 of the 4p-1-recursive sequence <q1, q2, q3, ...> of streamlined-3x+1-sequence- predecessor-terms to p1 = 24a+1 is q1 = [2k(24a+1)-1]/3 = 32a+1 for k = 2 — because, for k =1, q1 = [2(24a+1)-1]/3 = (48a+1)/3 is not an integer for any integer a because the numerator 48a+1 is never divisible by 3. Since, for any integer a > 0, q1 = 32a+1 > 24a+1 = p1 then p1 = 24a+1 cannot be a valid maximum cycle-term.
Case 2: m = p2 = 96a+5
If a = 0, then C5 = <5, (1)> — that is, C5 converges to C1.
If a = 4b > 0 then
m = 96(4b)+5 = 384b+5 = 4(96b+1)+1 = 4[4(24b)+1]+1.
If we replace b by b+1 then
384(b+1)+5 = 384b+389 = 4(96b+97)+1 = 4[4(24b+24)+1]+1.
If a = 4b+1, then
m = 96(4b+1)+5 = 384b+101 = 4(96b+25)+1 = 4[4(24b+6)+1]+1.
If we replace b by b+1 then
384(b+1)+101 = 384b+485 = 4(96b+121)+1 = 4[4(24b+30)+1]+1.
If a = 4b+2, then
m = 96(4b+2)+5 = 384b+197 = 4(96b+49)+1 = 4[4(24b+12)+1]+1.
If we replace b by b+1 then
384(b+1)+197 = 384b+581 = 4(96b+145)+1 = 4[4(24b+36)+1]+1.
If a = 4b+3, then
m = 96(4b+3)+5 = 384b+293 = 4(96b+73)+1 = 4[4(24b+18)+1]+1.
If we replace b by b+1 then
384(b+1)+293 = 384b+677 = 4(96b+169)+1 = 4[4(24b+42)+1]+1.
Thus, we could invoke the principle of mathematical induction on b for a sound generalization argument that every valid streamlined 3x+1 cyclic sequence Cn in this case converges to C1 = <(1)>. Therfore, m = 96a+5 (for any nonnegative integer a) is not a valid streamlined 3x+1 maximum cycle-term — indeed, every C96a+5 for any integer a converges to C1.
Case 3: m = p1 = 24a+17
The first term q1 of the 4p-1-recursive sequence <q1, q2, q3, ...> of streamlined-3x+1-sequence-predecessor-terms to p1 = 24a+17 is q1 = [2k(24a+17)+1]/3 = 32a+23 for k = 2 — because, for k =1, q1 = [2(24a+17)+1]/3 = (48a+35)/3 is not an integer for any integer a because the numerator 48a+35 is never divisible by 3.
Since q1 = 32a+23 > 24a+17 = p1 for any integer a, then p1 = 24a+17 cannot be a valid maximum cycle-term.
Case 4: m = p2 = 96a+69
Since m = p2 = 96a+69 = 4(24a+17)+1 = 4p1+1 is divisible by 3 for any integer a, then m = 96a+69 is not really a valid cycle-term — indeed, Cp2 = C96a+69 as well as Cp3, Cp4, Cp5, ... all converge to the same valid proper streamlined 3x+1 cyclic subsequence C1 (from case 3) of Cp1 = C24a+17.
Therefore, there is only 1 valid streamlined 3x+1 sequence — C1 = <(1)>.
[BenCawaling@Yahoo.com] - 121.97.221.189 (talk) 08:56, 29 January 2009 (UTC)
- snipped Ben's crap and reformatted it using only pure ASCII trying to make it readable (hope you don't mind) --Mensanator (talk) 08:03, 30 January 2009 (UTC)
Couldn't you have posted this on a web page and just made a link to it? Sadly, it's easier to read in the editor, a sure sign that someone doesn't understand Wikipedia's formatting. And what do all the little square boxes mean? Want me to host it on my web site? If so, e-amil me a .pdf and make sure all the characters show up. --Mensanator (talk) 23:44, 29 January 2009 (UTC)
Searching Collatz
When I type in Collatz, Wikipedia leads me to the conjecture rather than the person. Shouldn't there be a disambiguation page that links to both pages? Sr13 01:58, 28 September 2006 (UTC)
- Like this: Collatz? -GTBacchus(talk) 02:10, 28 September 2006 (UTC)
Thanks. Sr13 03:05, 28 September 2006 (UTC)
Another claim to a proof.
http://scitec.uwichill.edu.bb/cmp/journal/cadogan.pdf
In a mathematical journal this time, albeit an obscure one. AFAICT it's not verified independentl yet. Could someone take a look?
- I haven't had time to look at in detail but my initial impression is mixed. The techniques used seem to be very elementary. However, the paper has no obvious gaps or crankyness. You may get a better response by posting to sci.math on usenet. JoshuaZ 22:04, 4 December 2006 (UTC)
- I'm following it just fine until the bottom of page 7, where I'm stuck on the justification of (2.6). Is anybody else checking this out, for whom that step makes sense? -GTBacchus(talk) 00:04, 5 December 2006 (UTC)
- I'd like to see how his equations deal with -17. Yes, I know the conjecture is false in the negtive domain, but he has to show why his convergence method is a "proof" in the positive domain when it obviously isn't a proof in the negative domain.--Mensanator 13:03, 6 January 2007 (UTC)
- I'm pretty confident that the line on page 7 where I was tripping up is actually a fallacy. He basically uses the following logic: X implies Y, X implies Z, therefore Y implies Z. He's also the editor-in-chief of the journal that published it, so I'm guessing the peer review was minimal at best. I'm pretty sure the Collatz conjecture is still open. -GTBacchus(talk) 07:27, 8 January 2007 (UTC)
I just happen to read this post today --- the flaw in this "proof" is easily noticed …
- It is true that j ~ 3j+1 for all odd j --- however, they first coalesce at 3j+1 > j and not at some 1 < k < j < 3j+1 (that is, the sequence with starting number 3j+1 is a subsequence of the sequence with starting number j).
- Likewise, 4j+1 ~ 3j+1 for all j and they first coalesce at 3j+1 < 4j+1 --- that is, the sequence with starting number 3j+1 is also a subsequence of the sequence with starting number 4j+1.
- Therefore, j ~ 4j+1 but the sequence with starting number j is not a subsequence of the sequence with starting number 4j+1, or vice versa, and they first coalesce at 3j+1 with j < 3j+1 < 4j+1.
- In the assailed paper, Corollary 3.2 is true and, as stated, Lemmas 3.4 and 3.5 as well as Theorem 3.6 are true --- that is, the results are true but their alleged "proofs" (specifically, on "repeated application" on 4j+1 with supposedly descending coalescence points) are defective [we simply note that x ~ 1 and y ~ 1 by just generating their sequences so, by definition of "~", x ~ y for all positive integers x and y hence all "assertions" in the paper about "~" are "tautologous" --- to avoid this, all arguments in the paper should justify the existence of some _first_ coalescence number > 1 and then succeeding ones that converges to 1].
- Lemma 3.4 is faulty in its attempt to prove the convergence of 4j+1 to 1 --- specifically, in this claim: "1 + 3j ~ tk,l for some k >= 1 and l < j". Again, this claim is tautologously true because 1+3j ~ t0,1 = 1. But the mistake in the paper's reasoning is in the fact that when j is even and 1+3j is odd, what is asserted is that 1+3j ~ 1+3j and so tk,l = 1+3j > j. BenCawaling 03:27, 20 January 2007 (UTC)
Kawasaki Hiroyuki: Claimed proof
Kawasaki Hiroyuki's claim of proof
There is a link to the proof proposed by Kawasaki Hiroyuki. I didn't found on internet any information about the opinion of mathematiciens. Does anyone know a bit more about it ?
- I haven't seen it before. And I'm not a mathematician.
Personnaly, I started reading his proof and is blocked on the following sequence :
is effectively a partition of odd integers. I understand that 4k+3 leads to a 6k+5 form and 8k+1 to 6k+1, but I don't understand how he finds the others :
for example,
- You've got 9k+8 = 9k+4. I didn't see this exact derivation, did you copy it it or derive it?
- Sorry, I made a little mistake at the end. I've corrected it. It doesn't change the fact that could be even if , and if so, it becomes . In that case, if k' is odd, it can been written as which can be written like 6k+1. (I hope I haven't inversed odd and even in my explanations because I'm french and I never know when 2k+1 is called "even" or "odd". Dave Couptily (talk) 07:56, 4 May 2008 (UTC)
- I don't think k could be even, otherwise 3(3k+1)+5 would be even ("even" meaning divisible by 2 or congruent to 0 (mod 2)). Obviously, 3(24k+21)+1 doesn't reduce to 6k+5, it reduces to 9k+8. But 9k+8 is congruent to 5 (mod 6) when k is odd and 5 (mod 6) is another way of saying 6k+5 although I think Hiroyuki isn't being consistent in his use of "k". What I think he's saying is that a number that's 21 (mod 24) becomes 5 (mod 6). But I'm not sure as he has R3,1(x) = {6k+1 if x=24k+5, 6k+3 if x=24k+13, 6k+5 if x=24k+21}. Now it's true that 24k+21 -> 9k+8 which is congruent to 5 (mod 6). But 24k+13 -> 9k+5 which is also congruent to 5 (mod 6), not 3 (mod 6). Likewise, 24k+5 -> 9k+2 which is also congruent to 5 (mod 6), not 1 (mod 6). Either I'm making a mistake or Hiroyuki doesn't know what he's talking about. Notice in section 2-3.4 he has 2k+1 -> 6k+4, should be 6k+3. So my guess is that Hiroyuki doesn't know what he's talking about. --Mensanator (talk) 18:55, 4 May 2008 (UTC)
- Oops, looks like I'm the one who doesn't know what he's talking about. Forgot to add the 1, so it is 6k+4. You see, I was expecting it to be 6k+3 because 6k+4 is an even number, isn't it? Where then, does the 6k+3 com from? --76.214.209.165 (talk) 00:07, 5 May 2008 (UTC)
But if k is even,
- The 3n+1 operation is only performed on odd numbers, so there wouldn't be a 3k+1 evaluation if k were even and standalone. But in the above, k is never alone, it's always paired with an odd constant and has an even multiplier, so in those equations, k could be even.
3k+1 won't be even, so it won't be 6k'+1
Could someone explain me where I make the mistake ? Dave Couptily (talk) 14:37, 3 May 2008 (UTC)
- Better to ask where Hiroyuki's mistake is, but his work is very hard to follow, especially since he deleted half of it because he doesn't have a proper web host. --Mensanator (talk) 04:01, 4 May 2008 (UTC)
Note to Jibbist:
If you actually ever do find a relevant link, it goes under References and External Links not See Also.
And tell Andy that a do..while loop isn't a recursive algorithm. --Mensanator 00:49, 9 March 2007 (UTC)
It's a stupid problem
I don't understand why anyone would even think they could prove this conjecture. To do this, they'd have to test every number out to see that it hits 1 eventually, but there's infinity numbers. They can check as many numbers as they want, but they'll never reach infinity. —The preceding unsigned comment was added by Logicker (talk • contribs) 22:52, 14 March 2007 (UTC).
- The same might be said of proving something like "adding any number to itself gives you twice that number". Luckily, formal logic and the mathematical proof do indeed provide us with ways to determine and show the truth of such infinite classes of statements. Hv 23:19, 14 March 2007 (UTC)
- Formal logic and mathematical proof may help you when you have tautologies like "adding any number to itself gives you twice that number" but doesn't help if you have to test every single number out and there's infinity of them.Logicker 01:47, 15 March 2007 (UTC)
- Why do you think you have to test every number? That every 2**n-1 is divisible by 3 when n is even isn't a tautology and that can be proved without doing an infinity of tests. --Mensanator 04:30, 15 March 2007 (UTC)
- When n is even, n=2k for some k, so 2^n-1 = 2^(2k)-1 = 4^k-1 = 1^k-1 = 0(mod 3). It's a tautology (true for any k), so you don't have to test every number. But with the Collatz sequence, you can't do this, which is why you have to test every number out. It's a stupid problem which only cranks work on.Logicker 16:01, 15 March 2007 (UTC)
- You keep saying "you can't do this" but you've never explained why. That makes the statement a non sequitur, doesn't it? It's not stupid because I learned a lot while studying it. And it's not only cranks that work on it, it's only cranks that think they've proved it...or think it's unprovable.--Mensanator 20:59, 15 March 2007 (UTC)
- Try starting the Collatz sequence with the variable x, which can represent any number. Then the next iteration is x/2 if x=0 (mod 2). And it's (3x+1)/2 if x=1 (mod 2). And the next iteration is either x/4, (3x+1)/4, (3(3x+1)/2+1)/2, or (3x/2+1)/2.
- Why do you think that iteration is the only method available for proving the conjecture?
- You can go on forever with this pattern,
- And it can be proved that every possible pattern appears infinitely many times on the Collatz Tree (the union of all sequences). I do not have to actually trot out each pattern to prove it exists, no iteration necessary. Now explain how you know that there isn't a non-iterative proof.
- but you'll never know if it goes to 1 unless you know the value of x. But there are infinity possible x's.
- Which is only a problem for iterative proofs. Until you can prove that there can only be an iterative proof, the infinity of possible x's means nothing.
- Now that's what I call "proof by hocus-pocus". Logicker 02:03, 16 March 2007 (UTC)
- In other words, you can't prove that there can only be iterative proofs. And yet you cling to the notion that an infinite number of steps must be done. --Mensanator 19:37, 16 March 2007 (UTC)
- I don't need to prove that there can only be iterative proofs, just as I don't need to prove that the only way to drink a glass of water is to drink it. You see, the Collatz problem is a problem about the iterations of the Collatz function, so of course you have to iterate the Collatz function in order to get the answer! Unless you believe in "proof by hocus-pocus" as you apparently do.Logicker 22:58, 20 March 2007 (UTC)
- Yes, you do have to prove there can only be iterative proofs, if you're claiming the only way to prove Collatz is to iterate through every natural number. You have to show that an iterative proof is the only kind possible and then your objection has merit. Until you prove that, it can be ignored (everybody already knows that you can't iterate through an infinity of numbers. Duh.) And hasn't anyone ever explained to you how to drink a glass of water without drinking it? There is more to the Collatz problem than simply iterating the function. And no, I don't have to iterate. Did you know that (1180591620717411303424*A-195820718533800070543)/36472996377170786403 equals 27 when A=1? Funny, isn't it, how I got from 27 to 1 without iterating through all the intermediate values? Do you think I got those numbers by "hocus-pocus"? Try and guess what the next solution is, you can even iterate if you like. Did you get get A=36472996377170786404 which takes you to 1180591620717411303451? Spooky, eh? --Mensanator 05:06, 21 March 2007 (UTC)
- "(1180591620717411303424*A-195820718533800070543)/36472996377170786403 equals 27" when A=1 is irrelevant to our discussion about the Collatz Conjecture. I give up trying to convince you, since you obviously don't understand it.Logicker 16:23, 21 March 2007 (UTC)
- There is your problem. You only think it's irrelevant, the wise person would have asked what the relevance was. If you start at 27 and follow a Collatz sequence counting the n/2 steps along the way and starting a new count each time you do a (3n+1) step, you get the following list when you reach 1: [1, 2, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 2, 2, 4, 3, 1, 1, 5, 4]. Now, if you take that list and algebraically work backwards from 1 to 27, you get (2**70 - (3**0 * 2**66 + 3**1 * 2**61 + 3**2 * 2**60 + 3**3 * 2**59 + 3**4 * 2**56 + 3**5 * 2**52 + 3**6 * 2**50 + 3**7 * 2**48 + 3**8 * 2**44 + 3**9 * 2**43 + 3**10 * 2**42 + 3**11 * 2**41 + 3**12 * 2**38 + 3**13 * 2**37 + 3**14 * 2**36 + 3**15 * 2**35 + 3**16 * 2**34 + 3**17 * 2**33 + 3**18 * 2**31 + 3**19 * 2**30 + 3**20 * 2**28 + 3**21 * 2**27 + 3**22 * 2**26 + 3**23 * 2**23 + 3**24 * 2**21 + 3**25 * 2**20 + 3**26 * 2**19 + 3**27 * 2**18 + 3**28 * 2**16 + 3**29 * 2**15 + 3**30 * 2**14 + 3**31 * 2**12 + 3**32 * 2**11 + 3**33 * 2**9 + 3**34 * 2**7 + 3**35 * 2**6 + 3**36 * 2**5 + 3**37 * 2**4 + 3**38 * 2**3 + 3**39 * 2**1 + 3**40 * 2**0))/3**41 and that reduces to (1180591620717411303424-195820718533800070543)/36472996377170786403 so that fraction decribes the Collatz path from 27 to 1 without iterating through the intermediate numbers. True, I had to iterate to get the original pathway [1, 2, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 2, 2, 4, 3, 1, 1, 5, 4] but pathways can be created without iterating. And I only need to iterate once, all the rest of the infinite solutions can be derived from the fraction alone without any need for iteration. Any pathway that has 1 as a solution is a complete Collatz sequence. The second example I gave is the Collatz sequence from 1180591620717411303451 to 36472996377170786404 and although not a complete Collatz sequence, has the identical pathway that 27 has to 1. It's just as well you're giving up, your ideas aren't welcome here. --Mensanator 19:36, 21 March 2007 (UTC)
- So that's why the problem is a complete waste of time and energy for any serious mathematician.Logicker 22:50, 15 March 2007 (UTC)
- So who's a serious mathematician? --Mensanator 00:35, 16 March 2007 (UTC)
Logicker, are you familiar with the idea of a proof by contradiction? Like, maybe someone could show that, if some starting number didn't eventually reach 1, then that would imply something that's clearly false, therefore there must be no such number? Lots of statements in "serious mathematics" have no proofs excepts proofs by contradiction; does that make all of those statements "stupid" as well? -GTBacchus(talk) 00:51, 16 March 2007 (UTC)
- When I was in high school, my math teacher explained the fifteen puzzle (with tiles 14 and 15 exchanged) to the class and why it couldn't be solved. Everyone was satisfied with the explanation except for one kid named Bradley. Bradley insisted that the teacher's explanation wasn't good enough because he thought he could get around the fact that the solution and the original configuration have different parities. Bradley, is that you? Logicker 02:03, 16 March 2007 (UTC)
- There is a difference between "provably false" and "unproved". No one studying Collatz is trying to refute anything that's been proved. Sure, there are some cranks around who wrongly believe they have a proof. But so what? There are still cranks prattling on about FLT and that was settled years ago. The fact that Collatz hasn't been settled yet makes it a legitimate subject for research even if serious mathematicians don't care about it. --Mensanator 19:37, 16 March 2007 (UTC)
- No, I'm not Bradley, and I understand why the fifteen puzzle is unsolvable from certain configurations, with differet parity, as you say. In fact, I used that puzzle as an example when I was teaching group theory, when we were talking about even and odd permutations. What on Earth has that got to do with the Collatz conjecture? Also, did you even read my question about indirect proof? What's your justification for ruling those out; are you a constructivist or something? -GTBacchus(talk) 22:07, 17 March 2007 (UTC)
- There is no reason why a Collatz sequence can't go to infinity or end up in a nontrivial cycle, so there can't be any proof by contradiction. The only reason why no such example has ever been found is because the odds of such happenning are so low. See http://hdebruijn.soo.dto.tudelft.nl/www/programs/collatz.htm. Also, this paper formally proves that it's unprovable, http://arxiv.org/abs/math/0312309. I don't think the author of that paper had to go through so much detail to get his point across, as it's so obvious that you have to test out every number to prove the conjecture. I knew it right away when I first heard of the conjecture.Logicker 04:41, 18 March 2007 (UTC)
- Well, congratulations on being so much smarter than so many mathematicians. I see from that first link that you reject basic set theory, so I guess we haven't got much to talk about. Have a nice day. -GTBacchus(talk) 20:37, 18 March 2007 (UTC)
- There is no reason why a Collatz sequence can't go to infinity or end up in a nontrivial cycle, so there can't be any proof by contradiction. The only reason why no such example has ever been found is because the odds of such happenning are so low. See http://hdebruijn.soo.dto.tudelft.nl/www/programs/collatz.htm. Also, this paper formally proves that it's unprovable, http://arxiv.org/abs/math/0312309. I don't think the author of that paper had to go through so much detail to get his point across, as it's so obvious that you have to test out every number to prove the conjecture. I knew it right away when I first heard of the conjecture.Logicker 04:41, 18 March 2007 (UTC)
- I'm Bradley. Here's another "crank" paper you might want to read: http://www.geocities.com/bencawaling/collatz_conjecture_proved.pdf --- then you decide! BenCawaling 06:10, 19 March 2007 (UTC)
- Let's see, De Bruijn thinks he's proved it and Fenstein thinks it's unprovable. What a dumbass. --Mensanator 04:53, 20 March 2007 (UTC)
It amazes me how many places I've seen Fenstein's "proof" mentioned on the internet. It's rather obvious that if his method were vallid, then the n+1 version of the conjecture would also be unprovable. Which, by the way, is a good example of a problem similair to the Collatz that can easily be solved without itteration. Lastly, anyone with the internet can find that there are serious mathematicians interested in the Collatz Conjecture...sorry I'm aware this adds little to the conversation, I just can't help commenting when these kinds of discussions come up.Phoenix1177 (talk) 04:55, 31 December 2007 (UTC)
Iterating on rational numbers with odd denominators
I was a bit confused by this section...hopefully this is the appropriate place to voice that confusion. The first sentence states that the standard Collatz map can be extended...I assume this means the 3x+1 and/or the (3x+1)/2 variants in the first section. With this assumption, the 151/47 cycle doesn't work for me. I get 151/47 -> 227/47 -> 341/47 ... 1/47. I'm assuming this is something I'm missing, but figured I'd ask. --Garfieldsk 16:13, 20 June 2007 (UTC)
"The parity sequences as defined above..." means (3x+1)/2 is being used. Using Python with the rational number component of the gmpy module
import gmpy
def iterating_on_rational(n):
if n.numer() % 2 == 1: # it's "odd" if numerator is odd
n = (n*3 + 1)/2 # all math will be done with rationals
else: # and reduced to lowest terms
n = n/2
print n
return n
n = gmpy.mpq(151,47) # start by creating initial rational number
print n
for i in xrange(14):
n = iterating_on_rational(n)
which produces:
151/47 250/47 125/47 211/47 340/47 170/47 85/47 151/47 250/47 125/47 211/47 340/47 170/47 85/47 151/47
Must be human error. --Mensanator 01:25, 21 June 2007 (UTC)
On further pondering, I see what you did wrong. You multiplied 151 by 3 yielding 453 which, when 1 is added becomes 454 that then becomes 227 when divided by 2. But ... that's one of the cardinal sins of fractions: performing an addition without first establishing a common denominator. My program works because the math library recognizes n as a rational and coerces the " + 1" to " + 47/47" automagically. Thus, instead of 453+1, my program correctly does 453+47 which is 500 becoming the correct numerator 250. That's one of the nice things about a high-level language like Python, I can continue to think in terms of the algorithm (3n+1)/2 without fretting over the petty details like common denominators or reducing to lowest terms. --Mensanator 04:50, 21 June 2007 (UTC)
Ha, I can't believe how many times I stared at that and didn't see the obvious, thanks. That Python script may be the deciding factor in giving Python a chance after all. Neat problem in general. --Garfieldsk 14:43, 27 June 2007 (UTC)
This section says "The parity sequences as defined above are no longer unique for fractions." Now, I don't have any reference for this, but it seems to me that if p/q and r/s are fractions in lowest terms, then their parity sequences will agree in the first k terms iff ps and qr are equivalent modulo 2k, which would still imply that they're unique.
Am I wrong? —Preceding unsigned comment added by 63.170.40.2 (talk) 13:49, 9 October 2007 (UTC)
Main article, "Other ways of approaching the problem" / "In reverse"
In this section of the main article, it is stated that the graph from 1 upwards is a tree. Is there a proof of this? Because, if it is a tree, then the graph is connected and has no cycles, which would solve half the problem in the first place. Maybe the graph has been christened as a tree a bit hastily, IMHO. -Thanks. Pasmao 17:29, 22 July 2007 (UTC)
Well, if the use of "tree" implies the conjecture is true, then there's no proof of that, of course. If it was true, then it would depend on how you define the sequence, whether you stop at 1
16 8 4 2 1
or continue indefinitely
16 8 4 2 1 4 2 1 4 2 1 4 2 1 ...
To me, that distinction is unimportant. What matters is whether there is more than one graph, not whether the graph is actually a tree. And since defining the graph to have a loop cycle makes more sense, I suppose "tree" should be changed to "graph".--Mensanator 23:22, 22 July 2007 (UTC)
Thank you for your reply. Let me try to be more specific.
I assume that by "whether there is more than one graph", you mean simply stopping or not stopping at 1 to avoid the loop 1-4-2-1;
- Actually, I don't mean that at all. "More than one graph" means there are multiple disjoint graphs (there being no path from one graph to another). For example, there are 3 disjoint graphs in the negative domain at -1, -5 and -17. Also, for 3n+C (where C is an odd number not a power of 3), there are always at least 2 disjoint graphs (sometimes many) in the positive domain.
as for the rest of the graph, the operations are deterministic and, I would say, the [rest of the] graph is one. Let's for a moment forget the 1-4-2-1 loop; assume we will always stop at 1, at least for this discussion.
- Bad idea, you should always include the loop cycle. True, it's easy to snip it for 3n+1 in the positive domain, but not so easy elsewhere. If you snip off the loop cycle of +(3n+1), there remains only one "trunk". But the -5 & -17 graphs in -(3n+1) have more than one "trunk", so removing the loop cycle makes the pieces of the remaining graph disjoint. Same for the positive non-trivial graphs in 3n+C.
I'd grant you that the graph from 1 upwards is connected, by construction. What we don't know is a) if all numbers will appear on it, of course, and b) if a number will appear twice, causing another cycle (which might include 1 back, or not). My question is, then: is there any proof against b) ? --Pasmao 06:31, 23 July 2007 (UTC)
- I think a second cycle implies a disjoint graph, although I am not sure. Although that's all I've ever seen. If that is in fact the case, then not only is there no proof against b), there cannot be any proof since the premise is false. The counterexample is -17, a graph with a non-trivial loop cycle (+1, -1, -5 all being trivial). Now it could be the case that there is no counterexample in the positive domain making Collatz true. The formation of loop cycles is strictly an issue of factoring and that's independent of domain, so there's no reason a counterexample couldn't exist in the positive domain. If you could prove that the factor cancelling can't happen, that would cover both domains, negative and positive. The known counterexample at -17 means, of course, there cannot be any such proof.--Mensanator 22:09, 23 July 2007 (UTC)
Thanks for your clarifications. My concern came out of the fact that, in graph theory, a tree is a graph which is both connected and acyclic.
- Personally, I didn't know that (obvious if you read the very beginning of this discussion page). And, since the actual quote from the article is "Also, the inverse relation forms a tree except for the 1-2-4 loop" I suppose one could argue that it's technically correct since the author is excluding the loop cycle. But I would consider that to be misleading, if not incorrect.
Saying that it is a tree assumes both consequences a priori. (Though it can be argued that this section belongs to the original positive problem, not to the extension to Z which is talked about later in the article.)--Pasmao 07:34, 24 July 2007 (UTC)
- Right. If it's not a tree, one shouldn't pretend it is by excluding the loop cycle. The fact that it becomes serious only in the extenions is no excuse for being inconsistent.--Mensanator 17:20, 24 July 2007 (UTC)
- So, do you guys want to use Image:Collatz-graph-all-30-no27-loop.svg instead? —Keenan Pepper 18:26, 27 July 2007 (UTC)
- Since you are soliciting an opinion, mine is that I don't like either graph. I prefer something like what's shown at the very beginning of this discussion page, either the "V" style (employing (3n+1)/2) or the "inverted L" style employing 3n+1. My objection is in the attempt to minimize space requirements, objectionable visual distortions were introduced although it remains mathematically correct. I don't like how the orientation of the arrows does't consistently reflect the rule being employed. And although I always prefer 3n+1 over (3n+1)/2, I like how in the "V" style, 5 and 32 are members of the same level making reverse generation of the graph easier. And if the graph is not directed, you can show all kinds of neat things like how all sub-branches are in modulo 3 order, and this requires mixing n/2 & 3n+1 with their inverses n*2 & (n-1)/3, in other words, an undirected graph. Of course, what I like certainly isn't grounds for changing the image. My attempt at making a "tree" is shown here [9] but I wouldn't suggest using it in the Wikipedia article.--Mensanator 02:18, 29 July 2007 (UTC)
Severe cuts
Do you really think that this edit improves the article? I think the section "optimizations" was much more clear before.--Pokipsy76 (talk) 12:03, 29 December 2007 (UTC)
I agree. Even if this new material covers the same optimizations (which remains to be confirmed), there was no justification for deleting the previous material. Something like that ought to be discussed prior to editing. Especially as the exposition is wanting.--Mensanator (talk) 21:50, 30 December 2007 (UTC)
- I would suggest to revert back the old version of the section.--Pokipsy76 (talk) 07:07, 31 December 2007 (UTC)
Possible proof against a repeating cycle that does not include 1
I found this proof but I'm not sure if it is valid, and need confirmation. This is how it goes:
Consider only the odd positive numbers put into the function after initially putting in a1: (this is a valid assumption as all even positive numbers lead to an odd positive number) a1, a2, a3, ... , at, ... , ap, ..., where at = ap & p>t.
Then ap-(p-2) = at-(p-2). p cannot be >= t+2 because then at-(p-2) = at-(t+2)+2 = a0. But a0 does not exist. Therefore, p = t+1.
- Are you saying that a loop cycle can only contain a single odd number? Your reasoning must be flawed. I think someone has proved that a non-trivial 1-cycle cannot exist, but not that the only possible cycles are 1-cycles.--Mensanator (talk) 03:48, 13 January 2008 (UTC)
Then a2 = at-(t+1-2) = a1.
But:
a2 = (3a1+1)/2n, for some positive integer n
Then 2na2 = 3a1+1
2na1 = 3a1+1, as a2 = a1
a1 must be an odd positive integer. But if n is >= 3 then a1 = a fraction between 0 and 1. Therefore n cannot be >= 3. If n = 1, then a1 = -1. Therefore n cannot = 1. Thus n = 2.
4a1 = 3a1+1
a1 = 1
Therefore a2, a3, ..., are = 1.
Therefore 1 is the only number that can repeat in a sequence.
--Antu A (talk) 00:41, 13 January 2008 (UTC)
- Yeah, the proof is supposed to show that the only cycle that can exist is a 1-cycle.
- Which is trivally false in the negative domain, -17, -25, -37, -55, -41, -61, -91, -17. Now, before you object to the negative domain, read the rest.
- If there is a flaw I think it is that the proof does not show a contradiction, rather it shows the actual values of odd numbers in the sequence. Must a proof show a contradiction?
- No, of course not.
- On the issue of a sequence increasing without bound I think a good place to start would be to consider the sequence of odd numbers put into the function, i.e. a1, a2, ..., ak, and then finding a contradiction for ak being a number other than 1, as k→∞. There is an equation that relates ak and a1 that I have found. This is:
a1 = [(2mk-1+mk-2+...+m1)/(3k-1)] × ak - c, for some positive number c.
The m values are the number of times you divide 3x+1 by 2, for some x in the sequence. e.g. a2 = (3a1+1)/(2m1) and a3 = (3a2+1)/(2m2). This equation can be rearranged to make ak the subject.
- ak = (Y*a1 + Z)/X where, given a list of m-values such as [1,2,3,4], Y = 3**count([1,2,3,4], X = 2**sum([1,2,3,4]) and Z = 3**0*2**(1+2+3)+3**1*2**(1+2)+3**2*2**(1)+3**3*2**(0). That equation is a straight line whose slope cannot equal 1, thus, it ALWAYS intersecs the indentity line. That point of intersection is Z/(X-Y) and is always a rational. IF that rational happens to be an integer, the sequence is a loop. There are TWO ways that can happen 1) X-Y is a unit 2) the factors of Z cancel all those of X-Y. What's significant about -17 is that unlike any other loop, it is NOT case 1) (although it's in the negative domain because the m-values [1,1,1,2,1,1,4] result in X-Y being negative). It is the ONLY known example of case 2) which has nothing to do with the domain as factoring is independent of domain. What's important is that you can NEVER prove case 2) can't happen since an example exists. This is why I think your proof is invalid. You must prove that case 2) can only happen EXACTLY once (or that all examples fall in the negative domain).--Mensanator (talk) 01:40, 14 January 2008 (UTC)
- Does anyone agree this would be a good place to start?--Antu A (talk) 07:19, 13 January 2008 (UTC)
- I understand why it's wrong now. I never knew that there actually exists a starting number that gives a loop,
- If you don't stop when you reach 1, you'll loop 4-2-1-4-2-1-4-2-1...
- in any domain.
- Every 3n+C system (where C is an odd integer) has loops at +C, -C, -5C and -17C. When C is not a power of 3, there are additional loops. Basically, Collatz boils down to "there is only one loop in the positive domain".
- Would it be worthwhile including the sequence of -17 under the heading examples, or something, in the article?
- Absolutely. -17 is important because it's NOT TRIVIAL as the other loops are (their rationals (see below) always have 1 as a denominator, but the loop at -17 does not, the denominator is cancelled by the factors of Z).
- It would show people the complexity of the problem and what a proof would require.
- I agree. Because of -17, I can dismiss any purported proof that does not allow non-trivial loops.
- Mensanator, just to clarify, do you mean above: intersects the identity line?
- Yeah, that was a typo. There can only be one intersection of two non-parallel straight lines. The intersection may be in either domain, however, dependent on whether the sum of the m-values is greater than log(3)/log(2) times the count of the m-values.
- And do you mean that the identity line is the equation with a1 as the subject?
- The identity line is y=x or f(x)=x. In your case, it means a1 = ak for some k>1. Look in the article under "iterating on rational numbers with odd denominators". The "parity sequence" discussed there is equivalent to the m-value sequence. The rules for calculating the terms are slightly different than what I gave above for m-values, but either way you always get a series of rationals with a common odd denominator. This sequence of rationals is ALWAYS a loop cycle (because the line of the function always intersects the identity line, so there is always some starting number that, upon evaluation of the m-values, yields the same number). It's when the rationals are integers that you have a Collatz loop.--Mensanator (talk) 19:52, 22 January 2008 (UTC)
- Thanks for showing me the error in the proof.--Antu A (talk) 07:41, 22 January 2008 (UTC)
External references
- About Peter Schorer's papers on the 3x + 1 Problem —Preceding unsigned comment added by Porton (talk • contribs) 12:16, 14 January 2008 (UTC)
- Geez, can't anyone win the Spot The Fallacy Game? Am I the only one who can see that the emperor is naked?--Mensanator (talk) 17:56, 14 January 2008 (UTC)
What a load! No wonder no one wants to look over this, you need a machete and a guide.
- Hundreds of people visit the site www.occampress.com each month. Apart from Mensanator's comments here I haven't received any feedback that the papers are difficult to navigate through. I do include section headings in the bookmarks feature of the pdf files. I hope this is helpful to readers. The paper, "Are We Near a Solution to the 3x + 1 Problem?" is written in standard form and has few redundancies apart from several explanations of the strategy that I am trying to implement.
- Since I have placed top priority on incorporating feedback from readers and on presenting new results, I haven't had time to remove all of the redundancies in all three of my 3x + 1 papers and create a single, polished, final paper. I make clear on pp. 2-3 of the paper, "The Structure of the 3x + 1 Function: An Introduction" that there is considerable redundancy between that paper and the paper, "The Structure of the 3x + 1 Function".
- Mensanator has raised some useful discussion points below about the substance of my "...Solution...?" paper and I will try to address them. I thank Mensanator for spending so much time on my papers. Peter Schorer (talk) 05:57, 23 January 2008 (UTC)
- No point in arguing, you can lead a horse to knowledge but you can't make him think. I'll just add a couple facts that may interest the reader.--Mensanator (talk) 03:39, 28 January 2008 (UTC)
So, where to start? Well, since there is much fretting about how counterxamples can co-exist with non-counterexamples, suppose we start with: what exactly IS a non-counterexample?
A tuple that ends in an infinite sequence of 1's? <...,x,y,1,1,1...>
Close, but not rigorous. The rigorous definition is an exponent sequence that ends in an infinite sequence of 2's. {...,a,b,2,2,2...}
The first definition is value-centric and applies only to 3n+1. The second is structure-centric and applies to ALL 3n+C (where C is an odd integer). Loop cycles are determined solely by their exponent sequence structure.
- I am attempting to solve the original 3x + 1 Problem in the context of the original 3x + 1 Problem and that is the basis on which my papers should be read. I am not attempting to solve the 3n + C Problem (where C is an integer) and I am not attempting to solve the 3x + 1 Problem in the context of the 3n + C Problem. Peter Schorer (talk) 05:57, 23 January 2008 (UTC)
Thus, {...,a,b,2,2,2...} is ALWAYS The Trivial Positive Loop Cycle for any 3n+C system. Including C=1, of course. The tuples then end <...,x,y,C,C,C,C...> in The Trivial Positive Loop Cycle.
That makes a non-counterexample a tuple that has at its end a loop cycle defined by the exponent sequence {2}. And every tuple that has a loop cycle with an exponent sequence other than {2} is a counterexample.
Thus, ALL NEGATIVE NUMBERS ARE COUNTEREXAMPLES.
Do not be misled thinking the loop cycle at -1 is a non-counterexample. That's value-centric thinking which is wrong as said loop cycle is {1}, not {2}.
Now, if the author understood that, he wouldn't have said (emphasis added):
<quote>If (contrary to fact) counterexamples and only counterexamples were negative numbers...</quote>
- What I understand is that the domain of the original 3x + 1 Problem (the Problem I am attempting to solve) is the positive integers, and that if counterexamples exist, they are positive integers. The reason this is true is that the domain and range of the original 3x + 1 function is the positive integers. (In my papers, I use an equivalent 3x + 1 function whose domain and range is the odd, positive integers.)
- Fine, but there are STRUCTURAL issues that only manifest themselves in the negative domain (or 3n+C). Why? Is it because they CAN'T happen in the positive domain of 3n+1 or, due to The Law of Small Numbers, we haven't seen any such cases? How can you answer why if you don't know what?--Mensanator (talk) 03:39, 28 January 2008 (UTC)
- In addition to this I understand that, in the original 3x + 1 Problem, non-counterexamples are identified by the fact that they yield tuples <...x, y, 1, 1, 1, ... >.
- But looking at Collatz from a STRUCTURAL viewpoint, this is wrong. Structurally, non-counterexamples are defined by exponent sequences, not by tuples (which are irrelevant).--Mensanator (talk) 03:39, 28 January 2008 (UTC)
- This next material of Mensanator's, although very interesting, seems to be a taking-me-to-task for not having written my papers in the context of the 3n + C Problem. It may well turn out that working in that context is the only way to achieve a solution of the 3x + 1 Problem, but for now, my papers are attempting to solve the original 3x + 1 Problem in the context of the original 3x + 1 Problem. Peter Schorer (talk) 05:57, 23 January 2008 (UTC)
Speaking of negative numbers, it is wrong to think of the negative domain as being a different problem. The negative and positve domain are opposite sides of the same coin, not two different coins. For example, whenever C>3, sequences cross from the negative domain into the positive range as in (for 3n+7):
-1, +4, +2, +1, +10, +5, +22, +11, +40, +20, +10, ...
So, to properly study how counterexamples co-exist with non-counterexamples, we need to look at 3n+C in the positive domain (for some C not a power of 3) instead of fretting over the negative domain (which has its own issues).
3n+C is a Through-the-Looking-Glass world where things are the same only different. Depending on whether your mindset is structure-centric or value-centric.
Often mentioned is the series 1, 5, 21, 85, 341, ... and it's relation
succ(n) -> 4*n + 1
But that's value-centric thinking. The actual relation is
succ(n) -> 4*n + C
Now, that doesn't mean everything is wrong. Things properly defined structurally at the outset translate to 3n+C without problems, such as the distance formulae for i-level tuple elements.
We can see that the differences hold up in 3n+7 just as they do in 3n+1. (Due to programming constraints, I show tuple sets rotated 90 degrees from what's shown in Mr. Schorer's paper, i.e., tuples extend horizontally instead of vertically.)
C: 7 1 5 11 3 |--------------- distance 6 5 11 7 9 17 29 11 | 13 23 |---------- distance 18 15 | 17 29 47 37 19 | 21 35 | 23 | 25 41 65 | 27 | 29 47 | 31 | 33 53 83 |----- distance 54 35 | 37 59 | 39 | 41 65 101 | 43 | 45 71 | 47 | 49 77 119 91
The author, however, makes the leap that his distance formula proves Lemma 6.0. But it is readily shown that in 3n+C, counterexamples exist:
format C:7 # C of 3n+C
[1, 1, 1, 7] # exponent sequence
Anchor: 361 [ 545 821 1235 29 ] # anchor tuple
True # test for < 2*3**(i-1)
C:7 [1, 1, 1, 7] Anchor: 361 [ 545 821 1235 29 ] True C:7 [1, 1, 2, 6] Anchor: 689 [ 1037 1559 1171 55 ] True C:7 [1, 1, 3, 5] Anchor: 1345 [ 2021 3035 1139 107 ] True C:7 [1, 1, 4, 4] Anchor: 609 [ 917 1379 259 49 ] True C:7 [1, 1, 5, 3] Anchor: 1185 [ 1781 2675 251 95 ] True C:7 [1, 1, 6, 2] Anchor: 289 [ 437 659 31 25 ] True C:7 [1, 1, 7, 1] Anchor: 545 [ 821 1235 29 47 ] True C:7 [1, 2, 1, 6] Anchor: 157 [ 239 181 275 13 ] True C:7 [1, 2, 2, 5] Anchor: 813 [ 1223 919 691 65 ] True C:7 [1, 2, 3, 4] Anchor: 77 [ 119 91 35 7 ] True C:7 [1, 2, 4, 3] Anchor: 653 [ 983 739 139 53 ] True C:7 [1, 2, 5, 2] Anchor: 1805 [ 2711 2035 191 145 ] True C:7 [1, 2, 6, 1] Anchor: 13 [ 23 19 1 5 ] True C:7 [1, 3, 1, 5] Anchor: 1797 [ 2699 1013 1523 143 ] True C:7 [1, 3, 2, 4] Anchor: 1061 [ 1595 599 451 85 ] True C:7 [1, 3, 3, 3] Anchor: 1637 [ 2459 923 347 131 ] True C:7 [1, 3, 4, 2] Anchor: 741 [ 1115 419 79 61 ] True C:7 [1, 3, 5, 1] Anchor: 997 [ 1499 563 53 83 ] True C:7 [1, 4, 1, 4] Anchor: 981 [ 1475 277 419 79 ] True C:7 [1, 4, 2, 3] Anchor: 1557 [ 2339 439 331 125 ] True C:7 [1, 4, 3, 2] Anchor: 661 [ 995 187 71 55 ] True C:7 [1, 4, 4, 1] Anchor: 917 [ 1379 259 49 77 ] True C:7 [1, 5, 1, 3] Anchor: 1397 [ 2099 197 299 113 ] True C:7 [1, 5, 2, 2] Anchor: 501 [ 755 71 55 43 ] True C:7 [1, 5, 3, 1] Anchor: 757 [ 1139 107 41 65 ] True C:7 [1, 6, 1, 2] Anchor: 181 [ 275 13 23 19 ] True C:7 [1, 6, 2, 1] Anchor: 437 [ 659 31 25 41 ] True C:7 [1, 7, 1, 1] Anchor: 1845 [ 2771 65 101 155 ] True C:7 [2, 1, 1, 6] Anchor: 383 [ 289 437 659 31 ] True C:7 [2, 1, 2, 5] Anchor: 1039 [ 781 1175 883 83 ] True C:7 [2, 1, 3, 4] Anchor: 303 [ 229 347 131 25 ] True C:7 [2, 1, 4, 3] Anchor: 879 [ 661 995 187 71 ] True C:7 [2, 1, 5, 2] Anchor: 2031 [ 1525 2291 215 163 ] False C:7 [2, 1, 6, 1] Anchor: 239 [ 181 275 13 23 ] True
C:35 [1, 1, 1, 5] Anchor: 13 [ 37 73 127 13 ] True C:35 [1, 1, 2, 4] Anchor: 117 [ 193 307 239 47 ] True C:35 [1, 1, 3, 3] Anchor: 325 [ 505 775 295 115 ] True C:35 [1, 1, 4, 2] Anchor: 229 [ 361 559 107 89 ] True C:35 [1, 1, 5, 1] Anchor: 37 [ 73 127 13 37 ] True C:35 [1, 2, 1, 4] Anchor: 17 [ 43 41 79 17 ] True C:35 [1, 2, 2, 3] Anchor: 225 [ 355 275 215 85 ] True C:35 [1, 2, 3, 2] Anchor: 129 [ 211 167 67 59 ] True C:35 [1, 2, 4, 1] Anchor: 449 [ 691 527 101 169 ] False C:35 [1, 3, 1, 3] Anchor: 25 [ 55 25 55 25 ] True C:35 [1, 3, 2, 2] Anchor: 441 [ 679 259 203 161 ] True C:35 [1, 3, 3, 1] Anchor: 249 [ 391 151 61 109 ] True C:35 [1, 4, 1, 2] Anchor: 41 [ 79 17 43 41 ] True C:35 [1, 4, 2, 1] Anchor: 361 [ 559 107 89 151 ] True C:35 [1, 5, 1, 1] Anchor: 73 [ 127 13 37 73 ] True C:35 [2, 1, 1, 4] Anchor: 123 [ 101 169 271 53 ] True C:35 [2, 1, 2, 3] Anchor: 331 [ 257 403 311 121 ] True C:35 [2, 1, 3, 2] Anchor: 235 [ 185 295 115 95 ] True C:35 [2, 1, 4, 1] Anchor: 43 [ 41 79 17 43 ] True C:35 [2, 2, 1, 3] Anchor: 131 [ 107 89 151 61 ] True C:35 [2, 2, 2, 2] Anchor: 35 [ 35 35 35 35 ] True C:35 [2, 2, 3, 1] Anchor: 355 [ 275 215 85 145 ] True C:35 [2, 3, 1, 2] Anchor: 147 [ 119 49 91 77 ] True C:35 [2, 3, 2, 1] Anchor: 467 [ 359 139 113 187 ] False C:35 [2, 4, 1, 1] Anchor: 179 [ 143 29 61 109 ] True C:35 [3, 1, 1, 3] Anchor: 343 [ 133 217 343 133 ] True C:35 [3, 1, 2, 2] Anchor: 247 [ 97 163 131 107 ] True C:35 [3, 1, 3, 1] Anchor: 55 [ 25 55 25 55 ] True C:35 [3, 2, 1, 2] Anchor: 359 [ 139 113 187 149 ] True C:35 [3, 2, 2, 1] Anchor: 167 [ 67 59 53 97 ] True C:35 [3, 3, 1, 1] Anchor: 391 [ 151 61 109 181 ] False C:35 [4, 1, 1, 2] Anchor: 271 [ 53 97 163 131 ] True C:35 [4, 1, 2, 1] Anchor: 79 [ 17 43 41 79 ] True C:35 [4, 2, 1, 1] Anchor: 303 [ 59 53 97 163 ] False C:35 [5, 1, 1, 1] Anchor: 127 [ 13 37 73 127 ] True
Obviously, "the i-level value of the anchor tuple of an i-level tuple set is < 2*3**(i-1)" DOES NOT FOLLOW from the distance formula, even though it may be true in 3n+1. That makes Lemma 6.0 not a lemma at all but a Non Sequitur Fallacy.
And what of this prattle about counterexamples having to "squeeze in" or that non-counterexamples "push them away"? First of all, in a true system of counterexamples mixed with non-counterexamples, most of the tuples are counterexamples (only tuples whose elements are divisible by C are non-counterexamples) meaning it's the non-counterexamples that have to "squeeze in". And does anyone get "pushed away"? Not hardly, as we see here:
C:7 [1, 1, 1, 5] Anchor: 105 [ 161 245 371 35 ] 0 non-counterexample C:7 [1, 1, 2, 4] Anchor: 433 [ 653 983 739 139 ] 6 counterexample C:7 [1, 1, 3, 3] Anchor: 65 [ 101 155 59 23 ] 2 counterexample C:7 [1, 1, 4, 2] Anchor: 353 [ 533 803 151 115 ] 3 counterexample C:7 [1, 1, 5, 1] Anchor: 417 [ 629 947 89 137 ] 4 counterexample C:7 [1, 2, 1, 4] Anchor: 413 [ 623 469 707 133 ] 0 non-counterexample C:7 [1, 2, 2, 3] Anchor: 45 [ 71 55 43 17 ] 3 counterexample C:7 [1, 2, 3, 2] Anchor: 333 [ 503 379 143 109 ] 4 counterexample C:7 [1, 2, 4, 1] Anchor: 397 [ 599 451 85 131 ] 5 counterexample C:7 [1, 3, 1, 3] Anchor: 5 [ 11 5 11 5 ] 5 counterexample C:7 [1, 3, 2, 2] Anchor: 293 [ 443 167 127 97 ] 6 counterexample C:7 [1, 3, 3, 1] Anchor: 357 [ 539 203 77 119 ] 0 non-counterexample C:7 [1, 4, 1, 2] Anchor: 213 [ 323 61 95 73 ] 3 counterexample C:7 [1, 4, 2, 1] Anchor: 277 [ 419 79 61 95 ] 4 counterexample C:7 [1, 5, 1, 1] Anchor: 117 [ 179 17 29 47 ] 5 counterexample C:7 [2, 1, 1, 4] Anchor: 127 [ 97 149 227 43 ] 1 counterexample C:7 [2, 1, 2, 3] Anchor: 271 [ 205 311 235 89 ] 5 counterexample C:7 [2, 1, 3, 2] Anchor: 47 [ 37 59 23 19 ] 5 counterexample C:7 [2, 1, 4, 1] Anchor: 111 [ 85 131 25 41 ] 6 counterexample C:7 [2, 2, 1, 3] Anchor: 231 [ 175 133 203 77 ] 0 non-counterexample C:7 [2, 2, 2, 2] Anchor: 7 [ 7 7 7 7 ] 0 non-counterexample C:7 [2, 2, 3, 1] Anchor: 71 [ 55 43 17 29 ] 1 counterexample C:7 [2, 3, 1, 2] Anchor: 439 [ 331 125 191 145 ] 5 counterexample C:7 [2, 3, 2, 1] Anchor: 503 [ 379 143 109 167 ] 6 counterexample C:7 [2, 4, 1, 1] Anchor: 343 [ 259 49 77 119 ] 0 non-counterexample C:7 [3, 1, 1, 3] Anchor: 171 [ 65 101 155 59 ] 3 counterexample C:7 [3, 1, 2, 2] Anchor: 459 [ 173 263 199 151 ] 4 counterexample C:7 [3, 1, 3, 1] Anchor: 11 [ 5 11 5 11 ] 4 counterexample C:7 [3, 2, 1, 2] Anchor: 379 [ 143 109 167 127 ] 1 counterexample C:7 [3, 2, 2, 1] Anchor: 443 [ 167 127 97 149 ] 2 counterexample C:7 [3, 3, 1, 1] Anchor: 283 [ 107 41 65 101 ] 3 counterexample C:7 [4, 1, 1, 2] Anchor: 259 [ 49 77 119 91 ] 0 non-counterexample C:7 [4, 1, 2, 1] Anchor: 323 [ 61 95 73 113 ] 1 counterexample C:7 [4, 2, 1, 1] Anchor: 163 [ 31 25 41 65 ] 2 counterexample C:7 [5, 1, 1, 1] Anchor: 435 [ 41 65 101 155 ] 1 counterexample
- There are three explanations in the "Are We Near a Solution...?" paper alone of what I mean by "not enough room" for counterexamples, namely, in the sections "Summary of Solution Strategy", current pp. 2-3; "Strategy in Brief", current p. 17; and "The Underlying Intuition", current p. 37.
- Let me outline that explanation here: each i-level tuple-set, i >= 2, has exactly one i-level first tuple, which is called the "anchor tuple" for that tuple-set. The last element of an anchor tuple is called an "anchor". The anchor tuple, like all tuples, is a non-counterexample tuple or a counterexample tuple, but never both. Each tuple has an extension that is an anchor tuple. My strategy is to show that there is not enough room in the set of all anchor tuples for both non-counterexample anchor tuples and counterexample anchor tuples.
- Mensanator's list of counterexample anchor tuples is another case of his changing the definition of my terms and then proceeding to show that my statements are wrong when applied to the changed definitions. I can assure him that there are no counterexample anchors less than 56 • 10^15 (56 quadrillion) (with my definition of "counterexample" and "anchor" as set forth, e.g., in "Are We Near a Solution...?"). See papers on computer testing of the 3x + 1 function in Jeff Lagarias's excellent annotated bibliography for the currently largest number that has been found to terminate in 1, 1, 1, ... Putting it another way, there are no counterexample anchor tuples in i-level tuple-sets if i <35. (An i-level anchor is less than 2*3^(i - 1), and 2 • 3^(35 - 1) < 56 • 10^15.) Peter Schorer (talk) 05:57, 23 January 2008 (UTC)
- This does NOT refer to the largest number tested but the largest value such that all smaller number have been tested (of which there is an ongoing project to extend that limit). Personally, I've tested numbers a tad larger, such as 10^479940 (yes, that's 479 thousand DECIMAL DIGITS, you'll understand that I won't print it here). The exponent sequence from that number to 1 has 7,684,198 elements. And besides, why does that have any significance? Reading the main article, we see
- Experimental evidence The conjecture has been checked by computer for all start values up to 10×2^58 ≈ 2.88×10^18. While impressive, such computer bounds are of very limited evidential value. More than one important conjecture has been found to have only exceptionally large-valued counterexamples (see for examples the Pólya conjecture, the Mertens conjecture and the Skewes' number).
- How do we know that the first counterexample anchor in 3n+1 doesn't have 479940 digits?--Mensanator (talk) 03:39, 28 January 2008 (UTC)
And let's not forget those statements that are not just wrong, but reveal a complete ignorance about the structure of the 3n+1 problem that the author purports to be an expert on.
<quote>To repeat: there is no way of telling from a finite exponent sequence that it is associated with a counterexample. For example, the sequence {a2,a3,...,a2,a3,...a2,a3,...}, in which {a2,a3,...,a2} is repeated, say, a trillion times, does not imply the existence of a counterexample cycle.</quote>
Unbeknownst to the author, there IS just such a way of telling, see Google Group TrueButUnproven. Where, for example, one learns that the Crossover Point of an exponent sequence is invariant over generations. In other words, if the base sequence isn't a loop, then NO amount of repetition, even a trillion, can make it one. And if the base sequence defines a loop cycle, then ALL repetitions define the same cycle.
- I may not be fully understanding Mensanator's comment, but the reason that it is impossible to tell, from an exponent sequence alone, if a tuple associated with that exponent sequence is a counterexample tuple is Lemma 5.0, current p. 29 in the "...Solution...?" paper. This Lemma states that if counterexamples exist, then each tuple-set contains an infinity of non-counterexample tuples and an infinity of counterexample tuples. So if the exponent sequence generating a tuple-set consists of a sub-sequence of, say, 1,000,000 exponents, and then that sub-sequence is repeated, say, 10,000,000 times, it is still not possible to say that the corresponding tuple-set contains a counterexample tuple, e.g., an infinitely cycling tuple. Peter Schorer (talk) 05:57, 23 January 2008 (UTC)
- If the Lemma contradicts what I said, the Lemma is simply false. I'm not just making this up. One can look at Gottfried Helms papers linked to in the next section where you will find derivations identicle to mine (with a bit more mathematical rigor). He then goes off on a tangent about m-cycles whereas I go off on a different tangent as above.--Mensanator (talk) 03:39, 28 January 2008 (UTC)
- For example, take the exponent sequence [1,2,3,4]. The Hailstone Function Parameters (see section "Possible proof against a repeating cycle that does not include 1" above) are
X: 1024 Y: 81 Z: 133
- so the Crossover Point (Z/(X-Y)) is 133/943. Every exponent sequence is a loop cycle in the rationals (see "Iterating on rational numbers with odd denominators" in the main article). For this example, the loop cycle is
133/943 671/943 739/943 395/943 133/943
- [1,2,3,4] can't be a loop in 3n+1 because the Crossover Points of the cyclic permutations of the exponent sequence are not integers.
- But what if I repeat [1,2,3,4] a trillion times?
- Doesn't matter, the Crossover Point is invariant under exponent sequence repetition:
1 repetition: [1, 2, 3, 4]
xyz: (mpz(1024),
mpz(81),
mpz(133))
CP: 133/943
2 repetition: [1, 2, 3, 4, 1, 2, 3, 4]
xyz: (mpz(1048576),
mpz(6561),
mpz(146965))
CP: 146965/1042015
3 repetition: [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]
xyz: (mpz(1073741824),
mpz(531441),
mpz(151364773))
CP: 151364773/1073210383
4 repetition: [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]
xyz: (mpz(1099511627776L),
mpz(43046721),
mpz(155068209205L))
CP: 155068209205/1099468581055
5 repetition: [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]
xyz: (mpz(1125899906842624L),
mpz(3486784401L),
mpz(158795571439813L))
CP: 158795571439813/1125896420058223
6 repetition: [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4,
1, 2, 3, 4]
xyz: (mpz(1152921504606846976L),
mpz(282429536481L),
mpz(162607128896693845L))
CP: 162607128896693845/1152921222177310495
7 repetition: [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4,
1, 2, 3, 4, 1, 2, 3, 4]
xyz: (mpz(1180591620717411303424L),
mpz(22876792454961L),
mpz(166509737553342849253L))
CP: 166509737553342849253/1180591597840618848463
8 repetition: [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4,
1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]
xyz: (mpz(1208925819614629174706176L),
mpz(1853020188851841L),
mpz(170505974297236474144885L))
CP: 170505974297236474144885/1208925817761608985854335
9 repetition: [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4,
1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]
xyz: (mpz(1237940039285380274899124224L),
mpz(150094635296999121L),
mpz(174598117926821834641657093L))
CP: 174598117926821834641657093/1237940039135285639602125103
10 repetition: [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4,
1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]
xyz: (mpz(1267650600228229401496703205376L),
mpz(12157665459056928801L),
mpz(178788472777028145167557746325L))
CP: 178788472777028145167557746325/1267650600216071736037646276575
- Now, watch as I reduce the CP to lowest terms:
1 repetition: CP: 133/943 2 repetition: CP: 133/943 3 repetition: CP: 133/943 4 repetition: CP: 133/943 5 repetition: CP: 133/943 6 repetition: CP: 133/943 7 repetition: CP: 133/943 8 repetition: CP: 133/943 9 repetition: CP: 133/943 10 repetition: CP: 133/943
- Spooky, eh?
- Thus, any Lemma that implies that "it is still not possible to say that the corresponding tuple-set contains a counterexample tuple" is simply false as it is always possible to say because we always know the Crossover Point of the base sequence [1,2,3,4] and thus always know the Crossover Point of any and ALL possible repetitions.
- No tuples were harmed (or even used) in this demonstration in the 3n+1 positive domain which truly represents the 3n+1 structure.--Mensanator (talk) 07:33, 30 January 2008 (UTC)
Need we mention the errors due to just plain sloppiness, such as claiming that <7,11> is the anchor tuple of the tuple set defined by {1}? The anchor tuple is actually <3,5>, so whatever point was trying to be made, it obviously fell flat.
- I assume Mensanator is referring to current p. 14 in the section "Infinite Tuples, Marks, and Tuple-sets" in the "...Solution...?" paper. The error is minor indeed. I should have said that 17, not 11, is the anchor of the infinite tuple <7, 11, 17, 13, 5, 1, 1, 1, ... >and, in particular, is the anchor of the tuple-set generated by the exponent sequence {1, 1} not of the tuple-set generated by the exponent sequence {1}.
- Mensanator says that, as a result of this minor error, "whatever point was trying to be made, it obviously fell flat". I don't think this is true for anyone who has understood the section up to that point. Peter Schorer (talk) 05:57, 23 January 2008 (UTC)
- Sure, anyone who isn't a fool or an incompetent can see the value of tuple sets.--Mensanator (talk) 03:39, 28 January 2008 (UTC)
The author needs to go back to the blackboard, re-cast all his Lemmas in structure-centric terms, shake out all the value-centric non sequitur fallacies, throw out the naive intuitions about things he's never seen, replace them with sound, logical inferences drawn from true counterexamples and THEN he can present a new paper that hopefully will be consistent with reality. --Mensanator (talk) 00:51, 19 January 2008 (UTC)
- I repeat: I am trying to solve the original 3x + 1 Problem in the context of the original 3x + 1 Problem, not in the context of the 3n + C Problem. All the lemmas and proofs in my 3x + 1 papers have been checked and double-checked by more than half a dozen professional mathematicians and found to be correct. My primary task now is to see if I can deliver a correct proof based on the strategy mentioned above.
- I have written Mensanator urging him to add links and/or references to his papers on the 3n + C Problem, because I am sure they will be of interest to researchers. Peter Schorer (talk) 05:57, 23 January 2008 (UTC)
- There are already links in the References section of the main article, not to mention links in this discussion section.--Mensanator (talk) 03:39, 28 January 2008 (UTC)
Another link, about cycles
Hmm, perhaps these links should also go into attention. I was dealing with loops/cycles.
However, I did not much after the composition - if there is some interest in it I'd take time to improve.
Gottfried --Gotti 19:00, 23 January 2008 (UTC)
Dots in piecewise functions intended to end sentences
Just taking to talk instead of reverting and giving a summary explanation :) I see that they're *intended* to end the sentences, but they end up confusing the function declaration, especially in the piecewise functions, where they end up stranded in the middle of the statement. I don't think it's necessary to insert the period - the end of the sentence is implicit by the colon before the declaration and the declaration itself. The periods wind up appearing to be part of the mathematical or logical statement and merely confuse things without making anything more clear. I think we should take them out. Kyle Barbour 07:49, 5 April 2008 (UTC)
Frankly, I hadn't noticed them before you brought it up. But now that you've pointed it out, they do seem annoying and unnecessary. I would uhttp://en.wikipedia.org/w/index.php?title=Talk:Collatz_conjecture&action=edit Editing Talk:Collatz conjecture - Wikipedia, the free encyclopediase as a guide how this is handled in professional papers and textbooks (for which I haven't a clue). My two cents. --Mensanator (talk) 17:17, 5 April 2008 (UTC)
- Taking a quick look at my calculus textbook (Stewart's Calculus, 5th ed), there are no such periods. However, a quick look at a few papers (see, for example, [10] or [11] for some examples) shows that they use them there. Looking at Spivak's Calculus it looks like I'm further shown wrong :) So, I suppose that instead of removing them (which seems as though it would read better to me), we should just correct the TeX so that the periods don't wind up in the middle of the piecewise functions. Shucks. Kyle Barbour 20:45, 5 April 2008 (UTC)
Evidence that the conjecture may be proved
Please everyone. Check this link. The magazine publishes an article by Paul S. Bruckman under the title A proof of the Collatz conjecture. Write here your opinion. -- Magioladitis (talk) 19:47, 8 April 2008 (UTC)
$28 for the privelege of reading another crackpot proof? Surely you jest. And why is this published in an education journal? Because the peer reviewers aren't qualified to assess the article? I can tell you without even reading it what the problem with it is. The author has come up with some pet scheme (like Ken Conrow's Left Descent Assemblies, Peter Schorr's Tuple Sets or Alan Tyte's N-Chains) that is true in 3n+1 so he foolishly believes the truth of this scheme implies the truth of the CC. But it will work out that his scheme is true for all 3n+C so that the truth of CC doesn't follow from his scheme even though his scheme is true. It will be another non sequitur fallacy just like all the rest.--Mensanator (talk) 06:28, 9 April 2008 (UTC)
- Mensanator, I'm curious. Do you have any thoughts on what direction a successful proof might take? -GTBacchus(talk) 06:33, 9 April 2008 (UTC)
- Gee, if I knew that... Seriously, when I look at these "proofs", the first thing I ask myself is "how does this scheme explain why 3n+1 works whereas 3n+5 doesn't". Usually, I see no such explanation. For example, in Ken Conrow's LDAs, he says that the set of all LDAs leads to an integer density of one, implying all integers are reachable from this set implying CC is true. Alas, counterexample graphs also have LDAs, so gathering them together implies combining ALL graph components even when they are not connected. So of course he's going to get integer density of one for 3n+1. He'll get integer density of one for ALL 3n+C. He'll have no way of knowing whether the integer density of one is due to CC being true or due to the inclusion of unknown counterexample graph components. Thus, the truth of CC doesn't follow from LDA theory. It may be necessary but I have yet to see a system where it's sufficient. Another case is in my paper "Blueprint For Failure: How To Construct A Counterexample To The Collatz Conjecture". I talk about how Factor Congruence Matching is what causes 3n+C systems to fail the conjecture and how it is impossible for that failure to occur in 3n+1 because 1 has no factors - and THAT'S what sets 3n+1 apart from other 3n+C systems (where C is odd and not a power of 3). I do NOT claim a proof because I realized that although lack of FCM is necessary, it is not sufficient. Summing up, what I want to see is "here is why it works in 3n+1 and here is why it can't work in 3n+C".--Mensanator (talk) 07:12, 9 April 2008 (UTC)
- Yeah, ever since seeing the 3n+1 function as a special case of the 3n+C function, I do find it difficult to look back. It really seems to be the right context in which to be asking questions. -GTBacchus(talk) 07:16, 9 April 2008 (UTC)
- Gee, if I knew that... Seriously, when I look at these "proofs", the first thing I ask myself is "how does this scheme explain why 3n+1 works whereas 3n+5 doesn't". Usually, I see no such explanation. For example, in Ken Conrow's LDAs, he says that the set of all LDAs leads to an integer density of one, implying all integers are reachable from this set implying CC is true. Alas, counterexample graphs also have LDAs, so gathering them together implies combining ALL graph components even when they are not connected. So of course he's going to get integer density of one for 3n+1. He'll get integer density of one for ALL 3n+C. He'll have no way of knowing whether the integer density of one is due to CC being true or due to the inclusion of unknown counterexample graph components. Thus, the truth of CC doesn't follow from LDA theory. It may be necessary but I have yet to see a system where it's sufficient. Another case is in my paper "Blueprint For Failure: How To Construct A Counterexample To The Collatz Conjecture". I talk about how Factor Congruence Matching is what causes 3n+C systems to fail the conjecture and how it is impossible for that failure to occur in 3n+1 because 1 has no factors - and THAT'S what sets 3n+1 apart from other 3n+C systems (where C is odd and not a power of 3). I do NOT claim a proof because I realized that although lack of FCM is necessary, it is not sufficient. Summing up, what I want to see is "here is why it works in 3n+1 and here is why it can't work in 3n+C".--Mensanator (talk) 07:12, 9 April 2008 (UTC)
- The fact that the article has been published to an education journal was the reason I reverted the edits. An elementary proof written in five pages and with only one reference... well we have to be careful. Moreover, it is certain that Mathematicians that are really that have done some work trying to solve the problem haven't checked this proposed proof yet.
- Please everyone, here we are discussing about the Wikipedia article and not how to prove the conjecture. The are plenty of math forums for that. -- Magioladitis (talk) 08:12, 9 April 2008 (UTC)
- I know; it was just an idle question. Carry on. -GTBacchus(talk) 13:51, 9 April 2008 (UTC)
- Ok, but doesn't the quality of the evidence have a bearing on what should be included in the Wikipedia article? And doesn't knowing something about how the conjecture can be proved have a bearing on determining said quality? Isn't it fair to the author whose work is being deleted to explain why his evidence is not acceptable? I would say that this particular forum should be about why the evidence is unacceptable. Perhaps simply stating that the journal in question doesn't rate as being a reliable reference is sufficient for Wikipedia purposes. But I assumed that this discussion page is to go beyond the Edit Summaries. Maybe I'm wrong about that.--Mensanator (talk) 17:40, 9 April 2008 (UTC)
- I think that responding to the proffered evidence, with commentary as to its reliability, is very appropriate. It was I who went off-topic in asking you what direction you think a correct proof might take. -GTBacchus(talk) 17:46, 9 April 2008 (UTC)
- Ok, but doesn't the quality of the evidence have a bearing on what should be included in the Wikipedia article? And doesn't knowing something about how the conjecture can be proved have a bearing on determining said quality? Isn't it fair to the author whose work is being deleted to explain why his evidence is not acceptable? I would say that this particular forum should be about why the evidence is unacceptable. Perhaps simply stating that the journal in question doesn't rate as being a reliable reference is sufficient for Wikipedia purposes. But I assumed that this discussion page is to go beyond the Edit Summaries. Maybe I'm wrong about that.--Mensanator (talk) 17:40, 9 April 2008 (UTC)
- 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;
- ...
- Exceptional claims in Wikipedia require high-quality reliable sources; if such sources are not available, the material should not be included."
- "Certain red flags should prompt editors to examine the sources for a given claim:
- An accepted proof of the Collatz conjecture would surely get a lot of attention which hasn't been seen for this alleged proof in a journal which is primarily about education and doesn't appear to be high-quality for theorems. So leaving it out of the article is firmly based in policy. PrimeHunter (talk) 22:15, 9 April 2008 (UTC)
- We wouldn't want to "break the story" anyway. We aim to document things after the mainstream has done so. Don't come here w/ a paper proving a result; come with citations of that paper by people in the field who were convinced. -GTBacchus(talk) 00:58, 10 April 2008 (UTC)
- Could someone with access to a library having that obscure journal not report here ? Even if the alleged proof is easily rebuked, there might be something interesting about it. Strangely, it seems nothing at all's been posted yet in sci.math or other usenet n.g. - including by Paul S. Bruckman himself who otherwise is a frequent poster... Google et al. lead to nothing but the abstract at the site of the Journal. 90.54.9.124 (talk) 10:25, 13 April 2008 (UTC) Random Crank.
- My University stopped buying this magazine in paper form... in 1993. There is no preprint in ArXiv neither. I also have to state that as much as I know, by reading Lagarias's annotated bibliography, an approach by considering the minimum number that doesn't satisfy the conjecture is very unlikely to give a proof. I don't say it's impossible but we have to be very careful before we add anything in the main article. -- Magioladitis (talk) 12:24, 13 April 2008 (UTC)
Breaking news ! Jeff Lagarias doesn't buy Bruckman's proof; from his just revised annotated bibliography : "At present the 3x + 1 conjecture remains unsolved. In particular, the proofs claimed in Cadogan (2006) and Bruckman (2008) are incomplete." <http://arxiv.org/abs/math/0608208v3> Ninho (talk) 10:20, 24 April 2008 (UTC) Ninho
- Thanks! -- Magioladitis (talk) 08:39, 26 April 2008 (UTC)