Skip to content

Instantly share code, notes, and snippets.

@josejuan josejuan/torns.hs
Created Sep 17, 2014

Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.