2023-02-10 00:08
Problem details at Project Euler problem 64 page.
module Euler064Test (euler64suite) where
import Prelude
import Effect.Aff (Milliseconds(..), delay)
import Euler064 (euler64)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
euler64suite :: TestSuite
euler64suite =
suite "Euler 64" do
test "Warmup" do
delay (Milliseconds 0.0)
Assert.equal 4 (euler64 13)
test "Real" do
delay (Milliseconds 0.0)
Assert.equal 1322 (euler64 10_000)
module Euler064 where
import Prelude
import Data.Array (filter, length, range)
import Data.Int (floor, odd, round, toNumber)
import Data.Number (sqrt)
import Data.Set (empty, insert, member)
import Data.Tuple (Tuple(..))
import Data.Tuple.Nested (Tuple3, tuple3)
irrational :: Int -> Boolean
irrational n =
let si = floor $ sqrt $ toNumber n
in si * si /= n
next :: Number -> Tuple3 Int Int Int -> Tuple3 Int Int Int
next s (Tuple _ (Tuple j (Tuple k _))) =
let jo = toNumber j
ko = toNumber k
jn = round $ (s * s - ko * ko) / jo
an = floor $ (s + ko) / toNumber jn
kn = an * jn - k
in tuple3 an jn kn
repeating :: Int -> Int
repeating n =
let s = sqrt $ toNumber n
si = floor s
go j v t =
let tn = next s t
in case j of
_
| j == (-1) -> go (j + 1) v tn
| member tn v -> j
| otherwise -> go (j + 1) (insert tn v) tn
in go (-1) empty (tuple3 si 1 si)
euler64 :: Int -> Int
euler64 = length
<<< filter odd
<<< map repeating
<<< filter irrational
<<< range 1