3n+1. a.k.a. The Collatz Conjecture.

[storm5510]

I stumbled across this video on YouTube. It is an interesting watch. It has been tested to 2⁶⁸ with no resolution. Some say there might be a solution while others say no. Some have spent years on it. Many see it as a waste of time.

[science_man_88]

We do have restrictions on minimum element of a loop 3 mod 4 but not 3 mod 16 for example .

[science_man_88]

Collatz(n)=my(a=Vec(n));if(a[2]%2,a=3*a;a[2]=a[2]+1,a=a/2);print(a)

might be helpful.

[mathwiz]

Originally Posted by storm5510

Some say there might be a solution while others say no.

I don't understand this statement.

The conjecture is either true (every starting integer ultimately ends at 1), or false (there exists at least one positive integer that never converges to 1).

The relevant question is: is modern mathematics capable of proving or disproving the conjecture?

[science_man_88]

Originally Posted by mathwiz

The relevant question is: is modern mathematics capable of proving or disproving the conjecture?

https://en.m.wikipedia.org/wiki/Decidability_(logic)

[Reed_Young]

Originally Posted by mathwiz

The relevant question is: is modern mathematics capable of proving or disproving the conjecture?

Considering the multitude of starting integers that have already been shown to reach 1, my question is, "why does modern mathematics have so much trouble describing why the conjecture is true, sufficiently to meet the standards of a proof in formal mathematics?"

In other words, with so many specific cases already demonstrated, the fact that nobody has found a pattern on which to construct a good, old-fashioned proof by induction implies that the proof, if/when one is produced, will probably also have to introduce one or more fundamentally new tools to mathematicians' basic tool kits, or at the very least, use the standard took kit in a very unexpected manner.

[science_man_88]

I don't see what's complicated:



Algebra seems the way forward no ?

[LaurV]

Originally Posted by science_man_88

I don't see what's complicated:

Maybe your post is sarcastic and we don't catch it, but that is how they "proved" it to 2^68 (currently, it may be much larger, I assume 2^75 or so). You don't imagine they tested so many numbers, do you? 2^68 is 295'147'905'179'352'825'856. Even testing a million sequences per second (which is impossible, some sequences need days, and few need weeks to be tested) and using 10 thousand computers, you would still need about 900 years to go to 2^68.
The way they "proved" it is just like that: assume there is a smallest number which never converge to 1, let's cal it s, or "seed" and let's see what this number can be.
It can not be even. If s is even, i.e. s=2k, then in the next step you get s/2=k, a smaller number, so my seed was not the smallest.
So, it is odd, i.e. s=2k+1
You continue to split k.
If k is even (renaming it), s=4k+1, then next step you have 12k+4, which in 2 more steps is reduced to 3k+1, which is smaller than initial s, so my seed can't be 4k+1.
So, it is s=4k+3. Note that I already eliminated 75% of the numbers, those which are 0, 1, or 2 (mod 4).
Then s goes to 4k+3 -> 12k+10 -> 6k+5 -> 18k+16 -> 9k+8.
This last one, you don't know if it is even or odd, so you need to split k again, into odd, or even. So, if k=2t, your initial s was 8t+3, and if k was 2t+1, your initial seed was 4*(2t+1)+3=8t+7. In first case, you reached 18t+8 which splits again to 9t+4, still unclear, split again, rename to k (to save variables ) you start with 16k+3 and end with 18t+4, which goes to 9t+2, which is smaller. Similar for the second case.
Note that now you eliminated all numbers which are 0, 2, 4, 6, 8, 10, 12, 14 (mod 16) with the 2-split, then 1, 5, 9, 13 (mod 16), from the 4-split, (the 8-split eliminates nothing), and 3 (mod 16) from the 16 split.
So, you only have left the cases 7, 11, and 15 (mod 16).
When you move to (mod32), you will have to test only cases 7, 7+16=23, 11, 11+16=27, 15, 15+16=31.
From the 7 and 11 only one of each survives, and from 15 both survives. So, there are 4 cases in 32.
Moving to 64 brings no reduction, you have the 8 cases, but then, moving to 128 cuts out another 3 cases, so you have 13 left from 128.

s = 16k+0 → 8k+0 (smaller)
s = 16k+1 → 48k+4 → 24k+2 → 12k+1 (smaller)
s = 16k+2 → 8k+1 (smaller)
s = 16k+3 → 48k+10 → 24k+5 → 72k+16 → 36k+8 → 18k+4 → 9k+2 (smaller)
s = 16k+4 → 8k+2 (smaller)
s = 16k+5 → 48k+16 → 24k+8 → 12k+4 (smaller) → 6k+2 → 3k+1, (much smaller :P )
s = 16k+6 → 8k+3 (smaller)
s = 16k+7 → 48k+22 → 24k+11 → 72k+34 → 36k+17 → 108k+52 → 54k+26 → 27k+13 (undecided, needs more split)
s = 16k+8 → 8k+4 (smaller)
s = 16k+9 → 48k+28 → 24k+14 → 12k+7 (smaller)
s = 16k+10 → 8k+5 (smaller)
s = 16k+11 → 48k+34 → 24k+17 → 72k+52 → 36k+26 → 18k+13 → 54k+40 → 27k+20 (undecided, needs more split)
s = 16k+12 → 8k+6 (smaller)
s = 16k+13 → 48k+40 → 24k+20 → 12k+10 (smaller) → 6k+5, (even smaller)
s = 16k+14 → 8k+7 (smaller)
s = 16k+15 → 48k+46 → 24k+23 → 72k+70 → 36k+35 → 108k+106 → 54k+53 → 162k+160 → 81k+80 (undecided, needs more split)

s = 32k+7 → 96k+22 → 48k+11 → 144k+34 → 72k+17 → 216k+52 → 108k+26 → 54k+13 → 162k+40 → 81k+20 → Undecided, finer splitting is needed.
s = 32k+23 → 96k+70 → 48k+35 → 144k+106 → 72k+53 → 216k+160 → 108k+80 → 54k+40 → 27k+20 → Smaller. Proved. This case is closed.
s = 32k+11 → 96k+34 → 48k+17 → 144k+52 → 72k+26 → 36k+13 → 108k+40 → 54k+20 → 27k+10 → Smaller. Proved. This case is closed.
s = 32k+27 → 96k+82 → 48k+41 → 144k+124 → 72k+62 → 36k+31 → 108k+94 → 54k+47 → 162k+142 → 81k+71 → Undecided, finer splitting is needed.
s = 32k+15 → 96k+46 → 48k+23 → 144k+70 → 72k+35 → 216k+106 → 108k+53 → 324k+160 → 162k+80 → 81k+40 → Undecided, finer splitting is needed.
s = 32k+31 → 96k+94 → 48k+47 → 144k+142 → 72k+71 → 216k+214 → 108k+107 → 324k+322 → 162k+161 → 486k+484 → 243k+242 → Undecided, finer splitting is needed.

s = 64k+7 → 192k+22 → 96k+11 → 288k+34 → 144k+17 → 432k+52 → 216k+26 → 108k+13 → 324k+40 → 162k+20 → 81k+10 → Undecided, finer splitting is needed.
s = 64k+39 → 192k+118 → 96k+59 → 288k+178 → 144k+89 → 432k+268 → 216k+134 → 108k+67 → 324k+202 → 162k+101 → 486k+304 → 243k+152 → Undecided, finer splitting is needed.
s = 64k+27 → 192k+82 → 96k+41 → 288k+124 → 144k+62 → 72k+31 → 216k+94 → 108k+47 → 324k+142 → 162k+71 → 486k+214 → 243k+107 → Undecided, finer splitting is needed.
s = 64k+59 → 192k+178 → 96k+89 → 288k+268 → 144k+134 → 72k+67 → 216k+202 → 108k+101 → 324k+304 → 162k+152 → 81k+76 → Undecided, finer splitting is needed.
s = 64k+15 → 192k+46 → 96k+23 → 288k+70 → 144k+35 → 432k+106 → 216k+53 → 648k+160 → 324k+80 → 162k+40 → 81k+20 → Undecided, finer splitting is needed.
s = 64k+47 → 192k+142 → 96k+71 → 288k+214 → 144k+107 → 432k+322 → 216k+161 → 648k+484 → 324k+242 → 162k+121 → 486k+364 → 243k+182 → Undecided, finer splitting is needed.
s = 64k+31 → 192k+94 → 96k+47 → 288k+142 → 144k+71 → 432k+214 → 216k+107 → 648k+322 → 324k+161 → 972k+484 → 486k+242 → 243k+121 → Undecided, finer splitting is needed.
s = 64k+63 → 192k+190 → 96k+95 → 288k+286 → 144k+143 → 432k+430 → 216k+215 → 648k+646 → 324k+323 → 972k+970 → 486k+485 → 1458k+1456 → 729k+728 → Undecided, finer splitting is needed.

s = 128k+7 → 384k+22 → 192k+11 → 576k+34 → 288k+17 → 864k+52 → 432k+26 → 216k+13 → 648k+40 → 324k+20 → 162k+10 → 81k+5 → Smaller. Proved. This case is closed.
s = 128k+71 → 384k+214 → 192k+107 → 576k+322 → 288k+161 → 864k+484 → 432k+242 → 216k+121 → 648k+364 → 324k+182 → 162k+91 → 486k+274 → 243k+137 → Undecided, finer splitting is needed.
s = 128k+39 → 384k+118 → 192k+59 → 576k+178 → 288k+89 → 864k+268 → 432k+134 → 216k+67 → 648k+202 → 324k+101 → 972k+304 → 486k+152 → 243k+76 → Undecided, finer splitting is needed.
s = 128k+103 → 384k+310 → 192k+155 → 576k+466 → 288k+233 → 864k+700 → 432k+350 → 216k+175 → 648k+526 → 324k+263 → 972k+790 → 486k+395 → 1458k+1186 → 729k+593 → Undecided, finer splitting is needed.
s = 128k+27 → 384k+82 → 192k+41 → 576k+124 → 288k+62 → 144k+31 → 432k+94 → 216k+47 → 648k+142 → 324k+71 → 972k+214 → 486k+107 → 1458k+322 → 729k+161 → Undecided, finer splitting is needed.
s = 128k+91 → 384k+274 → 192k+137 → 576k+412 → 288k+206 → 144k+103 → 432k+310 → 216k+155 → 648k+466 → 324k+233 → 972k+700 → 486k+350 → 243k+175 → Undecided, finer splitting is needed.
s = 128k+59 → 384k+178 → 192k+89 → 576k+268 → 288k+134 → 144k+67 → 432k+202 → 216k+101 → 648k+304 → 324k+152 → 162k+76 → 81k+38 → Smaller. Proved. This case is closed.
s = 128k+123 → 384k+370 → 192k+185 → 576k+556 → 288k+278 → 144k+139 → 432k+418 → 216k+209 → 648k+628 → 324k+314 → 162k+157 → 486k+472 → 243k+236 → Undecided, finer splitting is needed.
s = 128k+15 → 384k+46 → 192k+23 → 576k+70 → 288k+35 → 864k+106 → 432k+53 → 1296k+160 → 648k+80 → 324k+40 → 162k+20 → 81k+10 → Smaller. Proved. This case is closed.
s = 128k+79 → 384k+238 → 192k+119 → 576k+358 → 288k+179 → 864k+538 → 432k+269 → 1296k+808 → 648k+404 → 324k+202 → 162k+101 → 486k+304 → 243k+152 → Undecided, finer splitting is needed.
s = 128k+47 → 384k+142 → 192k+71 → 576k+214 → 288k+107 → 864k+322 → 432k+161 → 1296k+484 → 648k+242 → 324k+121 → 972k+364 → 486k+182 → 243k+91 → Undecided, finer splitting is needed.
s = 128k+111 → 384k+334 → 192k+167 → 576k+502 → 288k+251 → 864k+754 → 432k+377 → 1296k+1132 → 648k+566 → 324k+283 → 972k+850 → 486k+425 → 1458k+1276 → 729k+638 → Undecided, finer splitting is needed.
s = 128k+31 → 384k+94 → 192k+47 → 576k+142 → 288k+71 → 864k+214 → 432k+107 → 1296k+322 → 648k+161 → 1944k+484 → 972k+242 → 486k+121 → 1458k+364 → 729k+182 → Undecided, finer splitting is needed.
s = 128k+95 → 384k+286 → 192k+143 → 576k+430 → 288k+215 → 864k+646 → 432k+323 → 1296k+970 → 648k+485 → 1944k+1456 → 972k+728 → 486k+364 → 243k+182 → Undecided, finer splitting is needed.
s = 128k+63 → 384k+190 → 192k+95 → 576k+286 → 288k+143 → 864k+430 → 432k+215 → 1296k+646 → 648k+323 → 1944k+970 → 972k+485 → 2916k+1456 → 1458k+728 → 729k+364 → Undecided, finer splitting is needed.
s = 128k+127 → 384k+382 → 192k+191 → 576k+574 → 288k+287 → 864k+862 → 432k+431 → 1296k+1294 → 648k+647 → 1944k+1942 → 972k+971 → 2916k+2914 → 1458k+1457 → 4374k+4372 → 2187k+2186 → Undecided, finer splitting is needed.

And so on, doubling the power of two every time, you get to 2^68, and you will just have "few" remaining cases which you can test "deeper". Like for example, under 128=2^7, you only need to test 13 sequences, i.e. those starting with 27, 31, 39, 47, 63, 71, 79, 91, 95, 103, 111, 123, 127.
(and nope, I didn't do that by hand, I have a script done years ago).

[science_man_88]

Originally Posted by LaurV

Maybe your post is sarcastic and we don't catch it

guess I don't see why algebra alone couldn't finish most of them off 3 mod 16 came the fact that 6k+5 needs to be 5 modulo 8 to have more divisions by 2 to follow to lower the number itself .

[chalsall]

Originally Posted by science_man_88

guess I don't see why algebra alone couldn't finish most of them off 3 mod 16 came the fact that 6k+5 needs to be 5 modulo 8 to have more divisions by 2 to follow to lower the number itself .

Algebra is to Calculus as Chess is to Go.

[science_man_88]

Originally Posted by chalsall

Algebra is to Calculus as Chess is to Go.

Fair. I'm not good at either.