Posts

Showing posts from 2010

Project Euler - Problem #15

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 Statistics (Popularity and Effectiveness)

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

Project Euler - Problem 21

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_matchLists_10000 = matchLists 1 10000…

Project Euler - Problem #14

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 → 1It 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 i) 1 ]
    let longest = List.ma…

Project Euler - Problem #13

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;
    64906352462741904929101432445813822663347944758178I;
    925758677183372176…

Project Euler - Problem #9

Description

A Pythagorean triplet is a set of three natural numbers, a  b  c, for which, a2 + b2 = c2For 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]

Project Euler - Problem #4

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..last do
               yield (i*j…

Project Euler - Problem #3

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 resultingPrimeFactor = FindLargestPr…

Project Euler - Problem #25

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

Project Euler - Problem #16

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.ToString()
    let max = strCharProd.Length
    let a…

Project Euler - Problem #10

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)


//recursive function to sum array of BigInteger
let rec sumArrayBigIn…

Project Euler - Problem #5

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 smallestWithNoRemainder div = 
    let mutable stat…

Project Euler - Problem #20

Description

n! means n  (n  1)  ...  3  2  1Find 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

Project Euler - Problem #8

Description


Find the greatest product of five consecutive digits in the 1000-digit number.


Solution


//the string to process
let arrStr = "73167176531330624919225119674426574742355349194934969835203127745063262395783180169848018694788518438586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557668966489504452445231617318564030987111217223831136222989342338030813533627661428280644448664523874930358907296290491560440772390713810515859307960866701724271218839987979087922749219016997208880937766572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397536978179778461740649551492908625693219784686224828397224137565705605749026140797296865241453510047482166370484403199890008895243450658541227588666881164271714799244429282308634656748139191231628245861786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408071984038509624554443629812309878799272442849091888458015616…

Project Euler - Problem #7

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.Sqrt(Convert.ToDouble(x)))
    let al…

Project Euler - Problem #6

Description
The sum of the squares of the first ten natural numbers is, 12 + 22 + ... + 102 = 385The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)2 = 552 = 3025Hence 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 (fun x -> x * x )
    Array.sum sqrLis…

Project Euler - Problem #2

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 let fibs = 1::2::(fibsRec 1 2 4000000)
//filter for even only let evenArray = fibs |> Li…

Project Euler - Problem #1

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


First Post and Raison d'Etre

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# NewsInside 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.