Search

Categories

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Send mail to the author(s) E-mail

# Friday, 09 October 2015

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

// Prime number generator - it can only divide by itself and 1 let primes = [for i in [3..2..7000] do let divisors = [3..2..i/2-1] let mutable isPrime = true for j in divisors do if i % j = 0 then isPrime <- false if isPrime then yield i] // largest prime factor.. notice I on the end to denote a bigint let num = 600851475143I for i in primes do if num % (bigint(i)) = 0I then printfn "%i is a factor" i // 6857

converting an int to a bigint was tricky to find.  As only  then could I divide a bigint by a bigint to check if it was a prime factor.

Note 7000.. could go up to int64 (sqrt(double num)).. but this takes a lot of time.

Functional Style
Much faster, and using sequences instead of a list above:

let maximumPossibleDivisor n = int64 (sqrt(double(n))) let factorsOf n = [3L..2L..maximumPossibleDivisor(n)] |> Seq.filter (fun x -> n % x = 0L) let isPrime n = factorsOf(n) |> Seq.length = 0 let findMaxPrimeFactorOf n = [3L..2L..maximumPossibleDivisor(n)] |> Seq.filter (fun x -> n % x = 0L) |> Seq.filter isPrime |> Seq.max let maxPrime = findMaxPrimeFactorOf(600851475143L) printfn "%A" maxPrime

Explanation

  • We only need to check up to the Sqrt of maxPrime for it’s prime factors eg for 13195, the sqrt is 114
  • Get a sequence of factors eg 3,5,7,9..113
  • IsPrime n… checks to see if any 13195 is divisible by any of the sequence above
| | # 
# Wednesday, 07 October 2015
( c# | Euler | Euler Functional | F# )

https://projecteuler.net/archives  is a fantastic list of puzzles which are solvable by programming.

I find them excellent for exploring into a language.

https://github.com/djhmateer/Euler

Strategy is to explore F#, then see how in C# it can be written

Problem1

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.

F#

// Solution5 - List.filter let total' = [1..999] // filter on a function (predicate) |> List.filter(fun i -> i % 5 = 0 || i % 3 = 0) |> List.sum printfn "result %i" total

C#

// Solution 1 - Iterative approach int sum = 0; for (int i = 1; i < 1000; i++) { if (i % 3 == 0 || i % 5 == 0) sum += i; } Console.WriteLine(sum); // Solution 2 - F# inspired solution - using Enumerable var result = Enumerable.Range(1, 999).Where(x => x % 3 == 0 || x % 5 == 0).Sum(); Console.WriteLine(result);
| | # 

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.

F# Iterative

module Euler2 // using a top level function as debugging experience better let Solution1() = // iterative.. a b temp let mutable a = 1 let mutable b = 1 let mutable sum = 0 while b <= 4000000 do if (b%2=0) then sum <- sum + b let temp = a + b a <- b b <- temp printfn "%A" sum // 4,613,732 Solution1()

F# Functional

//http://factormystic.net/blog/project-euler-in-fsharp-problem-2 // Some - given b.. if it is Some-thing.. return a Tuple with // first = b // second = a+b let fibGen (a,b) = Some(b, (b, a + b)) let fib = Seq.unfold(fibGen) (1,1) let results = fib |> Seq.takeWhile (fun x -> x < 4000000) for result in results do printfn "%A" result let sum = results |> Seq.filter(fun x -> x%2 = 0) |> Seq.sum printfn "%i" sum


C# Functional

//http://basildoncoder.com/blog/project-euler-problems-1-and-2.html static void Main() { var result = Fibs().TakeWhile(f => f < 4000000).Where(f => f % 2 == 0).Sum(); Console.WriteLine(result); } static IEnumerable<long> Fibs() { long a = 0, b = 1; while (true) { yield return b; b = a + b; a = b - a; } }

Very interesting implementation on an infinite list in C#
| | #