Problem #104 says:

Given that F(k) is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

First of all the Fibonacci number F(k) is some 68 thousand digits long. It’s insane to try to and brute force this using a big int class and a couple of variables; and it only gets worse if one tries to use a recursive algorithm. Even if you use some caching of previous Fibonacci terms the program still won’t get close to the answer before running out of memory.

So how can we solve this? Well consider what we need to look at; the first and last 9 digits. Which means of some 68 thousand digits we care about 18 of them so why bother calculating the rest? To do this for the last 9 digits should be pretty obvious. If we have the two previous Fibonacci numbers that are added to get the next Fibonacci number what we can do is only remember the Fibonacci number mod one billion. This will chop off all the numbers except for the last few which is what we want. We can then use a long data type to store and calculate the Fibonacci series (or at least the last couple of digits of it).

How then do we get the first couple of digits to check that? We can use a formula called Binet’s formula.
\[F(n) = \frac{\Phi^{n}-(1-\Phi)^{n}}{\sqrt{5}}\]
This helps because we only need to give it the k term we’re looking for and it will give back the first digits of the term F(k) without calculating the intervening terms. We modify it a bit to fit into c#/mono data types (basically we use it log base ten) with some other magic built it.

So the solution is provided below in c#/mono developed in monodevelop; runs in about 2 seconds.

using System;
using System.Linq;

namespace Problem104
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			long fnm2 = 1L;
			long fnm1 =1L;
			long fn = 0L;
			decimal k = 2;
			bool found = false;

			while (!found)
			{
				k++;

				fn = fnm2 + fnm1;

				if (CheckBottomDigits(fn))
				{
					if (CheckTopDigits(k))
						found = true;
				}

				fnm2 = fnm1 % 1000000000;
				fnm1 = fn % 1000000000;

				if (k % 500 == 0)
					Console.WriteLine(k);

			}

			Console.WriteLine(k);

		}
		public static decimal philog10 = decimal.Parse("0.2089876402499787");
		public static decimal sqrt5log10 = decimal.Parse("-0.349485002168009");
		public static bool CheckTopDigits (decimal n)
		{

			decimal td = (n * philog10) + sqrt5log10;
			double t = Math.Pow(10,(double)(td - (int)td + 8));

			if (t.ToString().Length < 9)
				return false;

			if (PanDigital(t.ToString().Substring(0,9)))
				return true;
			else
				return false;

		}

		public static bool CheckBottomDigits (long check)
		{
			string num = check.ToString();
			if ( num.Length >= 9)
			{
				if (PanDigital(num.Substring(num.Length - 9,9)))
					return true;
			}
			return false;
		}

		public static bool PanDigital (string num)
		{
			bool pan = true;
			if (!num.Contains('1'))
				pan = false;
			if (!num.Contains('2'))
				pan = false;
			if (!num.Contains('3'))
				pan = false;
			if (!num.Contains('4'))
				pan = false;
			if (!num.Contains('5'))
				pan = false;
			if (!num.Contains('6'))
				pan = false;
			if (!num.Contains('7'))
				pan = false;
			if (!num.Contains('8'))
				pan = false;
			if (!num.Contains('9'))
				pan = false;

			return pan;
		}
	}
}

So I was wandering the internet when I found an article about steganography, which is the art of hiding something in plain sight. Such as hiding a message inside a picture. Specifically the least significant bit method where you take the RGB color values of the pixel and set them based off a message in binary your encoding. So I figured I’d work something up and see if I could do that. This is a first attempt and it only encodes the message, right now it’ll truncate it if it doesn’t have enough pixels to work with or if the message length in binary isn’t divisible by three. Obviously this is a first attempt and a very simple one at that.

So basically you give it a picture and a text file and it reads the text file as a single string, converts it to binary then for each pixel it sets each of the RGB values based off the binary message value for that position. In this example if the binary message is odd for this position we set the color to an odd number (in effect setting the least significant bit to 1) else we make sure its an even number.

I have a few plans for expanding this project. It would be nice to decode the messages first of all, it would also be nice to have some options for encoding such as skipping a certain number of pixels between parts of the message, Only using certain color channels etc. But for now this is what I have.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.IO;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace Steganography
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void btnBrowse_Click(object sender, EventArgs e)
        {
            OpenFileDialog op = new OpenFileDialog();
            op.CheckPathExists = true;
            op.CheckFileExists = true;
            op.Filter = "JPG image |*.jpg";
            op.ShowDialog();
            textBox1.Text = op.FileName;
        }

        private void textBox1_TextChanged(object sender, EventArgs e)
        {
            try
            {
                Preview.ImageLocation = textBox1.Text ;
            }
            catch
            {

            }
        }

        private void BrowseMessage_Click(object sender, EventArgs e)
        {
            OpenFileDialog op = new OpenFileDialog();
            op.CheckPathExists = true;
            op.CheckFileExists = true;
            op.ShowDialog();
            textBox2.Text = op.FileName;
        }

        private void button1_Click(object sender, EventArgs e)
        {
            MessageBox.Show("Your image will be saved as " + textBox1.Text +".new");
            //Get message as a binary string;
            string message = LoadMessage(textBox2.Text);
            string binmessage = "";
            foreach (char letter in message.ToCharArray())
            {
                binmessage += Convert.ToString(letter, 2);
            }
            //get bitmap of image.
            Bitmap bitm = (Bitmap)Preview.Image.Clone();
            int mPosition = 0;
            //Embed message
            #region embed
            for (int height = 0; height < bitm.Height; height++)
            {
                for (int width = 0; width < bitm.Width; width++)
                {
                    if (mPosition + 3 <= binmessage.Length)
                    {
                        Color pixelColor = bitm.GetPixel(width, height);
                        int R = int.Parse(pixelColor.R.ToString());
                        int G = int.Parse(pixelColor.G.ToString());
                        int B = int.Parse(pixelColor.B.ToString());
                        int m1 = int.Parse(binmessage[mPosition].ToString());
                        mPosition++;
                        int m2 = int.Parse(binmessage[mPosition].ToString());
                        mPosition++;
                        int m3 = int.Parse(binmessage[mPosition].ToString());
                        mPosition++;

                        if (m1 % 2 == 0)
                        {
                            if (R % 2 != 0 && R > 0)
                            {
                                R -= 1;
                            }
                            else
                            {
                                R += 1;
                            }
                        }
                        else
                        {
                            if (R % 2 != 1 && R > 0)
                            {
                                R -= 1;
                            }
                            else
                            {
                                R += 1;
                            }
                        }
                        if (m2 % 2 == 0)
                        {
                            if (G % 2 != 0 && G > 0)
                            {
                                G -= 1;
                            }
                            else
                            {
                                G += 1;
                            }
                        }
                        else
                        {
                            if (G % 2 != 1 && G > 0)
                            {
                                G -= 1;
                            }
                            else
                            {
                                G += 1;
                            }
                        }
                        if (m3 % 2 == 0)
                        {
                            if (B % 2 != 0 && B > 0)
                            {
                                B -= 1;
                            }
                            else
                            {
                                B += 1;
                            }
                        }
                        else
                        {
                            if (B % 2 != 1 && B > 0)
                            {
                                B -= 1;
                            }
                            else
                            {
                                B += 1;
                            }
                        }
                        Color pc = Color.FromArgb(R, G, B);
                        bitm.SetPixel(width, height, pc);

                    }
                    else
                    {
                    }
                }
            }
            #endregion embed

            bitm.Save(textBox1.Text + ".new");

        }

        private string LoadMessage(string p)
        {
            string RetValue = "";
            StreamReader sr;
            sr = File.OpenText(p);
            RetValue = sr.ReadToEnd();
            sr.Close();
            return RetValue;
        }
    }
}

Problem 214 says:

Let φ be Euler’s totient function, i.e. for a natural number n, φ(n) is the number of k, 1 ≤ k ≤ n, for which gcd(k,n) = 1.

By iterating φ, each positive integer generates a decreasing chain of numbers ending in 1.
E.g. if we start with 5 the sequence 5,4,2,1 is generated.
Here is a listing of all chains with length 4:
5,4,2,1
7,6,2,1
8,4,2,1
9,6,2,1
10,4,2,1
12,4,2,1
14,6,2,1
18,6,2,1

Only two of these chains start with a prime, their sum is 12.

What is the sum of all primes less than 40000000 which generate a chain of length 25?

My first approach is to build a list of primes less than 40000000, and keeps a hashtable of all the totients that the program solves for, as well as a hashtable for storing all of the previous chains the program has come across. It works but it takes an age to give the answer, even when using .net 4′s task parallel library. So I’ll be reworking this and posting a better version.

Until then, here is the code. (C# requires .net 4)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;
namespace Problem214
{
	class MainClass
	{
        public static long[] primes = GetPrimesUpTo(40000000);
		public static Hashtable knownTotients = new Hashtable();
        public static Hashtable KnownChains = new Hashtable();
        private static object lockObject = new object();
        private static object lockObject2 = new object();

		public static void Main (string[] args)
		{
			long sum = 0L;
            Console.WriteLine("starting search");
            Parallel.ForEach(primes, p =>
            {
                //Console.WriteLine(p);
                if (Chain25((int)p))
                {
                    lock (lockObject)
                    {
                        sum = sum + p;
                        Console.WriteLine("Current Sum :: "+sum.ToString());
                    }
                }
            });
            Console.WriteLine(sum);
			Console.ReadLine();
		}
		static bool Chain25 (int num)
		{
			if (ChainLen(num) == 25)
				return true;
			else
				return false;
		}
		static int ChainLen (int num)
		{
			int c = chain(num,1);
            KnownChains.Add(num, c);
			return c;
		}
		static int chain(int num, int len)
		{
            if (KnownChains.Contains(num))
                return len + (int)KnownChains[num];
			if (len >= 25) return 60000;
            int phin = eulerTotientWrap(num);
			if (phin != 1) return chain(phin,len+1);
			else return len++;
		}
		static bool[] GetPrimeSieve(long upTo)
		{
		    long sieveSize = upTo + 1;
		    bool[] sieve = new bool[sieveSize];
		    Array.Clear(sieve, 0, (int)sieveSize);
		    sieve[0] = true;
		    sieve[1] = true;
		    long p, max = (long)Math.Sqrt(sieveSize) + 1;
		    for (long i = 2; i <= max; i++)
		    {
		        if (sieve[i]) continue;
		        p = i + i;
		        while (p < sieveSize) { sieve[p] = true; p += i; }
		    }
		    return sieve;
		}
		static long[] GetPrimesUpTo(long upTo)
		{
		    if (upTo < 2) return null;
		    bool[] sieve = GetPrimeSieve(upTo);
		    long[] primes = new long[upTo + 1];

		    long index = 0;
		    for (long i = 2; i <= upTo; i++) if (!sieve[i]) primes[index++] = i;

		    Array.Resize(ref primes, (int)index);
		    return primes;
		}
		static int GetLastIndex(int n)
		{
			for (int i = 0; i< primes.Length;i++)
			{
				if (primes[i] >= n)
					return i+1;
			}
			return primes.Length;
		}
        static int eulerTotientWrap(int n)
        {
            if (knownTotients.Contains(n))
                return (int)knownTotients[n];
            int t = eulerTotient(n);
            lock (lockObject2)
            {
                if (!knownTotients.Contains(n))
                    knownTotients.Add(n, t);
            }
            return t;

        }
		static int eulerTotient(int n)
		{
		    int numPrimes = GetLastIndex(n);

		    int totient = n;
		    int currentNum = n, temp, p, prevP = 0;
		    for (int i = 0; i < numPrimes; i++)
		    {
		        p = (int)primes[i];
		        if (p > currentNum) break;
		        temp = currentNum / p;
		        if (temp * p == currentNum)
		        {
		            currentNum = temp;
		            i--;
		            if (prevP != p) { prevP = p; totient -= (totient / p); }
		        }
		    }
		    return totient;
		}
	}
}

Problem 102 says:

Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.

Consider the following two triangles:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

This problem can be solved in a lot of different ways depending on how one wishes to approach it. You can find the angle of each two point pair of the triangle and the origin and check to see if they add to 360 degrees which would mean the point is inside the triangle, construct a special matrix and take the determinant, etc. However I chose to use a half plane method because it was quicker to implement and didn’t take that much longer to run. Basically we take the two point pairings of the points of the triangle and check to see if the origin is on the same side for all of them. I make the assumption that because they did not mention how points on the edge of the triangle should be handled that there are no such points which allows us to skip some checking.

Solution provided in c#/mono, runs in about .01 second including reading the file.

using System;
using System.Diagnostics;
using System.Drawing;
namespace Problem102
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			PointF origin = new PointF(0f,0f);
			Stopwatch sw = new Stopwatch();
			sw.Start();

			int TrianglesWithOrigin = 0;

			string line;
			System.IO.StreamReader file = new System.IO.StreamReader("triangles.txt");
			while((line = file.ReadLine()) != null)
			{
				string[] values = line.Split(',');
				PointF p1 = new PointF(float.Parse(values[0]),float.Parse(values[1]));
				PointF p2 = new PointF(float.Parse(values[2]),float.Parse(values[3]));
				PointF p3 = new PointF(float.Parse(values[4]),float.Parse(values[5]));
				if (Inside(origin,p1,p2,p3))
					TrianglesWithOrigin += 1;
			}
			file.Close();
			sw.Stop();
			Console.WriteLine(TrianglesWithOrigin);
			Console.WriteLine(sw.Elapsed);
			Console.ReadLine();
		}
		public static float Sign (PointF p1, PointF p2, PointF p3)
		{
			return (p1.X - p3.X) * (p2.Y - p3.Y) - (p2.X - p3.X) * (p1.Y - p3.Y);
		}
		public static bool Inside (PointF pt, PointF p1, PointF p2, PointF p3)
		{
			bool b1 = Sign(pt, p1, p2) < 0.0f;
			bool b2 = Sign(pt, p2, p3) < 0.0f;
  			bool b3 = Sign(pt, p3, p1) < 0.0f;
			return ((b1 == b2) && (b2 == b3));
		}

	}
}

Problem #75 says:

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer
sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right
angle triangle, and other lengths allow more than one solution to be found; for example,
using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly
one integer sided right angle triangle be formed?

Another counting problem but here we have to avoid duplicate entries that can come from a variety
of places. This solution uses the 2 number approach for generating Pythagorean triples, which it then finds
the lengths of the triple and catalogs it in an array to track duplicates, Then counts all the values of the
array that equal 1 for the final answer.

Solution is provided in c#/mono. Runs in under one second.

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

namespace Problem75
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			Stopwatch sw = new Stopwatch();
			sw.Start();
			int limit = 1500000;
			int adjlimit = (int)(Math.Sqrt((float)limit));
			ArrayList tri = new ArrayList(limit);

			for (int st = 0; st < limit+1; st++)
				tri.Add(0);

			for (int i = 1; i <= adjlimit; i=i+2)
			{
				for (int j = 2; j<= adjlimit; j=j+2)
				{
					if (GCD(i,j) == 1)
					{
						int sum = Math.Abs((j*j) - (i*i)) + (2*j*i) + ((i*i) + (j*j));
						for (int s = sum; s < limit; s=s+sum)
						{

							tri[s] = (int)tri[s]+1;
						}
					}
				}
			}
			Console.WriteLine(TallyResults(tri));
			sw.Stop();
			Console.WriteLine(sw.Elapsed);
			Console.ReadLine();
		}
		public static int TallyResults(ArrayList a)
		{
			int RetVal = 0;
			foreach (int i in a)
			{
				if (i == 1)
					RetVal= RetVal+1;
			}
			return RetVal;
		}
		public static int GCD (int a, int b)
		{
			if (b == 0)
				return a;
			else
				return GCD(b,(a%b));
		}
	}
}