Thursday 16 April 2009

PROJECT EULER #49

Link to Projrct Euler poblem 49


The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?



using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
static void Main()
{
//Problem 49
DateTime start = DateTime.Now;
List<int> primes = GeneratePrimes(10000);
while (primes[0] < 1000)
primes.Remove(primes[0]);
for (int i = 0; i < primes.Count; i++)
{
char[] c = primes[i].ToString().ToCharArray();
Array.Sort(c);
string s = new string(c);
for (int j = i + 1; j < primes.Count; j++)
{
char[] d = primes[j].ToString().ToCharArray();
Array.Sort(d);
string t = new string(d);
if (s == t)
if (primes.Contains(primes[i] + 2 * (primes[j] - primes[i])))
{
int third = primes[i] + 2 * (primes[j] - primes[i]);
char[] e = third.ToString().ToCharArray();
Array.Sort(e);
string u = new string(e);
if (u == t && u != "1478")
{
string result = primes[i].ToString() + primes[j] + third;
Console.WriteLine(result);
}
}
}
}
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 primes = new List<int> { 2, 3 };
for (int i = 5; i <= n; i += 2)
{
if (IsPrime(i))
primes.Add(i);
}
return primes;
}
}
}

No comments: