Jump to content
Objectivism Online Forum

Collatz Conjecture might have been solved

Rate this topic


Recommended Posts

For anyone who doesn't know: the Collatz Conjecture is a conjecture stating that if you take any natural number, and if its even you divide it by two, and if it's odd you multiply it by three and add one, and if you keep doing this, you will get one, eventually. Example:

17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Wiki

The alleged proof is here in a pdf.

If this proof is accurate, then this would be a pretty huge deal. The problem has been around for quite a while, about 80 years. I think this is pretty exciting.

Link to comment
Share on other sites

This strikes me as something that you can't really "prove", it's just a matter of statistics. This conjecture is set up so that they will always be integers.

What has to happen, in order for this number to reach 1, is that there must be a result that is a natural power of 2. Statistically, that is bound to happen if we're to do this to infinity.

Link to comment
Share on other sites

This strikes me as something that you can't really "prove", it's just a matter of statistics. This conjecture is set up so that they will always be integers.

What has to happen, in order for this number to reach 1, is that there must be a result that is a natural power of 2. Statistically, that is bound to happen if we're to do this to infinity.

Well, one thing that could happen with a number is it would start looping. For example, we know it'll never work for -5 because it would go -5, -14, -7, -20, -10, -5, -14. Obviously it could never tend to 1 for a negative integer (what happens when it gets to -1? it just goes to -2), but perhaps something like this could happen with certain natural numbers.

Link to comment
Share on other sites

  • 4 weeks later...
  • 1 month later...

The author added the following to page two of his paper:

Author’s note:

The reasoning on p. 11, that “The set of all vertices (2n,l) in all levels will

contain all even numbers 2n ≥ 6 exactly once.” has turned out to be incomplete.

Thus, the statement “that the Collatz conjecture is true” has to be withdrawn,

at least temporarily.

June 17, 2011

Link to comment
Share on other sites

It wouldn’t have any obvious repercussions in engineering or science.

The problem is interesting for several reasons though. Setting aside proving it, the statement is so simple a child can understand it. It’s been tested or proved to be true for all numbers up to 17 * 2^58 – about 4,900,000,000,000,000,000 – so it’s almost certainly true. Yet people interested in such puzzles, and there a lot of smart people in that class, so far haven’t been able to prove it for any general number.

Bryan Thwaites, a British mathematician, has offered a £1000 reward for a proof.

Link to comment
Share on other sites

Yeah, I would prefer mathematicians spend less time doing this stuff and spent more time trying to see why this theory is applicable to something. People are frequently finding applications for stuff like this in number theory, so who knows what someone might find to do with this eventually. Offer someone £1000 for that instead and then maybe they will prove it while they are at it...

Link to comment
Share on other sites

  • 2 years later...

The Collatz Conjecture

 

The Collatz Conjecture is pretty straightforward. In 1937, Lothar Collatz proposed the following conjecture: Start with a positive integer n, then repeatedly iterate the following: If n is even, divide it by 2; if n is odd, compute 3*n+1. Collatz conjectured that for every starting value n, the result will invariably return to 1.

 

Cody T. Dianopoulos submitted on May 30, 2012 as part of his abstract:

 

"The first step in proving the Collatz Conjecture would be to evaluate what actually needs to be proven. The recursive function needs to be proven across all n∈N . Since any even numbers will just be divided by 2 enough times to transform into an odd number, this conjecture only needs to be proven for all odd natural numbers."

 

The first odd number encountered is 3.

 

3 x 3 + 1 = 10

10/2 = 5

5 x 3 + 1 = 16, which is 24

 

7 x 3 + 1 = 22, precisely 6 more than 5 x 3 + 1.

 

Odd numbers step by 2 along the number sequence. Knowing this, the following abstraction can be drawn that 9 x 3 + 1 would be 6 more than 22, or 28.

 

Odd ƒ(9) = 28

Odd ƒ(11) = 34

Odd ƒ(13) = 40

Odd ƒ(15) = 46

Odd ƒ(17) = 52

Odd ƒ(19) = 58

Odd ƒ(21) = 64, which is 26 [CCƒ(42) exploits this as follows: 21, 64, 32, 16, 8, 4, 2, 1]

 

If  (Collatz Conjecture rules) CCƒ(19) is applied, the following sequence emerges:

58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

 

The next odd number of interest is 85. Odd ƒ(85) = 256, which is 28

 

21 – 5 = 16 and Odd ƒ(5) = 16, which is 24

85 – 21 = 64 and Odd ƒ(21) = 64, which is 26

 

Turning this around, the results are as follow:

21 + 64 = 85 and Odd ƒ(85) = 256, which is 28

85 + 256 = 341 and Odd ƒ(341) = 1024, which is 210

341 + 1024 = 1365 and Odd ƒ(1365) = 4096, which is 212

1365 + 4096 = 5461 and Odd ƒ(5461) = 16384, which is 214

5461 + 16384 = 21845 and Odd ƒ(21845) = 65536, which is 216

 

It is interesting to note that with the exception of numbers like 42, (2 x 85) 170, (2 x 341) 682, (2 x 1365) 2730, (2 x 5431) 10922, etc, solutions up to CCƒ(83) have resolved with an ending of . . . 5, 16, 8, 4, 2, 1

 

Considering that any odd number multiplied by 3 and then increased by 1 produces a number that is some multiple of 6 larger than any Odd ƒ(n) based on any previous odd number. Dividing by 2 will always result in an odd number different than the starting number. Or in other words, 3 x 1 + 1 = 4 , which is 22, [which incidentally 1 + 4 = 5 and Odd ƒ(5) = 16] dividing by 2 will always result in a different odd number except if the number were 1, which is the solution. This should be sufficient to ensure that the conjecture should not be trapped into an infinite loop.

Link to comment
Share on other sites

Any odd number times an odd number yields an odd number. An odd number plus one is an even number.

 

If x is odd, 3x+1=even.

The conjecture states that 2 shall divide even numbers.

(3x+1)/2=1.5x+0.5 and for simplicity, this will be referred to as the combined premise CPƒ(x) stopping at the first even number encountered.

 

CCƒ(3)=10, 5, 16, 8 . . .

. . .or. . .

CPƒ(1) = 2 . . .

CPƒ(3) = 5, 8 . . .

CPƒ(5) = 8, . . .

CPƒ(7) = 11, 17, 26 . . .

CPƒ(9) = 14 . . .

CPƒ(11) = 17, 26 . . .

CPƒ(13) = 20 . . .

CPƒ(15) = 23, 35, 53, 80 . . .

CPƒ(17) = 26 . . .

CPƒ(19) = 29, 44 . . .

CPƒ(21) = 32 . . .

CPƒ(23) = 35, 53, 80 . . .

CPƒ(25) = 38 . . .

CPƒ(27) = 41, 62 . . .

CPƒ(29) = 44 . . .

CPƒ(31) = 47, 71, 107, 161, 242 . . .

CPƒ(33) = 50

CPƒ(35) = 53, 80 . . .

CPƒ(37) = 56 . . .

CPƒ(39) = 59, 89, 134 . . .

CPƒ(41) = 62

CPƒ(43) = 65, 98 . . .

CPƒ(45) = 68 . . .

CPƒ(47) = 71, 107, 161, 242 . . .

CPƒ(49) = 74 . . .

CPƒ(51) = 77, 116 . . .

CPƒ(53) = 80 . . .

 

Aside from the obvious odd numbers CPƒ(x): 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23,25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53 . . . being a sequence of 2 apart, there are 2 other sequences at play here.

 

The next sequences are in the following vertical columns: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80 . . . being a sequence of 3 apart, starting with 3-1.

8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116 . . . being a sequence of 9 apart, starting with 9-1.

26, 53, 80, 107, 134, 161 . . . being a sequence of 27 apart, starting with 27-1.

And lastly illustrated: 80, 161, 242 . . . being a sequence of 81 apart, starting with 80-1.

 

The second sequence consists of 3, 9, 27, 81 . . . 31, 32, 33, 34 . . .

 

Lastly, going down the vertical columns, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53 . . .  are included in every CPƒ(x)

 

8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116 . . . skip every other row.

26, 53, 80, 107, 134, 161 . . . skip every 3rd row.

80, 161, 242 . . . skip every 7th row.

 

The third sequence consist of 1, 3, 7 . . . every column (1(n)) followed by (1(n) x 2+1=3), (3(n) x 2 + 1=7), (7(n) x 2 + 1=15) , , ,

Going vertically, depending on the how many columns it is away from the ‘=’ , dictates the spacing determined by the second sequence.

Edited by dream_weaver
Link to comment
Share on other sites

For every odd integer, CPƒ(1.5x+0.5) terminates with an even number.

 

For odd integers that satisfy the following, (x+3) is divisible by 4 with no remainder, one iteration of CPƒ(x) will result in the even number (x+3)/4*6-4

 

For odd integers that satisfy the following, (x+5) is divisible by 8 with no remainder, two iterations of CPƒ(x) will result in the even number (x+5)/8*18-10

 

For odd integers that satisfy the following, (x+9) is divisible by 16 with no remainder, three iterations of CPƒ(x) will result in the even number (x+9)/16*54-28

 

For odd integers that satisfy the following, (x+17) is divisible by 32 with no remainder, four iterations of CPƒ(x) will result in the even number (x+17)/32*162-82

 

For odd integers that satisfy the following, (x+33) is divisible by 64 with no remainder, five iterations of CPƒ(x) will result in the even number (x+33)/64*486-244

 

To determine the next rule, divide the 64 by 2, which is 32 and add it to the 33 to generate (x+65) is divisible by twice 64 or 128 with no remainder.

6 iterations of CPƒ(x) will result in the even number:

(x+33+64/2)/(2*64)*(3*486)-(486+244) or with combined terms: (x+65)/128*1458-730

 

For 7 iterations of CPƒ(x) even number terminus,

(x+65+128/2)/(2*128)*(3*1458)-(1458+730) or with combined terms: (x+129)/256*4374-2188

 

For 8, 9, 10 etc., iterations, this can continue to be extrapolated as needed.

Link to comment
Share on other sites

Since odd numbers are being resolved, even number resulting from the odd sequence times 3 plus 1 will be considered. This produces intervals of 6, with 4 being included as being 6 less than 10.

 

Even ƒ(4) = 2, 1

Even ƒ(10) = 5

Even ƒ(16) = 8, 4, 2, 1

Even ƒ(22) = 11

Even ƒ(28) = 14, 7

Even ƒ(34) = 17

Even ƒ(40) = 20, 10, 5

Even ƒ(46) = 23

Even ƒ(52) = 26, 13

Even ƒ(58) = 29

Even ƒ(64) = 32, 16, 8, 4, 2, 1

Even ƒ(70) = 35

Even ƒ(76) = 38, 19

Even ƒ(82) = 41

Even ƒ(88) = 44, 22, 11

Even ƒ(94) = 47

Even ƒ(100) = 50, 25

Even ƒ(106) = 53

Even ƒ(112) = 56, 28, 14, 7

Even ƒ(118) = 59

Even ƒ(124) = 62, 31

Even ƒ(130) = 65

Even ƒ(136) = 68, 34, 17

Even ƒ(142) = 71

Even ƒ(148) = 74, 37

Even ƒ(154) = 77

Even ƒ(160) = 80, 40, 20, 10, 5

 

Even Propositions:

1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, etc.,.

Note, conspicuously absent: 3, 9, 15, 21, 27, 33, 39, etc.,.

 

For even numbers that satisfy the following, (x+2) is divisible by 12 with no remainder, one division by 2 will result in the following (x+2)/12*6-1

 

For even numbers that satisfy the following, (x-4) is divisible by 24 with no remainder, two divisions by 2 will result in the following (x-4)/24*6+1

 

For even numbers that satisfy the following, (x+8) is divisible by 48 with no remainder, three divisions by 2 will result in the following (x+8)/24*6-1

 

For even numbers that satisfy the following, (x-16) is divisible by 96 with no remainder, four divisions by 2 will result in the following (x-16)/96*6+1

 

For five sequential divisions by 2:

To determine the next rule, multiply the even number modifier and divisor by 2 and reverse the addition/subtraction signs. (x+(2*16))/(2*96)*6-1 or with combined terms: (x+32)/192*6-1

 

For 6, 7, 8, etc., sequential divisions by 2 this can continue to be extrapolated as required.

 

For even numbers that can be divided by 2 to an odd power, the series steps by 6 starting with 5, 11, 17, 23, 29, 35, 41, 53, 59, 65, 71, 77, etc.

 

For even numbers that can be divided by 2 to an even power, the series steps by 6 starting with 1, 7, 13, 19, 25, 31, 37, etc.

Link to comment
Share on other sites

Post #15 deals with the treatment of odd numbers

 

(x+3)/4*6-4 starting with 4-3 or 1, every 4th number will result in a multiple of  6-4

2, 8, 14, 20 . . .

 

(x+5)/8*18-10 starting with  8-5 or 3, every 8th number will result in a multiple of 18-10

8, 26, 44, 62 . . .

 

(x+9)/16*54-28 starting with 16-9 or 7, every 16th number will result in a multiple of 54-28

26, 80, 134, 188 . . .

 

(x+17)/32*162-82 starting with 32-17 or 15, every 32nd number will result in a multiple of 162-82

80, 242, 404, 566 . . .

 

(x+33)/64*486-244 starting with 64-33 or 31, every 64th number will result in a multiple of 486-244

242, 728, 1214, 1700 . . .

 

 

Post #16 deals with the treatment of the even numbers resulting from (3x+1).

 

(x+2)/12*6-1 starting with 12-2 or 10, every 12th number will result in a multiple of 6-1

5, 11, 17, 23 . . .

 

(x-4)/24*6+1 starting with 4, every 24th number will result in a multiple of  6+1

1, 7, 13, 19 . . .

 

(x+8)/48*6-1 starting with 48-8 or 40, every 48th number will result in a multiple of 6-1

5, 11, 17, 23 . . .

(corrected for typo discovered in Post #16)

 

(x-16)/96*6+1 starting with 16, every 96th number will result in a multiple of 6+1

1, 7, 13, 19 . . .

 

(x+32)/192*6-1 starting with 192-32 or 160, every 192nd number will result in a multiple of 6-1

5, 11, 17, 23 . . .

 

 

Both of these approaches can be extended as needed.

 

So every odd number submitted to (3x+1)/2 is either odd or even, and the odd reduces to either 1, 7, 13, 19 . . . or 5, 11, 17, 23 . . .  and every even number that is the result of 3x+1 reduces to either 1, 7, 13, 19 . . . or 5, 11, 17, 23 . . .

 

On the even results list, numbers like 8, 26, 80, 242, 728 and their related kin, show up frequently in the results of the predictive formulas.

 

 

Another interesting note: For the odd numbers 1 to 85 there are a total of 82 instantiations of (3x+1) and 82 divisions by 2.

The even numbers resulting from (3x+1) generated 89 instances of division by 2.

This adds up to 82 invocations of 3x+1 and 171 divisions by 2.

 

Also, the odd sequence starting with 3 and every 6th number thereafter are never the result of (3x-1)/2n. The even numbers that could result in 6 and every 12th number thereafter do not appear either.

Link to comment
Share on other sites

1,

2, 1

3,

4, 2, 1

5,

6, 3

7,

8, 4

9,

10, 5

11,

12, 6, 3

13,

14, 7

15,

16, 8, 4, 2, 1

17,

18, 9

19,

20, 10, 5

21

 

3x+1 will always net a number 1 greater than the key sequence 3, 6, 9, 12, etc.

When dividing by 2, the first time will be 1 less than this key sequence.

Each subsequent division will alternate 1 more, then 1 less than the key.

 

This illustrates why 3, 9, 15, 21, 27, etc., did not appear in any of the earlier results.

This also illustrates why the two distinctive patterns kept reappearing: 1, 7, 13, 19 are all 1 less than the key sequence while 5, 11, 17, 23 are all 1 more than key sequence.

 

This is why the Collantz Conjecture works.

Link to comment
Share on other sites

Considering the odd numbers once again,

Every odd number establishes the same pattern in the sequence.

 

1*20, 1*21, 1*23, . . . 1*2n

3*20, 3*21, 3*23, . . . 3*2n

5*20, 5*21, 5*23, . . . 5*2n

. . .

. . .

. . .

x*20, x*21, x*23, . . . x*2n, where x is the next odd number in the series.

 

If you go to x*2n, the result can be divided by 2 until the result is x with no remainder.

Since the series 3, 6, 9, etc., multiplied by 3 and increased by 1 moves into the 1, 7, 13, 19 series, and any 5, 11, 17, 23 series multiplied by 3 and increased by 1 moves into the 1, 7, 13, 19 series, is it any surprise that taking the number sequence and dividing the even numbers by 2 provide another number series that aligns with the even numbers of the series it was derived from? Repeating this procedure only replicates the same result.

 

When this is understood, then it should be understood why Collatz Conjecture behaves as it does.

Edited by dream_weaver
Link to comment
Share on other sites

Correction from post #18.

 

This illustrates why 3, 9, 15, 21, 27, etc., did not appear in any of the earlier results.

This also illustrates why the two distinctive patterns kept reappearing: 1, 7, 13, 19 are all 1 less more than the key sequence while 5, 11, 17, 23 are all 1 more less than key sequence.

 

The following method can reconstruct the entire number series:

 

1=1*20, 2=1*21, 3=3*20, 4=1*22, 5=5*20, 6=3*21, 7=7*20, 8=1*23, 9=9*20, 10=5*21, 11=11*20, 12=3*22, 13=13*20, 14=7*21, 15=15*20, 16=1*24, 17=17*20, 18=9*21, 19=19*20, 20=5*22, 21=21*20 . . .

 

3 times any odd number produces an even number. Every even number can be expressed as x*2n, where x is the odd number and n determines when it reappears in the number sequence.

Link to comment
Share on other sites

NSƒ(x)=x*2n where x are the odd integers and n are all the integers

 

NSƒ(1) = 1, 2, 4, 8, 16 . . .

NSƒ(3) = 3, 6, 12, 24, 48 . . .

NSƒ(5) = 5, 10, 20, 40, 80 . . .

NSƒ(7)

NSƒ(9) = 9, 18, 36, 72, 144 . . .

NSƒ(11)

NSƒ(13)

NSƒ(15) = 15, 30, 60, 120, 240 . . .

NSƒ(17)

NSƒ(19)

NSƒ(21) = 21, 42, 84, 168, 334 . . .

NSƒ(23)

NSƒ(25)

NSƒ(27) = 27, 54, 108, 216, 432 . . .

NSƒ(29)

 

1*20, 1*21, 3, 1*22, 5*20, 6, 7*20, 1*23, 9, 5*21, 11*20, 12, 13*20, 7*21, 15, 1*24, 17*20, 18, 19*20, 5*22, 21, 11*21, 23*20, 24, 25*20, 13*21, 27, 7*22, 29*20, 30, 31*20, 1*25, 33 . . .

 

If a Collantz sequence begins with 240, 120, 60 or 30, it divides by 2 until it reaches 15. 15*3+1=45*20+1=46 or 23*21.

3, 6, 9, 12, 15 . . . serve as the destination address of the 3x portion of 3x+1. Adding one results in either 1*2n, 5*2n or another x*2n, which eventually leads to 1*2n, 5*2n.

 

If all of the odd numbers where multiplied by 3 and raised by 1 simultaneously, the result would be all of the even numbers. Divide the even numbers by 2, all the x*21 would become odd. Divide the remaining even numbers by 2, all the x*22 would become odd.

Simply repeat the process to resolve x*23, x*24, etc.

 

How are all of these series inter-connected?

 

5*21: 10-1=9/3=3

11*21: 22-1=21/3=7

17*21: 34-1=33/3=11

Adding 6 (5, 11, 17…) adds 4 (3,7, 11…)

 

1*22: 4-1=3/3=1

7*22: 28-1=27/3=9

13*22: 52-1=51/3=17

Adding 6 (1, 7, 13) adds 8 (1, 9, 17…)

 

5*23: 40-1=39/2=13

11*23: 88-1=87/3=29

17*23: 136-1=135/3=45

Adding 6 (5, 11, 17…) adds 16 (13, 29, 45…)

 

1*24: 16-1=15/3=5

7*24: 112-1=111/3=37

13*24: 208-1=207/2=69

Adding 6 (1, 7, 13…) adds 32 (5, 37, 69…)

 

It is known that encountering a 5 leads to 1

Looking above, 7 leads to 11 (see 11*21). 11 leads to 17 (see 17*21). 17 leads to 13 (see 13*22). 13 leads to 5 (see 5*23). Finally, 5 leads to 1 (see 1*24)

 

19 would lead to 29 (29*21=58-1=57/3=19). 29 leads to 11 (see 11*23). Pick up the rest of the trail in 7 example above.

 

5*25=160-1=159/3=53

Adding 6 (5, 11, 17…) adds 64 (32*2)

 

1*26=64-1=63/3=21

Adding 6 (5, 11, 17…) adds 128 (64*2)

 

Alternating between 5*2odd and 1*2even continues to produce new starting points with increasing multiples of 2.

 

Collatz Conjecture could be known as the Collatz-Lewis Theorem

Q.E.D.

Link to comment
Share on other sites

The following fact was just noticed as well.

1 is flanked by 0/3=0

1+0=1, 1*3+1=4. 4+1=5. 5*3+1=16. 16+5=21. 21*3+1=64, 85…

 

5-2=3. 3*3+1=10. 10+3=13. 13*3+1=40, 53…

flanks 6/3=2

7+2=9. 9*3+1=28. 28+9=37. 37*3+1=112, 149…

 

11-4=7. 7*3+1=22. 22+7=29. 29*3+1=88, 117…

flanks 12/3=4

13+4=17,..

 

17-6=11…

flanks 18/3=6

19+6=25…

 

(even multiple of 6-1)-AF…

(even multiple of 6)=EM/3=Additive Factor

(even multiple of 6+1)+AF…

 

By using x*2n to generate all the numbers allows a convenient way to rearrange the entire number line. Each even number, in this view, is used once and only once by the nature of how it was generated.

 

Every odd number is taken into consideration twice.

The first time, they are used to establish the even numbered array using the formula x*2n.

The second time to establish the how the odd numbers are placed using the formula 3x+1.

 

Link to comment
Share on other sites

This illustration shows what each x*20 generates and leading to where it can originate from. Using the results as a list, a new list can be generated from the results of the previous list.

Each x*20 generates it's own unique list, and all of these unique lists can generate a unique series which can exhaust an odd numbers once, and only once. The sequence can only repeat in a "home stretch", i.e.: when the same sequence is used to identify different origin numbers along as long a "starting" path as desired. Starting from 1, each consecutive drop down selection can match a previous sequence which is being identified as "a home stretch" sequence.

 

Number is objective.

 

Collatz_Illustration2.pdf

Edited by dream_weaver
Link to comment
Share on other sites

In the eagerness to upload the last chart, some errors were missed, which have been corrected.

 

This multi-page pdf contains the corrected illustration, combined with the 2nd set of illustrations and one more using the first table with some additional comments.

 

Corrected Collatz Conjecture.pdf

 

 

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...