![]() | This is an archive of past discussions. 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 |
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.
Example 1. , done in 2*4 = 8 steps
Example 2. , done in 2*5 = 10 steps
Note that up until the sequence equals it toggles between odd and even n times.
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.
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
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
Is this worth noting? Am I hitting on something here? Have others noted this before?
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,
</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)
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)
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)
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)
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)
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)
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)
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
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
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:
But so I would say f (4k + 1) = f ( 3k + 1)
Dave Couptily ( talk) 13:35, 2 May 2008 (UTC)
4k+1___even | 4k+1___even even | | even k___even | or | k___even even | | odd odd
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)
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?
I used the standard found here: [6] What standard are you referencing? -- Mensanator 22:39, 24 August 2006 (UTC)
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;
with probability 1/4, the next odd number is (3n+1)/4;
with probability 1/8, the next odd number is (3n+1)/8;
and so on.
Of course, these probabilities are only heuristic.
Anyway the expected size of the next number is
therefore
In other words, the probabilistic evidence suggests that the next odd number should be slightly larger.
Please correct me if I'm wrong.
Assuming I'm right,
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.
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)
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)
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)
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)
# 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)
# tc factor of 2 distribution (* scale = 8) # 1 ( 98) ************ # 2 (229) **************************** # 3 ( 63) ******* # 4 (110) *************
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)
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 ;)
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)
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)
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)
Thanks. Sr13 03:05, 28 September 2006 (UTC)
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 just happen to read this post today --- the flaw in this "proof" is easily noticed …
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 ?
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,
But if k is 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)
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)
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).
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)
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)
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)
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;
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.
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)
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.
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)
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 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.
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)
What a load! No wonder no one wants to look over this, you need a machete and a guide.
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.
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>
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
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.
X: 1024 Y: 81 Z: 133
133/943 671/943 739/943 395/943 133/943
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
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
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.
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)
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)
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/?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)
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)
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
![]() | This is an archive of past discussions. 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 |
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.
Example 1. , done in 2*4 = 8 steps
Example 2. , done in 2*5 = 10 steps
Note that up until the sequence equals it toggles between odd and even n times.
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.
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
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
Is this worth noting? Am I hitting on something here? Have others noted this before?
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,
</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)
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)
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)
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)
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)
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)
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)
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
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
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:
But so I would say f (4k + 1) = f ( 3k + 1)
Dave Couptily ( talk) 13:35, 2 May 2008 (UTC)
4k+1___even | 4k+1___even even | | even k___even | or | k___even even | | odd odd
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)
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?
I used the standard found here: [6] What standard are you referencing? -- Mensanator 22:39, 24 August 2006 (UTC)
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;
with probability 1/4, the next odd number is (3n+1)/4;
with probability 1/8, the next odd number is (3n+1)/8;
and so on.
Of course, these probabilities are only heuristic.
Anyway the expected size of the next number is
therefore
In other words, the probabilistic evidence suggests that the next odd number should be slightly larger.
Please correct me if I'm wrong.
Assuming I'm right,
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.
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)
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)
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)
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)
# 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)
# tc factor of 2 distribution (* scale = 8) # 1 ( 98) ************ # 2 (229) **************************** # 3 ( 63) ******* # 4 (110) *************
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)
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 ;)
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)
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)
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)
Thanks. Sr13 03:05, 28 September 2006 (UTC)
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 just happen to read this post today --- the flaw in this "proof" is easily noticed …
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 ?
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,
But if k is 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)
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)
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).
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)
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)
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)
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;
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.
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)
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.
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)
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 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.
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)
What a load! No wonder no one wants to look over this, you need a machete and a guide.
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.
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>
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
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.
X: 1024 Y: 81 Z: 133
133/943 671/943 739/943 395/943 133/943
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
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
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.
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)
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)
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/?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)
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)
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