Total Posts:18|Showing Posts:1-18
Jump to topic:

3n+1 problem

Mhykiel
Posts: 5,987
Add as Friend
Challenge to a Debate
Send a Message
1/23/2016 8:02:41 PM
Posted: 10 months ago
This is a unique problem that gets played with by amateurs a lot. It's known by a few different names. Such as the Collatz, Ulam, or Syracuse Conjecture.

The Conjecture has gone unproven despite many mathematicians and minds looking at it. Some become passionate about it's relevance while others are less interested in proving it correct. The Conjecture is given a series constructed from 2 steps: 1. Divide by 2 if Even. 2. multiply by 3 and add 1 if odd. Given those rules any natural integer over 0 will always end in 1.

f(n) { n/2 IF n is even OR 3n+1 if odd.}

Example: n = 7
Series would be:
7 (7 is odd so 3(7)+1)
22 (even so 22/2)
11 (odd so 3(11)+1)
34 (even 34/2)
16 (even 16/2)
8 (even 8/2)
4 (even 4/2)
2 (even 2/2)
1 (halt on 1.)

The idea is that no matter what number you start with you will end up with 1. Series where (n) is 1 to billions have been completed and all end in 1.

I'm asking why do people think this has not been proven yet?

If the heuristic argument shows that the orbit is shrinking. Take that with every number can be written as the summation of powers of 2. take that step 2 transforms a number to be pushed to step1. (every ascending step will be followed by a descending step) So isn't this proof enough?
DanneJeRusse
Posts: 12,598
Add as Friend
Challenge to a Debate
Send a Message
1/23/2016 8:21:28 PM
Posted: 10 months ago
At 1/23/2016 8:02:41 PM, Mhykiel wrote:
This is a unique problem that gets played with by amateurs a lot. It's known by a few different names. Such as the Collatz, Ulam, or Syracuse Conjecture.

The Conjecture has gone unproven despite many mathematicians and minds looking at it. Some become passionate about it's relevance while others are less interested in proving it correct. The Conjecture is given a series constructed from 2 steps: 1. Divide by 2 if Even. 2. multiply by 3 and add 1 if odd. Given those rules any natural integer over 0 will always end in 1.

f(n) { n/2 IF n is even OR 3n+1 if odd.}

Example: n = 7
Series would be:
7 (7 is odd so 3(7)+1)
22 (even so 22/2)
11 (odd so 3(11)+1)
34 (even 34/2)
16 (even 16/2)
8 (even 8/2)
4 (even 4/2)
2 (even 2/2)
1 (halt on 1.)

The idea is that no matter what number you start with you will end up with 1. Series where (n) is 1 to billions have been completed and all end in 1.

I'm asking why do people think this has not been proven yet?

If the heuristic argument shows that the orbit is shrinking. Take that with every number can be written as the summation of powers of 2. take that step 2 transforms a number to be pushed to step1. (every ascending step will be followed by a descending step) So isn't this proof enough?

Uh, doesn't 34/2 = 17?
Marrying a 6 year old and waiting until she reaches puberty and maturity before having consensual sex is better than walking up to
a stranger in a bar and proceeding to have relations with no valid proof of the intent of the person. Muhammad wins. ~ Fatihah
If they don't want to be killed then they have to subdue to the Islamic laws. - Uncung
Without God, you are lower than sh!t. ~ SpiritandTruth
RainbowDash52
Posts: 294
Add as Friend
Challenge to a Debate
Send a Message
1/23/2016 9:37:46 PM
Posted: 10 months ago
At 1/23/2016 8:21:28 PM, DanneJeRusse wrote:
At 1/23/2016 8:02:41 PM, Mhykiel wrote:
This is a unique problem that gets played with by amateurs a lot. It's known by a few different names. Such as the Collatz, Ulam, or Syracuse Conjecture.

The Conjecture has gone unproven despite many mathematicians and minds looking at it. Some become passionate about it's relevance while others are less interested in proving it correct. The Conjecture is given a series constructed from 2 steps: 1. Divide by 2 if Even. 2. multiply by 3 and add 1 if odd. Given those rules any natural integer over 0 will always end in 1.

f(n) { n/2 IF n is even OR 3n+1 if odd.}

Example: n = 7
Series would be:
7 (7 is odd so 3(7)+1)
22 (even so 22/2)
11 (odd so 3(11)+1)
34 (even 34/2)
16 (even 16/2)
8 (even 8/2)
4 (even 4/2)
2 (even 2/2)
1 (halt on 1.)

The idea is that no matter what number you start with you will end up with 1. Series where (n) is 1 to billions have been completed and all end in 1.

I'm asking why do people think this has not been proven yet?

If the heuristic argument shows that the orbit is shrinking. Take that with every number can be written as the summation of powers of 2. take that step 2 transforms a number to be pushed to step1. (every ascending step will be followed by a descending step) So isn't this proof enough?

Uh, doesn't 34/2 = 17?

correct

corrected example for n=7
7 (7 is odd so 3(7)+1)
22 (even so 22/2)
11 (odd so 3(11)+1)
34 (even 34/2)
17 (odd so 3(17)+1)
52 (even so 52/2)
26 (even so 26/2)
13 (odd so 3(13)+1)
40 (even so 40/2)
20 (even so 20/2)
10 (even so 10/2)
5 (odd so 3(5)+1)
16 (even 16/2)
8 (even 8/2)
4 (even 4/2)
2 (even 2/2)
1 (halt on 1.)
Mhykiel
Posts: 5,987
Add as Friend
Challenge to a Debate
Send a Message
1/23/2016 11:15:49 PM
Posted: 10 months ago
At 1/23/2016 9:37:46 PM, RainbowDash52 wrote:
At 1/23/2016 8:21:28 PM, DanneJeRusse wrote:
At 1/23/2016 8:02:41 PM, Mhykiel wrote:
This is a unique problem that gets played with by amateurs a lot. It's known by a few different names. Such as the Collatz, Ulam, or Syracuse Conjecture.

The Conjecture has gone unproven despite many mathematicians and minds looking at it. Some become passionate about it's relevance while others are less interested in proving it correct. The Conjecture is given a series constructed from 2 steps: 1. Divide by 2 if Even. 2. multiply by 3 and add 1 if odd. Given those rules any natural integer over 0 will always end in 1.

f(n) { n/2 IF n is even OR 3n+1 if odd.}

Example: n = 7
Series would be:
7 (7 is odd so 3(7)+1)
22 (even so 22/2)
11 (odd so 3(11)+1)
34 (even 34/2)
16 (even 16/2)
8 (even 8/2)
4 (even 4/2)
2 (even 2/2)
1 (halt on 1.)

The idea is that no matter what number you start with you will end up with 1. Series where (n) is 1 to billions have been completed and all end in 1.

I'm asking why do people think this has not been proven yet?

If the heuristic argument shows that the orbit is shrinking. Take that with every number can be written as the summation of powers of 2. take that step 2 transforms a number to be pushed to step1. (every ascending step will be followed by a descending step) So isn't this proof enough?

Uh, doesn't 34/2 = 17?

correct

corrected example for n=7
7 (7 is odd so 3(7)+1)
22 (even so 22/2)
11 (odd so 3(11)+1)
34 (even 34/2)
17 (odd so 3(17)+1)
52 (even so 52/2)
26 (even so 26/2)
13 (odd so 3(13)+1)
40 (even so 40/2)
20 (even so 20/2)
10 (even so 10/2)
5 (odd so 3(5)+1)
16 (even 16/2)
8 (even 8/2)
4 (even 4/2)
2 (even 2/2)
1 (halt on 1.)

Thank you.
Mhykiel
Posts: 5,987
Add as Friend
Challenge to a Debate
Send a Message
1/24/2016 6:23:32 AM
Posted: 10 months ago
My question is since it is true that all even numbers can be written as the sum of distinct powers of two and step 2 creates even numbers and step 1 reduces distinct powers of two then isn't it a proof by induction that the conjecture is true for all numbers?
chui
Posts: 507
Add as Friend
Challenge to a Debate
Send a Message
1/24/2016 12:13:49 PM
Posted: 10 months ago
At 1/24/2016 6:23:32 AM, Mhykiel wrote:
My question is since it is true that all even numbers can be written as the sum of distinct powers of two and step 2 creates even numbers and step 1 reduces distinct powers of two then isn't it a proof by induction that the conjecture is true for all numbers?

Here is an algorithm that you may be unaware off:
1 Assume you am wrong
2 Look for your error
3 Find your error
4 Learn something new

Try converting your word description of your possible solution to algebraic expressions. Your error becomes obvious then.
Dirty.Harry
Posts: 1,584
Add as Friend
Challenge to a Debate
Send a Message
1/24/2016 5:32:22 PM
Posted: 10 months ago
I think this is called the Collatz conjecture - its unproven.

https://en.wikipedia.org...

This and many similar problems have elegant implementations in functional programming languages, here's a comparison of a C# v and F# implementation.

http://www.refactorthis.net...

See how terse the F# version is which is much closer to mathematics as a language than C# and other procedural languages - just wanted to point this out.

Harry.
Dirty.Harry
Posts: 1,584
Add as Friend
Challenge to a Debate
Send a Message
1/24/2016 5:35:18 PM
Posted: 10 months ago
Even Erdos could not address the problem, one of the most proficient mathematicians of the 20th century.
Mhykiel
Posts: 5,987
Add as Friend
Challenge to a Debate
Send a Message
1/24/2016 6:43:23 PM
Posted: 10 months ago
At 1/24/2016 12:13:49 PM, chui wrote:
At 1/24/2016 6:23:32 AM, Mhykiel wrote:
My question is since it is true that all even numbers can be written as the sum of distinct powers of two and step 2 creates even numbers and step 1 reduces distinct powers of two then isn't it a proof by induction that the conjecture is true for all numbers?

Here is an algorithm that you may be unaware off:
1 Assume you am wrong
2 Look for your error
3 Find your error
4 Learn something new

Try converting your word description of your possible solution to algebraic expressions. Your error becomes obvious then.

Why don't you just speak plainly of what you think I have missed.

Case 1: (n is even)
All even numbers can be written as the summation of powers of 2.

n = (2^x + 2^y + 2^1)

When you divide something in half. A power is taken away.
(2^x + 2^y + 2^1) /2^1 = 2^x + 2^y + 2^1 + 2^-1 = 2^x + 2^y + 2^0

This of course leads to case 2. because 2^0 =1 meaning n is now odd.
Case 2:
When 2 odd numbers are added together that make an even. When 2 even numbers are added together the result is even.

n is odd. 3n+1 = n+n+n+1 = (2n) + (n+1)

As we see this creates an even number that is the summation of 2 even numbers. 2n is even because 2 odd added together make even. And n+1 is even because an odd plus an odd make an even. Taken together, even plus even make an even.

More so if I write n as ?+2^0 then I can tell that the oddness in n is turned into 4 by step 2.

(?+1) + (?+1) = 2?+2
plus
(?+1) +1 = ?+2

step1 (dividing by 2) will continue until a n is once again n+2^0. Then 4 is added again.

By induction I see that eventual ? in n will be divisible by 2 and no longer odd. In which case step 1 will happen again. An the cycle continues until step reduces to 2. Then to 1.

Why is this not a proof by induction for all and any integer greater than 1?
chui
Posts: 507
Add as Friend
Challenge to a Debate
Send a Message
1/26/2016 4:38:21 PM
Posted: 10 months ago
At 1/24/2016 6:43:23 PM, Mhykiel wrote:
At 1/24/2016 12:13:49 PM, chui wrote:
At 1/24/2016 6:23:32 AM, Mhykiel wrote:
My question is since it is true that all even numbers can be written as the sum of distinct powers of two and step 2 creates even numbers and step 1 reduces distinct powers of two then isn't it a proof by induction that the conjecture is true for all numbers?

Here is an algorithm that you may be unaware off:
1 Assume you am wrong
2 Look for your error
3 Find your error
4 Learn something new

Try converting your word description of your possible solution to algebraic expressions. Your error becomes obvious then.

Why don't you just speak plainly of what you think I have missed.

Case 1: (n is even)
All even numbers can be written as the summation of powers of 2.

n = (2^x + 2^y + 2^1)

When you divide something in half. A power is taken away.
(2^x + 2^y + 2^1) /2^1 = 2^x + 2^y + 2^1 + 2^-1 = 2^x + 2^y + 2^0

(2^x + 2^y + 2^1) /2^1 = 2^(x-1) + 2^(y-1) + 2^0= 2^(x-1) + 2^(y-1) + 2^0

This of course leads to case 2. because 2^0 =1 meaning n is now odd.
Case 2:
When 2 odd numbers are added together that make an even. When 2 even numbers are added together the result is even.

n is odd. 3n+1 = n+n+n+1 = (2n) + (n+1)

As we see this creates an even number that is the summation of 2 even numbers. 2n is even because 2 odd added together make even. And n+1 is even because an odd plus an odd make an even. Taken together, even plus even make an even.

More so if I write n as ?+2^0 then I can tell that the oddness in n is turned into 4 by step 2.

(?+1) + (?+1) = 2?+2
plus
(?+1) +1 = ?+2

3(2^(x-1) + 2^(y-1) + 2^0)+1=3(2^(x-1) + 2^(y-1) )+4=3(2^(x-1) + 2^(y-1) )+2^2

step1 (dividing by 2) will continue until a n is once again n+2^0. Then 4 is added again.


(3(2^(x-1) + 2^(y-1) )+2^2)/2=3(2^(x-2) + 2^(y-2) )+2^1 still even assuming x and y are larger than 2
(3(2^(x-2) + 2^(y-2) )+2^1)/2=3(2^(x-3) + 2^(y-3) )+2^0 odd assuming x and y greater than 3
(3(2^(x-3) + 2^(y-3) )+2^0)*3+1=9(2^(x-3) + 2^(y-3) )+2^2

By induction I see that eventual ? in n will be divisible by 2 and no longer odd. In which case step 1 will happen again. An the cycle continues until step reduces to 2. Then to 1.

Why is this not a proof by induction for all and any integer greater than 1?
Proof by induction is a rigorous mathematical technique which you have not followed. If your method was a proof it would have been found in 1937 when the conjecture was first suggested. What you do not address in your proof is the possibility of an infinite loop. Can we be sure that you never get the same answer twice in a sequence? If we do get a repeat then we are in stuck in a loop.
Proof by induction here would be to prove that any number 2n+2 will eventually become the number 2n. This would be sufficient to prove the conjecture. However this is impossible or someone would have done it by now.
Mhykiel
Posts: 5,987
Add as Friend
Challenge to a Debate
Send a Message
1/26/2016 7:15:39 PM
Posted: 10 months ago
At 1/26/2016 4:38:21 PM, chui wrote:
At 1/24/2016 6:43:23 PM, Mhykiel wrote:
At 1/24/2016 12:13:49 PM, chui wrote:
At 1/24/2016 6:23:32 AM, Mhykiel wrote:
My question is since it is true that all even numbers can be written as the sum of distinct powers of two and step 2 creates even numbers and step 1 reduces distinct powers of two then isn't it a proof by induction that the conjecture is true for all numbers?

Here is an algorithm that you may be unaware off:
1 Assume you am wrong
2 Look for your error
3 Find your error
4 Learn something new

Try converting your word description of your possible solution to algebraic expressions. Your error becomes obvious then.

Why don't you just speak plainly of what you think I have missed.

Case 1: (n is even)
All even numbers can be written as the summation of powers of 2.

n = (2^x + 2^y + 2^1)

When you divide something in half. A power is taken away.
(2^x + 2^y + 2^1) /2^1 = 2^x + 2^y + 2^1 + 2^-1 = 2^x + 2^y + 2^0

(2^x + 2^y + 2^1) /2^1 = 2^(x-1) + 2^(y-1) + 2^0= 2^(x-1) + 2^(y-1) + 2^0

This of course leads to case 2. because 2^0 =1 meaning n is now odd.
Case 2:
When 2 odd numbers are added together that make an even. When 2 even numbers are added together the result is even.

n is odd. 3n+1 = n+n+n+1 = (2n) + (n+1)

As we see this creates an even number that is the summation of 2 even numbers. 2n is even because 2 odd added together make even. And n+1 is even because an odd plus an odd make an even. Taken together, even plus even make an even.

More so if I write n as ?+2^0 then I can tell that the oddness in n is turned into 4 by step 2.

(?+1) + (?+1) = 2?+2
plus
(?+1) +1 = ?+2

3(2^(x-1) + 2^(y-1) + 2^0)+1=3(2^(x-1) + 2^(y-1) )+4=3(2^(x-1) + 2^(y-1) )+2^2

step1 (dividing by 2) will continue until a n is once again n+2^0. Then 4 is added again.


(3(2^(x-1) + 2^(y-1) )+2^2)/2=3(2^(x-2) + 2^(y-2) )+2^1 still even assuming x and y are larger than 2
(3(2^(x-2) + 2^(y-2) )+2^1)/2=3(2^(x-3) + 2^(y-3) )+2^0 odd assuming x and y greater than 3
(3(2^(x-3) + 2^(y-3) )+2^0)*3+1=9(2^(x-3) + 2^(y-3) )+2^2

By induction I see that eventual ? in n will be divisible by 2 and no longer odd. In which case step 1 will happen again. An the cycle continues until step reduces to 2. Then to 1.

Why is this not a proof by induction for all and any integer greater than 1?
Proof by induction is a rigorous mathematical technique which you have not followed. If your method was a proof it would have been found in 1937 when the conjecture was first suggested. What you do not address in your proof is the possibility of an infinite loop. Can we be sure that you never get the same answer twice in a sequence? If we do get a repeat then we are in stuck in a loop.
Proof by induction here would be to prove that any number 2n+2 will eventually become the number 2n. This would be sufficient to prove the conjecture. However this is impossible or someone would have done it by now.

There is a loop it starts at 8. 4 2 1

The question is does it have any other loops.

And 8 is interesting in that 2n equals 3(sqrt(3n+1)/2)+1

The difference between n^2 and (n+1)^2 is 2n+1.

I was asking why it wasn't a proof. The real quedtion for me that would make a proof is how high does the series go based on the shape of the number before it nose dives down. If one can prove n becomes double or triple even then plummets below n. Well then every cycle will end in 1.
medv4380
Posts: 200
Add as Friend
Challenge to a Debate
Send a Message
1/26/2016 8:26:00 PM
Posted: 10 months ago
At 1/26/2016 7:15:39 PM, Mhykiel wrote:
I was asking why it wasn't a proof. The real quedtion for me that would make a proof is how high does the series go based on the shape of the number before it nose dives down. If one can prove n becomes double or triple even then plummets below n. Well then every cycle will end in 1.

It only strongly suggests that it is true which is why most believe that it is. However, for it to be a proof it has to be written in a way that applies to all integers. Unless you have a solid proof about all natural numbers there exists a possibility of say a prime number with an unknown property that could make it false. Unlikely, but still possible without the proof otherwise. There is some work on upper level mathematics that treats numbers as Objects that has been said to be making headway on some of these difficult to formulate proofs. But it's hard to look it up since you'll end up with a lot of programming articles when you try to search for it. It's been used to make some headway on Fermat's Last Theorem, but these things take so long to debate that I don't know what came of it.
Mhykiel
Posts: 5,987
Add as Friend
Challenge to a Debate
Send a Message
1/26/2016 9:14:51 PM
Posted: 10 months ago
At 1/26/2016 8:26:00 PM, medv4380 wrote:
At 1/26/2016 7:15:39 PM, Mhykiel wrote:
I was asking why it wasn't a proof. The real quedtion for me that would make a proof is how high does the series go based on the shape of the number before it nose dives down. If one can prove n becomes double or triple even then plummets below n. Well then every cycle will end in 1.

It only strongly suggests that it is true which is why most believe that it is. However, for it to be a proof it has to be written in a way that applies to all integers. Unless you have a solid proof about all natural numbers there exists a possibility of say a prime number with an unknown property that could make it false. Unlikely, but still possible without the proof otherwise. There is some work on upper level mathematics that treats numbers as Objects that has been said to be making headway on some of these difficult to formulate proofs. But it's hard to look it up since you'll end up with a lot of programming articles when you try to search for it. It's been used to make some headway on Fermat's Last Theorem, but these things take so long to debate that I don't know what came of it.

I did make a claim about all natural numbers. They all, even primes, can be written as the summation of base 2s.

Dividing by 2 is the same as subtracting 1 from the lowest exponent of base 2.

No matter how many times the number is duplicated if enough 1s are added to even out any odd compents eventually the number will be divisble by 2 till it reduces to one.

If n is odd then 3n+1 makes to even components. After division any odd component comes out again.

I was trying to start some interesting conversation I found the puzzle interesting.

As for proofing it I don't think is just in the domain of professionals. I yhink anyone with an interest can add to a field.
chui
Posts: 507
Add as Friend
Challenge to a Debate
Send a Message
1/27/2016 10:40:20 AM
Posted: 10 months ago
At 1/26/2016 9:14:51 PM, Mhykiel wrote:
At 1/26/2016 8:26:00 PM, medv4380 wrote:
At 1/26/2016 7:15:39 PM, Mhykiel wrote:
I was asking why it wasn't a proof. The real quedtion for me that would make a proof is how high does the series go based on the shape of the number before it nose dives down. If one can prove n becomes double or triple even then plummets below n. Well then every cycle will end in 1.

It only strongly suggests that it is true which is why most believe that it is. However, for it to be a proof it has to be written in a way that applies to all integers. Unless you have a solid proof about all natural numbers there exists a possibility of say a prime number with an unknown property that could make it false. Unlikely, but still possible without the proof otherwise. There is some work on upper level mathematics that treats numbers as Objects that has been said to be making headway on some of these difficult to formulate proofs. But it's hard to look it up since you'll end up with a lot of programming articles when you try to search for it. It's been used to make some headway on Fermat's Last Theorem, but these things take so long to debate that I don't know what came of it.

I did make a claim about all natural numbers. They all, even primes, can be written as the summation of base 2s.


Dividing by 2 is the same as subtracting 1 from the lowest exponent of base 2.

No it is not.

No matter how many times the number is duplicated if enough 1s are added to even out any odd compents eventually the number will be divisble by 2 till it reduces to one.

If n is odd then 3n+1 makes to even components. After division any odd component comes out again.

I was trying to start some interesting conversation I found the puzzle interesting.

As for proofing it I don't think is just in the domain of professionals. I yhink anyone with an interest can add to a field.
chui
Posts: 507
Add as Friend
Challenge to a Debate
Send a Message
1/27/2016 11:26:05 AM
Posted: 10 months ago
At 1/26/2016 7:15:39 PM, Mhykiel wrote:
At 1/26/2016 4:38:21 PM, chui wrote:
At 1/24/2016 6:43:23 PM, Mhykiel wrote:
At 1/24/2016 12:13:49 PM, chui wrote:
At 1/24/2016 6:23:32 AM, Mhykiel wrote:
My question is since it is true that all even numbers can be written as the sum of distinct powers of two and step 2 creates even numbers and step 1 reduces distinct powers of two then isn't it a proof by induction that the conjecture is true for all numbers?

Here is an algorithm that you may be unaware off:
1 Assume you am wrong
2 Look for your error
3 Find your error
4 Learn something new

Try converting your word description of your possible solution to algebraic expressions. Your error becomes obvious then.

Why don't you just speak plainly of what you think I have missed.

Case 1: (n is even)
All even numbers can be written as the summation of powers of 2.

n = (2^x + 2^y + 2^1)

When you divide something in half. A power is taken away.
(2^x + 2^y + 2^1) /2^1 = 2^x + 2^y + 2^1 + 2^-1 = 2^x + 2^y + 2^0

(2^x + 2^y + 2^1) /2^1 = 2^(x-1) + 2^(y-1) + 2^0= 2^(x-1) + 2^(y-1) + 2^0

This of course leads to case 2. because 2^0 =1 meaning n is now odd.
Case 2:
When 2 odd numbers are added together that make an even. When 2 even numbers are added together the result is even.

n is odd. 3n+1 = n+n+n+1 = (2n) + (n+1)

As we see this creates an even number that is the summation of 2 even numbers. 2n is even because 2 odd added together make even. And n+1 is even because an odd plus an odd make an even. Taken together, even plus even make an even.

More so if I write n as ?+2^0 then I can tell that the oddness in n is turned into 4 by step 2.

(?+1) + (?+1) = 2?+2
plus
(?+1) +1 = ?+2

3(2^(x-1) + 2^(y-1) + 2^0)+1=3(2^(x-1) + 2^(y-1) )+4=3(2^(x-1) + 2^(y-1) )+2^2

step1 (dividing by 2) will continue until a n is once again n+2^0. Then 4 is added again.


(3(2^(x-1) + 2^(y-1) )+2^2)/2=3(2^(x-2) + 2^(y-2) )+2^1 still even assuming x and y are larger than 2
(3(2^(x-2) + 2^(y-2) )+2^1)/2=3(2^(x-3) + 2^(y-3) )+2^0 odd assuming x and y greater than 3
(3(2^(x-3) + 2^(y-3) )+2^0)*3+1=9(2^(x-3) + 2^(y-3) )+2^2

By induction I see that eventual ? in n will be divisible by 2 and no longer odd. In which case step 1 will happen again. An the cycle continues until step reduces to 2. Then to 1.

Why is this not a proof by induction for all and any integer greater than 1?
Proof by induction is a rigorous mathematical technique which you have not followed. If your method was a proof it would have been found in 1937 when the conjecture was first suggested. What you do not address in your proof is the possibility of an infinite loop. Can we be sure that you never get the same answer twice in a sequence? If we do get a repeat then we are in stuck in a loop.
Proof by induction here would be to prove that any number 2n+2 will eventually become the number 2n. This would be sufficient to prove the conjecture. However this is impossible or someone would have done it by now.

There is a loop it starts at 8. 4 2 1

Any loop starting 2^2n ends in 1. It can be shown by induction that for any positive integer value of n there is an integer number m such that 3m+1=2^2n.

The question is does it have any other loops.

And 8 is interesting in that 2n equals 3(sqrt(3n+1)/2)+1

The quadratic equation you have produced has solutions n=2.7991, n=-0.1116?
Did you mean m= ((2^2n)-1)/3 ? m= 1 ,5 ,21 ,85 ,341...

The difference between n^2 and (n+1)^2 is 2n+1.

Square numbers are a subset of all integer numbers?

I was asking why it wasn't a proof.

I told you why. Infinite loops have to be explicitly dis-proven.

The real quedtion for me that would make a proof is how high does the series go based on the shape of the number before it nose dives down.

Potentially infinitely high, this is one of the main problems to a proof.

If one can prove n becomes double or triple even then plummets below n. Well then every cycle will end in 1.

Consider the number given by 2^0+2^1+2^2+2^3+2^4+...+2^n, where n is arbitrarily large. This series will, I think I am right in saying, alternate between tripling and then halving continuously. It grows in a near exponential fashion. Since n can be arbitrarily large then this series grows near exponentially to an arbitrarily large number. If it is a finite series it will eventually start to reduce, but if it returns to a previous value it will hit an infinite loop. This is the second major problem in the proof, showing that no infinite loops exist.
Dirty.Harry
Posts: 1,584
Add as Friend
Challenge to a Debate
Send a Message
1/27/2016 12:36:18 PM
Posted: 10 months ago
At 1/27/2016 11:26:05 AM, chui wrote:
At 1/26/2016 7:15:39 PM, Mhykiel wrote:
At 1/26/2016 4:38:21 PM, chui wrote:
At 1/24/2016 6:43:23 PM, Mhykiel wrote:
At 1/24/2016 12:13:49 PM, chui wrote:
At 1/24/2016 6:23:32 AM, Mhykiel wrote:
My question is since it is true that all even numbers can be written as the sum of distinct powers of two and step 2 creates even numbers and step 1 reduces distinct powers of two then isn't it a proof by induction that the conjecture is true for all numbers?

Here is an algorithm that you may be unaware off:
1 Assume you am wrong
2 Look for your error
3 Find your error
4 Learn something new

Try converting your word description of your possible solution to algebraic expressions. Your error becomes obvious then.

Why don't you just speak plainly of what you think I have missed.

Case 1: (n is even)
All even numbers can be written as the summation of powers of 2.

n = (2^x + 2^y + 2^1)

When you divide something in half. A power is taken away.
(2^x + 2^y + 2^1) /2^1 = 2^x + 2^y + 2^1 + 2^-1 = 2^x + 2^y + 2^0

(2^x + 2^y + 2^1) /2^1 = 2^(x-1) + 2^(y-1) + 2^0= 2^(x-1) + 2^(y-1) + 2^0

This of course leads to case 2. because 2^0 =1 meaning n is now odd.
Case 2:
When 2 odd numbers are added together that make an even. When 2 even numbers are added together the result is even.

n is odd. 3n+1 = n+n+n+1 = (2n) + (n+1)

As we see this creates an even number that is the summation of 2 even numbers. 2n is even because 2 odd added together make even. And n+1 is even because an odd plus an odd make an even. Taken together, even plus even make an even.

More so if I write n as ?+2^0 then I can tell that the oddness in n is turned into 4 by step 2.

(?+1) + (?+1) = 2?+2
plus
(?+1) +1 = ?+2

3(2^(x-1) + 2^(y-1) + 2^0)+1=3(2^(x-1) + 2^(y-1) )+4=3(2^(x-1) + 2^(y-1) )+2^2

step1 (dividing by 2) will continue until a n is once again n+2^0. Then 4 is added again.


(3(2^(x-1) + 2^(y-1) )+2^2)/2=3(2^(x-2) + 2^(y-2) )+2^1 still even assuming x and y are larger than 2
(3(2^(x-2) + 2^(y-2) )+2^1)/2=3(2^(x-3) + 2^(y-3) )+2^0 odd assuming x and y greater than 3
(3(2^(x-3) + 2^(y-3) )+2^0)*3+1=9(2^(x-3) + 2^(y-3) )+2^2

By induction I see that eventual ? in n will be divisible by 2 and no longer odd. In which case step 1 will happen again. An the cycle continues until step reduces to 2. Then to 1.

Why is this not a proof by induction for all and any integer greater than 1?
Proof by induction is a rigorous mathematical technique which you have not followed. If your method was a proof it would have been found in 1937 when the conjecture was first suggested. What you do not address in your proof is the possibility of an infinite loop. Can we be sure that you never get the same answer twice in a sequence? If we do get a repeat then we are in stuck in a loop.
Proof by induction here would be to prove that any number 2n+2 will eventually become the number 2n. This would be sufficient to prove the conjecture. However this is impossible or someone would have done it by now.

There is a loop it starts at 8. 4 2 1

Any loop starting 2^2n ends in 1. It can be shown by induction that for any positive integer value of n there is an integer number m such that 3m+1=2^2n.

The question is does it have any other loops.

And 8 is interesting in that 2n equals 3(sqrt(3n+1)/2)+1

The quadratic equation you have produced has solutions n=2.7991, n=-0.1116?
Did you mean m= ((2^2n)-1)/3 ? m= 1 ,5 ,21 ,85 ,341...

The difference between n^2 and (n+1)^2 is 2n+1.

Square numbers are a subset of all integer numbers?

I was asking why it wasn't a proof.

I told you why. Infinite loops have to be explicitly dis-proven.

The real quedtion for me that would make a proof is how high does the series go based on the shape of the number before it nose dives down.

Potentially infinitely high, this is one of the main problems to a proof.

If one can prove n becomes double or triple even then plummets below n. Well then every cycle will end in 1.

Consider the number given by 2^0+2^1+2^2+2^3+2^4+...+2^n, where n is arbitrarily large. This series will, I think I am right in saying, alternate between tripling and then halving continuously. It grows in a near exponential fashion. Since n can be arbitrarily large then this series grows near exponentially to an arbitrarily large number. If it is a finite series it will eventually start to reduce, but if it returns to a previous value it will hit an infinite loop. This is the second major problem in the proof, showing that no infinite loops exist.

Which may be equivalent to Turing's halting problem - and therefore unprovable.
Ramshutu
Posts: 4,063
Add as Friend
Challenge to a Debate
Send a Message
1/27/2016 10:12:41 PM
Posted: 10 months ago
At 1/23/2016 8:02:41 PM, Mhykiel wrote:
This is a unique problem that gets played with by amateurs a lot. It's known by a few different names. Such as the Collatz, Ulam, or Syracuse Conjecture.

The Conjecture has gone unproven despite many mathematicians and minds looking at it. Some become passionate about it's relevance while others are less interested in proving it correct. The Conjecture is given a series constructed from 2 steps: 1. Divide by 2 if Even. 2. multiply by 3 and add 1 if odd. Given those rules any natural integer over 0 will always end in 1.

f(n) { n/2 IF n is even OR 3n+1 if odd.}

Example: n = 7
Series would be:
7 (7 is odd so 3(7)+1)
22 (even so 22/2)
11 (odd so 3(11)+1)
34 (even 34/2)
16 (even 16/2)
8 (even 8/2)
4 (even 4/2)
2 (even 2/2)
1 (halt on 1.)

The idea is that no matter what number you start with you will end up with 1. Series where (n) is 1 to billions have been completed and all end in 1.

I'm asking why do people think this has not been proven yet?

If the heuristic argument shows that the orbit is shrinking. Take that with every number can be written as the summation of powers of 2. take that step 2 transforms a number to be pushed to step1. (every ascending step will be followed by a descending step) So isn't this proof enough?

This is an interesting one!

The basic conditions seem to point to why it hasn't been solved yet and when you analyze them in a little detail, it shows the point.

An even number, when plugged into the algorithm, may come out as an odd number.

An odd number, when plugged into the algorithm, will always come out even.

This means, if you have an odd number; it increases by 3n+1, but there is a 50% chance of any odd number subsequently decreasing by n/4 (if 3n+1 is divisible by 4), a 25% change of it decreasing by n/8 (if 3n+1 is divisible by 8), 12.5% of it decreasing by n/16, etc.

Statistically speaking, any random number you chose is likely to decrease for this reason, because there is a greater chance at any point of it decreasing more than increasing.

But showing it is at least statistically unlikely to be anything other than 1, it is not the same as showing it's impossible.

To show it's impossible, you have to be able to show two things.

First: that there are no conditions in which F(n) = n ; where F = your algorithm iterating X times. IE there is no number you can chose which will eventually yield itself when plugging successive numbers into the function (. IE: the function will loop forever and not reach 1.

Second: that there are no numbers in which F(n) will always or mostly generate a number divisible by only 2 and not any other factor of 2. (IE: the value will keep increasing).

They both sound easy, but it's all to do with distribution of primes, and a variety of things that when you think about are actually really hard to mathematically prove.
Mhykiel
Posts: 5,987
Add as Friend
Challenge to a Debate
Send a Message
1/28/2016 7:20:02 PM
Posted: 10 months ago
At 1/27/2016 11:26:05 AM, chui wrote:
At 1/26/2016 7:15:39 PM, Mhykiel wrote:
At 1/26/2016 4:38:21 PM, chui wrote:
At 1/24/2016 6:43:23 PM, Mhykiel wrote:
At 1/24/2016 12:13:49 PM, chui wrote:
At 1/24/2016 6:23:32 AM, Mhykiel wrote:
My question is since it is true that all even numbers can be written as the sum of distinct powers of two and step 2 creates even numbers and step 1 reduces distinct powers of two then isn't it a proof by induction that the conjecture is true for all numbers?

Here is an algorithm that you may be unaware off:
1 Assume you am wrong
2 Look for your error
3 Find your error
4 Learn something new

Try converting your word description of your possible solution to algebraic expressions. Your error becomes obvious then.

Why don't you just speak plainly of what you think I have missed.

Case 1: (n is even)
All even numbers can be written as the summation of powers of 2.

n = (2^x + 2^y + 2^1)

When you divide something in half. A power is taken away.
(2^x + 2^y + 2^1) /2^1 = 2^x + 2^y + 2^1 + 2^-1 = 2^x + 2^y + 2^0

(2^x + 2^y + 2^1) /2^1 = 2^(x-1) + 2^(y-1) + 2^0= 2^(x-1) + 2^(y-1) + 2^0

This of course leads to case 2. because 2^0 =1 meaning n is now odd.
Case 2:
When 2 odd numbers are added together that make an even. When 2 even numbers are added together the result is even.

n is odd. 3n+1 = n+n+n+1 = (2n) + (n+1)

As we see this creates an even number that is the summation of 2 even numbers. 2n is even because 2 odd added together make even. And n+1 is even because an odd plus an odd make an even. Taken together, even plus even make an even.

More so if I write n as ?+2^0 then I can tell that the oddness in n is turned into 4 by step 2.

(?+1) + (?+1) = 2?+2
plus
(?+1) +1 = ?+2

3(2^(x-1) + 2^(y-1) + 2^0)+1=3(2^(x-1) + 2^(y-1) )+4=3(2^(x-1) + 2^(y-1) )+2^2

step1 (dividing by 2) will continue until a n is once again n+2^0. Then 4 is added again.


(3(2^(x-1) + 2^(y-1) )+2^2)/2=3(2^(x-2) + 2^(y-2) )+2^1 still even assuming x and y are larger than 2
(3(2^(x-2) + 2^(y-2) )+2^1)/2=3(2^(x-3) + 2^(y-3) )+2^0 odd assuming x and y greater than 3
(3(2^(x-3) + 2^(y-3) )+2^0)*3+1=9(2^(x-3) + 2^(y-3) )+2^2

By induction I see that eventual ? in n will be divisible by 2 and no longer odd. In which case step 1 will happen again. An the cycle continues until step reduces to 2. Then to 1.

Why is this not a proof by induction for all and any integer greater than 1?
Proof by induction is a rigorous mathematical technique which you have not followed. If your method was a proof it would have been found in 1937 when the conjecture was first suggested. What you do not address in your proof is the possibility of an infinite loop. Can we be sure that you never get the same answer twice in a sequence? If we do get a repeat then we are in stuck in a loop.
Proof by induction here would be to prove that any number 2n+2 will eventually become the number 2n. This would be sufficient to prove the conjecture. However this is impossible or someone would have done it by now.

There is a loop it starts at 8. 4 2 1

Any loop starting 2^2n ends in 1. It can be shown by induction that for any positive integer value of n there is an integer number m such that 3m+1=2^2n.

The question is does it have any other loops.

And 8 is interesting in that 2n equals 3(sqrt(3n+1)/2)+1

The quadratic equation you have produced has solutions n=2.7991, n=-0.1116?
Did you mean m= ((2^2n)-1)/3 ? m= 1 ,5 ,21 ,85 ,341...

No I should have wrote 2n = 3(square root of ((3n+1)/2)+1


The difference between n^2 and (n+1)^2 is 2n+1.

Square numbers are a subset of all integer numbers?

Yes I bring it up as an interesting thing I see. Every square array has a legs of n. But also a diagonal of n. Then 2n+1creates the consecutive higher square array.(well the next higher square arrays legs and diagonal)

It appears eventually step 2 followed by one will find a perfect square array one that is divisible by 4


I was asking why it wasn't a proof.

I told you why. Infinite loops have to be explicitly dis-proven.

Yes. Thank you

The real quedtion for me that would make a proof is how high does the series go based on the shape of the number before it nose dives down.

Potentially infinitely high, this is one of the main problems to a proof.

What if a function that takes in the natural number and spits out how many terms that series will have was found? Would that discount a infinitly high climb?


If one can prove n becomes double or triple even then plummets below n. Well then every cycle will end in 1.

Consider the number given by 2^0+2^1+2^2+2^3+2^4+...+2^n, where n is arbitrarily large. This series will, I think I am right in saying, alternate between tripling and then halving continuously. It grows in a near exponential fashion. Since n can be arbitrarily large then this series grows near exponentially to an arbitrarily large number. If it is a finite series it will eventually start to reduce, but if it returns to a previous value it will hit an infinite loop. This is the second major problem in the proof, showing that no infinite loops exist.

That series grows exponitially I don't see any halving. But when a power of 2 is gotten like 128 the step one of yhe conjecture nose dives it to 1.

Wouldn't it be a proof if every natural number transformed by interations of (3n+1)/2 would eventualy become a square array number?

Maybe something like the series from odd numbers that go 2, 5, 8, 11, ...
F(n)=x that would be for n is odd x+((x+1)/2)

Which is 3n+1"2

Where it meets with x^2