3 people like it.

Like the snippet!

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

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

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)

if b = 0 then

abs a

else

gcd b (a % b)

// using problem 32

let coprime a b = gcd a b = 1

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 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

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

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

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

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 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)

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: |
3 years ago |

Author: |
Cesar Mendoza (website) |

Tags: |
Ninety-Nine F# Problems, tutorial, F#, arithmetic |