Skip to content

Instantly share code, notes, and snippets.

@adilakhter adilakhter/gist:4991646
Last active Dec 13, 2015

Embed
What would you like to do?
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.