@anonymous/

# CharmingSuperbBlackandtancoonhound

## No description

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))

(*******  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...