My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
September 3rd, 2017, 12:42 AM   #1
Newbie
 
Joined: Sep 2017
From: United States

Posts: 1
Thanks: 0

Collatz Conjecture

I was recently thinking back to the collatz conjecture and decided to just think about it for a while. For those who do not know, the conjecture is basically this:

If n is even divide n by 2. If n is odd, multiply n by three then add one. Take that answer and repeat the process such that you have a sequence. For any positive even integer n, does the sequence ever not terminate at 1?

My thoughts:
  • Any sequence which reaches 1 terminates as it enters the loop 1>4>2>1
  • Any sequence which contains a number known to terminate at 1, also terminates at one
  • All odd numbers do not need to be checked
  • Take a and b to both be positive odd integers.
  • a can be written as 2c+1 by the definition of an odd number
  • b can be written as 2d+1 by the definition of an odd number
  • a*b = (2c+1)(2d+1) by subsitution
  • (2c+1)(2d+1) = 4cd+2c+2d+1 by distribution
  • 4cd+2c+2d+1 = (4cd+2c+2d)+1 by association
  • (4cd+2c+2d)+1 = 2(2cd+c+d)+1 by distribution
  • 2(2cd+c+d)+1 is an odd number by definition. any integer multiplied by 2 and added to 1 is odd.
  • Any odd number plus one is even by definition
  • Therefore, after one iteration any odd number will become even.
  • For any integer a where n is equal to 2^a the sequence will terminate at 1
  • Since 2^a is even, and can be divided by 2 exactly a times, the product of each iteration becomes 2^a-k where k is the current iteration
  • When a=k then the product of the iteration will be 2^a-a which is 2^0 which is equal to 1
Based on the proof above, does that mean that a solution to the problem would be to determine if all the series eventually reach a point of 2^n? Thereby making the conjecture:

For any positive integer n; If n is even divide n by 2. If n is odd, multiply n by three then add one. Take that answer and repeat the process such that you have a sequence. For any positive integer n, does the sequence ever not contain a value 2^n?
Trenly is offline  
 
September 3rd, 2017, 04:25 AM   #2
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

That's a lot of words to say something fairly simple. Yes, the 3n+1 step by definition will give you an even number. Yes, when it is 2^a that is the end of the chain as it will go to 1. And yes, you are right, one way to think about attacking the problem is to consider whether all chains starting from b will reach 2^a before they reach b(2^a). But that doesn't actually help very much as this is a horribly difficult thing to prove. Think for instance about the negative loops starting from -5 and -17. Why do those numbers lead to -5( 8 ) and -17(2048 ) rather than to a power of 2? If you could answer that question you might have a start on the problem.
Hedge is offline  
September 4th, 2017, 03:51 AM   #3
Member
 
Joined: Jul 2014
From: israel

Posts: 76
Thanks: 3

Quote:
Originally Posted by Hedge View Post
Think for instance about the negative loops starting from -5 and -17. Why do those numbers lead to -5( 8 ) and -17(2048 ) rather than to a power of 2? If you could answer that question you might have a start on the problem.
answering to that question will give you nothing

for any given loop (negative or positive) grater then 3 values the minimum value of that loop will be 12k+7 or 12k+11

12(-1)+7=-5
12(-2)+7=-17

you can even go further

96k+7
96k+31
96k+79
96k+91

96k+47
96k+59
96k+71
96k+95

etc...
isaac is offline  
September 4th, 2017, 06:37 AM   #4
Senior Member
 
Joined: Mar 2012

Posts: 572
Thanks: 26

Quote:
Originally Posted by isaac View Post
answering to that question will give you nothing

for any given loop (negative or positive) grater then 3 values the minimum value of that loop will be 12k+7 or 12k+11
That might depend on what the answer was although I grant you it is most likely as much of a dead-end as any other path.

What do you mean by minimum value and '3 values' in the sentence above, out of curiosity?
Hedge is offline  
September 4th, 2017, 11:33 PM   #5
Member
 
Joined: Jul 2014
From: israel

Posts: 76
Thanks: 3

Quote:
Originally Posted by Hedge View Post
That might depend on what the answer was although I grant you it is most likely as much of a dead-end as any other path.

What do you mean by minimum value and '3 values' in the sentence above, out of curiosity?
Any cycle has a minimum and maximum value to it as well as "size"

4 -> 2 -> 1 is a cycle with 3 values (2 even and 1 odd) "size" of 3

minimum value is 1
maximum value is 4

What I wrote above is for cycles with "size" of 5 or higher,
where the minimum value will be 12k+7 or 12k+11.

Last edited by skipjack; September 5th, 2017 at 01:13 AM.
isaac is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
collatz, conjecture



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
On the Collatz Conjecture JwClaassen Number Theory 0 March 18th, 2017 09:47 AM
collatz conjecture isaac Number Theory 6 March 15th, 2016 02:12 AM
Collatz conjecture isaac Number Theory 37 April 3rd, 2015 03:54 AM
About Collatz conjecture vlagluz Number Theory 10 November 5th, 2014 12:27 AM
Collatz conjecture & More (Please Help) Aika Number Theory 6 April 29th, 2012 07:34 AM





Copyright © 2017 My Math Forum. All rights reserved.