torns.hs

import Data.Maybe
import System.Environment
{--
   On my Atom D510 1.6Ghz
   Torns:
     - up to 100.000.000 take 0,01 seconds
     - up to 1.000.000.000.000 take 1.4 seconds
     - up to 100.000.000.000.000 take 15.7 seconds
     - ...
    Using
        n = q^2 = (a + b)^2 = a + 10^x b
    then substracting equations
        n = a + 10^x b
        q = a + b
    is
        n – q = 999..999 b
    check all 999..999 can reduce using only one check
        n - q = 9 * 111...111 * b
--}
torns :: Integer -> [Integer]
torns maxQ = catMaybes
               [if x1 q d then Just n else Nothing
                       | q <- [1..maxQ], let n      = q * q
                                             nq     = n - q
                                             (d, r) = nq `divMod` 9
                                       , r == 0 ]
             where x1 q d = not$null [()| p <- takeWhile (<=d) $ iterate ((+1).(*10)) 1
                                        , let (b, r) = d `divMod` p
                                        , r == 0 && q >= b]
main = getArgs >>= mapM_ print . torns . read . head