primes = (2 : filter (check primes) [3..]) where
    check (p:ps) n | p*p > n = True
                   | n `mod` p == 0 = False
                   | otherwise = check ps n
 
primeDivs n = divs n primes where
    divs 1 _ = []
    divs n (p:ps) =
        if p*p > n
            then [(n, 1)]
            else let (c, r) = cnt n p 0 in
                if c == 0
                    then divs n ps
                    else (p, c) : divs r ps
    cnt n p c | mod n p == 0 = cnt (div n p) p (c+1)
              | otherwise = (c, n)
 
combine divs = comb [1] divs where
    comb list [] = list
    comb list ((p, c) : ps) =
        comb [ x*y | x <- take (c+1) $ iterate (*p) 1, y <- list ] ps
 
sumDiv n = (sum $ combine $ primeDivs n) - n
 
 
friends :: [(Int, Int)]
friends = filter (\(x, s) -> x < s && sumDiv s == x) $ map (\x -> (x, sumDiv x)) [1..]
 
main = mapM print $ take 30 friends
 

cHJpbWVzID0gKDIgOiBmaWx0ZXIgKGNoZWNrIHByaW1lcykgWzMuLl0pIHdoZXJlCiAgICBjaGVjayAocDpwcykgbiB8IHAqcCA+IG4gPSBUcnVlCiAgICAgICAgICAgICAgICAgICB8IG4gYG1vZGAgcCA9PSAwID0gRmFsc2UKICAgICAgICAgICAgICAgICAgIHwgb3RoZXJ3aXNlID0gY2hlY2sgcHMgbgoKcHJpbWVEaXZzIG4gPSBkaXZzIG4gcHJpbWVzIHdoZXJlCiAgICBkaXZzIDEgXyA9IFtdCiAgICBkaXZzIG4gKHA6cHMpID0KICAgICAgICBpZiBwKnAgPiBuCiAgICAgICAgICAgIHRoZW4gWyhuLCAxKV0KICAgICAgICAgICAgZWxzZSBsZXQgKGMsIHIpID0gY250IG4gcCAwIGluCiAgICAgICAgICAgICAgICBpZiBjID09IDAKICAgICAgICAgICAgICAgICAgICB0aGVuIGRpdnMgbiBwcwogICAgICAgICAgICAgICAgICAgIGVsc2UgKHAsIGMpIDogZGl2cyByIHBzCiAgICBjbnQgbiBwIGMgfCBtb2QgbiBwID09IDAgPSBjbnQgKGRpdiBuIHApIHAgKGMrMSkKICAgICAgICAgICAgICB8IG90aGVyd2lzZSA9IChjLCBuKQoKY29tYmluZSBkaXZzID0gY29tYiBbMV0gZGl2cyB3aGVyZQogICAgY29tYiBsaXN0IFtdID0gbGlzdAogICAgY29tYiBsaXN0ICgocCwgYykgOiBwcykgPQogICAgICAgIGNvbWIgWyB4KnkgfCB4IDwtIHRha2UgKGMrMSkgJCBpdGVyYXRlICgqcCkgMSwgeSA8LSBsaXN0IF0gcHMKCnN1bURpdiBuID0gKHN1bSAkIGNvbWJpbmUgJCBwcmltZURpdnMgbikgLSBuCgoKZnJpZW5kcyA6OiBbKEludCwgSW50KV0KZnJpZW5kcyA9IGZpbHRlciAoXCh4LCBzKSAtPiB4IDwgcyAmJiBzdW1EaXYgcyA9PSB4KSAkIG1hcCAoXHggLT4gKHgsIHN1bURpdiB4KSkgWzEuLl0KIAptYWluID0gbWFwTSBwcmludCAkIHRha2UgMzAgZnJpZW5kcwo=