Ninety-Nine F# Problems - Problems 31 - 41 - Arithmetic]

These are F# solutions of Ninety-Nine Haskell Problems which are themselves translations of Ninety-Nine Lisp Problems and Ninety-Nine Prolog Problems. The solutions are hidden so you can try to solve them yourself.

Ninety-Nine F# Problems - Problems 31 - 41 - Arithmetic

 1: /// Ninety-Nine F# Problems - Problems 31 - 41 
 2: ///
 3: /// These are F# solutions of Ninety-Nine Haskell Problems 
 4: /// (http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems), 
 5: /// which are themselves translations of Ninety-Nine Lisp Problems
 6: /// (http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html)
 7: /// and Ninety-Nine Prolog Problems
 8: /// (https://sites.google.com/site/prologsite/prolog-problems).
 9: ///
10: /// If you would like to contribute a solution or fix any bugs, send 
11: /// an email to paks at kitiara dot org with the subject "99 F# problems". 
12: /// I'll try to update the problem as soon as possible.
13: ///
14: /// The problems have different levels of difficulty. Those marked with a single asterisk (*) 
15: /// are easy. If you have successfully solved the preceeding problems you should be able to 
16: /// solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of 
17: /// intermediate difficulty. If you are a skilled F# programmer it shouldn't take you more than 
18: /// 30-90 minutes to solve them. Problems marked with three asterisks (***) are more difficult. 
19: /// You may need more time (i.e. a few hours or more) to find a good solution
20: ///
21: /// Though the problems number from 1 to 99, there are some gaps and some additions marked with 
22: /// letters. There are actually only 88 problems.

(**) Problem 31 : Determine whether a given integer number is prime.

 1: /// Example: 
 2: /// * (is-prime 7)
 3: /// T
 4: ///  
 5: /// Example in F#: 
 6: /// 
 7: /// > isPrime 7;;
 8: /// val it : bool = true
 9: 
10: (Solution 1)
11: 
12: (Solution 2)

(**) Problem 32 : Determine the greatest common divisor of two positive integer numbers. Use Euclid's algorithm.

 1: /// Example: 
 2: /// * (gcd 36 63)
 3: /// 9
 4: ///  
 5: /// Example in F#: 
 6: /// 
 7: /// > [gcd 36 63; gcd (-3) (-6); gcd (-3) 6];;
 8: /// val it : int list = [9; 3; 3]
 9: 
10: (Solution)

(*) Problem 33 : Determine whether two positive integer numbers are coprime.

 1: /// Two numbers are coprime if their greatest common divisor equals 1.
 2: ///  
 3: /// Example: 
 4: /// * (coprime 35 64)
 5: /// T
 6: ///  
 7: /// Example in F#: 
 8: /// 
 9: /// > coprime 35 64;;
10: /// val it : bool = true
11: 
12: (Solution)

(**) Problem 34 : Calculate Euler's totient function phi(m).

 1: /// Euler's so-called totient function phi(m) is defined as the number of 
 2: /// positive integers r (1 <= r < m) that are coprime to m.
 3: ///  
 4: /// Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.
 5: ///  
 6: /// Example: 
 7: /// * (totient-phi 10)
 8: /// 4
 9: ///  
10: /// Example in F#: 
11: /// 
12: /// > totient 10;;
13: /// val it : int = 4
14: 
15: (Solution)

(**) Problem 35 : Determine the prime factors of a given positive integer.

 1: /// Construct a flat list containing the prime factors in ascending order.
 2: ///  
 3: /// Example: 
 4: /// * (prime-factors 315)
 5: /// (3 3 5 7)
 6: ///  
 7: /// Example in F#: 
 8: /// 
 9: /// > primeFactors 315;;
10: /// val it : int list = [3; 3; 5; 7]
11: 
12: (Solution)

(**) Problem 36 : Determine the prime factors of a given positive integer.

 1: /// 
 2: /// Construct a list containing the prime factors and their multiplicity. 
 3: /// 
 4: /// Example: 
 5: /// * (prime-factors-mult 315)
 6: /// ((3 2) (5 1) (7 1))
 7: ///  
 8: /// Example in F#: 
 9: /// 
10: /// > primeFactorsMult 315;;
11: /// [(3,2);(5,1);(7,1)]
12: 
13: (Solution)

(**) Problem 37 : Calculate Euler's totient function phi(m) (improved).

 1: /// See problem 34 for the definition of Euler's totient function. If the list of the prime 
 2: /// factors of a number m is known in the form of problem 36 then the function phi(m) 
 3: /// can be efficiently calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of 
 4: /// prime factors (and their multiplicities) of a given number m. Then phi(m) can be 
 5: /// calculated with the following formula:
 6: ///  phi(m) = (p1 - 1) * p1 ** (m1 - 1) + 
 7: ///          (p2 - 1) * p2 ** (m2 - 1) + 
 8: ///          (p3 - 1) * p3 ** (m3 - 1) + ...
 9: ///  
10: /// Note that a ** b stands for the b'th power of a. 
11: /// 
12: /// Note: Actually, the official problems show this as a sum, but it should be a product.
13: /// > phi 10;;
14: /// val it : int = 4
15: 
16: (Solution)

(*) Problem 38 : Compare the two methods of calculating Euler's totient function.

1: /// Use the solutions of problems 34 and 37 to compare the algorithms. Take the 
2: /// number of reductions as a measure for efficiency. Try to calculate phi(10090) as an 
3: /// example.
4: ///  
5: /// (no solution required) 
6: ///

(*) Problem 39 : A list of prime numbers.

1: /// Given a range of integers by its lower and upper limit, construct a list of all prime numbers
2: /// in that range.
3: ///  
4: /// Example in F#: 
5: /// 
6: /// > primesR 10 20;;
7: /// val it : int list = [11; 13; 17; 19]
8: 
9: (Solution)

(**) Problem 40 : Goldbach's conjecture.

 1: /// Goldbach's conjecture says that every positive even number greater than 2 is the 
 2: /// sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts 
 3: /// in number theory that has not been proved to be correct in the general case. It has 
 4: /// been numerically confirmed up to very large numbers (much larger than we can go 
 5: /// with our Prolog system). Write a predicate to find the two prime numbers that sum up 
 6: /// to a given even integer.
 7: ///  
 8: /// Example: 
 9: /// * (goldbach 28)
10: /// (5 23)
11: ///  
12: /// Example in F#: 
13: /// 
14: /// *goldbach 28
15: /// val it : int * int = (5, 23)
16: 
17: (Solution)

(**) Problem 41 : Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.

 1: /// In most cases, if an even number is written as the sum of two prime numbers, one of 
 2: /// them is very small. Very rarely, the primes are both bigger than say 50. Try to find 
 3: /// out how many such cases there are in the range 2..3000.
 4: ///  
 5: /// Example: 
 6: /// * (goldbach-list 9 20)
 7: /// 10 = 3 + 7
 8: /// 12 = 5 + 7
 9: /// 14 = 3 + 11
10: /// 16 = 3 + 13
11: /// 18 = 5 + 13
12: /// 20 = 3 + 17
13: /// * (goldbach-list 1 2000 50)
14: /// 992 = 73 + 919
15: /// 1382 = 61 + 1321
16: /// 1856 = 67 + 1789
17: /// 1928 = 61 + 1867
18: ///  
19: /// Example in F#: 
20: /// 
21: /// > goldbachList 9 20;;
22: /// val it : (int * int) list =
23: ///   [(3, 7); (5, 7); (3, 11); (3, 13); (5, 13); (3, 17)]
24: /// > goldbachList' 4 2000 50
25: /// val it : (int * int) list = [(73, 919); (61, 1321); (67, 1789); (61, 1867)]
26: 
27: (Solution)

//naive solution
let isPrime n =
let sqrtn n = int <| sqrt (float n)
seq { 2 .. sqrtn n } |> Seq.exists(fun i -> n % i = 0) |> not

// Miller-Rabin primality test
open System.Numerics

let pow' mul sq x' n' =
    let rec f x n y =
        if n = 1I then
            mul x y
        else
            let (q,r) = BigInteger.DivRem(n, 2I)
            let x2 = sq x
            if r = 0I then
                f x2 q y
            else
                f x2 q (mul x y)
    f x' n' 1I

let mulMod (a :bigint) b c = (b * c) % a
let squareMod (a :bigint) b = (b * b) % a
let powMod m = pow' (mulMod m) (squareMod m)
let iterate f = Seq.unfold(fun x -> let fx = f x in Some(x,fx))

///See: http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
let millerRabinPrimality n a =
    let find2km n =
        let rec f k m =
            let (q,r) = BigInteger.DivRem(m, 2I)
            if r = 1I then
                (k,m)
            else
                f (k+1I) q
        f 0I n
    let n' = n - 1I
    let iter = Seq.tryPick(fun x -> if x = 1I then Some(false) elif x = n' then Some(true) else None)
    let (k,m) = find2km n'
    let b0 = powMod n a m

    match (a,n) with
        | _ when a <= 1I && a >= n' ->
            failwith (sprintf "millerRabinPrimality: a out of range (%A for %A)" a n)
        | _ when b0 = 1I || b0 = n' -> true
        | _ -> b0
                 |> iterate (squareMod n)
                 |> Seq.take(int k)
                 |> Seq.skip 1
                 |> iter
                 |> Option.exists id

///For Miller-Rabin the witnesses need to be selected at random from the interval [2, n - 2].
///More witnesses => better accuracy of the test.
///Also, remember that if Miller-Rabin returns true, then the number is _probable_ prime.
///If it returns false the number is composite.
let isPrimeW witnesses = function
    | n when n < 2I -> false
    | n when n = 2I -> true
    | n when n = 3I -> true
    | n when n % 2I = 0I -> false
    | n -> witnesses |> Seq.forall(millerRabinPrimality n)

// let isPrime' = isPrimeW [2I;3I] // Two witnesses
// let p = pown 2I 4423 - 1I // 20th Mersenne prime. 1,332 digits
// isPrime' p |> printfn "%b";;
// Real: 00:00:03.184, CPU: 00:00:03.104, GC gen0: 12, gen1: 0, gen2: 0
// val it : bool = true

let rec gcd a b =
    if b = 0 then
        abs a
    else
        gcd b (a % b)

// using problem 32
let coprime a b = gcd a b = 1

// naive implementation. For a better solution see problem 37
let totient n = seq { 1 .. n - 1} |> Seq.filter (gcd n >> (=) 1) |> Seq.length

let primeFactors n =
    let sqrtn n = int <| sqrt (float n)
    let get n =
        let sq = sqrtn n
        // this can be made faster by using a prime generator like this one :
        // https://github.com/paks/ProjectEuler/tree/master/Euler/Primegen
        seq { yield 2; yield! seq {3 .. 2 .. sq} } |> Seq.tryFind (fun x -> n % x = 0)
    let divSeq = n |> Seq.unfold(fun x ->
        if x = 1 then
            None
        else
            match get x with
                | None -> Some(x, 1) // x it's prime
                | Some(divisor) -> Some(divisor, x/divisor))
    divSeq |> List.ofSeq

// using problem 35
let primeFactorsMult n =
    let sqrtn n = int <| sqrt (float n)
    let get n =
        let sq = sqrtn n
        // this can be made faster by using a prime generator like this one :
        // https://github.com/paks/ProjectEuler/tree/master/Euler/Primegen
        seq { yield 2; yield! seq {3 .. 2 .. sq} } |> Seq.tryFind (fun x -> n % x = 0)
    let divSeq = n |> Seq.unfold(fun x ->
        if x = 1 then
            None
        else
            match get x with
                | None -> Some(x, 1) // x it's prime
                | Some(divisor) -> Some(divisor, x/divisor))
    divSeq |> Seq.countBy id |> List.ofSeq

// using problem 36
let phi = primeFactorsMult >> Seq.fold(fun acc (p,m) -> (p - 1) * pown p (m - 1) * acc) 1

// using problem 31
let primeR a b = seq { a .. b } |> Seq.filter isPrime |> List.ofSeq

// using problem 31. Very slow on big numbers due to the implementation of primeR. To speed this up use a prime generator.
let goldbach n =
    let primes = primeR 2 n |> Array.ofList
    let rec findPairSum (arr: int array) front back =
        let sum = arr.[front] + arr.[back]
        match compare sum n with
            | -1 -> findPairSum arr (front + 1) back
            | 0 -> Some(arr.[front] , arr.[back])
            | 1 -> findPairSum arr front (back - 1)
            | _ -> failwith "not possible"
    Option.get <| findPairSum primes 0 (primes.Length - 1)

let goldbachList a b =
let start = if a % 2 <> 0 then a + 1 else a
seq { start .. 2 .. b } |> Seq.map goldbach |> List.ofSeq

let goldbachList' a b limit = goldbachList a b |> List.filter(fst >> (<) limit)

More information

Link:	http://fssnip.net/aq
Posted:	1 years ago
Author:	Cesar Mendoza (website)
Tags:	Ninety-Nine F# Problems, tutorial, F#, arithmetic