# Project Euler: Problem 49 – Prime permutations

#### Problem 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?

#### Idea:

The problem mentioned permutations, so right away I know I’m going to need to use the nextPermutation method I wrote for problem 24. I’m also going to need a list of all the 4 digit prime numbers (well, not really, but I thought it would be faster to compute them once rather than repeatedly call “isProbablePrime” in the BigInteger class.

I also made a “visited” array to see if any of the primes later on were permutations of a previous prime number (so I could skip over them). I then decided to generate a list of prime permutations based off a given number.

Now, since I didn’t know if the next answer would also exhibit the characteristic of being able to add 3330 to it and get 2 more prime permutations, I assumed that wouldn’t be the case (since the problem only said “increasing sequence” but failed to mention by how much).

Since the sequence had to contain at least 3 terms, I ignored anything less than that. From there I started adding 1 to 5000 to the initial number to see if the next number was prime, and if so, added that same number again.

```long answer = -1;
//get list of 4 digit primes
{
BigInteger number = BigInteger.valueOf(1000);
number = number.nextProbablePrime();
while(number.compareTo(BigInteger.valueOf(10000)) < 0) {
number = number.nextProbablePrime();
}
}

Iterator<Integer> itr = primes.iterator();
boolean[] visited = new boolean[9000];
while(itr.hasNext()) {
Integer num = itr.next();
//check to see if this is a permutation of an earlier prime
if(visited[num.intValue()-1000]) {
continue;
}
visited[num.intValue()-1000] = true;
ArrayList<Integer> perms = new ArrayList<Integer>();
while((num = EulerUtils.Permutation.nextPermutation(num)) != null) {
//build list of prime permutations
if(primes.contains(num) && num > 1000) {
visited[num.intValue()-1000] = true;
}
}
//analyze list of prime permutations for condition
boolean found = false;
if(perms.size() >= 3) {
for(Integer i : perms) {
int secondTerm = i.intValue() + add;
boolean inPrimes = primes.contains(secondTerm);
boolean inPerms = perms.contains(secondTerm);
if(!inPrimes || !inPerms) {
continue;
} else {
int thirdTerm = secondTerm + add;
inPrimes = primes.contains(thirdTerm);
inPerms = perms.contains(thirdTerm);
if(!inPrimes || !inPerms) {
continue;
} else {
//adding to a prime twice resulted in 2 primes
if(i.intValue() == 1487) {
//already have this, find the next one
continue;
}
String tmp = ""+i.intValue()+""+secondTerm+""+thirdTerm;