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

Note: This solution marks my completion of 1- 50 in the project euler problem set. bringing the total number of problems I’ve solved to 64.

Problem #26 says

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Where 0.1(6) means 0.166666…, and has a 1-digit recurring cycle. It can be seen that ^(1)/_(7) has a 6-digit recurring cycle.

Find the value of d < 1000 for which ^(1)/_(d) contains the longest recurring cycle in its decimal fraction part.

The trick to this one is to realize that the decimals your going to end up dealing with are not going to fit into and standard decimal class. So you could go and try to find an arbitrary precision decimal class and then convert it to a string and hook that into some pattern detection. Or you can use a simple trick to build an array of quotients using nothing but integer math and check to see if you start going through the same sequence.

Solution provided below is in f# and requires .net 4. runs in under one second.

// Learn more about F# at http://fsharp.net
#light
open System
open System.Diagnostics
open System.Collections.Generic

//get some prime numbers
//set the limit and bound
let UpperLimit = 1000.
let UpperBound = 1000
//generate numbers to check
let LNums = ref [2..(int UpperLimit)] in
// loop through all numbers
// keep removing numbers that divide evenly
for div = 2 to UpperBound do
  LNums := List.filter(fun num -> (num % div <> 0 || div >= num))
        !LNums
done;
let Primes:list<int> = !LNums

let divby rem div =
    let y =
        [0..4]
        |> Seq.filter (fun x -> (rem * int (float 10 ** float x)) > div)
    if (y |> Seq.length) <> 0 then
        let miny = Seq.min y
        rem * int (float 10 ** float miny) % div
    else
        0

let rec patternlength init (rems:list<int>) d =
    let rem = divby init d
    if (List.exists (fun x -> x = rem) rems) then
        (rems.Length - (List.findIndex (fun y -> y = rem) rems))
    else
        patternlength rem (List.append rems [rem]) d

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

let Check =
    let mutable Longest = 0
    let mutable Nlongest = 0
    for p in Primes do
        let l = patternlength 1 [] p
        if l > Longest then
            Longest <- l
            Nlongest <- p
    Nlongest

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

Problem #46 says

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^(2)
15 = 7 + 2×2^(2)
21 = 3 + 2×3^(2)
25 = 7 + 2×3^(2)
27 = 19 + 2×2^(2)
33 = 31 + 2×1^(2)

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Solution below uses the method of generating a list of primes and then using a set list of numbers to square and checking the combination’s to see if we can find one that makes the number we’re looking for.

Solution provided in f# and requires .net 4. runs in ~50 seconds. could be made much faster by rewriting the “Check” function to use a set of recursive functions instead of for loops so we could break out of them.

#light
open System
open System.Diagnostics
open System.Collections.Generic

//get some prime factors
//set the limit and bound
let UpperLimit = 10000.
let UpperBound = 10000
//generate numbers to check
let LNums = ref [2..(int UpperLimit)] in
// loop through all numbers
// keep removing numbers that divide evenly
for div = 2 to UpperBound do
  LNums := List.filter(fun num -> (num % div <> 0 || div >= num))
        !LNums
done;
let Primes:list<int> = !LNums

//numbers to check
let nums = [13 .. 6000]

let NonPrime =
     (Set.ofList nums) - (Set.ofList Primes) |> Set.toList |> List.filter (fun x -> x % 2 <> 0)

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

let Check number =
    let mutable RetValue = true
    for n in Primes do
        for c in [1..100] do
            if (n + (2 * (c * c))) = number then
                RetValue <- false
    RetValue

let N =
    NonPrime
    |> Seq.filter Check
    |> Seq.toArray

watch.Stop()
Console.WriteLine(N.[0])
Console.WriteLine(watch.Elapsed)
Console.ReadKey()

UPDATED: solution now faster.

Problem 47 says:

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?

So I attempted to do this one in F# to help me learn the language and the basic work flow I came up with for the first attempt was to create the list of numbers to check use Seq.windowed to group them in series of 4 then to factor and check there factors against one another.

Solution below requires .net 4 and f# and runs in about 2 min.

#light
open System
open System.Diagnostics
open System.Collections.Generic

//numbers to check
let nums = [130000 .. 140000]

//get some prime factors

//set the limit and bound
let UpperLimit = 5000.
let UpperBound = 5000

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

let DivisorTest x y =
    if (x % y =0) then
        true
    else
        false

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

let Primes:list<int> = !LNums

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

let union l1 l2 l3 l4 =
    l1 @ l2 @ l3 @ l4 |> Seq.distinct |> List.ofSeq

let UniqueList factors =
    let dict = new Dictionary<int,int>()
    for x in factors do
        if (dict.ContainsKey x) then
            dict.[x] <- dict.[x] + 1
        else
            dict.Add(x,1)
    let mutable t2 = []
    for x2 in dict.Keys do
        t2 <- int ((double x2) ** (double dict.[x2])) :: t2
    t2

let NonPrime = (Set.ofList nums) - (Set.ofList Primes) |> Set.toList

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

let MList l =
    let l2:int = List.reduce (fun acc elem -> acc * elem) l
    l2

let Check (L:array<int list>) =
    let n1:list<int> = L.[0]
    let n2:list<int> = L.[1]
    let n3:list<int> = L.[2]
    let n4:list<int> = L.[3]
    if (n1.Length <> 4) || (n2.Length <> 4) || (n3.Length <> 4) || (n4.Length <> 4) then
        false
    else
        if ((MList n1)+1) <> (MList n2) then
            false
        else if ((MList n2)+1) <> (MList n3) then
            false
        else if ((MList n3)+1) <> (MList n4) then
            false
        else
            true

let CheckLength (l:list<int>) =
    if l.Length <> 4 then
        false
    else
        true

let N =
    NonPrime
    |> Seq.map factorise
    |> Seq.map UniqueList
    |> Seq.distinct
    |> Seq.filter CheckLength
    |> Seq.windowed 4
    |> Seq.filter Check
    |> Seq.take 1
    |> Seq.toArray

watch.Stop()

Console.WriteLine((MList N.[0].[0]))
Console.WriteLine(watch.Elapsed)
Console.ReadKey()