# Difference between revisions of "99 questions/31 to 41"

m |
(moved solutions to subpages of 99 questions/Solutions) |
||

Line 10: | Line 10: | ||

Example: | Example: | ||

+ | |||

<pre> | <pre> | ||

* (is-prime 7) | * (is-prime 7) | ||

T | T | ||

</pre> | </pre> | ||

+ | |||

Example in Haskell: | Example in Haskell: | ||

− | < | + | |

+ | <haskell> | ||

P31> isPrime 7 | P31> isPrime 7 | ||

True | True | ||

− | </ | + | </haskell> |

− | + | [[99 questions/Solutions/31 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 32 == | == Problem 32 == | ||

− | (**) Determine the greatest common divisor of two positive integer numbers. | + | (**) Determine the greatest common divisor of two positive integer numbers. Use Euclid's algorithm. |

− | + | ||

+ | Example: | ||

<pre> | <pre> | ||

− | |||

* (gcd 36 63) | * (gcd 36 63) | ||

9 | 9 | ||

+ | </pre> | ||

Example in Haskell: | Example in Haskell: | ||

+ | |||

+ | <haskell> | ||

[myGCD 36 63, myGCD (-3) (-6), myGCD (-3) 6] | [myGCD 36 63, myGCD (-3) (-6), myGCD (-3) 6] | ||

[9,3,3] | [9,3,3] | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

</haskell> | </haskell> | ||

− | + | [[99 questions/Solutions/32 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 33 == | == Problem 33 == | ||

− | (*) Determine whether two positive integer numbers are coprime. | + | (*) Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1. |

− | Two numbers are coprime if their greatest common divisor equals 1. | ||

Example: | Example: | ||

+ | |||

<pre> | <pre> | ||

* (coprime 35 64) | * (coprime 35 64) | ||

Line 75: | Line 59: | ||

Example in Haskell: | Example in Haskell: | ||

− | < | + | |

+ | <haskell> | ||

* coprime 35 64 | * coprime 35 64 | ||

True | True | ||

− | </ | + | </haskell> |

− | + | [[99 questions/Solutions/33 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

== Problem 34 == | == Problem 34 == | ||

(**) Calculate Euler's totient function phi(m). | (**) Calculate Euler's totient function phi(m). | ||

+ | |||

Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m. | Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m. | ||

+ | |||

Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1. | Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1. | ||

+ | |||

+ | Example: | ||

+ | |||

<pre> | <pre> | ||

− | |||

* (totient-phi 10) | * (totient-phi 10) | ||

4 | 4 | ||

+ | </pre> | ||

+ | |||

Example in Haskell: | Example in Haskell: | ||

+ | |||

+ | <haskell> | ||

* totient 10 | * totient 10 | ||

4 | 4 | ||

− | </ | + | </haskell> |

+ | |||

+ | [[99 questions/Solutions/34 | Solutions]] | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 35 == | == Problem 35 == | ||

− | (**) Determine the prime factors of a given positive integer. | + | (**) Determine the prime factors of a given positive integer. Construct a flat list containing the prime factors in ascending order. |

− | Construct a flat list containing the prime factors in ascending order. | ||

Example: | Example: | ||

+ | |||

<pre> | <pre> | ||

* (prime-factors 315) | * (prime-factors 315) | ||

(3 3 5 7) | (3 3 5 7) | ||

</pre> | </pre> | ||

+ | |||

Example in Haskell: | Example in Haskell: | ||

− | < | + | |

+ | <haskell> | ||

> primeFactors 315 | > primeFactors 315 | ||

[3, 3, 5, 7] | [3, 3, 5, 7] | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

</haskell> | </haskell> | ||

− | + | [[99 questions/Solutions/35 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 36 == | == Problem 36 == | ||

+ | |||

(**) Determine the prime factors of a given positive integer. | (**) Determine the prime factors of a given positive integer. | ||

Line 177: | Line 121: | ||

Example: | Example: | ||

+ | |||

<pre> | <pre> | ||

* (prime-factors-mult 315) | * (prime-factors-mult 315) | ||

((3 2) (5 1) (7 1)) | ((3 2) (5 1) (7 1)) | ||

</pre> | </pre> | ||

+ | |||

Example in Haskell: | Example in Haskell: | ||

− | < | + | |

+ | <haskell> | ||

*Main> prime_factors_mult 315 | *Main> prime_factors_mult 315 | ||

[(3,2),(5,1),(7,1)] | [(3,2),(5,1),(7,1)] | ||

− | </ | + | </haskell> |

+ | |||

+ | [[99 questions/Solutions/36 | Solutions]] | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 37 == | == Problem 37 == | ||

(**) Calculate Euler's totient function phi(m) (improved). | (**) Calculate Euler's totient function phi(m) (improved). | ||

+ | |||

See problem 34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem 36 then the function phi(m) can be efficiently calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula: | See problem 34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem 36 then the function phi(m) can be efficiently calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula: | ||

Line 204: | Line 148: | ||

Note that a ** b stands for the b'th power of a. | Note that a ** b stands for the b'th power of a. | ||

+ | |||

<i>Note</i>: Actually, the official problems show this as a sum, but it should be a product. | <i>Note</i>: Actually, the official problems show this as a sum, but it should be a product. | ||

− | + | [[99 questions/Solutions/37 | Solutions]] | |

− | + | ||

− | |||

− | |||

− | |||

== Problem 38 == | == Problem 38 == | ||

Line 219: | Line 161: | ||

(no solution required) | (no solution required) | ||

+ | |||

== Problem 39 == | == Problem 39 == | ||

Line 226: | Line 169: | ||

Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range. | Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range. | ||

− | |||

Example in Haskell: | Example in Haskell: | ||

+ | |||

+ | <haskell> | ||

P29> primesR 10 20 | P29> primesR 10 20 | ||

[11,13,17,19] | [11,13,17,19] | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

</haskell> | </haskell> | ||

− | + | [[99 questions/Solutions/39 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 40 == | == Problem 40 == | ||

+ | |||

(**) Goldbach's conjecture. | (**) Goldbach's conjecture. | ||

+ | |||

Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers (much larger than we can go with our Prolog system). Write a predicate to find the two prime numbers that sum up to a given even integer. | Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers (much larger than we can go with our Prolog system). Write a predicate to find the two prime numbers that sum up to a given even integer. | ||

+ | |||

+ | Example: | ||

<pre> | <pre> | ||

− | |||

* (goldbach 28) | * (goldbach 28) | ||

(5 23) | (5 23) | ||

+ | </pre> | ||

Example in Haskell: | Example in Haskell: | ||

+ | |||

+ | <haskell> | ||

*goldbach 28 | *goldbach 28 | ||

(5, 23) | (5, 23) | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

</haskell> | </haskell> | ||

− | + | [[99 questions/Solutions/40 | Solutions]] | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

== Problem 41 == | == Problem 41 == | ||

Line 297: | Line 209: | ||

Example: | Example: | ||

+ | |||

<pre> | <pre> | ||

* (goldbach-list 9 20) | * (goldbach-list 9 20) | ||

Line 313: | Line 226: | ||

Example in Haskell: | Example in Haskell: | ||

− | < | + | |

+ | <haskell> | ||

*Exercises> goldbachList 9 20 | *Exercises> goldbachList 9 20 | ||

[(3,7),(5,7),(3,11),(3,13),(5,13),(3,17)] | [(3,7),(5,7),(3,11),(3,13),(5,13),(3,17)] | ||

*Exercises> goldbachList' 4 2000 50 | *Exercises> goldbachList' 4 2000 50 | ||

[(73,919),(61,1321),(67,1789),(61,1867)] | [(73,919),(61,1321),(67,1789),(61,1867)] | ||

− | </ | + | </haskell> |

+ | |||

+ | [[99 questions/Solutions/41 | Solutions]] | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

[[Category:Tutorials]] | [[Category:Tutorials]] |

## Revision as of 17:01, 13 July 2010

This is part of Ninety-Nine Haskell Problems, based on Ninety-Nine Prolog Problems.

## Arithmetic

## Problem 31

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

Example:

* (is-prime 7) T

Example in Haskell:

```
P31> isPrime 7
True
```

## Problem 32

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

Example:

* (gcd 36 63) 9

Example in Haskell:

```
[myGCD 36 63, myGCD (-3) (-6), myGCD (-3) 6]
[9,3,3]
```

## Problem 33

(*) Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1.

Example:

* (coprime 35 64) T

Example in Haskell:

```
* coprime 35 64
True
```

## Problem 34

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

Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m.

Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.

Example:

* (totient-phi 10) 4

Example in Haskell:

```
* totient 10
4
```

## Problem 35

(**) Determine the prime factors of a given positive integer. Construct a flat list containing the prime factors in ascending order.

Example:

* (prime-factors 315) (3 3 5 7)

Example in Haskell:

```
> primeFactors 315
[3, 3, 5, 7]
```

## Problem 36

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

Construct a list containing the prime factors and their multiplicity.

Example:

* (prime-factors-mult 315) ((3 2) (5 1) (7 1))

Example in Haskell:

```
*Main> prime_factors_mult 315
[(3,2),(5,1),(7,1)]
```

## Problem 37

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

See problem 34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem 36 then the function phi(m) can be efficiently calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:

phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2 ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ...

Note that a ** b stands for the b'th power of a.

*Note*: Actually, the official problems show this as a sum, but it should be a product.

## Problem 38

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

Use the solutions of problems 34 and 37 to compare the algorithms. Take the number of reductions as a measure for efficiency. Try to calculate phi(10090) as an example.

(no solution required)

## Problem 39

(*) A list of prime numbers.

Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.

Example in Haskell:

```
P29> primesR 10 20
[11,13,17,19]
```

## Problem 40

(**) Goldbach's conjecture.

Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers (much larger than we can go with our Prolog system). Write a predicate to find the two prime numbers that sum up to a given even integer.

Example:

* (goldbach 28) (5 23)

Example in Haskell:

```
*goldbach 28
(5, 23)
```

## Problem 41

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

In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than say 50. Try to find out how many such cases there are in the range 2..3000.

Example:

* (goldbach-list 9 20) 10 = 3 + 7 12 = 5 + 7 14 = 3 + 11 16 = 3 + 13 18 = 5 + 13 20 = 3 + 17 * (goldbach-list 1 2000 50) 992 = 73 + 919 1382 = 61 + 1321 1856 = 67 + 1789 1928 = 61 + 1867

Example in Haskell:

```
*Exercises> goldbachList 9 20
[(3,7),(5,7),(3,11),(3,13),(5,13),(3,17)]
*Exercises> goldbachList' 4 2000 50
[(73,919),(61,1321),(67,1789),(61,1867)]
```