Collatz Conjecture

[NortonH]

This is a simple but elusive problem that has been around for years and defeated some of the best mathematicians who have attempted it.

It is also known as the hail stone problem, for obvious reasons.

I think I might have a proof of it but need to check that I have not missed anything.

For those who are interested i believe that i have proved it in the affirmative and that no counterexamples exist.

Are there any experts out there who can lend a hand checking my work?

 

[taeto]

Sure, bring it on

[koti]

Oh this is gonna be good, I can’t wait.

[taeto]

2 hours ago, koti said:

I can’t wait.

Do not worry: he will want to check every detail in his argument first. Diligence is supposed to be the mother of good luck. Possibly a distant aunt, whatever.

[Strange]

5 hours ago, NortonH said:

It is also known as the hail stone problem, for obvious reasons.

I had to look it up to find out what this "obvious" reason was

 

[Sensei]

To make tiny senseful contribution to this thread, I made quickly C/C++ program to generate Collatz Problem sequence integers.

Source code is attached in archive.

/*
 * CollatzProblem v1.0 created by Sensei (c) Aug 2018
 */

#include <stdio.h>
#include <stdlib.h>

void CollatzProblem( int value )
{
	for(;;)
	{
		printf( "%d ", value );
		if( value == 1 ) break;
		if( ( value & 0x1 ) == 0 )
		{
			value /= 2;
		}
		else
		{
			value = value * 3 + 1;
		}
	}
}

int main( int argc, int *argv[] )
{
	if( argc >= 2 )
	{
		const char *buffer = (const char *) argv[ 1 ];
		int value = atoi( buffer );
		CollatzProblem( value );
	}
	else
	{
		printf( "Usage:\r\nCollatzProblem.exe [value]\r\n" );
	}
	return( 0 );
}

CollatzProblem.zip

ps. If you want to test also negative integers, add lines:

if( value == -1 ) break;

if( value == -5 ) break;

if( value == -68 ) break;

 

Edited August 17, 2018 by Sensei

[taeto]

Your code is missing the line of output which says "your input is a counterexample" 

[Sensei]

2 minutes ago, taeto said:

Your code is missing the line of output which says "your input is a counterexample" 

But such input would cause endless loop, which will be instantly visible..

 

[koti]

As far as I know the proof is to be considered to be one of the most complex problems to ever exist in mathematics hence my anticipation.

[taeto]

38 minutes ago, Sensei said:

But such input would cause endless loop, which will be instantly visible..

Are you sure of that? 

36 minutes ago, koti said:

As far as I know the proof is to be considered to be one of the most complex problems to ever exist in mathematics hence my anticipation.

Pál Erdős said once, and maybe it was more than once, that mathematics in its current state is not yet mature enough to solve a problem like this.

But then, the time may come when powerful enough techniques become developed. Maybe soon we will see.  

[wtf]

I hope this isn't going to be one of those probabalistic arguments. Half the integers are even, half are odd. If you pick an even n you make it n/2. If you pick an odd n you make it 3n + 1, then since that number is even on the next step you make it (3/2)n + 1/2. So over time you're multiplying by 3/2 and dividing by 2. The limit goes to 0 therefore all numbers eventually go to 1. This is a fairly common false proof. You have to prove it for all n, not just the behavior of n in the limit.

I've seen more than one version of this over the years.

Edited August 17, 2018 by wtf

[NortonH]

Thanks WTF, you make a good point.

I have not chosen a probabilistic argument but, following your advice, I have given my proof some extra scrutiny.

I have identified a weakness in my proof and so am in the process of buttressing it. Everything hangs on the properties of prime numbers and how they relate to even numbers. It seemed obvious that even numbers can be composed of the sum of two primes but then i realised that i need to prove that for my overall proof to be rigorous.

Watch this space.

[wtf]

1 hour ago, NortonH said:

Thanks WTF, you make a good point.

I have not chosen a probabilistic argument but, following your advice, I have given my proof some extra scrutiny.

I have identified a weakness in my proof and so am in the process of buttressing it. Everything hangs on the properties of prime numbers and how they relate to even numbers. It seemed obvious that even numbers can be composed of the sum of two primes but then i realised that i need to prove that for my overall proof to be rigorous.

Watch this space.

The claim that every even number is the sum of two primes is the famous Goldbach conjecture. It's an open problem.

https://en.wikipedia.org/wiki/Goldbach's_conjecture

If you have a proof that Collatz depends on Goldbach that in itself would be valuable. I would say it's unlikely you have such a proof but if you do you'll get famous, even without solving Collatz.

[taeto]

+1 for rediscovering the Goldbach conjecture 

[NortonH]

No. I'm stuck. I missed something else and now i think i am in a state beyond repair.

 

[wtf]

4 hours ago, NortonH said:

No. I'm stuck. I missed something else and now i think i am in a state beyond repair.

 

Congratulations on being able to recognize that. It's the beginning of learning.

[studiot]

5 hours ago, wtf said:

Congratulations on being able to recognize that. It's the beginning of learning.

I'll second that and add a +1 for encouragement.