mersenneforum.org 3n+1. a.k.a. The Collatz Conjecture.
 Register FAQ Search Today's Posts Mark Forums Read

 2022-11-01, 16:30 #1 storm5510 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 268 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.
 2022-11-02, 13:23 #2 science_man_88     "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 .
 2022-11-02, 17:38 #3 science_man_88     "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) might be helpful.
2022-11-02, 18:15   #4
mathwiz

Mar 2019

32710 Posts

Quote:
 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?

2022-11-02, 18:42   #5
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

Quote:
 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)

2022-11-02, 21:52   #6
Reed_Young

"Reed Young"
Sep 2009
Oregon

111112 Posts

Quote:
 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.

 2022-11-02, 22:20 #7 science_man_88     "Forget I exist" Jul 2009 Dartmouth NS 2×3×23×61 Posts I don't see what's complicated: $2048x+1\mapsto 6144x+4\mapsto 3072x+2\mapsto 1536x+1$ $2048x+3\mapsto 6144x+10\mapsto 3072x+5$ $2048x+5\mapsto 6144x+16\mapsto 3072x+8\mapsto 1536x+4\mapsto 768x+2\mapsto 384x+1\mapsto 1152x+4\mapsto 576x+2\mapsto 288x+1\mapsto 864x+4\mapsto 432x+2\mapsto 216x+1\mapsto 648x+4\mapsto 324x+2\mapsto 162x+1\mapsto 486x+4\mapsto 243x+2$ Algebra seems the way forward no ? Last fiddled with by science_man_88 on 2022-11-02 at 22:35
2022-11-04, 05:22   #8
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3·23·149 Posts

Quote:
 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.
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 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).

Last fiddled with by LaurV on 2022-11-04 at 05:29

2022-11-04, 13:56   #9
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 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 .

2022-11-04, 16:23   #10
chalsall
If I May

"Chris Halsall"
Sep 2002

2B4B16 Posts

Quote:
 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.

2022-11-04, 18:36   #11
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by chalsall Algebra is to Calculus as Chess is to Go.
Fair. I'm not good at either.

 Similar Threads Thread Thread Starter Forum Replies Last Post RMLabrador Miscellaneous Math 12 2022-12-26 18:58 Steve One Miscellaneous Math 21 2018-03-08 08:18 MattcAnderson MattcAnderson 16 2018-02-28 19:58 MattcAnderson MattcAnderson 4 2017-03-12 07:39 nibble4bits Math 1 2007-08-04 07:09

All times are UTC. The time now is 20:33.

Fri Feb 3 20:33:19 UTC 2023 up 169 days, 18:01, 1 user, load averages: 1.50, 1.15, 1.02