Project Euler Problem 49

Problem 49

01 August 2003

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?

Answer: 296962999629

 

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    static class Program {
        static bool isPrime(int value) {
            if (value <= 1) return false;
            for (int i = 2; i * i <= value; i++) {
                if (value % i == 0) return false;
            }
            return true;
        }

        static void Main(string[] args) {
            for (var n = 1487; n <= 9999; n++) {
                if (!isPrime(n)) continue;
                var strN = new HashSet<char>(n.ToString());
                var incMax = (9999 - n) / 2;
                for (var inc = 1; inc <= incMax; inc++) {                    
                    var n2 = n + inc;
                    if (!isPrime(n2)) continue;
                    var strN2 = new HashSet<char>(n2.ToString());
                    if (strN.SetEquals(strN2)) {
                        var n3 = n2 + inc;
                        if (!isPrime(n3)) continue;
                        var strN3 = new HashSet<char>(n3.ToString());
                        if (strN.SetEquals(strN3)) {
                            Console.WriteLine("{0}{1}{2}", n, n2, n3);                            
                        }
                    }
                }
            }
            Console.ReadKey();
        }
    }
}