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

PROJECT EULER #77

Link to Project Euler problem 77

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

A modification of the previous algorithm

using System;
using System.Collections.Generic;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 77
            DateTime start = DateTime.Now;
            var primes = GeneratePrimes(80);
            int maxNumber = 80,target=0,sum=0;
            int[,] a = new int[maxNumber + 1, maxNumber + 1];
            for (int i = 0; i < maxNumber + 1; i++)
            {
                a[i, 0] = 0;
                a[0, i] = 1;
            }
            int n = 2;
            while (sum < 5000)
            {
                    if (n%2 == 0) a[n, 1] = 1;
                    else a[n, 1] = 0;
                    for (int j = 2; j < primes.Count; j++)
                    {
                        int k = n - primes[j];
                        if (k < 0)
                            a[n, j] = a[n, j - 1];
                        else
                            a[n, j] = a[n, j - 1] + a[k, j];
                        if (a[n, j] > 5000)
                        {
                            target = n;
                            sum = a[n, j];
                            break;
                        }
                    }
                n++;
            }
            Console.WriteLine(sum + "  " +target);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
        public static bool IsPrime(int n)
        {
            if (n < 2) return false;
            if (n == 2) return true;
            for (long i = 2; i <= Math.Sqrt(n); i++)
                if (n % i == 0) return false;
            return true;
        }
        public static List<int> GeneratePrimes(int n)
        {
            var primeNumbers = new List<int> { 0,2, 3 };
            for (int i = 5; i <= n; i += 2)
                if (IsPrime(i))
                    primeNumbers.Add(i);
            return primeNumbers;
        }
    }
}

PROJECT EULER #76

Link to Project Euler problem 76

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

Here we go...yet more virgin territory for me, but isn't that the point?
Partitions....the clue is to store values somewhere, so we do it in a 2-D grid.

using System;

namespace ProjectEuler
{
    class Program
    {
        static void Main()
        {
            //Problem 76
            DateTime start = DateTime.Now;
            int n = 100;
            int[,] a = new int[n + 1, n + 1];
            for (int i = 0; i < n + 1; i++)
            {
                a[i, 0] = 0;
                a[0, i] = 1;
            }
            for (int i = 1; i < n + 1; i++)
            {
                a[i, 1] = 1;
                for (int j = 2; j < n + 1; j++)
                {
                    int k = i - j;
                    if (k < 0)
                        a[i, j] = a[i, j - 1];
                    else
                        a[i, j] = a[i, j - 1] + a[k, j];
                }
            }
            Console.WriteLine(a[n, n - 1]);
            TimeSpan time = DateTime.Now - start;
            Console.WriteLine("This took {0}", time);
            Console.ReadKey();
        }
    }
}