[C/C++] Project Euler #49 - Prime Permutations

Project Euler #49 Prime Permutations problem may seem complex, but the actual solving process is straightforward. The difficulty level is 5%, classified as “very easy.”

Three four-digit numbers are prime numbers that are permutations of each other.

For example, the numbers 1487, 4817, and 8147 consist of the same four digits (1, 4, 7, 8) arranged in different orders, and each of them is a prime number.

The task is to find another set of numbers that meet these conditions. (In fact, when considering all cases, there are only two such sets of four-digit numbers: the example given and the one that is the answer to this problem.)

---

When designing the algorithm, the most important part was how to generate permutations using four-digit numbers. Checking all possible cases would be possible, but the number of cases would be too large.

So, in my approach, I first selected four digits, then generated permutations using those digits, and checked whether the resulting numbers were prime. The number of permutations for a four-digit number is 4!, which is only 24 cases.

---

prime permutations

Here is the code I wrote:

//------------------------------------------------
//    Project Euler #49 - Prime Permutations
//        - by Aubrey Choi
//        - created at 2015-03-30
//------------------------------------------------
#include <stdio.h>
#include "isprime.h"

void TestAndDisplay(int n[], int s, int d);
int main()
{
    int n[4];
    TestAndDisplay(n, 0, 0);
}

void TestAndDisplay(int n[], int s, int d)
{
    int perm[][4] = 
    {
        { 0, 1, 2, 3 }, { 0, 1, 3, 2 }, { 0, 2, 1, 3 }, { 0, 2, 3, 1 },
        { 0, 3, 1, 2 }, { 0, 3, 2, 1 }, { 1, 0, 2, 3 }, { 1, 0, 3, 2 }, 
        { 1, 2, 0, 3 }, { 1, 2, 3, 0 }, { 1, 3, 0, 2 }, { 1, 3, 2, 0 },
        { 2, 0, 1, 3 }, { 2, 0, 3, 1 }, { 2, 1, 0, 3 }, { 2, 1, 3, 0 },
        { 2, 3, 0, 1 }, { 2, 3, 1, 0 }, { 3, 0, 1, 2 }, { 3, 0, 2, 1 },
        { 3, 1, 0, 2 }, { 3, 1, 2, 0 }, { 3, 2, 0, 1 }, { 3, 2, 1, 0 }
    };
    if( d == 4 )
    {
        int m[24], count = 0;
        for( int i = 0 ; i < 24 ; i++ )
        {
            int q = 0;
            for( int j = 0 ; j < 4 ; j++ ) { q*=10; q+=n[perm[i][j]]; }
            for( int j = 0 ; j < count ; j++ ) 
                if( q == m[j] ) { q = 0; break; }
            if( q > 1000 && isPrime(q) ) m[count++] = q;
        }
        if( count < 3 ) return;
        for( int i = 0 ; i < count-2 ; i++ )
        {
            for( int j = i+1 ; j < count-1 ; j++ )
            {
                int cd = m[j]-m[i];
                for( int k = j+1 ; k < count ; k++ )
                {
                    if( m[k] != m[j]+cd ) continue;
                    printf("%04d%04d%04d cd = %d\n", m[i], m[j], m[k], cd);
                    break;
                }
            }
        }
        return;
    }
    for( int i = s ; i < 10 ; i++ )
    {
        n[d] = i;
        TestAndDisplay(n, i, d+1);
    }
}

 

1. Predefining permutations

int perm[][4] = 
{
    { 0, 1, 2, 3 }, { 0, 1, 3, 2 }, { 0, 2, 1, 3 }, { 0, 2, 3, 1 },
    { 0, 3, 1, 2 }, { 0, 3, 2, 1 }, { 1, 0, 2, 3 }, { 1, 0, 3, 2 }, 
    { 1, 2, 0, 3 }, { 1, 2, 3, 0 }, { 1, 3, 0, 2 }, { 1, 3, 2, 0 },
    { 2, 0, 1, 3 }, { 2, 0, 3, 1 }, { 2, 1, 0, 3 }, { 2, 1, 3, 0 },
    { 2, 3, 0, 1 }, { 2, 3, 1, 0 }, { 3, 0, 1, 2 }, { 3, 0, 2, 1 },
    { 3, 1, 0, 2 }, { 3, 1, 2, 0 }, { 3, 2, 0, 1 }, { 3, 2, 1, 0 }
};

This array predefines all possible permutations (4!) of four-digit numbers. Instead of generating permutations dynamically, the program can efficiently access them from this array.

 

2. Generating numbers from permutations and checking for primes

int m[24], count = 0;
for( int i = 0 ; i < 24 ; i++ )
{
    int q = 0;
    for( int j = 0 ; j < 4 ; j++ ) { q*=10; q+=n[perm[i][j]]; }
    for( int j = 0 ; j < count ; j++ ) 
        if( q == m[j] ) { q = 0; break; }
    if( q > 1000 && isPrime(q) ) m[count++] = q;
}

• Uses predefined permutations (perm) to generate a four-digit number from selected digits (n[]).
• Ensures that the number is unique before adding it to m[].
• Only considers numbers greater than 1000 and checks if they are prime using isPrime(q).

 

3. Finding an arithmetic sequence of prime numbers

if( count < 3 ) return;
for( int i = 0 ; i < count-2 ; i++ )
{
    for( int j = i+1 ; j < count-1 ; j++ )
    {
        int cd = m[j]-m[i];
        for( int k = j+1 ; k < count ; k++ )
        {
            if( m[k] != m[j]+cd ) continue;
            printf("%04d%04d%04d cd = %d\n", m[i], m[j], m[k], cd);
            break;
        }
    }
}

• If at least three prime numbers are found (count >= 3), the program searches for an arithmetic sequence.
• It calculates the common difference cd between two numbers and checks if the third number follows the same pattern.
• If a valid sequence is found, it prints the result.

 

4. Recursive selection of digits

for( int i = s ; i < 10 ; i++ )
{
    n[d] = i;
    TestAndDisplay(n, i, d+1);
}

• Iterates through digits 0 to 9, storing them in n[] and recursively forming a four-digit number.
• The recursion ensures that all valid combinations are explored before checking permutations and primes.