Learning F#

Description Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 20×20 grid? Solution Thanks to the following for providing the insight required to solve this, based on combinatronics: http://realultimateprogramming.blogspot.com/2009/03/project-euler-problem-15.html let rec factorialBI (n:bigint) (acc:bigint) =     if n <= 1I then         acc     else         let newAcc = n * acc         factorialBI (n-1I) newAcc let combine (sides:bigint) =           let factorial1 = factorialBI (sides * 2I) 1I     let factorial2 = factorialBI sides 1I     factorial1/(factorial2 * factorial2) let UT_combine_2 = combine 2I   let UT_combine_20 = combine 20I

Project Euler (PE) provides some statistics, but I wanted to see the effectiveness of the languages in solving problems.  Although PE lists Mathematica as number 1, and on balance of popularity and effectiveness it might be, it is not the language used to solve the highest proportion of problems.  For that, the language and programmers of the following are most effective. Frink (43%) PARI/GP (28%) Magma (21%) MUMPS (18%) Mathematica (17%) For comparison, the results of a few other oher languages Haskell (11%) Python (10%) Perl (10%) Ruby (9%) F# (9%) Scala (8%) C/C++ (8%) Java (8%) C# (8%) The entire list (Zipped Excel files):   ProjectEulerStats.zip

Description Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers. For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220. Evaluate the sum of all the amicable numbers under 10000. Solution (Improved) let DivisorsSum num = [1..num] |> List.filter (fun x -> num % x = 0 && x < num) |> List.sum let rec matchLists num max arr =     if num = max then         (List.sum arr)/2     else         let newTest = DivisorsSum num         let check = DivisorsSum(newTest)         if num = check && newTest <> check then             matchLists (num+1) max (List.append arr [newTest+check])         else             matchLists (num+1) max arr let UT_matchList

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

Description Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. Number is listed in solution, for brevity Solution //libraries for BitArray and BigInteger, respectively open System.Collections open System.Numerics //array of Big integer let hugeArray =     [|     37107287533902102798797998220837590246510135740250I;     46376937677490009712648124896970078050417018260538I;     74324986199524741059474233309513058123726617309629I;     91942213363574161572522430563301811072406154908250I;     23067588207539346171171980310421047513778063246676I;     89261670696623633820136378418383684178734361726757I;     28112879812849979408065481931592621691275889832738I;     44274228917432520321923589422876796487670272189318I;     47451445736001306439091167216856844588711603153276I;     70386486105843025439939619828917593665686757934951I;     62176457141856560629502157223196586755079324193331I;     649063524627419049291014324458138226633479447581

Description A Pythagorean triplet is a set of three natural numbers, a  b  c, for which, a2 + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc. Solution let triplets start last =     seq {for i in start..last do             for j in start..last do                 yield (float i,float j, sqrt(float((i*i) + (j*j))))} //functions to get at tuple elemets, instead of matching let first (x,y,z) = x let second (x,y,z) = y let third (x,y,z) = z let pythTriple1000_2 =     let values = triplets 1 1000 |> Seq.filter (fun x -> first(x) < second(x))     let filter = values |> Seq.filter (fun x -> first(x) + second(x) + third (x) = float 1000)     let result = filter |> Seq.map( fun x -> first(x) * second(x) * third (x))     (Seq.toArray result).[0]   

Description 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. Solution (Improved) The improvements are minor, but include a smaller corelation matrix amd more concise syntax. let corrMatrix start last =      seq {for i in start..last do           for j in start..last do                if i<  j then yield (i*j)}  let reverse (s:string) = new string(s |> Seq.toArray |> Array.rev) let palindromes =      (corrMatrix 100 999) |> Seq.filter (fun x -> string x = reverse(string x)) |> Seq.max Solution (Original) //function for reversing a string let reverse (s:string) = new string(s |> Seq.toArray |> Array.rev) //function to multiple each number in the series by itself, similar to a correlation matrix let corrMatrix start last =      seq {for i in start..last do           for j in start..l

I 'cheated' solving this, using a hint for a limit on higher-end of the primes, since there is no built-in way to calculate square roots of Big Integer, other than constructing my own function using the Babylonian, aka Newton's, method. Description The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143? Solution open System.Collections open System.Numerics let getPrimesInt64 max =   let primes = new BitArray(max+1, true)   seq { 2 .. max } |>   Seq.filter (fun n ->     if primes.[int n] then       for i in bigint n * bigint n..bigint n..bigint max do primes.[int i] <- false     primes.[int n]) //use this size for your array of primes //let unitTest_P3_PrimeFactors_1_7 = getPrimesInt64 1000000 let FindLargestPrimeFactor (n:BigInteger) =     let primes = getPrimesInt64 1000000     let filteredList = primes |> Seq.filter(fun x -> n % bigint x = 0I)     Seq.max filteredList let resul

Description The Fibonacci sequence is defined by the recurrence relation:     F_(n) = F_(n−1) + F_(n−2), where F_(1) = 1 and F_(2) = 1. Hence the first 12 terms will be:     F_(1) = 1     F_(2) = 1     F_(3) = 2     F_(4) = 3     F_(5) = 5     F_(6) = 8     F_(7) = 13     F_(8) = 21     F_(9) = 34     F_(10) = 55     F_(11) = 89     F_(12) = 144 The 12th term, F_(12), is the first term to contain three digits. What is the first term in the Fibonacci sequence to contain 1000 digits? Solution open System.Numerics //tail-recursion to return Fibonacci based on length of a number's string let rec fibsRecTailBigIntSingle (x:BigInteger) (y:BigInteger) acc max =     let lenY = (y.ToString()).Length     if lenY >= max then         acc + 1     else         let next = x + y         let item = acc + 1         fibsRecTailBigIntSingle y next item max let Prob25_1 = fibsRecTailBigIntSingle 1I 1I 1 1000

I'm fairly happy with this, since it executes speedily, and builds on prior work solving problems.  It uses a tail-recursive function and BigInteger to find the power, and a fairly straightforward conversion of the number in to a string, which it then sums. Description 215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 2^1000? Solution //tail-recursive function to sum array of BigInteger open System.Numerics let rec productBigInt (num:BigInteger) (power:BigInteger) (max:BigInteger) (acc:BigInteger) =     if  power = max  then         acc  * num     else         productBigInt num (power + 1I) max (num * acc) //smaller aspects of function ot solve problem let prodResult = productBigInt 2I 1I 1000I 1I let strCharProd = prodResult.ToString() let lenProd = strCharProd.Length //main to solve problem let sumPower =      let prodResult = productBigInt 2I 1I 1000I 1I     let strCharProd = prodResult.ToStr

Description The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. Solution open System.Collections open System.Numerics //gets primes but can't handle the number size //very fast, a huge improvement over prior code let getPrimes max =     let primes = new BitArray(max+1, true)     seq { 2 .. max } |>     Seq.filter (fun n ->         if primes.[int n] then             for i in int64 n * int64 n..int64 n..int64 max do primes.[int i] <- false         primes.[int n]) //same function, but written to use and return BigInteger let getPrimesBigInt max =     let primes = new BitArray(max+1, true)     seq { 2 .. max } |>     Seq.filter (fun n ->         if primes.[int n] then             for i in bigint n * bigint n..bigint n..bigint max do primes.[int i] <- false         primes.[int n]) //creates array of primes, up to 2MM let arrPrimeBigInt = Array.ofSeq(getPrimesBigInt 2000000) //recur

I was not entirely happy with the solution for this, primarily because of the time it takes to find the answer.  If I had more insight into the mathematical relationships between factor, the calculation would have been streamlined. Description 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? Overview for every number from 1 to some maximum (or until) check to see if any divisior from 1 to 20 has remainder Solution let remainders div num =     let divisors = [|1..div|]     let rem = divisors |> Array.map (fun d -> System.Math.DivRem(num,d))     rem let isEvenlyDivisble div num =      let resultPartial  = remainders div num     let resultRemainder = resultPartial |> Array.map (fun x -> snd(x))     let sum = Array.sum resultRemainder     if sum = 0 then         true     else         false let

Description n! means n  (n  1)  ...  3  2  1 Find the sum of the digits in the number 100! Solution //required library to handle very large numbers open System.Numerics //recursive factorial let rec factorialTailBigInt (n:BigInteger) : BigInteger =     if n <= 1I then          1I     else         n * factorialTailBigInt (n - 1I) //primary process let sumFactorial =      let resFactorialBigInt = factorialTailBigInt 100I     let strCharFactorial = resFactorialBigInt.ToString()     let max = strCharFactorial.Length     let arrNum = Array.create max 0         for i=0 to max-1 do         arrNum.[i] <- System.Convert.ToInt32(strCharFactorial.Chars(i).ToString())     Array.sum arrNum

Description Find the greatest product of five consecutive digits in the 1000-digit number. Solution //the string to process let arrStr = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909

Description By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number? Solution (Improved) My original solution was slow, and the code a bit ugly.  The new solution is more idiomatic and dynamic than the original. let isPrime n =     let upperBound = int32(sqrt(float(n)))     let allNumbers = [2..upperBound]     let divisors = allNumbers |> List.filter (fun div -> n % div = 0 && n <> div)     if List.length divisors = 0 then         true     else         false let rec recursePrimes num count max =     if count = max then         num-1     else         if isPrime num then             recursePrimes (num+1) (count+1) max         else             recursePrimes (num+1) (count) max let UT_recursePrimes = recursePrimes 2 0 10001 Solution (Original) open System let primeFind find =     let x = (find /10) * (find /10)     let upperBound = Convert.ToInt32(System.Math.S

Description The sum of the squares of the first ten natural numbers is, 12 + 22 + ... + 102 = 385 The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)2 = 552 = 3025 Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025  385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum. Solution (Improved) More concise ways than the original solution. let sqrSumNat2 listNat = Array.sum listNat |> (fun x -> x*x) let sumSqrListNat2 listNat = listNat |> Array.map (fun x -> x * x ) |> Array.sum let diffNat100_2 = sqrSumNat2 [|1..100|] - sumSqrListNat2 [|1..100|] Solution (Orignal) //Square of Sum of Natural Numbers let sqrSumNat listNat =     let sumNat = Array.sum listNat     sumNat * sumNat //Sum of Squares of Natural Numbers let sumSqrListNat listNat =      let sqrListNat = listNat |> Array.map (f

Description Problem #2 is to find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million. General Order calculate Fibonacci series up to 4MM filter list for evens sum filtered list Solution (Improved) The fundamental improvement is a updated Fibonacci series function, rewritten as a tail-recursion. let rec fibsRec a b max arr =     if a + b > max then         arr     else         let current = a + b         let newArr = List.append arr [current]         fibsRec b current max newArr let evenArray = (1::2::(fibsRec 1 2 4000000 [])) |> List.filter (fun x -> x % 2 = 0) |> List.sum Solution (Original) //fibonacci via recursion let rec fibsRec a b max =     if a + b < max then         let current = a + b         let rest = fibsRec b current max         current :: rest     else         [] //generate list with 1, 2 and all other larger fibonaccis

Description On Project Euler, problem #1, the easiest one, is to find a way of finding the sum of all the multiples of 3 or 5 below 1000.solving, As an example, 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. Solution let natNums = [|1..999|] |> Array.filter (fun x -> x % 3 = 0 || x % 5 = 0) |> Array.sum

I am enjoying delving into learning F#, currently working through Programming F#: A comprehensive guide for writing simple code to solve complex problems on mu iPad via Kindle, as well as using a variety of web sources: WikiBook's F# Programming Project Euler, a "series of challenging mathematical/computer programming problems" F# News Inside F# Learn Visual F# (MSDN) I am currently working with MS Visual Studio Shell 2010 and F# 2.0 to work though various self-designed ideas, as well as working through various problems from Project Euler.