fork(1) download
copy 
  1. let max = 1000001L
  2. let memo = Array.create (max|>int) 0L
  3.  
  4. let nextCollatz (n:int64) = 
  5.     if n%2L = 0L then n/2L else 3L*n+1L
  6.  
  7. // Computes Collatz sequence length, given a
  8. // positive integer, x.   
  9. let rec collatzSeqLength (x:int64):int64 = 
  10.  
  11.   let rec seqLength' (n:int64)  contd = 
  12.     match n with 
  13.     | 1L        -> contd 1L // initalizing sequence length with 1 
  14.     | _         -> 
  15.       if n < max && memo.[n|>int] <> 0L then 
  16.         contd memo.[n|>int]
  17.       else 
  18.         seqLength' (nextCollatz n) (fun x -> 
  19.                                       let x' = x+1L //incrementing length and storing it in memo.
  20.                                       if n<max then 
  21.                                         memo.[n|>int] <- x'
  22.                                       else
  23.                                         ()
  24.                                       contd x'
  25.                                   )
  26.  
  27.   x|>(fun i -> seqLength' i id)
  28.  
  29.  
  30. let maxCollazSeqLength (x:int64,y:int64) = 
  31.   let x',y' = System.Math.Min(x,y), System.Math.Max(x,y)
  32.  
  33.   seq[x'..y'] 
  34.   |> Seq.fold (fun max x -> 
  35.                     let r = collatzSeqLength x
  36.                     if r > max then r else max) 0L
  37.  
  38. let maxCollazSeqLength'' (x:int64,y:int64) = 
  39.   let x',y' = System.Math.Min(x,y), System.Math.Max(x,y)
  40.  
  41.   seq[x'..y'] 
  42.   |> Seq.map collatzSeqLength 
  43.   |> Seq.max
  44.  
  45.  
  46.  
  47. // Iterative version   
  48. let maxCollazSeqLength' (x:int64,y:int64) = 
  49.   let x',y' = System.Math.Min(x,y), System.Math.Max(x,y)
  50.   let mutable maxL = 0L
  51.   let mutable num = 0
  52.  
  53.   for i=(x'|>int) to (y'|>int) do 
  54.     let r = collatzSeqLength (i|>int64) 
  55.     if r>maxL then
  56.       maxL <- r 
  57.       num  <- i
  58.     else 
  59.       ()
  60.   maxL,num
  61.  
  62.  
  63. // IO stuff   
  64. let solvePROBTNPO() = 
  65.   let mutable (line:string) = System.Console.ReadLine();
  66.  
  67.   while line <> null do
  68.     let args = line.Split()
  69.     let x,y  = args.[0],args.[1]
  70.  
  71.     (x|>int64,y|>int64)
  72.     |> maxCollazSeqLength
  73.     |> printfn "%s %s %d" x y
  74.  
  75.     line <- System.Console.ReadLine()
  76.  
  77. solvePROBTNPO()
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
Success #stdin #stdout 0.13s 22568KB
comments (?)
stdin
copy 
1 10
100 200
201 210
900 1000
stdout
copy 
1 10 20
100 200 125
201 210 89
900 1000 174
https://ideone.com/egk3zI
language:
F# (mono 4.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!