A friend of mine asks me to solve an exercise in haskell. As I made a mistake in solving it the first time, due to the missed unicity, I considered posting it here.
Problem
Here is the revised problem:
Find all the unique couple (a,b) such that a*b = n, for n in N+
Note As the multiplication is commutative, we consider : for any a, b, (a,b) == (b,a)
Discussion
To avoid making duplicates (a,b) /= (b,a), we can consider the input as a kind of pyramid instead of square.
for n = 9
a in 1 2 3 4 5 6 7 8 9 (we can see a in rows)
b in the range [a n] (b in columns)
12 3 4 5 6 7 8 9
1 23 4 5 6 7 8 9
1 2 34 5 6 7 8 9
1 2 3 45 6 7 8 9
1 2 3 4 56 7 8 9
1 2 3 4 5 67 8 9
1 2 3 4 5 6 78 9
1 2 3 4 5 6 7 89
1 2 3 4 5 6 7 8 9
So, again, the trick is to bound oneself. What about using b in [a..n].
|-----+-----------------+-------------------------| | a | b in [a..n] | a * b | |-----+-----------------+-------------------------| | 1 | 1 2 3 4 5 ... n | 1 2 3 4 5 6 ... n | | 2 | . 2 3 4 5 ... n | . 4 6 8 10 12 ... 2n | | 3 | . . 3 4 5 ... n | . . 9 12 15 18 ... 3n | | 4 | . . . 4 5 ... n | . . . 16 20 24 ... 4n | | 5 | . . . . 5 ... n | . . . . 25 30 ... 5n | | 6 | . . . . . ... n | . . . . . 36 ... 6n | | ... | . . . . . ... n | . . . . . . . ... | | n | . . . . . ... n | . . . . . . . ... n^2 | |-----+-----------------+-------------------------|
Seems right. But then again, we could limit the range [a..n] to [a..sqrt n].
algorithm
isqrt :: Int -> Int isqrt = floor . sqrt . fromIntegral couple :: Int -> [(Int, Int)] couple n = [(a,b) | a <- [1..isqrt n], b <- [a..n], a * b == n]
I can do some repl to check the output:
*Couple> couple 10 [(1,10),(2,5)] *Couple> couple 12 [(1,12),(2,6),(3,4)] *Couple> couple 24 [(1,24),(2,12),(3,8),(4,6)] *Couple> couple 100 [(1,100),(2,50),(4,25),(5,20),(10,10)] *Couple> couple 1000 [(1,1000),(2,500),(4,250),(5,200),(8,125),(10,100),(20,50),(25,40)] *Couple> couple 1000 [(1,1000),(2,500),(4,250),(5,200),(8,125),(10,100),(20,50),(25,40)] *Couple> couple 10000 [(1,10000),(2,5000),(4,2500),(5,2000),(8,1250),(10,1000),(16,625),(20,500),(25,400),(40,250),(50,200),(80,125),(100,100)]
Seems ok to me…
source: couple.hs
Quickcheck
Now that we have the algorithm, we can use Quickcheck to help up in generating the tests.
For using quickcheck, we need to define the properties of our algorithm:
- for all a,b in [(a,b) | n <- [1..], couple n], a * b == n
- for all n,m in N+ x N+, couple n == couple m
- for all a,b in [(a,b) | n <- [1..], couple n], a <= isqrt n
Now we tell quickcheck to generate data and check those properties:
prop_productOk = (\ n -> all (\ (a,b) -> a * b == n ) (couple n)) prop_coupleIdempotence = (\ x y -> couple x == couple y) prop_coupleInfSqrt = (\ n -> all (\ (a,b) -> a <= isqrt n ) (couple n)) -- adding main = do verboseCheckWith stdArgs { maxSuccess = 1000, maxSize = 5 } prop_productOk verboseCheckWith stdArgs { maxSuccess = 1000, maxSize = 5 } prop_coupleIdempotence verboseCheckWith stdArgs { maxSuccess = 1000, maxSize = 5 } prop_coupleInfSqrt
Here, I ask to chain the checking of each properties in limiting the number of success to 1000 and the size of the input.
This could be adapted for more hard checking!
output
Here is a sample output:
*Couple> main Passed: 0 ... Passed: 3 +++ OK, passed 10 tests. Passed: -1 ... Passed: 11 +++ OK, passed 10 tests. Passed: -1 Passed: 6 ... Passed: -12 +++ OK, passed 10 tests.
As we saw OK for all tests, we are more serene for delivering this code :D