Files
  • main.fs
main.fs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
// Project Euler 1: Multiples of 3 and 5; 233168
// If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
// Find the sum of all the multiples of 3 or 5 below 1000. 

// Project Euler 2: Even Fibonacci numbers; 4613732
// Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
// 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
// By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
let rec fibsRec a b limit =
    if a + b < limit then
        let current = a + b
        let rest = fibsRec b current limit
        current :: rest
    else 
        []

// Project Euler 3: Largest prime factor; 6857
// The prime factors of 13195 are 5, 7, 13 and 29.
// What is the largest prime factor of the number 600851475143 ?
let findFactors (num:int64) =
    let upperBound = int64(System.Math.Sqrt(double(num)))
    [ 2L .. upperBound ] |> Seq.filter (fun x -> num % x = 0L)

let isPrime(num:int64) = findFactors(num) |> Seq.length = 0

let findMaxPrimeFactor(num:int64) =
    let upperBound = int64(System.Math.Sqrt(double(num)))

    [ 2L .. upperBound ] |> Seq.filter (fun x -> num % x = 0L)
                         |> Seq.filter isPrime
                         |> Seq.max

// Project Euler 4: Largest palindrome product; 906609
// A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
// Find the largest palindrome made from the product of two 3-digit numbers.
open System.Linq

let isPalindrome n =
    let charArray = n.ToString().ToCharArray()
    let revCharArray = Array.rev charArray
    charArray.SequenceEqual(revCharArray)

let findLargestPalindrome numbers =
    numbers |> List.collect (fun x -> numbers |> List.map (fun y -> x * y))
            |> Seq.filter isPalindrome
            |> Seq.max

// Project Euler 5: Smallest multiple; 232792560
// 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
// What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
let evenlyDivided(num, fact) = num % fact = 0
let evenlyDividedByAll(num, facts) = facts |> Seq.forall (fun x -> evenlyDivided(num, x))

let findSmallestMultiple(numbers) =
    let max = Array.max(numbers)
    Seq.unfold (fun x -> Some(x, x + 1)) 1
        |> Seq.map (fun x -> x * max)
        |> Seq.filter (fun x -> evenlyDividedByAll(x, numbers))
        |> Seq.head


(*******  Project Euler 1 : Sum of multiples of 3 and 5 ***************)

let sumFactorsOfNBelowK k n = 
    let m = ( k - 1 ) / n
    n * m * ( m + 1 ) / 2
    
let mod3or5 x =
    x % 3 = 0 || x % 5 = 0

let euler_1_org() = [ 1 .. 999 ] |> Seq.filter (fun x -> x % 3 = 0 || x % 5 = 0) |> Seq.sum
let euler_1a_org() = [ 1 .. 999 ] |> Seq.filter mod3or5 |> Seq.sum
let euler_1b_org() = { 1 .. 999 } |> Seq.filter mod3or5 |> Seq.sum

let euler_1_v2() = sumFactorsOfNBelowK 1000 3 + sumFactorsOfNBelowK 1000 5 - sumFactorsOfNBelowK 1000 15

// http://theburningmonk.com/project-euler-solutions/

(** Project Euler 2 : Sum of even Fibonacci under 4 million ***********)

let isEven n =
    n % 2 = 0

let euler_2_org() = 1 :: 2 :: (fibsRec 1 2 4000000) |> Seq.filter (fun x -> x % 2 = 0) |> Seq.sum
let euler_2_v2() = 1 :: 2 :: (fibsRec 1 2 4000000) |> Seq.filter isEven |> Seq.sum


(** Project Euler 3 : Max prime factor under 600851475143L ************)

let findMaxPrimeFactor_v2 (number:int64) =
    let mutable newNumber:int64 = number
    let mutable largestFactor = 0L
    
    let mutable counter = 2L
    while counter * counter <= newNumber do
        if newNumber % counter = 0L then
            newNumber <- newNumber / counter
            largestFactor <- counter
        else
            counter <- counter + 1L
 
    if newNumber > largestFactor then
       largestFactor <- newNumber
       
    largestFactor
    
let euler_3_org() = findMaxPrimeFactor 600851475143L
let euler_3_v2() = findMaxPrimeFactor_v2 600851475143L


(** Project Euler 4 : Largest palindrom of xxx*yyy ********************)

let findLargestPalindrome_v2 maximum minimum=
    seq { for x in { maximum .. -1 .. minimum } do
              for y in { x .. -1 .. minimum }  do
                  yield x * y }
    |> Seq.filter isPalindrome
    |> Seq.max

let findLargestPalindrome_v3 maximum minimum=
    let mutable maxPalindrome = 0
    let outer_max = maximum
    let outer_min = minimum
    let inner_min = minimum
    
    let mutable i = outer_max
    
    let mutable outerLoop = true
    while outerLoop do
        let mutable innerLoop = true
        let inner_max = i
        let mutable j = inner_max
        while innerLoop do
            let product = i * j
            
            if product < maxPalindrome then
                innerLoop <- false
                
            if isPalindrome product && product > maxPalindrome then
                maxPalindrome <- product
                
            j <- j - 1
            
            if j < inner_min then 
               innerLoop <- false
               
        i <- i - 1
        if i < outer_min then
           outerLoop <- false

    maxPalindrome
    
let euler_4_org() = findLargestPalindrome [ 100 .. 999 ]
let euler_4_v2() = findLargestPalindrome_v2 999 100
let euler_4_v3() = findLargestPalindrome_v3 999 100



(** Project Euler 5 : Smallest multiple of 1..20 **********************)

let smallestMultiple top =
    let mutable prod = 1
    for i in { 1 .. 20 } do
        let prevprod = prod
        while prod % i <> 0 do
            prod <- prod + prevprod

    prod

let rec reduce_helper original previous divisor =
    if previous % divisor = 0 then
        previous
    else
        reduce_helper original (previous + original) divisor

// Could replace the anonymous fun in the next segment 
let smallestMultipleReducer original divisor = 
    reduce_helper original original divisor
    
let smallestMultipleUsingReduction top =
    seq { 1 .. top } 
    |> Seq.reduce (fun original divisor -> 
          reduce_helper original original divisor )

let euler_5_org() = findSmallestMultiple [| 1 .. 20 |]
let euler_5_v2() = smallestMultiple 20
let euler_5_v3a() = smallestMultipleUsingReduction 20
let euler_5_v3b() = smallestMultipleUsingReduction 20

(** My timing function ************************************************)
let time f =
  let sw = System.Diagnostics.Stopwatch()
  sw.Start()
  let res = f()
  sw.Stop()
  (res, sw.Elapsed.TotalMilliseconds)
  
  
[<EntryPoint>]
let main argv =
    let (euler1, time1) = time euler_1_org
    let (euler1a, time1a) = time euler_1a_org
    let (euler1b, time1b) = time euler_1b_org
    let (euler1_v2, time1_v2) = time euler_1_v2

    printfn "Solution to Project Euler 1"
    printfn "  Org: %i in %f ms" euler1 time1 
    printfn "    A: %i in %f ms" euler1a time1a 
    printfn "    B: %i in %f ms" euler1b time1b 
    printfn "   v2: %i in %f ms" euler1_v2 time1_v2 
    
    let (euler2, time2) = time euler_2_org
    let (euler2_v2, time2_v2) = time euler_2_v2
    
    printfn "Solution to Project Euler 2"
    printfn "  Org: %i in %f ms" euler2 time2 
    printfn "  v2a: %i in %f ms" euler2_v2 time2_v2
    
    let (euler3, time3) = time euler_3_org
    let (euler3_v2, time3_v2) = time euler_3_v2

    printfn "Solution to Project Euler 3"
    printfn "  Org: %i in %f ms" euler3 time3 
    printfn "  v2 : %i in %f ms" euler3_v2 time3_v2 
    
    let (euler4, time4) = time euler_4_org
    let (euler4_v2, time4_v2) = time euler_4_v2
    let (euler4_v3, time4_v3) = time euler_4_v3

    printfn "Solution to Project Euler 4"
    printfn "  Org: %i in %f ms" euler4 time4 
    printfn "  v2 : %A in %f ms" euler4_v2 time4_v2 
    printfn "  v3 : %A in %f ms" euler4_v3 time4_v3 

    let (euler5, time5) = time euler_5_org
    let (euler5_v2, time5_v2) = time euler_5_v2
    let (euler5_v3a, time5_v3a) = time euler_5_v3a
    let (euler5_v3b, time5_v3b) = time euler_5_v3b
    
    printfn "Solution to Project Euler 5"
    printfn "  Org: %i in %f ms" euler5 time5 
    printfn "  v2 : %i in %f ms" euler5_v2 time5_v2 
    printfn "  v3a: %i in %f ms" euler5_v3a time5_v3a 
    printfn "  v3a: %i in %f ms" euler5_v3b time5_v3b 
    // Something strange is happening with regards to v3a & v3b which
    // should be identical coding...

    // System.Console.ReadLine() |> ignore
    0 // return an integer exit code