[C/C++] Project Euler #37 - Truncatable Primes

Truncatable Prime refers to a very special type of prime number. These numbers retain their primality even when digits are removed one by one from the left or from the right. For example, while a regular prime is defined as a number divisible only by 1 and itself, Truncatable Primes not only meet this condition but also require that all numbers formed by progressively removing digits remain prime. This makes Truncatable Primes much rarer and more unique compared to ordinary primes.

 

For instance, the number 3797 is a good example of a Truncatable Prime. When digits are removed from the left, it becomes 379, 37, and 3, all of which are primes. Similarly, when digits are removed from the right, it becomes 797, 97, and 7, which are also primes. This confirms that 3797 fully satisfies the conditions of a Truncatable Prime. However, single-digit primes (e.g., 2, 3, 5, 7) cannot be considered Truncatable Primes because there is no possibility of further truncation. As such, Truncatable Primes must consist of at least two digits, and they must maintain their primality through all possible truncation processes.

 

The goal of the problem is to find all such Truncatable Primes. The problem specifies that the total number of Truncatable Primes is finite, making it possible to define a reasonable search range for exploration. After identifying all Truncatable Primes, the sum of these numbers must be calculated to solve the problem. This requires efficient algorithms for prime checking and iterative validation, with both accuracy and performance in mind.

 

The difficulty of the problem is relatively low, rated at 5%. The task is to identify primes that remain prime when truncated from either the left or the right. For instance, 3797 is a prime number by itself, and its truncated forms—797, 97, and 7 (from the left) as well as 379, 37, and 3 (from the right)—are all primes as well.

 

Ordinarily, the problem could be solved by generating all primes, then checking each prime to see if it remains prime through truncation. Using a binary search for efficient prime checks could simplify this task. However, the focus here is on the properties of such primes rather than brute-force enumeration.

 

For numbers with two or more digits, it is important to note some key constraints. If the last digit of a number is 5, that number will always be divisible by 5 and cannot be a prime. Similarly, if the first or last digit is 9, truncating the number will leave a 9, which disqualifies it as a prime. Therefore, the first and last digits of a Truncatable Prime cannot include 1, 5, or 9. Among odd digits, only 3 and 7 can appear as the first or last digit of such numbers.

 

Instead of implementing a more generalized solution with robust stopping conditions, I simplified the program to stop after finding the 11 Truncatable Primes, as the problem explicitly states that only 11 such numbers exist.

truncatable primes

The resulting program, while somewhat complex, effectively identifies these special primes.

//------------------------------------------------
//    Project Euler #37 - Truncatable Primes
//        - by Aubrey Choi
//        - created at 2015-03-21
//------------------------------------------------
#include <stdio.h>

bool IsOddPrime(int p);
void Push(int tp[][2], int &t, int v, int e);
void Pop(int tp[][2], int &h, int *v, int *e);

int main()
{
    int tp[1000000][2];
    int h = 0, t = 0;

    Push(tp, t, 3, 10);
    Push(tp, t, 7, 10);

    int ans = 0;
    int count = 0;
    while( count < 11 )
    {
        int s[] = { 2, 3, 5, 7 };
        int p[] = { 1, 3, 7, 9 };
        int v, e;
        Pop(tp, h, &v, &e);
        for( int i = 0 ; i < 4 ; i++ )
        {
            int t = s[i]*e + v;
            int u;
            for( u = t ; u > 10 ; u /= 10 )
                if( IsOddPrime(u) == false ) break;
            if( u > 10 ) continue;
            ans += t;
            count++;
        }
        for( int i = 0 ; i < 4 ; i++ )
        {
            if( IsOddPrime(p[i]*e+v) == false ) continue;
            Push(tp, t, p[i]*e+v, e*10);
        }
    }
    printf("ans = %d\n", ans);
}

void Push(int tp[][2], int &t, int v, int e)
{
    tp[t][0] = v;
    tp[t][1] = e;
    t = (t+1)%1000000;
}

void Pop(int tp[][2], int &h, int *v, int *e)
{
    *v = tp[h][0];
    *e = tp[h][1];
    h = (h+1)%1000000;
}

bool IsOddPrime(int p)
{
    for( int i = 3 ; i*i <= p ; i+=2 )
        if( p%i == 0 ) return false;
    return true;
}