Thursday 30 April 2009

PROJECT EULER #78

Link to Project Euler problem 78

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.
OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O O
Find the least value of n for which p(n) is divisible by one million.

Well this was difficult, not to mention memory hungry. This solution ate about 4-5 gigs of ram before coming up with the answer in the nick of time. It's a variation on the two previous problems.



using System;
using System.Collections.Generic;

namespace ProjectEuler
{
class Program
{
static void Main()
{
//Problem 78
DateTime start = DateTime.Now;
var pOfN = new List<int[]> { new[] { 1 }, new[] { 1,1 } };
int max = 0;
bool success = false;
int n = 1;
while (!success)
{
n++;
int[] thisN = new int[n+1];
thisN[0] = 0;
thisN[1] = 1;
for (int i = 2; i < n+1; i++)
{
int k = n - i;
if (k < 0)
thisN[i] = thisN[i - 1];
else if (i < k)
thisN[i] = thisN[i - 1] + pOfN[k][i];
else
thisN[i] = thisN[i - 1] + pOfN[k][k];
if (thisN[i] > 10000000)
thisN[i] = thisN[i]%1000000;
}
if (thisN[thisN.Length - 1]%10000 == 0)
Console.WriteLine(thisN[thisN.Length - 1] + ", " + n);
pOfN.Add(thisN);
if (thisN[thisN.Length-1]%1000000==0)
{
max = n;
success = true;
}
}
Console.Write(pOfN[max][max]+", "+max);
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
}
}

No comments: