Generating sorted list of all possible coprimes

Question

I need to generate infinite sorted list of all coprimes. The first element in each pair must be less than the second. The sorting must be done in ascending order -- by the sum of pair's elements; and if two sums are equal, then by the pair's first element.

So, the resulting list must be

[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)...`

Here's my solution.

coprimes :: [(Int, Int)]
coprimes = sortBy (\t1 t2 -> if uncurry (+) t1 <= uncurry (+) t2 then LT else GT) $ helper [2..]
    where helper xs = [(x,y) | x <- xs, y <- xs, x < y, gcd x y == 1]

The problem is that I can't take n first pairs. I realize that sorting can't be done on infinite lists.

But how can I generate the same sequence in a lazy way?

Doering

The trick would probably be to generate the pairs for 2, for 3 in ascending order and merge them. – Avow

Answer 1

While probably not the most optimal way it should works if you first generate all possible pairs and then filter them.

So using your criteria:

pairs :: [(Integer,Integer)]
pairs = [ (i,l-i) | l <- [1..], i <- [1..l-1] ]

coprimes :: [(Integer,Integer)]
coprimes = [ (i,j) | (i,j) <- pairs, 1 < i, i < j,gcd i j == 1]

produces

λ> take 10 coprimes
[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)]

now of course you can put some of the stuff 1 < i and i < j comes to mind into the pairs definition or even join them but I think here it's more obvious what's going on

Tinctorial

Answer 2

Here's a possible solution following Chapter 9 of Richard Bird's Thinking Functionally in Haskell:

coprimes = mergeAll $ map coprimes' [2..]

coprimes' n = [(n, m) | m <- [n+1..], gcd m n == 1]

merge (x:xs) (y:ys)
    | s x < s y =  x:merge xs (y:ys)
    | s x == s y = x:y:merge xs ys
    | otherwise = y:merge (x:xs) ys
    where s (x, y) = x+y

xmerge (x:xs) ys = x:merge xs ys

mergeAll = foldr1 xmerge

And the result is:

> take 10 $ coprimes
[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)]

Note that the natural definition of mergeAll would be foldr1 merge, but this doesn't work because it will try to find the minimum of the first elements of all the list before returning the first element, and hence you end up in an infinite loop. However, since we know that the lists are in ascending order and the minimum is the first element of the first list xmerge does the trick.

---

Note: this solution appears to be significantly (like 2 order of magnitudes) slower than Carsten "naive" answer. So I advise to avoid this if you are interested in performance. Yet it still is an interesting approach that might be effective in other situations.

Avow

instead of foldr1 xmerge, you could use Data.List.Ordered.mergeAllBy (comparing (uncurry (+))) from data-ordlist. it uses a tree-like structure for the folding, so should bring significant algorithmic (I mean, complexity-wise) advantage (and hence, speed-up). the comparison returns EQ on equal sums, but all functions in that package are left-biased, so that's OK. – Futile

Answer 3

As @Bakuriu suggests, merging an infinite list of infinite lists is a solution, but the devil is in the details.

The diagonal function from the universe-base package can do this, so you could write:

import Data.Universe.Helpers

coprimes = diagonal [ go n | n <- [2..] ]
  where go n = [ (n,k) | k <- [n+1..], gcd n k == 1 ]

Note - this doesn't satisfy your sorted criteria, but I mention it because the functions in that package are useful to know about, and implementing a function like diagonal correctly is not easy.

If you want to write your own, consider decomposing the infinite grid N x N (where N is the natural numbers) into diagonals:

[ (1,1) ] ++ [ (1,2), (2,1) ] ++ [ (1,3), (2,2), (3,1) ] ++ ...

and filtering this list.

Knitting

@daniel-wagner is the author of universe-base. His answer is right before yours (this). – Chip

Answer 4

I need to generate infinite sorted list of all coprimes. The first element in each pair must be less than the second. The sorting must be done in ascending order -- by the sum of pair's elements; and if two sums are equal, then by the pair's first element.

So, we generate ascending pairs of sum and first element, and keep only the coprimes. Easy cheesy!

[ (first, second)
| sum <- [3..]
, first <- [2..sum `div` 2]
, let second = sum-first
, gcd first second == 1
]

Prairie