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()

Problem #142 say:

Find the smallest x + y + z with integers x > y > z > 0 such that x + y, x − y, x + z, x − z, y + z, y − z are all perfect squares.

Now one can brute force this by looping over x, y and z. That takes around 4 hours on a modern computer. However there are a few relationships we can take advantage of:

x+y=a
x-y=b
x+z=c
x-z=d
y+z=e
y-z=f

e=a-d
f=a-c
b=c-e

(x+z) = (x+y)-(x-z)
(y-z) = (x+y)-(x+z)
(x-y) = (x+z)-(y+z)

x=(a+b)/2
y=(e+f)/2
z=(c-d)/2

these relationships allow us to loop on a,c,d and get the rest of the numbers from those three, this makes the solution run in around 33 msecs. That’s around a ~436363% speedup! Solution provided in c#/mono.

using System;
using System.Collections;
using System.Diagnostics;

namespace ProjectEuler
{
    class Program
    {
        static object LockHandle = new object();
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            long a2, b2, c2, d2, e2, f2;
            bool solved = false;
            sw.Start();

            for (long a = 10;!solved;a++)
            {
                a2 = a * a;
                for (long c = 5 + (0 & a); c < a && !solved; c += 2)
                {
                    c2 = c * c;
                    f2 = a2 - c2;
                    if (f2 < 1 || !IsSquare(f2))
                        continue;
                    for (long d = 2 + (1 & c); d < c; d += 2)
                    {
                        d2 = d * d;
                        e2 = a2 - d2;
                        if (e2 < 1 || !IsSquare(e2))
                            continue;
                        b2 = c2 - e2;
                        if (b2 > 0 && IsSquare(b2))
                        {
                            long x = (a2 + b2) / 2;
                            long y = (e2 + f2) / 2;
                            long z = (c2 - d2) / 2;
                            solved = true;
                            Console.WriteLine("x= " + x.ToString() +
                                 " y = " + y.ToString() + " z = " + z.ToString()
                                 + " sum = " + (z + y + x).ToString());
                            break;
                        }
                    }

                }
            }

            Console.WriteLine(sw.Elapsed);
            Console.ReadLine();
        }
        public static bool IsSquare(long n )
        {
            double root = Math.Sqrt(n);
            return (root % 1 == 0);
        }
    }
}

Problem #112 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.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.

Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.

This is pretty simple. we just need a function that can tell us if a number qualifies as “bouncy” which means it can’t be increasing or decreasing. So we create three functions and then start counting. Solution below is in c#/mono and runs in well under a minute

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace ProjectEuler
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();

            double Count = 1;
            double NumBouncy = 0;

            while (NumBouncy / Count != .99)
            {
                Count++;
                if (Count % 50000 == 0)
                    Console.WriteLine(NumBouncy/Count);
                if (IsBouncy(Count))
                {
                    NumBouncy++;
                }

            }

            Console.WriteLine(Count);
            Console.WriteLine(sw.Elapsed);
            Console.ReadLine();
        }
        static bool IsBouncy(double l)
        {
            if (IsIncreasing(l))
                return false;
            if (IsDecreasing(l))
                return false;
            return true;
        }
        static bool IsIncreasing(double l)
        {
            char[] digits = l.ToString().ToCharArray();

            for (int i = 0; i < digits.Length-1; i++)
            {
                if (Convert.ToInt32(digits[i].ToString()) > Convert.ToInt32(digits[i+1].ToString()))
                {
                    return false;
                }
            }

            return true;
        }
        static bool IsDecreasing(double l)
        {
            char[] digits = l.ToString().ToCharArray();
            Array.Reverse(digits);

            for (int i = 0; i < digits.Length - 1; i++)
            {
                if (Convert.ToInt32(digits[i].ToString()) > Convert.ToInt32(digits[i + 1].ToString()))
                {
                    return false;
                }
            }
            return true;
        }
    }

}

Problem #145 says:

Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (10^(9))?

The solution below is c# with .Net 4.0. It does a very basic divide and conquer on the one billion numbers to check. This will take a while to run depending on your computer, it ran reasonably fast on a quad core machine. Pretty simple stuff could be made much faster but was written out of boredom.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Parallel;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics;

namespace Net4Test
{
    class Program
    {
        static object LockHandle = new object();
        static long Answer = 0;
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();

            Parallel.For(1L, 1000000000L, i =>
                {
                    if (i % 50000 == 0)
                        Console.WriteLine(i);

                    if (Reversable(i))
                    {
                        lock (LockHandle)
                        {
                            Answer += 1;
                        }
                    }

                });

            Console.WriteLine(Answer);
            sw.Stop();
            Console.WriteLine(sw.Elapsed);
            Console.ReadLine();
        }
        static bool Reversable(long l)
        {
            bool RetValue = true;
            char[] lchar = l.ToString().ToCharArray();
            Array.Reverse(lchar);

            if (lchar[0] != '0')
            {

                long Reversel = (long)Convert.ToDouble(new string(lchar));

                char[] AChar = (l + Reversel).ToString().ToCharArray();

                foreach (char c in AChar)
                {
                    if (!IsOdd(Convert.ToInt32(c.ToString())))
                        RetValue = false;
                }
            }
            else
                RetValue = false;
            return RetValue;
        }
        static bool IsOdd(int i)
        {
            if (i == 0)
                return false;
            if (i % 2 == 0)
                return false;
            else
                return true;
        }
    }
}