## 0710: "Collatz Conjecture"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

BlazeOrangeDeer
Posts: 61
Joined: Tue Aug 25, 2009 3:44 am UTC

### Re: "Collatz Conjecture" Discussion

So here it is in TI-Basic, it's always fun to have a portable collatz calculator, you know.

:0→dim(L1
:Input A
:int(abs(A
:While Ans≠1
:Ans→L1(1+dim(L1
:If fPart(Ans/2
:Then:3Ans+1
:Else:Ans/2
:End:End
:1→L1(1+dim(L1
:Disp dim(L1)-1
:L1

the "L1"s are typed with (2nd)(1), and the rest of the stuff can be found in the catalog if you aren't sure (2nd)(0)
it shows how many steps were taken, then the list of numbers.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

### Re: "Collatz Conjecture" Discussion

Has anyone else noticed the lengths of sequences tend to clump together?
0 1 7 2 5 8 16 3 19 6 14 9 9 17 17 4 12 20 20 7 7 15 15 10 23 10 111 18 18 18 106 5 26 13 13 21 21 21 34 8 109 8 29 16 16 16 104 11 24 24 24 11 11 112 112 19 32 19 32 19 19 107 107 6 27 27 27 14 14 14 102 22 115 22 14 22 22 35 35 9 22 110 110 9 9 30 30 17 30 17 92 17 17 105 105 12 118 25 25 25 25 25 87 12 38 12 100 113 113 113 69 20 12 33 33 20 20 33 33 20 95 20 46 108 108 108 46 7 121 28 28 28 28 28 41 15 90 15 41 15 15 103 103 23 116 116 116 23 23 15 15 23 36 23 85 36 36 36 54 10 98 23 23 111 111 111 67 10 49 10 124 31 31 31 80 18 31 31 31 18 18 93 93 18 44 18 44 106 106 106 44 13 119 119 119 26 26 26 119 26 18 26 39 26 26 88 88 13 39 39 39 13 13 101 101 114 26 114 52 114 114 70 70 21 52 13 13 34 34 34 127 21 83 21 127 34 34 34 52 21 21 96 96 21 21 47 47 109 47 109 65 109 109 47 47 8 122 122 122 29 29 29 78 29 122 29 21 29 29 42 42 16 29 91 91 16 16 42 42 16 42 16 60 104 104 104 42 24 29 117 117 117 117 117 55 24 73 24 117 16 16 16 42 24 37 37 37 24 24 86 86 37 130 37 37 37 37 55 55 11 24 99 99 24 24 24 143 112 50 112 24 112 112 68 68 11 112 50 50 11 11 125 125 32 125 32 125 32 32 81 81 19 125 32 32 32 32 32 50 19 45 19 45 94 94 94 45 19 19 45 45 19 19 45 45 107 63 107 58 107 107 45 45 14 32 120 120 120 120 120 120 27 58 27 76 27 27 120 120 27 19 19 19 27 27 40 40 27 40 27 133 89 89 89 133 14 133 40 40 40 40 40 32 14 58 14 53 102 102 102 40 115 27 27 27 115 115 53 53 115 27 115 53 71 71 71 97 22 115 53 53 14 14 14 40 35 128 35 128 35 35 128 128 22 35 84 84 22 22 128 128 35 35 35 27 35 35 53 53 22 48 22 22 97 97 97 141 22 48 22 141 48 48 48 97 110 22 48 48 110 110 66 66 110 61 110 35 48 48 48 61 9 35 123 123 123 123 123 61 30 123 30 123 30 30 79 79 30 30 123 123 30 30 22 22 30 22 30 48 43 43 43 136 17 43 30 30 92 92 92 43 17 136 17 30 43 43 43 87 17 43 43 43 17 17 61 61 105 56 105 30 105 105 43 43 25 30 30 30 118 118 118 30 118 56 118 118 118 118 56 56 25 74 74 74 25 25 118 118 17 56 17 69 17 17 43 43 25 131 38 38 38 38 38 69 25 131 25 131 87 87 87 131 38 25 131 131 38 38 38 38 38 30 38 30 56 56 56 131 12 51 25 25 100 100 100 38 25 144 25 100 25 25 144 144 113 51 51 51 113 113 25 25 113 51 113 144 69 69 69 95 12 64 113 113 51 51 51 64 12 64 12 38 126 126 126 38 33 126 126 126 33 33 126 126 33 126 33 64 82 82 82 170 20 33 126 126 33 33 33 64 33 25 33 25 33 33 51 51 20 46 46 46 20 20 46 46 95 33 95 139 95 95 46 46 20 139 20 20 46 46 46 95 20 90 20 46 46 46 46 139 108 20 64 64 108 108 59 59 108 33 108 152 46 46 46 59 15 33 33 33 121 121 121 152 121 33 121 59 121 121 121 121 28 121 59 59 28 28 77 77 28 77 28 103 121 121 121 72 28 59 20 20 20 20 20 72 28 46 28 134 41 41 41 134 28 41 41 41 28 28 134 134 90 134 90 41 90 90 134 134 15 28 134 134 41 41 41 85 41 41 41 41 41 41 33 33 15 59 59 59 15 15 54 54 103 28 103 147 103 103 41 41 116 147 28 28 28 28 28 178 116 147 116 28 54 54 54 147 116 116 28 28 116 116 54 54 72 147 72 46 72 72 98 98 23 67 116 116 54 54 54 116 15 67 15 54 15 15 41 41 36 129 129 129 36 36 129 129 36 129 36 67 129 129 129 116 23 129 36 36 85 85 85 129 23 173 23 85 129 129 129 36 36 36 36 36 36 36 28 28 36 28 36 28 54 54 54 129 23 49 49 49 23 23 23 142 98 49 98 36 98 98 142 142 23 98 49 49 23 23 142 142 49 23 49 36 49 49 98 98 111 93 23 23 49 49 49 49

EDIT: Changed to consider "1"'s sequence to be 0 in length because that's how A006577 does it.

Obligatory code:

Code: Select all

#include <stdio.h>int main() {   for(int i=1;i<1000;i++) {      int n = i;      int j = 0;      for(;;) {         if(n == 1) break;         n = n%2?n*3+1:n/2;         j++;      }//      printf("%d: [%d]",i,j);      printf(" %d",j);      n=i;//      for(;;) { // need to do it again to print the numbers after the count//         printf(" %d",n);//         if(n == 1) break;//         n = n%2?n*3+1:n/2;//      }//      putchar('\n');   }   return 0;}

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

As everyone knows (hopefully), there are usually three outcomes of a theorem that settle it:
-It is proven true.
-It is proven false.
-It is proven impossible to prove/disprove.

Another option is that it is impossible to prove, and impossible to prove impossible to prove. So no one can do one or two, and no one can do three, either. In this case, it is likely that people would try for... well, forever, attempting to prove it one way or the other, or trying to prove it impossible to prove. Luckily, often it can be proven impossible to prove impossible to prove, in which case people could stop with the third option.

Below I outline a proof that the Collatz Conjecture cannot be proven impossible to prove.

Any theorem for which its falsity has a necessary and sufficient condition of the existence of a counterexample can easily be proven impossible to prove impossible to prove (this is a well known, easy to show statement). For example, the Four-Color theorem and Fermat's last theorem were both such theorems - if they were not true, there would be a counter-example, and if there was a counter-example, they would be untrue. In order to prove that the Collatz Conjecture cannot be proven impossible to prove, all we must do is come up with a way of showing that a counterexample disproves the theorem in finite time.

For periodic numbers under iteration of the Collatz function, and numbers that eventually go into a periodic cycle, or numbers that climb without bound, we can check in finite time. For each number x that we would like to verify is a counter-example, it can be re-written as a Turing machine. This is not difficult to do. Now, we look at the corresponding Busy Beaver number. We do not need to know it exactly, only its upper bound. If the number does not go to one in steps less than or equal to the Busy Beaver number, we know it to be a counter-example. In fact, we can check it in less, because the Turing machine will use several steps for each iteration of the Collatz function.

So, any supposed counter-example can be proven to be a counter-example. We can show that it is impossible for it to be proven impossible to prove by contradiction: If it was false, there would exist a counterexample. This counter example is necessarily finite, so it could be found if it was false (given enough time). If we assume it is impossible to prove/disprove, then there must not be any counterexamples. This means it cannot be false, so it must be true. I.e., showing it impossible to prove is equivalent to proving it - this is the contradiction.

Please note that this doesn't mean it's unprovable - it might still be that there exists no proof, nor counterexample. It only means that we can't show that there isn't a proof or counterexample. So this could be bad news... but don't blame me, remember it was true before I wrote this too!!
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

sharky3112
Posts: 2
Joined: Sun Mar 07, 2010 5:00 pm UTC
Location: Germany

### Re: "Collatz Conjecture" Discussion

leifbk wrote:
sharky3112 wrote:hi!
great comic, like most of yours!
i've never heard about the collatz-probleme before reading the comic, but i had to wikipedia it. after writing a little java-program and testing every number up to 2147483647 (java-int-maximum) i'm still fascinated.
Keep at it!
sharky3112

If you wrote a Java program and tested more than two billion values in it in about 60 hours, I'm very, very impressed.

youre right, java worked a quite long time... so i decided to try python:
Spoiler:

Code: Select all

import timelist=[]def c(num):   while (num != 1):      odd = num%2      if (odd == 1):         num = num * 3 + 1         if num not in list:            list.append(num)         else:            break      else:         num = num / 2         if num not in list:            list.append(num)         else:            breakdef test(max):   timeb = time.time()   i=1   while (i<max):      c(i)      i=i+1   timel = time.time() - timeb   print timeltest(9999)11.9720001221

python worked just 11.9 seconds and checked every number up to 9998.

 i deleted list.sort() after every list.append(), because i realized that it takes a good deal more time

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: "Collatz Conjecture" Discussion

This comic inspired me to build a Collatz sequence generator in Conway's Game of Life. It does the calculations in binary and can handle numbers up to 127 bits long.

For details, see the ConwayLife forum.

krucifi
Posts: 68
Joined: Mon Mar 22, 2010 3:12 am UTC

### Re: "Collatz Conjecture" Discussion

ok i have a theory please correct me if im wrong.
the need to converge to one seems a little much. wouldnt it be logical to save time and energy and allow it to converge to 4 to the power k?
also i believe it is not impossible to prove as no matter what number you start with there is always a number before it in the chain. eg if i choose to start with 65 then you can say well if 65 converges so does 130 and so on till eventually i could cover every number as every number has a double and some of those will inevitably fall into 3k plus 1 somewhere along the lines. so a continuous growth would be impossible as after every 3k plus 1 there must be a 2k step. and its really hard to see an infinite process where it would alternate constanly as that would require infinite numbers in the sequence. its weird to get my thoughts down.

try this. if you did have a chain where it constantly alternated then in all instances where 3k plus 1 occurs then half of the new 2k must always be odd. so this new 2k cannot be a multiple of 4. so every number that falls into that category have to be removed for the theory that the conjecture has one chain that constantly increases. but the problem with that is eventually 3k plus 1 will hit a multiple of four or worse 4 to the power n. every fourth number will risk this happening and it is impossible for you to miss them all to get a continuously rising chain.

so what a bout a loop? well i dont think so a number needed for a loop would encompass all the numbers inside and all possible numbers leading to those numbers. which is infinite. lets say there is a chain of 5 numbers that do this. well those five are numbers that if we choose them all will loop. but we can choose to start with say 64k of any of those numbers and converge to it. so we have 6 numbers in the loop. but then we have to include all the numbers we went through to get back to k adn therefore the loop. so we have a few more. then i add 512k. now that adds 3 more numbers to get to k than 64k did. as you can see the numbers in a loop if there was any will become infinite so no loops can exist bar the 4 2 1 loop but that does encompass every number and we terminate by this point anyway.

if i have spoken bull pleeeez say so i think what i have sed is on the ball but im not sure. so any feedback will help
Yes, my name is the negative frequency of radioactive decay, of the initial speed of light's radius.
And on the eighth day God created Irony.
But on the ninth day Satan was all like, "Nuh uh!"
And ironically made Alanis Morrisette his minion.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

krucifi, I'm afraid there are some small holes in your reasoning. Most of it is completely correct, though!

It's not "impossible" that a number would keep alternating; it might be that there is some type of number that, after multiplying by three and then dividing by two, leaves you with exactly the same "type" of number. These would be extremely rare, yes; but such a singular type of number could exist, for all we know.

As for the loops: suppose there are five numbers, so that a->b, b->c, c->d, d->e, e->a. Then, yes, 64a would go into the loop too - but it still wouldn't be part of the loop. The sequence would go 64a->31a->16a->8a->4a->2a->a->b->c->d->e->a->... etc. So 64 a would act as an "entry point", but not necessarily as part of the loop. No number in the loop would have to go back to it.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

krucifi
Posts: 68
Joined: Mon Mar 22, 2010 3:12 am UTC

### Re: "Collatz Conjecture" Discussion

thanks for helping me out lolz.

but i still have qualms

if i had a loop from a) through e) where e) would be the smallest just to keep things tidy, then it would have to be odd and this means to reach a) the step 3k+1 must be performed. however every second doubling of a) when working backwards is in the form of 3k+1. so we now have infinite branches leading to this loop some way or another. but they are all converging to one singular point ,e), yes? if this is the case then i have a loop that every possible finite integer can reach because we can reach them through this loop by working backwards. but this means if there is a loop every single number must reach it. there is such a loop, the 4 2 1 loop at which point the conjecture terminates.

or am i talkin crap agen....?
Yes, my name is the negative frequency of radioactive decay, of the initial speed of light's radius.
And on the eighth day God created Irony.
But on the ninth day Satan was all like, "Nuh uh!"
And ironically made Alanis Morrisette his minion.

scarletmanuka
Posts: 533
Joined: Wed Oct 17, 2007 4:29 am UTC
Location: Perth, Western Australia

### Re: "Collatz Conjecture" Discussion

I think the point you are missing is that although there are infinitely many entry points to this loop, that doesn't mean that all numbers will reach the loop. You can take infinitely many numbers out of the pile and still have infinitely many left.

krucifi
Posts: 68
Joined: Mon Mar 22, 2010 3:12 am UTC

### Re: "Collatz Conjecture" Discussion

im getting it now thanks lol.

heres something im thinking to make the process quicker. can you make a program that checks all the numbers that havent been through the process? for example if you checked 212 then if it hit a number that was already in 1 to 211 chains then it would skip it entirely whilst referring you to which number it reached and therefore which chain it intersected? well what im thinking is it skips all odd numbers and all multiples of 4 leaving only numbers in form of 4k-2. because all odds can be reached by 4k-2 and all multiples of 4 can reach 4k-2. just a thought.
Yes, my name is the negative frequency of radioactive decay, of the initial speed of light's radius.
And on the eighth day God created Irony.
But on the ninth day Satan was all like, "Nuh uh!"
And ironically made Alanis Morrisette his minion.

sourmìlk
If I can't complain, can I at least express my fear?
Posts: 6393
Joined: Mon Dec 22, 2008 10:53 pm UTC
Location: permanently in the wrong
Contact:

### Re: "Collatz Conjecture" Discussion

Random832 wrote:Has anyone else noticed the lengths of sequences tend to clump together?
0 1 7 2 5 8 16 3 19 6 14 9 9 17 17 4 12 20 20 7 7 15 15 10 23 10 111 18 18 18 106 5 26 13 13 21 21 21 34 8 109 8 29 16 16 16 104 11 24 24 24 11 11 112 112 19 32 19 32 19 19 107 107 6 27 27 27 14 14 14 102 22 115 22 14 22 22 35 35 9 22 110 110 9 9 30 30 17 30 17 92 17 17 105 105 12 118 25 25 25 25 25 87 12 38 12 100 113 113 113 69 20 12 33 33 20 20 33 33 20 95 20 46 108 108 108 46 7 121 28 28 28 28 28 41 15 90 15 41 15 15 103 103 23 116 116 116 23 23 15 15 23 36 23 85 36 36 36 54 10 98 23 23 111 111 111 67 10 49 10 124 31 31 31 80 18 31 31 31 18 18 93 93 18 44 18 44 106 106 106 44 13 119 119 119 26 26 26 119 26 18 26 39 26 26 88 88 13 39 39 39 13 13 101 101 114 26 114 52 114 114 70 70 21 52 13 13 34 34 34 127 21 83 21 127 34 34 34 52 21 21 96 96 21 21 47 47 109 47 109 65 109 109 47 47 8 122 122 122 29 29 29 78 29 122 29 21 29 29 42 42 16 29 91 91 16 16 42 42 16 42 16 60 104 104 104 42 24 29 117 117 117 117 117 55 24 73 24 117 16 16 16 42 24 37 37 37 24 24 86 86 37 130 37 37 37 37 55 55 11 24 99 99 24 24 24 143 112 50 112 24 112 112 68 68 11 112 50 50 11 11 125 125 32 125 32 125 32 32 81 81 19 125 32 32 32 32 32 50 19 45 19 45 94 94 94 45 19 19 45 45 19 19 45 45 107 63 107 58 107 107 45 45 14 32 120 120 120 120 120 120 27 58 27 76 27 27 120 120 27 19 19 19 27 27 40 40 27 40 27 133 89 89 89 133 14 133 40 40 40 40 40 32 14 58 14 53 102 102 102 40 115 27 27 27 115 115 53 53 115 27 115 53 71 71 71 97 22 115 53 53 14 14 14 40 35 128 35 128 35 35 128 128 22 35 84 84 22 22 128 128 35 35 35 27 35 35 53 53 22 48 22 22 97 97 97 141 22 48 22 141 48 48 48 97 110 22 48 48 110 110 66 66 110 61 110 35 48 48 48 61 9 35 123 123 123 123 123 61 30 123 30 123 30 30 79 79 30 30 123 123 30 30 22 22 30 22 30 48 43 43 43 136 17 43 30 30 92 92 92 43 17 136 17 30 43 43 43 87 17 43 43 43 17 17 61 61 105 56 105 30 105 105 43 43 25 30 30 30 118 118 118 30 118 56 118 118 118 118 56 56 25 74 74 74 25 25 118 118 17 56 17 69 17 17 43 43 25 131 38 38 38 38 38 69 25 131 25 131 87 87 87 131 38 25 131 131 38 38 38 38 38 30 38 30 56 56 56 131 12 51 25 25 100 100 100 38 25 144 25 100 25 25 144 144 113 51 51 51 113 113 25 25 113 51 113 144 69 69 69 95 12 64 113 113 51 51 51 64 12 64 12 38 126 126 126 38 33 126 126 126 33 33 126 126 33 126 33 64 82 82 82 170 20 33 126 126 33 33 33 64 33 25 33 25 33 33 51 51 20 46 46 46 20 20 46 46 95 33 95 139 95 95 46 46 20 139 20 20 46 46 46 95 20 90 20 46 46 46 46 139 108 20 64 64 108 108 59 59 108 33 108 152 46 46 46 59 15 33 33 33 121 121 121 152 121 33 121 59 121 121 121 121 28 121 59 59 28 28 77 77 28 77 28 103 121 121 121 72 28 59 20 20 20 20 20 72 28 46 28 134 41 41 41 134 28 41 41 41 28 28 134 134 90 134 90 41 90 90 134 134 15 28 134 134 41 41 41 85 41 41 41 41 41 41 33 33 15 59 59 59 15 15 54 54 103 28 103 147 103 103 41 41 116 147 28 28 28 28 28 178 116 147 116 28 54 54 54 147 116 116 28 28 116 116 54 54 72 147 72 46 72 72 98 98 23 67 116 116 54 54 54 116 15 67 15 54 15 15 41 41 36 129 129 129 36 36 129 129 36 129 36 67 129 129 129 116 23 129 36 36 85 85 85 129 23 173 23 85 129 129 129 36 36 36 36 36 36 36 28 28 36 28 36 28 54 54 54 129 23 49 49 49 23 23 23 142 98 49 98 36 98 98 142 142 23 98 49 49 23 23 142 142 49 23 49 36 49 49 98 98 111 93 23 23 49 49 49 49

EDIT: Changed to consider "1"'s sequence to be 0 in length because that's how A006577 does it.

Obligatory code:

Code: Select all

#include <stdio.h>int main() {   for(int i=1;i<1000;i++) {      int n = i;      int j = 0;      for(;;) {         if(n == 1) break;         n = n%2?n*3+1:n/2;         j++;      }//      printf("%d: [%d]",i,j);      printf(" %d",j);      n=i;//      for(;;) { // need to do it again to print the numbers after the count//         printf(" %d",n);//         if(n == 1) break;//         n = n%2?n*3+1:n/2;//      }//      putchar('\n');   }   return 0;}

Why did you do it in C?

Python ftw.

Also, I tested it for some 3000+ digit numbers. It took about 100,000 steps for some of them O_O
Terry Pratchett wrote:The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### Re: "Collatz Conjecture" Discussion

It may be illuminating to contemplate reverse iteration of Collatz sequences, and to examine the behaviour of numbers of the form mk+r for various moduli m.

For example, using arithmetic mod 6, forward iteration gives:
0 -> 0 or 3
1 -> 4
2 -> 1 or 4
3 -> 4
4 -> 2 or 5
5 -> 4

Reverse iteration gives:
0 <- 0
1 <- 2
2 <- 4
3 <- 0
4 <- 1, 2, 3, 5
5 <- 4

Here's the same information in the form of a directed graph:

So when reverse iterating, numbers of the form n=6k+4 are crucial, as they are where branching occurs. And once n=6k+3, on the next step it will become 0 mod 6, and no further branching from this sequence is possible.

In the spoiler below are some sequences created by reverse iteration. Each sequence commences with a number of the form 6k+4. The first term is doubled, but thereafter the odd branch is followed, ie any numbers of the form n=6k+4 become (n - 1)/3. Each sequence continues until a number of the form 6k appears.

I've used colour coding based on the number's residue mod 6 to make the patterns more apparent, using the same colour scheme as in the graph above. Here is the colour key:
0=black, 1=brown, 2=orange, 3=green, 4=blue, 5=purple.

So all these sequences begin with a blue number and end in a black number (apart from the initial [1, 4, 2, 1] sequence). Any blue numbers arising in the sequences are branch points.

The big questions are: does reverse iteration starting from a blue number always lead to a black number? And do all these sequences tie together into a single tree?
Spoiler:
1 2 4 1
4 8 16 5 10 3 6
10 20 40 13 26 52 17 34 11 22 7 14 28 9 18
16 32 64 21 42
22 44 88 29 58 19 38 76 25 50 100 33 66
28 56 112 37 74 148 49 98 196 65 130 43 86 172 57 114
34 68 136 45 90
40 80 160 53 106 35 70 23 46 15 30
46 92 184 61 122 244 81 162
52 104 208 69 138
58 116 232 77 154 51 102
64 128 256 85 170340 113 226 75 150
70 140 280 93 186
76 152 304 101 20267 134 268 89 17859 118 39 78
82 164 328 109 218 436 145 290 580 193 386 772 257 514 171 342
88 176 352 117 234
94 188 376 125 25083 166 55 110 22073 146 292 97 194 388 129 258
100 200 400 133 266 532 177 354
106 212 424 141 282
112 224 448 149 298 99 198
118 236 472 157 314 628 209 418 139 278 556 185 370 123 246
124 248 496 165 330
130 260 520 173 346 115 230 460 153 306

FWIW, the above table was produced by a program I wrote in (old) Python. It can also produce output in the Graphviz Dots language, which can be used to generate nice tree diagrams, like the one earlier in this post. I'll clean it up & post it here, if there's any interest.

Black
Posts: 81
Joined: Fri Sep 19, 2008 4:24 am UTC

### Re: "Collatz Conjecture" Discussion

Dentroman
Posts: 22
Joined: Sun Mar 14, 2010 6:20 pm UTC

### Re: "Collatz Conjecture" Discussion

Wrote a program that can verify all numbers up to 2^25 in about 11 seconds. I've got to fix up some memory errors, but I'll post my code here soon.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

Okay, another implementation. It's a Google Gadget, so now you can even mess around with it on your homepage!! (Assuming Google is your homepage, and there's a good chance it isn't).

<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

Posts: 6
Joined: Tue Apr 20, 2010 10:37 pm UTC

### Re: "Collatz Conjecture" Discussion

I made a program in Visual studio C#. I timed it and it took about 20 seconds to work through all the numbers between 1 and 1,000,000. Based on that, it would take over five million years to work through all the numbers between 1 and the max of a signed long int, and it would take about one day to work through all the numbers between 1 and the max of a unsigned standard int. Unless my math is off or I programmed it wrong. Here is the code if anyone is interested, sorry in advance for my poor commenting skills:

//two buttons
//one text box

//text box text determines the end number
//one button starts it
//one button clears everything

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace WindowsFormsApplication6
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

long startnumber;
long placeholder;
long wrknum;
long roundcount;
long endnum;
bool proof;

private void btngo_Click(object sender, EventArgs e)
{
endnum = Convert.ToInt64(txtinput.Text);

for (int i = 1; i < endnum; i++)
{
startnumber = i;
lblfalse.Visible = false;
lbltrue.Visible = true;
placeholder = 0;
placeholder = startnumber;
roundcount = 0;

if (lblfalse.Visible == true)
{
i = short.MaxValue;
}

else
{
proof = false;
checker();
}
}
}
void checker()
{
if (proof == false)
{
placeholder = wrknum;
//odd number check
if (placeholder / 2 == (placeholder + 1) / 2)
{
wrknum = placeholder * 3 + 1;
}
else if (placeholder / 2 != (placeholder + 1) / 2)
{
wrknum = placeholder / 2;
}
if (placeholder == 1)
{
proof = true;
}
}
if (proof == true)
{
lbltrue.Visible = true;
}

if (roundcount == long.MaxValue)
{
lblfalse.Visible = true;
}

else if (proof == false)
{
roundcount = roundcount + 1;
checker();
}
}

private void btnclear_Click(object sender, EventArgs e)
{
lblfalse.Visible = false;
lbltrue.Visible = false;
}
}
}

krucifi
Posts: 68
Joined: Mon Mar 22, 2010 3:12 am UTC

### Re: "Collatz Conjecture" Discussion

lol when i seen your code start i thought u were making a 2 girls one cup joke haha
Yes, my name is the negative frequency of radioactive decay, of the initial speed of light's radius.
And on the eighth day God created Irony.
But on the ninth day Satan was all like, "Nuh uh!"
And ironically made Alanis Morrisette his minion.

Suineder
Posts: 1
Joined: Thu Apr 22, 2010 2:34 am UTC

### Re: "Collatz Conjecture" Discussion

I'm very late to this thread, but this comic inspired me to implement this algorithm on the old Basic Programming cartridge for the Atari VCS(http://www.atariage.com/software_page.html?SoftwareLabelID=15). Still very easy to make (this isn't optimized, though):

1 If S > 0 Then Goto 3
2 S <- Key Goto 1
3 If S Mod 2 = 0 Then S <- S / 2 Goto 3
4 If S = 1 Then Goto 4
5 S <- S * 3 +1 Goto 3

It should be run at speed 60 and the output is in the Variables pane.

Migi
Posts: 8
Joined: Sat Feb 21, 2009 12:13 pm UTC

### Re: "Collatz Conjecture" Discussion

squareroot wrote:... it can be re-written as a Turing machine. This is not difficult to do. Now, we look at the corresponding Busy Beaver number. We do not need to know it exactly, only its upper bound. If the number does not go to one in steps less than or equal to the Busy Beaver number, we know it to be a counter-example ...

Sorry, but there's a problem with this step: Finding an upper bound to the Busy Beaver function is only trivially easier than just knowing the exact value for it, unless it's impractically huge, in which case it's no good for your solution either. If you knew a reasonable upper bound for the Busy Beaver function of N, you could calculate how fast any 2-symbol N-state Turing machine halts. So solving it this way requires you to solve every problem that can be encoded in a 2-symbol N-state Turing machine, including the Collatz problem itself. Good luck

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

We don't have to actually know the value - just the fact that you cannot construct a Turing machine that runs for an arbitrary amount of time, yet halting, with only N instructions for some N, is enough to know that the Collatz sequence can't taker forever.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

ConMan
Shepherd's Pie?
Posts: 1690
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

### Re: "Collatz Conjecture" Discussion

squareroot wrote:We don't have to actually know the value - just the fact that you cannot construct a Turing machine that runs for an arbitrary amount of time, yet halting, with only N instructions for some N, is enough to know that the Collatz sequence can't taker forever.

But that very fact is a description of the Halting Problem/Busy Beaver uncomputability issue. If you could bound the number of steps - i.e. bound the BB from above - then you could solve the Halting Problem, therefore the function that specifies the bound is as uncomputable as the BB. Which is not to say that you can't define a function which is larger than the BB over a finite range including the number of instructions a Collatz machine uses, and from that create a Collatz-decider that would presumably prove the Collatz Conjecture, but that would definitely be a lot of work (especially proving that your function is in fact an upper bound for the BB over the required interval).
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

But the thing is we don't need to know any computable function that satisfies those requirements! We don't need to know a bounding function at all! (But if you really need one to satisfy yourself, try f(x)=BB(x)+1.) Just the fact that the BB function doesn't become infinite for finite X is enough to know that the Collatz sequence would have to stop in finite time if it does go to zero, so you could prove any number that doesn't go to zero to not, so all counterexamples are provable counterexamples.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

FatherStorm
Posts: 3
Joined: Fri Mar 05, 2010 1:38 pm UTC

### Re: "Collatz Conjecture" Discussion

thanks all. So far the "proof" has been proven to over 2 Billion numbers..

http://www.fatherstorm.com/Portfolio/collatzProofOnly.php

ConMan
Shepherd's Pie?
Posts: 1690
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

### Re: "Collatz Conjecture" Discussion

squareroot wrote:But the thing is we don't need to know any computable function that satisfies those requirements! We don't need to know a bounding function at all! (But if you really need one to satisfy yourself, try f(x)=BB(x)+1.) Just the fact that the BB function doesn't become infinite for finite X is enough to know that the Collatz sequence would have to stop in finite time if it does go to zero, so you could prove any number that doesn't go to zero to not, so all counterexamples are provable counterexamples.

I think I kind of follow you here, until the last line - the problem is that without knowing specifically what the bound is, there is no way to find the counterexample without iterating the function until it loops. If we knew the value of the appropriate BB function, then we could improve the efficiency of our proof by only iterating through BB(n) steps and stating that "Since the machine did not halt in BB(n) steps, it will never halt, therefore it is a counterexample".
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

### Re: "Collatz Conjecture" Discussion

Well, yes, theoretically we could. But the Busy Beaver function grows so quickly that (I think) if the next unproved number didn't end, then it would take so long for it to go above the upper bound that even with the best supercomputers and Moore's law, the Earth by the Sun before we reached it. Just the fact that some other race could, though, is enough.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

cuberoot
Posts: 1
Joined: Thu Sep 30, 2010 1:05 pm UTC

### Re: "Collatz Conjecture" Discussion

Dan04 wrote:
Breaking it down one step further, n god 16 ∈ {7, 11, 15} is equivalent to n god 32 ∈ {7, 11, 15, 23, 27, 31} .

n = 32m+7 → 96m+22 → 48m+11 → 144m+34 → 72m+17 → 216m+52 → 108m+26 → 54m+13 → 162m+40 → 81m+20, which may be even or odd depending on m.
n = 32m+11 → 96m+34 → 48m+17 → 144m+52 → 72m+26 → 36m+13 → 108m+40 → 54m+20 → 27m+10, which is always less than n.
n = 32m+15 → 96m+46 → 48m+23 → 144m+70 → 72m+35 → 216m+106 → 108m+53 → 324m+160 → 162m+80 → 81m+40, which may be even or odd depending on m.
n = 32m+23 → 96m+70 → 48m+35 → 144m+106 → 72m+53 → 216m+160 → 108m+80 → 54m+40 → 27m+20, which is always less than n.
n = 32m+27 → 96m+82 → 48m+41 → 144m+124 → 72m+62 → 36m+31 → 108m+94 → 54m+47 → 162m+142 → 81m+71, which may be even or odd depending on m.
n = 32m+31 → 96m+94 → 48m+47 → 144m+142 → 72m+71 → 216m+214 → 108m+107 → 324m+322 → 162m+161 → 486m+484 → 243m+242, which may be even or odd depending on m.

So the counterexample must have n god 32 ∈ {7, 15, 27, 31}.

This got me excited, so I created an account on this forum to follow up on your line of reasoning. I wrote a short program to automate it, and got this:

16: 3 inconclusive (1 out of 5.333)
32: 4 inconclusive (1 out of 8.000)
64: 8 inconclusive (1 out of 8.000)
128: 13 inconclusive (1 out of 9.846)
256: 19 inconclusive (1 out of 13.474)
512: 38 inconclusive (1 out of 13.474)
1024: 64 inconclusive (1 out of 16.000)
2048: 128 inconclusive (1 out of 16.000)
4096: 226 inconclusive (1 out of 18.124)
8192: 367 inconclusive (1 out of 22.322)
16384: 734 inconclusive (1 out of 22.322)
32768: 1295 inconclusive (1 out of 25.303)
65536: 2114 inconclusive (1 out of 31.001)
131072: 4228 inconclusive (1 out of 31.001)
262144: 7495 inconclusive (1 out of 34.976)
524288: 14990 inconclusive (1 out of 34.976)
1048576: 27328 inconclusive (1 out of 38.370)
2097152: 46611 inconclusive (1 out of 44.993)
4194304: 93222 inconclusive (1 out of 44.993)
8388608: 168807 inconclusive (1 out of 49.693)
16777216: 286581 inconclusive (1 out of 58.543)
33554432: 573162 inconclusive (1 out of 58.543)
67108864: 1037374 inconclusive (1 out of 64.691)
134217728: 1762293 inconclusive (1 out of 76.161)
268435456: 3524586 inconclusive (1 out of 76.161)
536870912: 6385637 inconclusive (1 out of 84.075)
1073741824: 12771274 inconclusive (1 out of 84.075)
2147483648: 23642078 inconclusive (1 out of 90.833)
4294967296: 41347483 inconclusive (1 out of 103.875)
8589934592: 82694966 inconclusive (1 out of 103.875)
17179869184: 151917636 inconclusive (1 out of 113.087)
34359738368: 263841377 inconclusive (1 out of 130.229)
68719476736: 527682754 inconclusive (1 out of 130.229)
137438953472: 967378591 inconclusive (1 out of 142.074)
274877906944: 1934757182 inconclusive (1 out of 142.074)

At the final step there, all but 967378591 values of k can be eliminated from the form n=137438953472m+k.

Running single-threaded on my E8400, it reached 4294967296 (2^32) in 11 seconds, taking only 135 more seconds to get to 2^36 and promptly run out of RAM. Running on swapfile memory it finished 2^37 (taking several minutes) and then 2^38 (taking over an hour due to heavy swapfile use, and not even weeding out any values) and then ran out of memory. I'll have to optimize my program if I want it to keep going. My code is currently quite simple and uses a dynamically reallocated array of 64-bit unsigned ints to store the addends (values of k). With some simple compression on the array of addends it'll probably be able to stay entirely within RAM for much longer.

There's probably lots more optimizations that can be done to this algorithm, but I don't think it would help in reaching or going beyond 2^60, let alone 2^71. With the current algorithm, completing each consecutive power of two takes about 1.95 times as long as the previous one. Extrapolating, even at the pure RAM speed with quad cores it would take 24 years to finish all the steps up to 2^60 — and even with good compression, I estimate the data set at that point would take up 2 petabytes. (So at 2^44 or so, it would have to stop weeding out values of k and just apply the ones it'd already found.)

could you give me a list of the possible counter-examples in Mod 8192? I don't really know how to program and I was trying to do it by hand.

by the way, there is no point where there are no exceptions because when you go up a power of 2 each exception splits into two possible exceptions with one going up on the last step and one going down

TimeHorse
Posts: 4
Joined: Thu Oct 23, 2008 2:22 pm UTC

### Re: 0710: "Collatz Conjecture"

First off, I don't think the curve will necessarily involve elliptic curves to solve like the Wiles proof of Fermat's Last Theorem, but I do firmly believe that it will take some very esoteric maths and perhaps even some element of graph/set theory to prove or disprove the Collatz Conjecture and such a proof is at least well beyond my ability. Since the problem is essentially Diophantine, I think it will follow a similar trajectory, though I favor an overall proof by contradiction as most likely. For example, assume a cycle besides 1->4->2->1 exists, then show that such an assumption is contradictory.

Second of all, no-one has mentioned that in addition to brute-force techniques up to [imath]5 \times 2^{60}[/imath], a number of mathematicians have tried a large variety of algebraic solutions for cycles of the form:

UD: [imath]\frac{3 n + 1}{2} = n[/imath] -> n = -1
UDD: [imath]\frac{3 n + 1}{4} = n[/imath] -> n = 1
UUD: Impossible (D always follows U since U produces an even number)
UDDD: [imath]\frac{3 n + 1}{8} = n[/imath] -> No solution
UDUD: [imath]\frac{3 \frac{3 n + 1}{2} + 1}{2} = n = \frac{9 n + 3 + 2}{4} = \frac{9 n + 5}{4}[/imath] -> n = -1
etc.

One can apply as many U and D to the starting number as necessary to get the resultant number to be the same as the start and IIRC it's been proven that if there is another positive chain, it must be very long. But there's no proof that that very long chain does not exist.

And finally, for Lothar Collatz's 100th birthday, which was a few months ago, I started writing this algorithm in Objective-C (nope, no-one posted it in Objective-C yet, though +5 for the C++/MPL implementation; that was way cool!) for my first iPhone App; the first pass was rejected but it gives me time to embed a link to xkcd in the next version thanks to this wonderful little comic of Randall's!

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: 0710: "Collatz Conjecture"

A number going up n amount of times must be (2^n)-1 mod 2^n so there is no number that goes up an infinite amount of times (unless you include -1, of course)

alexriehl
Posts: 127
Joined: Wed Sep 22, 2010 1:19 am UTC
Location: Auburn, AL
Contact:

### Re: "Collatz Conjecture" Discussion

s0merand0mdude wrote:Oddly enough, my geometry class spent yesterday and today working on calculator programs on the TI-83 and TI-84. Here's a quick program I made after seeing this comic to test the conjecture using a given number.

Spoiler:

Code: Select all

PROGRAM:COLLATZ:Disp "ENTER A NUMBER":Input N:0→I:Lbl 3:While N=int(N):While N≠1:I+1→I:If N/2=int(N/2):Then:Disp N/2:N/2→N:Else:Disp 3*N+1:3*N+1→N:End:Goto 3:End:0.5→N:Disp "NUMBER OF STEPS":Disp I:End:
I probably didn't need that many "if-then-else" statements, but it was a fun program to write.

Spoiler:
Edit: If you add I+1→I after the second ":Else" and put ":Disp "NUMBER OF STEPS",:Disp I", you can even count the number of steps used to get to 1. Although, you probably would need to put 0→I before the ":Lbl 3" to make sure you don't carry over any values of I previously used.

Edit 2: After a quick read of the manual and some outside-of-the-box thinking, I removed all the goto's except for the one causing the main loop. 3: Using one more While loop, I got rid of all the goto's and now the program runs much much faster, especially when there are many steps
.

Damnit. I tried this with 5. It completed and immediately went into a loop that crashed my calculator and cleared RAM. Luckily all the important programs were grouped, but I lost some good stuff.
Spoiler:

DavidSpencer
Posts: 64
Joined: Mon Jan 24, 2011 10:04 pm UTC

### Re: "Collatz Conjecture" Discussion

Random832 wrote:Has anyone else noticed the lengths of sequences tend to clump together?

I looked at this a couple of years ago. I don't remember everything clearly, but I think it has to do with the fact that (3n+1)/2 is very close to 3(n/2)+1 - the second is always 1/2 greater because the one isn't halved. If memory serves, series of numbers near each other often converge towards the same number because of the placements of those halves. I looked at the binary strings of their sequences with "1" representing 3n+1 and "0" representing n/2 and, sure enough, the 1s clumped themselves closer and closer to the beginning of the strings as the numbers increased.

bigjeff5
Posts: 127
Joined: Tue Nov 10, 2009 3:59 am UTC

### Re: 0710: "Collatz Conjecture"

pscottdv wrote:
Nevvy wrote:Would it be possible to prove this statistically? Any odd n will go through (3n+1)/2. Any even n has a 50/50 shot at becoming another even n.

After a certain point the +1 becomes insignificant and you have a 50/50 chance between n*1.5 and n*.5. Since 1.5 * .5 is .75 over a long enough timeline n will reduce to the point where the +1 becomes significant, and at some point in there I become lost.

I think the problem with this is that there are infinite natural numbers, so even if you proved that there is a zero probability, it doesn't prove that there isn't some small group of numbers that don't converge to 1.

Just nitpicking about probabilities here, but if you've proved that there is zero probability that a group of numbers don't converge to 1 then you've proved that there isn't some small group of numbers that don't converge to 1. That's what zero probability means. If you cannot prove that there isn't some small group of numbers that don't converge to 1, then your probability must be something greater than zero, even if it is incredibly small.

I think what you meant to say is that you cannot prove a zero probability statistically, because to do so would require running through an infinite set of numbers and an infinite set of numbers by definition does not end.

Furthermore, thanks to what infinity does to probability, even though Collatz Conjecture has held up through ~5x10^18 integers and shows no signs of failing, the probability of it actually being true is still infinitely close to zero without actually being zero, because ~5x10^18 is no closer to infinity than 1 is. Really, the only way that ever changes is if someone comes up with an inductive proof that it is true or false, or someone finds a number that loops, proving it false. Finding a number that ascends to infinity would technically prove it false as well, but it would itself be impossible to prove an infinitely ascending number (again, thanks to what infinity does to probability, the odds that any such number will continue to infinity is infinitely close to, but not equal to, zero).

The take away is that, assuming that no inductive proof will be found* and despite a complete lack of failure since the pattern's discovery 70+ years ago, any smart betting man still bets that the Collatz Conjecture is false.

*This actually flips the probability calculation the other way. Given an infinite amount of time the probability that someone will prove it inductively moves infinitely close to 1. Even given a few billion years, however, the probability is still pretty close to 1 that a proof will be found. However, if we bound the probability to a reasonable amount of time for any betting man - say 50 years or so - then the probability that a proof will be found drops back down towards 0, though nowhere near as low as the probability of not falsifying it via calculation. In any case, inductive proof seems to be the usual way these types of infinite problems are solved.

scarletmanuka
Posts: 533
Joined: Wed Oct 17, 2007 4:29 am UTC
Location: Perth, Western Australia

### Re: 0710: "Collatz Conjecture"

bigjeff5 wrote:Just nitpicking about probabilities here, but if you've proved that there is zero probability that a group of numbers don't converge to 1 then you've proved that there isn't some small group of numbers that don't converge to 1. That's what zero probability means.

Zero probability means that as the number of trials conducted tends to infinity, the proportion satisfying that condition tends to 0. It does not mean that the condition cannot be satisfied. Pick a real number uniformly randomly from the interval [0, 1]. The probability that it is, say, 1/2 is zero. That doesn't mean there's no choice of number that gives you 1/2. The probability of getting any specific number is zero, but you must get some particular number every time you do it.

Now in this case, we're only talking about positive integers and there are only countably many of them. So we can't select integers to try with a uniform distribution. We can specify some pmf where the probability is strictly positive for all positive integers, for instance P(n) = 2^(-n). Then each integer is chosen with a certain positive probability, and in this case a zero probability of a successful result would indicate that there is no successful integer.

However, the OP isn't following this approach but seems to be thinking about some sort of asymptotic probability-like thing. It doesn't look to be a very promising method, though.

bigjeff5 wrote:Furthermore, thanks to what infinity does to probability, even though Collatz Conjecture has held up through ~5x10^18 integers and shows no signs of failing, the probability of it actually being true is still infinitely close to zero without actually being zero, because ~5x10^18 is no closer to infinity than 1 is.

This is essentially meaningless. What do you mean by the "probability" of the conjecture being true? Are you going to establish its truth or falsity a large number of times and see how many of those times it is determined to be true? You are not using the mathematical definition of probability here, and you don't seem to be using the natural version here ("what I think the odds are that it will eventually turn out to be true"). Saying "the probability of it actually being true is infinitely close to zero" seems to say that it is almost certainly false. I don't think you'll find many people who agree with you on that.

bigjeff5 wrote:Finding a number that ascends to infinity would technically prove it false as well, but it would itself be impossible to prove an infinitely ascending number

Sorry, you can't just assert that without proving it. There may be a method of proving that some specific number ascends to infinity. For instance, by proving a relationship between the n'th number and the (n+m)'th number in the sequence for some specific n and m, and showing that the n'th, (n+m)'th, (n+2m)'th, etc. numbers form an ascending sequence.

bigjeff5 wrote:The take away is that, assuming that no inductive proof will be found* and despite a complete lack of failure since the pattern's discovery 70+ years ago, any smart betting man still bets that the Collatz Conjecture is false.

I think you are in the minority there. For instance, according to the fount of all knowledge:
Wikipedia wrote:Although the conjecture has not been proven, most mathematicians who have looked into the problem think the conjecture is true because experimental evidence and heuristic arguments support it.

Does the smart betting man really bet against the majority opinion of the experts in the field? If so, I have a bridge I want to sell you. Most of the experts in the field think the bridge doesn't exist, but as a smart betting man I'm sure you can see that the probability that it is real is infinitely close to 1.

Posts: 34
Joined: Thu Jun 10, 2010 10:56 pm UTC

### Re: 0710: "Collatz Conjecture"

What if you could prove that all numbers eventually converge to an integer of the form $\frac{2^n - 1}{3}$ ?

All such integers are odd from my experience, meaning the 3n+1 algorithm is applied, leaving a power of 2, which converges to 1.

scarletmanuka
Posts: 533
Joined: Wed Oct 17, 2007 4:29 am UTC
Location: Perth, Western Australia

### Re: 0710: "Collatz Conjecture"

Assuming that you mean "all numbers except powers of 2", then yes, that would certainly work, because it's equivalent to the Collatz Conjecture itself.

For any number that reaches 1, reversing the chain will give us a sequence of powers of 2 (possibly only the number 1), optionally followed by a number of the form you suggest, optionally followed by more numbers. So the Collatz Conjecture implies that any number that isn't a power of 2 will reach a number of this form. And the reverse implication is trivial as you point out. So you've basically found a more cumbersome way of stating the Collatz Conjecture.

Cranica
Posts: 42
Joined: Thu Sep 18, 2008 1:58 am UTC

### Re: 0710: "Collatz Conjecture"

alreadytaken4536 wrote:What if you could prove that all numbers eventually converge to an integer of the form $\frac{2^n - 1}{3}$ ?

All such integers are odd from my experience, meaning the 3n+1 algorithm is applied, leaving a power of 2, which converges to 1.

Your experience is correct (2^n - 1 is always odd, and so is (2^n - 1)/3 for n even [it's not an integer otherwise]), but that statement is equivalent to the conjecture to begin with.

gerbe1
Posts: 1
Joined: Wed Aug 31, 2011 5:44 am UTC

### Re: 0710: "Collatz Conjecture"

The cartoon created here was referenced in my recent QCS test in Queensland Australia. It was question one. I don't know if the author of the comic will consider it an achievement and I am unsure whether or not to be angry or to congratulate them. I just thought that for a test for the final year of senior high school state wide, referencing Xkcd was hilarious. In the words of Proff. Quirrel: "Thought you oughta know."

The test this year was sat by 30 000 students.

Posts: 1
Joined: Wed Aug 31, 2011 8:51 am UTC

### Re: 0710: "Collatz Conjecture"

gerbe1 wrote:The cartoon created here was referenced in my recent QCS test in Queensland Australia. It was question one. I don't know if the author of the comic will consider it an achievement and I am unsure whether or not to be angry or to congratulate them. I just thought that for a test for the final year of senior high school state wide, referencing Xkcd was hilarious. In the words of Proff. Quirrel: "Thought you oughta know."

The test this year was sat by 30 000 students.

I joined up on the xkcd forum with the sole purpose of posting a comment about this; I'm happy to see I'm not the only year 12 xkcd fan in Queensland. The cartoon was in the short response component of the exam for anyone who's curious, and I think the folk who design the exam need to use thicker paper for the front - after all the effort they go through to make sure nobody knows what's in the exam until the students are instructed to open it, it was rather easy for you to see through the cover sheet. I spent a good ten minutes staring at it thinking "That slightly egg-like head crouched over the desk looks an awful lot like an xkcd head", rather than listening to the instructions for the exam.

Anyway, my little ramble is over, good to see the QCST had a sense of humour.
Last edited by Admiral Bacon on Thu Sep 01, 2011 10:00 am UTC, edited 1 time in total.

GreenStormElf
Posts: 27
Joined: Sat Aug 22, 2009 1:21 am UTC

### Re: 0710: "Collatz Conjecture"

I also just did the QCS paper. However, I was annoyed by the incorrect capitalisation of "Xkcd" in the acknowledgements, and I sent the QSA an email to complain.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: "Collatz Conjecture" Discussion

Dan04 wrote:Breaking it down one step further, n mod 16 ∈ {7, 11, 15} is equivalent to n mod 32 ∈ {7, 11, 15, 23, 27, 31} .

• n = 32m+7 → 96m+22 → 48m+11 → 144m+34 → 72m+17 → 216m+52 → 108m+26 → 54m+13 → 162m+40 → 81m+20, which may be even or odd depending on m.
• n = 32m+11 → 96m+34 → 48m+17 → 144m+52 → 72m+26 → 36m+13 → 108m+40 → 54m+20 → 27m+10, which is always less than n.
• n = 32m+15 → 96m+46 → 48m+23 → 144m+70 → 72m+35 → 216m+106 → 108m+53 → 324m+160 → 162m+80 → 81m+40, which may be even or odd depending on m.
• n = 32m+23 → 96m+70 → 48m+35 → 144m+106 → 72m+53 → 216m+160 → 108m+80 → 54m+40 → 27m+20, which is always less than n.
• n = 32m+27 → 96m+82 → 48m+41 → 144m+124 → 72m+62 → 36m+31 → 108m+94 → 54m+47 → 162m+142 → 81m+71, which may be even or odd depending on m.
• n = 32m+31 → 96m+94 → 48m+47 → 144m+142 → 72m+71 → 216m+214 → 108m+107 → 324m+322 → 162m+161 → 486m+484 → 243m+242, which may be even or odd depending on m.

So the counterexample must have n mod 32 ∈ {7, 15, 27, 31}.

This got me excited, so I created an account on this forum to follow up on your line of reasoning. I wrote a short program to automate it, and got this:

16: 3 inconclusive (1 out of 5.333)
32: 4 inconclusive (1 out of 8.000)
64: 8 inconclusive (1 out of 8.000)
128: 13 inconclusive (1 out of 9.846)
256: 19 inconclusive (1 out of 13.474)
512: 38 inconclusive (1 out of 13.474)
1024: 64 inconclusive (1 out of 16.000)
2048: 128 inconclusive (1 out of 16.000)
4096: 226 inconclusive (1 out of 18.124)
8192: 367 inconclusive (1 out of 22.322)
16384: 734 inconclusive (1 out of 22.322)
32768: 1295 inconclusive (1 out of 25.303)
65536: 2114 inconclusive (1 out of 31.001)
131072: 4228 inconclusive (1 out of 31.001)
262144: 7495 inconclusive (1 out of 34.976)
524288: 14990 inconclusive (1 out of 34.976)
1048576: 27328 inconclusive (1 out of 38.370)
2097152: 46611 inconclusive (1 out of 44.993)
4194304: 93222 inconclusive (1 out of 44.993)
8388608: 168807 inconclusive (1 out of 49.693)
16777216: 286581 inconclusive (1 out of 58.543)
33554432: 573162 inconclusive (1 out of 58.543)
67108864: 1037374 inconclusive (1 out of 64.691)
134217728: 1762293 inconclusive (1 out of 76.161)
268435456: 3524586 inconclusive (1 out of 76.161)
536870912: 6385637 inconclusive (1 out of 84.075)
1073741824: 12771274 inconclusive (1 out of 84.075)
2147483648: 23642078 inconclusive (1 out of 90.833)
4294967296: 41347483 inconclusive (1 out of 103.875)
8589934592: 82694966 inconclusive (1 out of 103.875)
17179869184: 151917636 inconclusive (1 out of 113.087)
34359738368: 263841377 inconclusive (1 out of 130.229)
68719476736: 527682754 inconclusive (1 out of 130.229)
137438953472: 967378591 inconclusive (1 out of 142.074)
274877906944: 1934757182 inconclusive (1 out of 142.074)

At the final step there, all but 967378591 values of k can be eliminated from the form n=137438953472m+k.

Running single-threaded on my E8400, it reached 4294967296 (2^32) in 11 seconds, taking only 135 more seconds to get to 2^36 and promptly run out of RAM. Running on swapfile memory it finished 2^37 (taking several minutes) and then 2^38 (taking over an hour due to heavy swapfile use, and not even weeding out any values) and then ran out of memory. I'll have to optimize my program if I want it to keep going. My code is currently quite simple and uses a dynamically reallocated array of 64-bit unsigned ints to store the addends (values of k). With some simple compression on the array of addends it'll probably be able to stay entirely within RAM for much longer.

There's probably lots more optimizations that can be done to this algorithm, but I don't think it would help in reaching or going beyond 2^60, let alone 2^71. With the current algorithm, completing each consecutive power of two takes about 1.95 times as long as the previous one. Extrapolating, even at the pure RAM speed with quad cores it would take 24 years to finish all the steps up to 2^60 — and even with good compression, I estimate the data set at that point would take up 2 petabytes. (So at 2^44 or so, it would have to stop weeding out values of k and just apply the ones it'd already found.)

You can actually eliminate a lot more numbers by considering the cases where two collatz series converge to the same value, for example:
64n+15->96n+23->144n+35->216n+53->324n+80->162n+40->81n+20, but:
32n+7->48n+11->72n+17->108n+26->54n+13->81n+20 which is the same. Therefore a number of the form 64n+15 cannot be the lowest counter-example, and that takes a whole lot of examples off of higher moduli. Also, numbers of the form 4xn+4x-1-1, and 2*4xn+2*4x-2*4x-1-1 cannot be the lowest counter-examples. This should shorten your list by quite a bit.
My list of 1049 inconclusive values mod 32768 is below:
Spoiler:
27,31,47,71,91,103,111,155,159,167,239,251,283,327,359,447,487,495,511,559,603,639,667,671,703,743,751,763,767,795,859,871,927,959,1007
1051,1055,1115,1127,1179,1183,1255,1263,1307,1351,1383,1439,1471,1511,1519,1583,1627,1639,1663,1691,1695,1767,1791,1819,1863,1883,1895,1951
1959,2043,2047,2139,2151,2159,2175,2207,2215,2287,2375,2407,2459,2463,2495,2535,2543,2559,2651,2671,2687,2715,2751,2791,2811,2815,2843,2887
2919,2927,3007,3055,3071,3099,3103,3175,3183,3199,3227,3231,3239,3263,3311,3323,3355,3375,3399,3431,3487,3519,3567,3615,3631,3695,3711,3739
3751,3775,3815,3823,3839,3867,3871,3931,3943,3951,3999,4123,4127,4143,4167,4207,4255,4263,4335,4347,4379,4399,4423,4511,4543,4583,4591,4607
4635,4639,4699,4719,4735,4763,4767,4775,4799,4839,4847,4863,4891,4895,4935,4967,5055,5147,5151,5167,5211,5223,5247,5279,5287,5351,5359,5403
5423,5447,5479,5535,5567,5659,5663,5679,5735,5759,5791,5823,5863,5887,5915,5991,5999,6055,6079,6139,6171,6191,6235,6247,6271,6303,6311,6383
6395,6427,6471,6555,6591,6639,6655,6703,6767,6811,6823,6847,6887,6895,6911,6939,6943,7015,7103,7151,7167,7195,7271,7279,7295,7323,7327,7335
7359,7407,7419,7451,7471,7527,7579,7583,7615,7663,7707,7711,7727,7807,7835,7839,7871,7919,7931,7935,7963,8027,8039,8095,8127,8175,8191,8219
8223,8239,8263,8283,8295,8303,8319,8351,8359,8443,8475,8519,8551,8603,8607,8639,8679,8687,8703,8751,8831,8859,8863,8895,8935,8943,8955,8959
8987,9031,9063,9119,9151,9199,9243,9247,9287,9307,9319,9343,9447,9455,9467,9499,9543,9575,9631,9663,9703,9775,9819,9831,9855,9883,9887,9967
9983,10011,10087,10095,10143,10151,10235,10239,10311,10331,10343,10351,10367,10399,10407,10471,10479,10491,10567,10599,10651,10687,10727
10751,10843,10879,10907,10911,10919,10943,10983,10991,11003,11007,11035,11039,11111,11175,11199,11247,11263,11291,11295,11355,11367,11375
11391,11419,11423,11431,11455,11495,11503,11515,11547,11591,11623,11711,11759,11803,11823,11887,11903,11931,11935,12007,12015,12031,12059
12123,12135,12191,12199,12223,12287,12315,12319,12335,12359,12379,12399,12447,12455,12479,12527,12539,12591,12615,12703,12735,12775,12783
12799,12831,12847,12891,12911,12927,12955,12959,12991,13031,13039,13055,13083,13127,13159,13247,13339,13343,13359,13403,13415,13423,13439
13471,13479,13503,13543,13551,13595,13615,13639,13671,13727,13759,13855,13871,13927,13951,13983,14015,14055,14079,14107,14183,14191,14247
14331,14363,14367,14383,14427,14447,14463,14495,14503,14575,14587,14619,14663,14695,14747,14783,14831,14847,14951,14959,14975,15003,15015
15039,15079,15087,15099,15103,15131,15135,15207,15355,15359,15387,15391,15463,15471,15487,15515,15519,15527,15551,15599,15611,15643,15663
15719,15771,15775,15807,15855,15899,15903,15975,15999,16031,16063,16111,16127,16155,16219,16231,16319,16367,16379,16383,16411,16415,16431
16455,16475,16487,16495,16511,16539,16543,16551,16623,16635,16667,16711,16795,16799,16831,16879,16895,16943,16987,17023,17051,17055,17087
17127,17135,17151,17179,17223,17243,17255,17311,17343,17391,17435,17439,17479,17499,17511,17535,17563,17567,17639,17647,17659,17691,17823
17855,17895,17903,17967,18023,18047,18075,18079,18151,18159,18175,18203,18247,18267,18279,18287,18335,18343,18427,18431,18503,18523,18535
18543,18559,18591,18599,18663,18671,18683,18759,18791,18843,18847,18879,18919,18927,18943,19055,19071,19099,19103,19111,19135,19175,19183
19195,19227,19231,19271,19303,19311,19367,19391,19439,19455,19483,19487,19547,19559,19567,19583,19611,19615,19647,19687,19695,19707,19739
19759,19783,19815,19871,19903,19951,19995,19999,20015,20095,20123,20127,20135,20159,20207,20223,20251,20255,20315,20327,20335,20383,20391
20415,20511,20551,20571,20591,20639,20647,20671,20719,20731,20763,20807,20895,20967,20975,20991,21019,21039,21083,21119,21147,21151,21159
21183,21231,21247,21275,21279,21319,21351,21439,21531,21535,21551,21595,21607,21615,21631,21663,21671,21695,21735,21743,21787,21831,21863
21919,21951,22043,22063,22119,22143,22175,22247,22271,22299,22375,22383,22439,22463,22523,22555,22559,22575,22619,22631,22639,22687,22695
22767,22779,22855,22887,22975,23023,23039,23087,23143,23151,23167,23195,23207,23271,23279,23291,23295,23323,23327,23487,23535,23547,23551
23579,23583,23655,23663,23679,23707,23711,23719,23743,23791,23855,23911,23963,23967,23999,24047,24091,24095,24111,24167,24191,24219,24223
24255,24315,24319,24347,24411,24423,24479,24511,24571,24603,24607,24623,24667,24687,24703,24731,24735,24743,24815,24827,24859,24903,24935
24987,24991,25023,25063,25071,25087,25135,25179,25215,25243,25279,25319,25327,25339,25343,25371,25415,25435,25447,25535,25627,25631,25671
25727,25755,25759,25839,25851,25883,25927,25959,26015,26047,26095,26159,26203,26215,26239,26271,26343,26351,26367,26395,26439,26459,26471
26479,26619,26623,26695,26715,26727,26735,26751,26783,26791,26855,26863,26875,26951,26983,27035,27039,27071,27119,27135,27227,27247,27263
27295,27303,27327,27367,27375,27387,27391,27419,27423,27463,27495,27503,27559,27583,27631,27647,27675,27679,27739,27751,27775,27803,27807
27815,27879,27887,27899,27931,27951,28007,28063,28095,28143,28187,28191,28207,28271,28287,28315,28319,28327,28351,28391,28399,28415,28443
28447,28507,28519,28527,28575,28583,28607,28671,28699,28719,28743,28763,28783,28831,28839,28863,28911,28923,28955,28975,29087,29119,29159
29167,29183,29211,29215,29231,29275,29295,29311,29339,29343,29351,29375,29415,29423,29439,29471,29511,29543,29631,29723,29727,29787,29799
29807,29823,29855,29887,29927,29935,29979,29999,30023,30055,30111,30143,30235,30239,30255,30335,30367,30399,30439,30463,30491,30567,30575
30631,30655,30751,30811,30823,30831,30847,30879,30959,30971,31003,31047,31079,31131,31167,31215,31231,31279,31335,31343,31359,31387,31399
31423,31463,31471,31483,31487,31515,31519,31591,31679,31727,31739,31743,31775,31847,31855,31871,31903,31911,31935,31983,31995,32027,32047
32103,32159,32191,32283,32287,32303,32359,32383,32411,32415,32447,32495,32507,32511,32539,32615,32671,32703,32751,32763,32767 Sorry, its a bit messy.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.