Monday 13 April 2009

PROJECT EULER #43

Link to Project Euler problem 43

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

The clue here was to find d8d9d10 first as there are only 58 multiples of 17 under 1000, then to remove these digits from the List. The next digit is added and we check if d7d8d9 is divisible by 13. If so, remove this digit from the list. The next digit is added etc.

As we step back up the for-loops we put the digits back into the list. When there are only two digits left, both will produce d2d3d4 divisible by 2. Numbers with a leading zero (d1 = 0) are excluded.


using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
static void Main()
{
//Problem 43
DateTime start = DateTime.Now;
long sum = 0;
//find numbers divisible by 17
for (int i = 17; i < 1000; i += 17)
{
List<string> test = new List<string> { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };
//Add leading zero if < 100
string ia = i < 100 ? "0" + i : i.ToString();

//Check uniqueness
if (ia[0] != ia[1] && ia[0] != ia[2] && ia[1] != ia[2])
{
//remove from list
for (int j = 0; j < 3; j++)
test.Remove(ia[j].ToString());//7 left
for (int j = 0; j < test.Count; j++)
{
string js = test[j];
if (int.Parse(js + ia[0] + ia[1]) % 13 == 0)
{
test.Remove(js);//6 left
for (int k = 0; k < test.Count; k++)
{
string ks = test[k];
if (int.Parse(ks + js + ia[0]) % 11 == 0)
{
test.Remove(ks);//5 left
for (int l = 0; l < test.Count; l++)
{
string ls = test[l];
if (int.Parse(ls + ks + js) % 7 == 0)
{
test.Remove(ls);//4 left
for (int m = 0; m < test.Count; m++)
{
string ms = test[m];
if (int.Parse(ms + ls + ks) % 5 == 0)
{
test.Remove(ms);//3 left
for (int n = 0; n < test.Count; n++)
{
string ns = test[n];
if (int.Parse(ns + ms + ls) % 3 == 0)
{
test.Remove(ns);//2 left
if (int.Parse(ms) % 2 ==0)
{
sum += long.Parse(test[1] + test[0] + ns + ms + ls + ks + js + ia);
if (test[0]!="0")
{
sum += long.Parse(test[0] + test[1] + ns + ms + ls + ks + js + ia);
}
}
test.Add(ns);
test.Sort();
}
}
test.Add(ms);
test.Sort();
}
}
test.Add(ls);
test.Sort();
}
}
test.Add(ks);
test.Sort();
}
}
test.Add(js);
test.Sort();
}
}
}
}
Console.WriteLine(sum);
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
}
}

No comments: