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
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;
         }
      }
   }
}
Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *