**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 LinkedHashSet<Integer> primes = new LinkedHashSet<Integer>(); { BigInteger number = BigInteger.valueOf(1000); number = number.nextProbablePrime(); while(number.compareTo(BigInteger.valueOf(10000)) < 0) { primes.add(number.intValue()); 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>(); perms.add(num); while((num = EulerUtils.Permutation.nextPermutation(num)) != null) { //build list of prime permutations if(primes.contains(num) && num > 1000) { perms.add(num); visited[num.intValue()-1000] = true; } } //analyze list of prime permutations for condition boolean found = false; if(perms.size() >= 3) { for(Integer i : perms) { for(int add = 1; add < 5000 && !found; add++) { 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; answer = Long.parseLong(tmp); found = true; } } } if(found) { break; } } } }