Chapter 05 Daily 3

These exercises are intended to be more challenging, for people who have completed the more straightforward exercises.

1. (myisqrt :: Int -> Int) Given a nonnegative integer n, produce the largest integer k so that k*k <= n. That is the “integer square root”. Do not use Float, sqrt, or functions like floor.

2. (sps :: Int -> [(Int,Int)]) Can a number be expressed as the sum of two perfect squares? For example: $17 = 1^2 + 4^2$. Produce a list of ordered pairs whose squares sum to the given number.

3. (rsum : Int -> (Int, Int)). Given an integer $n>1$, find two distinct integers $a$ and $b$ so that $1/a + 1/b = 1/n$. Hint: do some algebra first; stay away from floating point numbers.

4. (n10mult :: Int -> [Int] -> Float) Given a number k and then a list of numbers, find the probability that randomly choosing k numbers from the list (with repetition) gives a multiple of 10. Suggestion: compute the probability by checking all possibilities.

5. (sameSum :: [Int] -> ([Int],[Int])) Given ten distinct two digit numbers (in the decimal system), produce two disjoint subsets that have the same sum.

   You should first write a function that works when you give it the ten numbers in a list.

Testing Notes

(sameSum) If you want to test it to see that it works for lots of numbers, you need a method of producing 10 distinct two digit numbers. There are about $5.7 \cross 10^{12}$ possibilities. By itself this is a challenge. You can find a random list generator online?