# Project Euler in F# – Problems 1 – 3

## Problem 1

Find the sum of all the multiples of 3 or 5 below 1000.

Brute force is the first thing that comes to mind

```let problem1 () =
{1 .. 999}
|> Seq.filter (fun x -> (x % 3 = 0) || (x % 5 = 0))
|> Seq.sum
```

But the wise Euler shows Math to be a better tactic, as his answer is unquestionably faster.

```let problem1_correct () =
let target = 999

let sumDivisibleBy value =
let p = target / value
value * (p * (p + 1)) / 2

(sumDivisibleBy 3) + (sumDivisibleBy 5) - (sumDivisibleBy 15)
```

## Problem 2

Sum of all even Fibonacci numbers under 4 million

No real curveball here, unfold with a limit was the first Fibonacci method that came to mind

```let problem2 () =
let fibonacciSeq withLimit =
Seq.unfold (fun previousState ->
let nMinusTwo, nMinusOne = previousState
let nextValue = nMinusTwo + nMinusOne
let nextState = (nMinusOne, nextValue)

match nextValue < withLimit with
| true -> Some(nextValue, nextState)
| false -> None
) (0, 1)

fibonacciSeq 4000000
|> Seq.filter(fun x -> x % 2 = 0)
|> Seq.sum
```

## Problem 3

What is the largest prime factor of the number 600851475143?

This one might take a few tries to get correct. I actually went and completed a few other Euler problems before coming back to this one.

The sample number, 13195, is the red herring here because it is so easy to get the answer if you aren’t thinking.

```let problem3 () =
let testPrime (possiblePrime:int64) =
let sqrRootOfPrime = int64(System.Math.Sqrt(float(possiblePrime)))

{1L .. sqrRootOfPrime}
|> Seq.forall(fun divisor ->
match divisor with
| 1L -> true
| x when divisor = possiblePrime -> true
| _ -> possiblePrime % divisor > 0L)

let factorSeq ofNumber =
{2L .. (ofNumber/2L)}
|> Seq.filter(fun testNumber -> ofNumber % testNumber = 0L)
|> Seq.map(fun factor1 -> (factor1, (ofNumber / factor1)))
|> Seq.takeWhile(fun (factor1, factor2) -> factor1 <= factor2)
|> Seq.fold (fun acc (factor1, factor2) -> factor1 :: factor2 :: acc) []
|> Seq.sort
|> Seq.toList
|> List.rev

factorSeq 600851475143L
|> Seq.find (fun factor -> testPrime factor)
```

That was unofficially my fourth attempt.