Assignment 4: Truncatable Primes

Background

A left-truncatable prime number is one where the numbers resulting from removing the left-most digits are also prime. For instance, the number 9137 is a left-truncatable prime since 9137, 137, 37 and 7 are all prime.

A right-truncatable prime number is similarly defined, but removes a digit from the right. For example, 31193 is a right-truncatable prime since 31193, 3119, 311, 31, 3 are all prime.

A truncatable prime, also known as a two-sided prime, is one that is both left-truncatable and right-truncatable simultaneously. An example of such a prime is 3797.

We will be writing a program to explore these truncatable primes.

As a side note, the property of truncatable is dependent upon the base that the number is represented in. For this program, only worry about base 10.

Analysis

First note that the property of truncatability always produces a chain of numbers that terminate in single digit prime numbers. Therefore we can identify prime numbers by starting at the end of that chain and build numbers by adding digits. That is, we should be able to identify 3797 as a truncatable prime by building it from the right as in 7, 97, 797, then 3797, all the while verifying each step is left-truncatable.

Next note that when building from the right, we can only add odd digits. If we were to add a 0, 2, 4, 6, or 8, the resulting number would be divisible by 2 and thus not prime.

Finally, all of the single digit prime numbers are 2, 3, 5, and 7. These form the basis of our search.

Approach

Based upon the analysis above, we can find truncatable primes by building primes that are right-truncatable by construction, and verify they are left truncatable as we go. This suggest the following recursive algorithm

Build Truncatable Primes(int start)

if (start is not prime)

return

if (start is left truncatable)

found one. print it out

Build Truncatable Primes (start * 10 + 1)

Build Truncatable Primes (start * 10 + 3)

Build Truncatable Primes (start * 10 + 7)

Build Truncatable Primes (start * 10 + 9)

For left-truncatable, consider testing the number 12345. We know that we need to check 12345, 2345, 345, 45, and 5. But since all must be prime, the order they are tested in does not matter. In particular, we can check them in the order 5, 45, 345, 2345, 12345. What is nice about that order is we can get those digits by modding by successive powers of 10. Therefore you can use a loop that starts at 10, and updates by multiplying by 10.

Tips

· Start by writing an is_prime function.

· Next write an is_left_truncatable function.

· Using the modulus operator with powers of 10 can cut off digits from the left side.

· Write the algorithm specified above.

· Start the algorithm with all possible single digit prime numbers.

Sample Output

The truncatable primes are:

2

23

3

313

3137

317

37

373

3797

5

53

7

73

739397

797