50 lines
1,015 B
Text
50 lines
1,015 B
Text
import system'collections;
|
|
import extensions;
|
|
|
|
const int maxNumber = 100000;
|
|
|
|
Hailstone(int n,Map<int,int> lengths)
|
|
{
|
|
if (n == 1)
|
|
{
|
|
^ 1
|
|
};
|
|
|
|
while (true)
|
|
{
|
|
if (lengths.containsKey(n))
|
|
{
|
|
^ lengths[n]
|
|
}
|
|
else
|
|
{
|
|
if (n.isEven())
|
|
{
|
|
lengths[n] := 1 + Hailstone(n/2, lengths)
|
|
}
|
|
else
|
|
{
|
|
lengths[n] := 1 + Hailstone(3*n + 1, lengths)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
public program()
|
|
{
|
|
int longestChain := 0;
|
|
int longestNumber := 0;
|
|
auto recursiveLengths := new Map<int,int>(4096,4096);
|
|
|
|
for(int i := 1, i < maxNumber, i+=1)
|
|
{
|
|
var chainLength := Hailstone(i, recursiveLengths);
|
|
if (longestChain < chainLength)
|
|
{
|
|
longestChain := chainLength;
|
|
longestNumber := i
|
|
}
|
|
};
|
|
|
|
console.printFormatted("max below {0}: {1} ({2} steps)", maxNumber, longestNumber, longestChain)
|
|
}
|