Project Euler - Problem #14

Description

• The following iterative sequence is defined for the set of positive integers:
•  - n → n/2 (n is even)
•  - n → 3n + 1 (n is odd)
• Using the rule above and starting with 13, we generate the following sequence:
• 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
• It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
• Which starting number, under one million, produces the longest chain?
• NOTE: Once the chain starts the terms are allowed to go above one million.

Solution(s)

//int64 is required because the remainders are larger than int32
let rec Collatz (n:int64) count =
    if n = 1L then
        count
    elif n % 2L > 0L then
        Collatz ((3L*n) + 1L) (count + 1)
    else
        Collatz (n/2L)  (count + 1)

let CollatzSequence start max =
    let nums = [start..max]
    let result = [ for i in nums -> Collatz (int64 i) 1 ]
    let longest = List.max result
    let idx = result |> List.findIndex (fun x -> x = longest)
    nums.[idx]

let LargestCollatzSequence = CollatzSequence 1 999999

Alternative Recursions for Collatz, including Terras

let rec CollatzSequence num count =
    if num = 1 then
        count
    else
        let rem = if num % 2 = 0 then num/2 else (3*num) + 1
        CollatzSequence rem (count+1)

let rec CollatzSequenceArray num count arr =
    if num = 1 then
        arr
    else
        let rem = if num % 2 = 0 then num/2 else (3*num) + 1
        let newArr = List.append  arr [rem]
        CollatzSequenceArray rem (count+1) newArr

let rec TerrasSequence num count =
    if num = 2 || count = 10 then
        count
    else
        let rem = if (num-1) % 2 = 0 then (num-1)/2 else (3*(num-1) + 1)/2
        TerrasSequence rem (count+1)

let rec TerrasSequenceArray num count arr =
    if num = 1 || count = 10 then
        arr
    else
        let rem = if num % 2 = 0 then num/2 else (3*(num) + 1)/2
        let newArr = List.append  arr [rem]
        TerrasSequenceArray rem (count+1) newArr
            
let unitTest4 = CollatzSequence 4 1      
let unitTest4_1 = CollatzSequenceArray 4 1 [4]      
let unitTest4_2 = TerrasSequence 4 1
let unitTest4_3 = TerrasSequenceArray 3 1 [3]