let max = 1000001L
let memo = Array.create (max|>int) 0L
let nextCollatz (n:int64) =
if n%2L = 0L then n/2L else 3L*n+1L
// Computes Collatz sequence length, given a
// positive integer, x.
let rec collatzSeqLength (x:int64):int64 =
let rec seqLength' (n:int64) contd =
match n with
| 1L -> contd 1L // initalizing sequence length with 1
| _ ->
if n < max && memo.[n|>int] <> 0L then
contd memo.[n|>int]
else
seqLength' (nextCollatz n) (fun x ->
let x' = x+1L //incrementing length and storing it in memo.
if n<max then
memo.[n|>int] <- x'
else
()
contd x'
)
x|>(fun i -> seqLength' i id)
let maxCollazSeqLength (x:int64,y:int64) =
let x',y' = System.Math.Min(x,y), System.Math.Max(x,y)
seq[x'..y']
|> Seq.fold (fun max x ->
let r = collatzSeqLength x
if r > max then r else max) 0L
let maxCollazSeqLength'' (x:int64,y:int64) =
let x',y' = System.Math.Min(x,y), System.Math.Max(x,y)
seq[x'..y']
|> Seq.map collatzSeqLength
|> Seq.max
// Iterative version
let maxCollazSeqLength' (x:int64,y:int64) =
let x',y' = System.Math.Min(x,y), System.Math.Max(x,y)
let mutable maxL = 0L
let mutable num = 0
for i=(x'|>int) to (y'|>int) do
let r = collatzSeqLength (i|>int64)
if r>maxL then
maxL <- r
num <- i
else
()
maxL,num
// IO stuff
let solvePROBTNPO() =
let mutable (line:string) = System.Console.ReadLine();
while line <> null do
let args = line.Split()
let x,y = args.[0],args.[1]
(x|>int64,y|>int64)
|> maxCollazSeqLength
|> printfn "%s %s %d" x y
line <- System.Console.ReadLine()
solvePROBTNPO()
bGV0IG1heCA9IDEwMDAwMDFMCmxldCBtZW1vID0gQXJyYXkuY3JlYXRlIChtYXh8PmludCkgMEwKCmxldCBuZXh0Q29sbGF0eiAobjppbnQ2NCkgPSAKICAgIGlmIG4lMkwgPSAwTCB0aGVuIG4vMkwgZWxzZSAzTCpuKzFMCiAgCi8vIENvbXB1dGVzIENvbGxhdHogc2VxdWVuY2UgbGVuZ3RoLCBnaXZlbiBhCi8vIHBvc2l0aXZlIGludGVnZXIsIHguICAgCmxldCByZWMgY29sbGF0elNlcUxlbmd0aCAoeDppbnQ2NCk6aW50NjQgPSAKICAKICBsZXQgcmVjIHNlcUxlbmd0aCcgKG46aW50NjQpICBjb250ZCA9IAogICAgbWF0Y2ggbiB3aXRoIAogICAgfCAxTCAgICAgICAgLT4gY29udGQgMUwgLy8gaW5pdGFsaXppbmcgc2VxdWVuY2UgbGVuZ3RoIHdpdGggMSAKICAgIHwgXyAgICAgICAgIC0+IAogICAgICBpZiBuIDwgbWF4ICYmIG1lbW8uW258PmludF0gPD4gMEwgdGhlbiAKICAgICAgICBjb250ZCBtZW1vLltufD5pbnRdCiAgICAgIGVsc2UgCiAgICAgICAgc2VxTGVuZ3RoJyAobmV4dENvbGxhdHogbikgKGZ1biB4IC0+IAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxldCB4JyA9IHgrMUwgLy9pbmNyZW1lbnRpbmcgbGVuZ3RoIGFuZCBzdG9yaW5nIGl0IGluIG1lbW8uCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgbjxtYXggdGhlbiAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1lbW8uW258PmludF0gPC0geCcKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAoKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRkIHgnCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICApCgogIHh8PihmdW4gaSAtPiBzZXFMZW5ndGgnIGkgaWQpCgoKbGV0IG1heENvbGxhelNlcUxlbmd0aCAoeDppbnQ2NCx5OmludDY0KSA9IAogIGxldCB4Jyx5JyA9IFN5c3RlbS5NYXRoLk1pbih4LHkpLCBTeXN0ZW0uTWF0aC5NYXgoeCx5KQoKICBzZXFbeCcuLnknXSAKICB8PiBTZXEuZm9sZCAoZnVuIG1heCB4IC0+IAogICAgICAgICAgICAgICAgICAgIGxldCByID0gY29sbGF0elNlcUxlbmd0aCB4CiAgICAgICAgICAgICAgICAgICAgaWYgciA+IG1heCB0aGVuIHIgZWxzZSBtYXgpIDBMCiAgCmxldCBtYXhDb2xsYXpTZXFMZW5ndGgnJyAoeDppbnQ2NCx5OmludDY0KSA9IAogIGxldCB4Jyx5JyA9IFN5c3RlbS5NYXRoLk1pbih4LHkpLCBTeXN0ZW0uTWF0aC5NYXgoeCx5KQoKICBzZXFbeCcuLnknXSAKICB8PiBTZXEubWFwIGNvbGxhdHpTZXFMZW5ndGggCiAgfD4gU2VxLm1heAoKCgovLyBJdGVyYXRpdmUgdmVyc2lvbiAgIApsZXQgbWF4Q29sbGF6U2VxTGVuZ3RoJyAoeDppbnQ2NCx5OmludDY0KSA9IAogIGxldCB4Jyx5JyA9IFN5c3RlbS5NYXRoLk1pbih4LHkpLCBTeXN0ZW0uTWF0aC5NYXgoeCx5KQogIGxldCBtdXRhYmxlIG1heEwgPSAwTAogIGxldCBtdXRhYmxlIG51bSA9IDAKCiAgZm9yIGk9KHgnfD5pbnQpIHRvICh5J3w+aW50KSBkbyAKICAgIGxldCByID0gY29sbGF0elNlcUxlbmd0aCAoaXw+aW50NjQpIAogICAgaWYgcj5tYXhMIHRoZW4KICAgICAgbWF4TCA8LSByIAogICAgICBudW0gIDwtIGkKICAgIGVsc2UgCiAgICAgICgpCiAgbWF4TCxudW0KCgovLyBJTyBzdHVmZiAgIApsZXQgc29sdmVQUk9CVE5QTygpID0gCiAgbGV0IG11dGFibGUgKGxpbmU6c3RyaW5nKSA9IFN5c3RlbS5Db25zb2xlLlJlYWRMaW5lKCk7CgogIHdoaWxlIGxpbmUgPD4gbnVsbCBkbwogICAgbGV0IGFyZ3MgPSBsaW5lLlNwbGl0KCkKICAgIGxldCB4LHkgID0gYXJncy5bMF0sYXJncy5bMV0KICAgIAogICAgKHh8PmludDY0LHl8PmludDY0KQogICAgfD4gbWF4Q29sbGF6U2VxTGVuZ3RoCiAgICB8PiBwcmludGZuICIlcyAlcyAlZCIgeCB5CgogICAgbGluZSA8LSBTeXN0ZW0uQ29uc29sZS5SZWFkTGluZSgpCgpzb2x2ZVBST0JUTlBPKCkKCgoKCgo=