Project Euler Problem #99!

May 1st, 2010
by Serinox

Problem #99 says:

Comparing two numbers written in index form like 2^(11) and 3^(7) is not difficult,
as any calculator would confirm that 2^(11) = 2048 < 3^(7) = 2187.

However, confirming that 632382^(518061) > 519432^(525806) would be much more difficult,
as both numbers contain over three million digits.

Using base_exp.txt (right click and ‘Save Link/Target As…’), a 22K text file containing one
thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

This is a problem that seems kinda complicated at first. Each of the base exponent sets creates a number that easily dwarfs anything a computer can currently handle. The solution is to do something else that still lets us compare them to one another. So instead of expanding the exponent base pair what we do is multiply the exponent by the natural log of the base and use that value. Using this method reading the file in is almost harder than solving the task.

Solution in F# requires .net 4, runs in under one second.


open System
open System.IO
open System.Diagnostics

let sw = new Stopwatch()
sw.Start()

let test b e =
    e * Math.Log(b)    

let CheckSets =
    let f = new StreamReader("base_exp.txt")
    let mutable lines = []
    let mutable line = f.ReadLine()
    while line <> null do
        lines <- lines @ [line]
        line <- f.ReadLine()
    lines

let mutable mv = 0.0
let mutable ml = 0
let mutable ln = 0

let FindAnswer =
    for s in CheckSets do
        ln <- ln + 1
        let ss = s.Split(",".ToCharArray())
        let b = float ss.[0]
        let e = float ss.[1]
        if (test b e) > mv then
            mv <- (test b e)
            ml <- ln
FindAnswer
Console.WriteLine(ml)
sw.Stop()
Console.WriteLine(sw.Elapsed)
Console.ReadLine() |> ignore

Tags: , , ,
Posted in Project Euler | Comments (0)

No comments yet

Leave a Reply

You must be logged in to post a comment.