Problem 141

http://projecteuler.net/index.php?section=problems&id=141

とりあえず、ものすごく正直な(愚直ともいう)コード

import Data.List
divQuotRem n = do d <- [1..n]
let (q,r) = divMod n d
return [q,d,r]
progressive [a,b,c] = let [x,y,z] = sort [a,b,c]
in y*y==x*z
isProgressive = any progressive.divQuotRem
p141 n = filter isProgressive.map (^2) $ [1..n]

当然、話にならないぐらい遅い。もちろん解けない。

ただ、初めの三つは9=3^2,10404=102^2,16900=130^2であることが分かった。

また、平方数という制約を外すと100以下には

[6,9,12,20,28,30,34,42,56,58,65,72,75,90]

と結構ある。

だから何?って話ではあるが…

{--
r = a*a*r
d = b*a*r
q = b*b*r
ghc a b = 1 , a < b
n^2 = q*d+r = a*b^3*r^2+a*a*r = a*r*(b^3*r+a)
--}
import Control.Monad
main = print.sum$progressive
lim = 10^12
lim'= floor.sqrt.sqrt.fromIntegral$lim
progressive = do
a <-[1..lim']
b <-takeWhile( b-> a*(b^3+a) < lim) [a+1..]
guard$ gcd a b == 1
r <- takeWhile( r-> a*r*(b^3*r+a) < lim) [1..]
let n = a*r*(b^3*r+a)
guard.(==n ).(^2).floor.sqrt.fromIntegral$n
return n

まぁ、これといった工夫もなく、力技。

More Reading
Newer// Problem 145
Older// Problem 142