Project Euler - Problem 49

Today we'll look at problem 49 in project euler:

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?

Simple, but interesting!

My strategy was to use my primes sieve to generate primes up to 10000, then look for series which were prime and permutations - brute force essentially.

The only piece of code I didn't have was a method to compare two numbers and evaluate if they were permutations of one another. So I came up with the following:

public static bool IsPermutation(int n1, int n2)

{

char[] ac1 = n1.ToString().ToCharArray();

char[] ac2 = n2.ToString().ToCharArray();

if (ac1.Length != ac2.Length) return false;

Array.Sort(ac1);

Array.Sort(ac2);

for (int i = 0; i < ac1.Length; i++)

if (ac1[i] != ac2[i]) return false;

return true;

}

Works well enough!

All that remains is some ugly nested loops and ifs:

var primes = CustomMath.Primes(10000);

for (int prime = 1489; prime < 10000; prime += 2)

{

if (primes[prime])

{

for (int nextPrime = prime + 2; nextPrime < 10000; nextPrime += 2)

{

int thirdPrime = 2 * nextPrime - prime;

if (thirdPrime.ToString().Length > 4) break;

if (primes[nextPrime] && primes[thirdPrime])

{

if (IsPermutation(prime, nextPrime) && IsPermutation(prime, thirdPrime))

{

var sb = new StringBuilder();

sb.Append(prime);

sb.Append(nextPrime);

sb.Append(thirdPrime);

return sb.ToString();

}

}

}

}

}

You'll notice I'm starting at 1489, the first odd digit above the given sequence. Yes, I did check from 1001 first, but it stopped after finding the sequence at 1487, so then I checked above that number. Runs in about 100ms.

For the curious, the next (and only other sequence) is:

2969

6299

9629