Skip to content

Instantly share code, notes, and snippets.

@mrmikejones
Created March 5, 2013 10:05
Show Gist options
  • Save mrmikejones/5089229 to your computer and use it in GitHub Desktop.
Save mrmikejones/5089229 to your computer and use it in GitHub Desktop.
Find the longest Collatz chain below the input number
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static uint CollatzNumber(uint number)
{
if (number % 2 == 0)
{
return number / 2;
}
return 1 + (number * 3);
}
static void Main(string[] args)
{
Dictionary<uint, uint> dictionary = new Dictionary<uint, uint>();
uint chainlength = 0;
uint maxchainlength = 0;
uint startnumber = 0;
uint maxnum = 0;
Console.WriteLine("Enter max number");
string input = Console.ReadLine();
while (!uint.TryParse(input, out maxnum))
{
Console.WriteLine("Not a recognised number, try again");
input = Console.ReadLine();
}
for(uint count = 0; count < maxnum; count++)
{
Console.Write("\r{0:F2}%: {1} {2} ", ((float)count / (float)maxnum) * 100.0f, count, maxchainlength);
chainlength = 1;
uint number = count;
while (number > 1)
{
if(dictionary.ContainsKey(number))
{
chainlength += dictionary[number];
number = 1;
}
else
{
chainlength++;
number = Program.CollatzNumber(number);
}
}
if(chainlength > maxchainlength)
{
maxchainlength = chainlength;
startnumber = count;
dictionary.Add(count, chainlength);
}
}
Console.Write("\r");
Console.WriteLine("Longest chain under {0} is {1} generated by {2}", maxnum, chainlength, startnumber);
Console.WriteLine("Press any key to quit");
Console.ReadLine();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment