On the Collatz Conjecture
Solving Collatz Conjecture could bring instant happiness to your life... Fine, maybe not happiness, but approximately $1,000,000.00 based on my estimates of how famous you'll be.
Let's start with the conjecture, then we'll talk more:
Professor Collatz came up with this conjecture when he was only 22 years old, in 1932, while working on some graph construction problems. He himself made no progress in solving it. Almost 100 years later, and still very little progress has been made. It is one of the simplest open problems in modern mathematics, and yet one for which mathematicians have little to no clue on how to even begin to tackle it.
I wrote the code below to calculate it (also known as "the 3x+1 conjecture"), and using BigIntegers, you can try really big numbers. No matter how large you try, as far as I know, it always stops....
Cheers, ACC.
Collatz.exe 12332112332112332112332112332112332112332112332112332112332112332112332112332112332112332112332112344321
A.: 2434
using System;
Let's start with the conjecture, then we'll talk more:
prove that the code below always ends for any positive integer
Professor Collatz came up with this conjecture when he was only 22 years old, in 1932, while working on some graph construction problems. He himself made no progress in solving it. Almost 100 years later, and still very little progress has been made. It is one of the simplest open problems in modern mathematics, and yet one for which mathematicians have little to no clue on how to even begin to tackle it.
I wrote the code below to calculate it (also known as "the 3x+1 conjecture"), and using BigIntegers, you can try really big numbers. No matter how large you try, as far as I know, it always stops....
Cheers, ACC.
Collatz.exe 12332112332112332112332112332112332112332112332112332112332112332112332112332112332112332112332112344321
A.: 2434
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;
namespace Collatz
{
class Program
{
static void Main(string[] args)
{
BigInteger n = BigInteger.Parse(args[0]);
Console.WriteLine(_Collatz(n));
}
static int _Collatz(BigInteger n)
{
return (n == 1) ? 0 : (1 + _Collatz(n % 2 == 0 ? n / 2 : 3 * n + 1));
}
}
}
Proof by induction that ultimately a recursive call to a number = some pow(2) will be made which will stop the function after O(log x) calls
ReplyDeletewhen n=1 = 0th power of 2, it stops
when n=2= 1st power of 2 it stops after a single recursive call,
when n=3, _coll(3) --> _coll(10) --> _coll(5) --> _coll(16)
16 = 4th power of 2.
Once this is reached, calls will start reducing to _coll(8) --> _coll(4) --> _coll(2) --> _coll(1). STOP
thus, when n= n-1 or n, recursive calls will happen till 3n+1 leads to a number which is power of 2 and after that point calls will reduce logarithmically
Cool but how do you prove that recurrent calls to 3n+1 leads to a number that is power of 2?
Delete