(This post is the first in a new section on this site. This will probably become a regular item on the site as I read through the library of books I have laying about. As I have a lot of math related books around right now most of the book reviews will be math related at first.)

Mathematics: A Very Short Introduction is an easy to read book that attempts to explain to the reader the differences between research mathematics and the math taught in high schools. It covers subjects such as: mathematical modeling which is the creation of a mathematical system to describe a measurable phenomenon, Abstraction the application of ideas in a general manner, Proofs, Dimensions above an beyond the three we live in, Accurate Estimation plus a whole section on Questions the author (Timothy Gowers) is frequently asked. The book also touches on complex numbers, limits, and infinity making all of these ideas accessible for those that have never seen them before while not focusing on those ideas enough to bore the people already familiar with them (such as those that have taken a college calculus course). Mathematics: A Very Short Introductionuses diagrams and basic English to explain ideas and theories. There is almost no math in the book as it’s primarily about the type of work mathematicians come across in their daily jobs. This would be a good read for anybody that might be interested in going into mathematics to get a basic idea about what mathematics entails at the higher levels. The most interesting part of the book would have to be the chapter of questions the author is asked. It’s great to get the opinion from someone who has been in the field about some of the questions that appear, such as the common question of whether or not mathematicians burn out in their late twenties. With Mathematics: A Very Short Introduction costing less than $10 USD it’s a great book for anybody interested in math to pickup and read.

In preparation for some upcoming project euler problems I’ve been looking for faster methods of determining if a number is prime. One such method I’ve come across was the Miller-Rabin primality test which is a probabilistic test for determining if a given number is probably prime. The higher the value of s passed to the original function the higher the probability the answer is correct.

I found an example of this algorithm in python which I’ve rewritten to use in F#, I do not have the original python source but if you are interested in learning more you can check out the Wikipedia page.

The following code snippet uses .net 4′s BigInteger class for part of test. I have plans to rewrite it making more f# like right now its a direct translation of the python code.

open System.Numerics

let rec toBinary (n:BigInteger) r =
    if n > BigInteger.Zero then
        toBinary (n/(BigInteger 2)) (r @ [n% (BigInteger 2)])
    else
        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 Rand = new System.Random()

let MillerRabin (n:uint64) (s:int) =
    let mutable Prime = true
    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
    Prime

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 #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;
        }
    }
}

Problem #188 says:

     The hyperexponentiation or tetration of a number
a by a positive integer b, denoted by a↑↑b or ^(b)a,
is recursively defined by:

a↑↑1 = a,
a↑↑(k+1) = a^((a↑↑k)).

Thus we have e.g. 3↑↑2 = 3^(3) = 27,
hence 3↑↑3 = 3^(27) = 7625597484987
and 3↑↑4 is roughly 10^(3.6383346400240996*10^12).

Find the last 8 digits of 1777↑↑1855.

This problem rather basic when you think about it mathematically. And even simpler once you realize that python has a built in modulo parameter to its pow() function. Making this whole problem rather simple. And with a bit of poking around one realizes that you don’t have to go through the whole loop as the value we’re looking for appears in the first 20 loops through the program.
Anyway, Solution is in python (2.6).

def Tetrate(Base,Tetrate,Modulo):
    Value = 1
    while Tetrate:
        Value = pow(Base,Value,10**Modulo)
        Tetrate = Tetrate - 1
    return Value

print "Answer : ", Tetrate(1777,1855,8)