Problem #113 says:

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a “bouncy” number; for example, 155349.

As n increases, the proportion of bouncy numbers below n increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below 10^(10).

How many numbers below a googol (10^(100)) are not bouncy?

This is a simple combinatorial counting problem. As such we just need to calculate the binomial of a few numbers and remove the duplicates. The binomial requires the use of a unbounded integer class (in this case the biginteger class from System.Numerics) if you don’t want to use such a class you need to do some optimization on the binomial calculation.

Solution below in FSharp requires .Net 4 the FSharp powerpack. Runs in under 1 second.

#light

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

let rec Factorial (x:BigInteger) =
    if x = BigInteger.One then
        BigInteger.One
    else
        BigInteger.Multiply (x,(Factorial (BigInteger.op_Decrement x)))

let binomial (n:int) (k:int) =
    let bN = BigInteger n
    let bK = BigInteger k
    (Factorial bN) / ((Factorial bK) * (Factorial(bN-bK)))

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

let BigBinom = binomial 110 10
let SmallBinom = binomial 109 9
let n100 = BigInteger (10*100)
let two = BigInteger 2

Console.WriteLine(BigBinom + SmallBinom - n100 - two)
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.ReadKey() |> ignore

Problem #72 says:

Consider the fraction, n/d, where n and d are positive integers. If n

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

The simplest way to solve this is to realize that its simply the sum of the euler totient (phi function) of all the numbers from 2 to 1,000,000. So we just need to generate some primes write a nifty totient function and run the numbers down.

Solution below in fSharp and requires the FSharp power pack and .Net 4.

#light

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

//prime generation from
//http://bit.ly/aWFrGy
let is_prime_juliet n =
    let maxFactor = sqrt(float n)
    let rec loop testPrime tog =
        if testPrime > maxFactor then true
        elif n % testPrime = 0. then false
        else loop (testPrime + tog) (6. - tog)
    if n = 2. || n = 3. || n = 5. then true
    elif n <= 1. || n % 2. = 0. || n % 3. = 0. || n % 5. = 0. then false
    else loop 7. 4.

let getPrimes upTo =
    seq {
        yield 2.;
        yield 3.;
        yield 5.;
        yield! (7., 4.)
        |> Seq.unfold (fun (p, tog) -> if p <= upTo then Some(p, (p + tog, 6. - tog)) else None)
    }
    |> Seq.filter is_prime_juliet

let Primes =
    (getPrimes (1000.))
    |> Seq.toList

let rec factorise (n:float) =
    if n = 1. then
        []
    else
        let c = Primes |> List.filter (fun x -> n % x = 0.)
        if c.Length = 0 then
            [n]
        else
            let a = Primes |> List.find (fun x -> n % x = 0.)
            a :: factorise (n / a)

let Totient (x:float) =
    (factorise x)
    |> Seq.distinct
    |> Seq.map (fun x -> 1. - (1./x))
    |> Seq.fold(fun acc a -> acc * a) x

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

let Answer =
    [2. .. 1000000.]
    |> PSeq.map Totient
    |> PSeq.toArray
    |> PSeq.sum

Console.WriteLine(Answer)
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.ReadKey() |> ignore

Problem #62 says:

The cube, 41063625 (345^(3)), can be permuted to produce two other cubes: 56623104 (384^(3)) and 66430125 (405^(3)). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

The solution below uses a custom class that takes a int64 in its constructor and to identify it later, it then creates a list of all of the digits of the number sorted by size. We then take an item in the list and see how many times it matches another class in the list including matching against itself. If the items returns 5 then we know its one of the numbers we’re looking for.

Solution in f# and requires FSharp.PowerPack and .Net 4. Runs in ~10 seconds.

#light

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

type TestCase (y) =
    let num = y
    let icube = (num*num*num).ToString().ToCharArray() |> Seq.sort |> Seq.toList
    member x.Num
        with get() = num
    member x.Cube
        with get() = icube

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

let mutable CheckSet =
    [1000L .. 9000L]
    |> Seq.map (fun x -> new TestCase(x))
    |> Seq.toList

Console.WriteLine("starting check")

let Check (num:TestCase) =
    let count =
        CheckSet
        |> Seq.filter (fun (x:TestCase) -> num.Cube = x.Cube)
        |> Seq.length
    if count = 5 then
        true
    else
        false

let Answer =
    let n =
        CheckSet
        |> PSeq.filter Check
        |> PSeq.toList
    n.[0]

Console.WriteLine(Answer.Num*Answer.Num*Answer.Num)
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.ReadKey() |> ignore

Problem #70 says:

Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 10^(7), for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

For this problem we can take advantage of a nifty property of Euler’s totient. if we have a number that is the product of two(or more) primes such that P = J*K where J and K are Prime then the totient can be found with the formula φ(P) = (J-1)*(K-1). So we need a range of prime numbers that when we multiple the two highest numbers gives us a comfortable overhead on the maximum range we are checking. We then pair all of these numbers together by looping through them with two loops and by using two prime numbers to generate the number P we get the nifty totient function and we also maximize φ(P) by limiting the distinct factors of P.

Solution provided in f# requires .net4 and visual studio RC. Runs in about 4 seconds including prime generation.

#light

open System
open System.Diagnostics
//open Microsoft.FSharp.Linq
open Microsoft.FSharp.Collections

//prime generation from
//http://stackoverflow.com/questions/2053691/can-the-execution-time-of-this-prime-number-generator-be-improved
let is_prime_juliet n =
    let maxFactor = int64(sqrt(float n))
    let rec loop testPrime tog =
        if testPrime > maxFactor then true
        elif n % testPrime = 0L then false
        else loop (testPrime + tog) (6L - tog)
    if n = 2L || n = 3L || n = 5L then true
    elif n <= 1L || n % 2L = 0L || n % 3L = 0L || n % 5L = 0L then false
    else loop 7L 4L

let getPrimes upTo =
    seq {
        yield 2L;
        yield 3L;
        yield 5L;
        yield! (7L, 4L)
        |> Seq.unfold (fun (p, tog) -> if p <= upTo then Some(p, (p + tog, 6L - tog)) else None)
    }
    |> Seq.filter is_prime_juliet

let w = new Stopwatch();
w.Start()

let Primes =
    (getPrimes 5000L) 

w.Stop()
Console.WriteLine("Primes Generated in")
Console.WriteLine(w.Elapsed)

let Perm x y =
    (x.ToString().ToCharArray()
    |> Seq.sort
    |> Seq.toList) = (y.ToString().ToCharArray()
    |> Seq.sort
    |> Seq.toList)

Console.WriteLine("Starting Check")
let watch = new Stopwatch()
watch.Start()

let answer =
    let mutable num = 1L
    let mutable min = Decimal 100
    for j in Primes do
        for k in Primes do
            if (j <> k) then
                let i = j * k
                if i < 10000000L then
                    let totient = (j-1L)*(k-1L)
                    if (Perm i totient) then
                        if (Decimal i / Decimal totient) < min then
                            min <- (Decimal i / Decimal totient)
                            num <- i
    num

Console.WriteLine(answer)
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.ReadKey() |> ignore

Problem #69 says:

Euler’s Totient function, φ(n) [sometimes called the phi function], is used to determine the number of
numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than
nine and relatively prime to nine, φ(9)=6.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

For this problem I created a class that held the number and it’s totient and then create them in parallel.
Then I loop through the mess looking for the instance with the highest check value. The Parallelism is handled by
the PSeq object from the F# power pack.

Solution in f# and requires .net 4 and the F# power pack from codeplex. Runs in ~48 seconds.

#light

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

//set the limit and bound
let UpperLimit = 1000000.
let UpperBound = (Math.Sqrt(UpperLimit))

//generate numbers to check
let Primes = ref [2. .. (UpperLimit)] in

// loop through all numbers
// keep removing numbers that divide evenly
for div = 2 to int UpperBound do
  Primes := List.filter(fun num -> (num % (float div) <> 0. || (float div) >= num))
        !Primes
done;

let rec factorise (n:float) =
    if n = 1. then [] else
    let a = !Primes |> List.find (fun x -> n % x = 0.)
    a :: factorise (n / a)

let Totient (x:float) =
    (factorise x)
    |> Seq.distinct
    |> Seq.map (fun x -> 1. - (1./x))
    |> Seq.fold(fun acc a -> acc * a) x

type TestCase (Num:float) =
    let mutable _num = Num
    let _tot = Totient (float _num)
    member x.num
        with get() = _num
        and set(v) = _num <- v

    member x.Check
        with get() = x.num / _tot

Console.WriteLine("Starting Check")
let watch = new Stopwatch()
watch.Start()

let Answer =
    let mutable Ans = new TestCase(1.)
    let Tests =
        [2. .. 1000000.]
        |> PSeq.map (fun x -> new TestCase(x))
    for t in Tests do
        if t.Check > Ans.Check then
            Ans <- t
    Ans.num

Console.WriteLine(Answer)
watch.Stop()
Console.WriteLine(watch.Elapsed)
Console.ReadKey() |> ignore