20221101, 16:30  #1 
Random Account
Aug 2009
Not U. + S.A.
17×149 Posts 
3n+1. a.k.a. The Collatz Conjecture.
I stumbled across this video on YouTube. It is an interesting watch. It has been tested to 2^{68} 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.

20221102, 13:23  #2 
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
We do have restrictions on minimum element of a loop 3 mod 4 but not 3 mod 16 for example .

20221102, 17:38  #3 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Code:
Collatz(n)=my(a=Vec(n));if(a[2]%2,a=3*a;a[2]=a[2]+1,a=a/2);print(a) 
20221102, 18:15  #4 
Mar 2019
327_{10} Posts 
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? 
20221102, 18:42  #5  
"Forget I exist"
Jul 2009
Dartmouth NS
20E2_{16} Posts 
Quote:


20221102, 21:52  #6  
"Reed Young"
Sep 2009
Oregon
11111_{2} Posts 
Quote:
In other words, with so many specific cases already demonstrated, the fact that nobody has found a pattern on which to construct a good, oldfashioned 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. 

20221102, 22:20  #7 
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
I don't see what's complicated:
Algebra seems the way forward no ? Last fiddled with by science_man_88 on 20221102 at 22:35 
20221104, 05:22  #8 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3·23·149 Posts 
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 2split, then 1, 5, 9, 13 (mod 16), from the 4split, (the 8split 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. Code:
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 nope, I didn't do that by hand, I have a script done years ago). Last fiddled with by LaurV on 20221104 at 05:29 
20221104, 13:56  #9 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 

20221104, 16:23  #10 
If I May
"Chris Halsall"
Sep 2002
Barbados
2B4B_{16} Posts 

20221104, 18:36  #11 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Collatz conjecture  RMLabrador  Miscellaneous Math  12  20221226 18:58 
Collatz Conjecture Proof  Steve One  Miscellaneous Math  21  20180308 08:18 
this thread is for a Collatz conjecture again  MattcAnderson  MattcAnderson  16  20180228 19:58 
Collatz conjecture  MattcAnderson  MattcAnderson  4  20170312 07:39 
Related to Collatz conjecture  nibble4bits  Math  1  20070804 07:09 