Karmic Code Monkey

Today I was reading an article in The Onion, Conquerors You May Have Missed,  and noticed that the number for the ant looked like it might be a big old prime, or at least have a large prime divisor. (For reference, the ant is # 43,168,974,563,247.) There are a number of algorithms for finding this answer, but my favorite is a little brute force algorithm that keeps dividing the big number by some other value until the two numbers are equal. Yes, I know I can short circuit a bunch of testing via a square root function, but BigInteger doesn’t have a sqrt function (yet.).

Anyhow, I cobbled this together and it worked right out of the gate:

let rec largestFactor x y =
    if (x = y) then y
    else
        let z = x % y
        if z = 0I then largestFactor (x/y) y
        else largestFactor x (y + 1I)

let LargestPrime x = largestFactor x 2I

let a = LargestPrime 43168974563247I

printf "%A" a

Answer: 84,826,177

So, the number isn’t prime, but the largest prime factor is pretty big! And, writing up the code to figure out the answer itself was pretty simple.