Skip to content

Project Euler Problem 80

March 13, 2012

Project Euler Problem 80 solution is straightforward. For calculating approximations of irrational square roots we can use F# Rational numbers that are part of F# Power Pack. In order to get first 100 digits of a square root we may use any of known approximations approximating until the error is less, than 1/100. In order to get to these first 100 digits the easiest would be to multiply our rational square root by 10**99 and convert the result to BigInteger:

let sumOfDigits (n: bigint) =
    n.ToString().ToCharArray()
    |> Array.map (fun x -> (int)x - (int)'0') |> Array.sum

let ``10**99`` = BigNum.PowN (10N, 99)
let ``10**100`` = ``10**99`` * 10N
let err = 1N/``10**100``

let rec SqRt v =
    let rec nextX x =
        let x' = (x + v/x)/2N
        if abs(x' - x) > err then nextX x'
        else (BigNum.ToBigInt (x' * ``10**99``))
    nextX v

let problem080 () =
    (set [2..99] - set [4;9;16;25;36;49;64;81])
    |> Set.fold (fun s x ->
            s + sumOfDigits (SqRt (BigNum.FromInt x))) 0
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: