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

The price is based on these factors:

Academic level

Number of pages

Urgency

Basic features

- Free title page and bibliography
- Unlimited revisions
- Plagiarism-free guarantee
- Money-back guarantee
- 24/7 support

On-demand options

- Writer’s samples
- Part-by-part delivery
- Overnight delivery
- Copies of used sources
- Expert Proofreading

Paper format

- 275 words per page
- 12 pt Arial/Times New Roman
- Double line spacing
- Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Delivering a high-quality product at a reasonable price is not enough anymore.

That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read moreEach paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read moreThanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read moreYour email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read moreBy sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more