Posts Tagged ‘fsharp’

Project Euler Problem #99!

May 1st, 2010

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)

Project Euler Problem #58!

April 25th, 2010

Problem #58 says:

Starting with 1 and spiraling anticlockwise in the following way, a square spiral with side length 7 is formed.

It is interesting to note that the odd squares lie along the bottom right diagonal,
but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime;
that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed.
If this process is continued, what is the side length of the square spiral for which the ratio of
primes along both diagonals first falls below 10%?

The below solution simply counts the offset between corners and checks that number to see if its prime or composite then the next cycle after its check it updates the offset amount and continues this way until its collected a list of prime and composite numbers that have less than 10% prime numbers. very simple, no optimizations applied. The solution could be made faster by using a simpler test and also by not keeping a list of composite numbers but a counter instead.

Solution in f# and requires the .net 4.0 run-time. runs in ~50 seconds.

#light
module ProjectEuler

open System
open System.Diagnostics
open Microsoft.FSharp.Linq
open Microsoft.FSharp.Collections
open Microsoft.FSharp.Math
open System.Numerics

let toBinary (n:BigInteger) =
    let mutable m = n
    let mutable r = []
    while m > BigInteger.Zero do
        r <- r @ [(m % (BigInteger 2))]
        m <- m / BigInteger 2
    r

let test (a:BigInteger) (n:BigInteger) =
    let (b:List<BigInteger>) = toBinary (n - BigInteger.One)
    let mutable d = BigInteger.One
    let mutable Prime = false
    let CheckList = [0 .. b.Length-1 ] |> List.rev
    for i in CheckList do
        let x = d
        d <- (d*d) % n
        if (d = BigInteger.One && x <> BigInteger.One && x <> n-BigInteger.One) then
            Prime <- true // complex
        if b.[i] = BigInteger.One then
            d <- (d*a) % n
    if d <> BigInteger.One then
        Prime <- true //complex
    Prime //if its still false then prime

let MillerRabin (n:uint64) (s:int) =
    let Rand = new System.Random()
    let mutable Prime = true
    if n < Convert.ToUInt64(Int32.MaxValue) then
        for j in [1 .. s+1] do
            let a = Rand.Next(1, Convert.ToInt32(n)-1)
            if (test (BigInteger a) (BigInteger n)) then
                Prime <- false
    else
        for j in [1 .. s+1] do
            let a = Rand.Next(1, Int32.MaxValue)
            if (test (BigInteger a) (BigInteger n)) then
                Prime <- false
    Prime

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

let rec Answer (currentnum:uint64) (step:uint64) (prime:List<uint64>) (composite:List<uint64>) (tick:bool) =
    let check = (float prime.Length)/((float composite.Length)+(float prime.Length))
    if check < 0.1 && currentnum > 100UL  then
        step-1UL
    else
        if (tick) then
            if (MillerRabin currentnum 10) then
                Answer (currentnum+step) step (currentnum::prime) composite (false)
            else
                Answer (currentnum+step) step (prime) (currentnum::composite) (false)
        else
            if (MillerRabin currentnum 10) then
                Answer (currentnum+step) (step+1UL) (currentnum::prime) composite (true)
            else
                Answer (currentnum+step) (step+1UL) (prime) (currentnum::composite) (true)

Console.WriteLine(Answer 3UL 2UL [] [1UL] true )
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.Beep() |> ignore
Console.ReadKey() |> ignore


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

This blog collects statistical data with Statpress SEOlution in the reVierphone Edition! Give it a try.