Problem 049


Project Euler

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?


This problem is working with prime again and since we created a function from problem 43 to output the next permutation of a number, I thought it would be simple. However, the function I created does not account for repeating number like 1123. Since I know there is only 4 digits number involve in this problem. I created 2D array that map 0-3 into its 24 permutation and use this same array to get all 24 permutation of each number I want to test.

I want to minimize the number of value I have to test. To start of, I know I only need to test from 1001 to 9999 with increment of 2 because we need 4 digits prime number.

Since we have an array of all the prime value from our prime sieve, we can eliminate any composite value at the beginning.

Next, of the 24 permutation created from a single number, I can again test for prime, any repeated number, and any number less than 1000. For example, 1063 and its permutation 0163 are both prime but 0163 is less than 1000 so it can’t be part of the solution.

Then, I’ll sort the permutation and check for any three permutations that are equally apart. Whether I found the solution or not, I am done with all the number in the permutation list and can mark them off as if they are composite number so I don’t have to check them again. For example, once I found the solution for 1487, I can skip 4817, 8147 and any permutation of these digits later in my program.

for (i = 1001; i < 9999; i+= 2) {
  if (isValid(i))
    createPermutation(i);
    if (findAnswer())
       printAnswer();
    invalidate(i);
}

isValid() check if i is prime or i has been one of the permutation used previously. createPermutation() create a list of 24 permutation from i, remove repeat, remove invalid number, and sort the permutation in ascending order. findAnswer() check and store the 3 values that is equally apart. printAnswer() is self-explanatory and invalidate() just mark all permutation created by i as invalid so that it will never be use again to search for the solution.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s