A new type of prime numbers are the focus of Problem 37 of Project Euler. This time the type of prime numbers is truncatable primes. I have never heard of this type of primes before, but the problem description gives a good explanation.

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

So we know that we are supposed to find 11 of these. I will present you with two similar approaches. The first one is pure brute force where we search through all primes until we hit the ones with the right property. In the other solution we will only generate numbers which are left truncatable and then check if the are right truncatable. However, both solutions are missing one important thing I think. They are missing a clear upper bound. I haven’t been able to establish one through any means, so if you can share some insight to that I would be very happy to hear from you.

## Brute Force

First thing we need is a method to check if a given number is a prime. Since I knew I would need a list of primes I went with a simple method that checks if the number is contained in that list.

Such that the function looks like

private bool IsPrime(int number) { return Array.BinarySearch(primeList, number) >= 0; }

when we want to use an array to hold the prime list. The list will then be filled with our trusty Sieve of Eratosthenes from Problem 10.

The main part of the code searches through the list of primes where we have two temporary numbers. One which starts out as the prime, and the other which starts at zero. The I have made a small method that move the last digit on the first number to become the first digit of the second number. Much like you can push the markers on an abacus.

This way we can go through the list of primes until we have found 11. The C# code for that looks like

int result = 0; int[] primeList = ESieve(isPrimeLimit); int count = 0; int i = 4; while (count < 11) { int rightTrunk = primeList[i]; int leftTrunk = 0; int multiplier = 1; bool isTrunkPrime = true; while (rightTrunk > 0 && isTrunkPrime) { leftTrunk += multiplier * (rightTrunk % 10); isTrunkPrime = IsPrime(leftTrunk) && IsPrime(rightTrunk); rightTrunk /= 10; multiplier *= 10; } if (isTrunkPrime) { count++; result += primeList[i]; } i++; }

In order for this code to be really up and running, I should have made a method to check if I had reached the end of the prime list as well as expanding it if I was. But I disliked the problem so much that I just went for a sufficiently large set of primes.

When the code is executed I get the following result

The sum of all truncatable primes is 748317 Solution took 29 ms

## Generating Left Truncatable Primes

The second approach we will investigate is a method where we start with low numbers and add digits to the beginning of it. Thereby we only generate candidates which are left truncatable. So we only need to check if the newly generated candidate is also truncatable from the right.

The way this will be done is to append one digit to the front of an already known left truncatable prime, but we don’t need to append 0, 4,6 or 8. Since if they are appended they for sure aren’t right truncatable.

The c# code is fairly long and looks like

int result = 0; int count = 0; int[] primeList = ESieve(isPrimeLimit); List searchList = new List(); searchList.Add(3); searchList.Add(7); int[] appends = { 1, 2, 3, 5, 7, 9 }; while (count < 11) { int primeCandidate = searchList[0]; searchList.RemoveAt(0); if (IsPrime(primeCandidate)) { bool isTruncablePrime = true; int n = primeCandidate; int multiplier = 1; //Check right trunacatability while (n > 0) { isTruncablePrime = IsPrime(n) && isTruncablePrime; n /= 10; multiplier *= 10; } //Add to the result if a prime is found if (isTruncablePrime && primeCandidate > 10) { result += primeCandidate; count++; } //Generate new candidates for (int i = 0; i < appends.Length; i++) { searchList.Add(multiplier * appends[i] + primeCandidate); } } }

As you can see I have added 3 and 7. I could have added 2 and 5, but I know for sure that no matter what you prepends to them the result wont be a prime. The solution is a tad faster and executes in 8ms.

## Wrapping up

Originally I used a sorted set to hold the primes in, since the contains function is cheaper using SortedSet than a List. However, SuprDewd pointed me to the BinarySearch method in the API, which lowered the execution time significantly since I avoided having to create the sorted set, which is expensive. Thanks to SuprDewd for that.

To be honest I don’t really like any of the solutions to the problem. However it was the best I could come up with. Over at DreamShire he takes an approach of filtering a list of primes based on a set of rules of when a number can be truncatable or not.

As usual I have made the source code available.

Comments, questions and other solutions are as always welcome. If you have the brilliant solution to this problem I would very much like to hear from you.

Last thing I wanted to add is that Wikipedia has a nice article on truncatable primes. Apparently there are 4260 left truncatable primes and 83 right truncatable primes. I guess you could prove that there are no more left truncatable primes by showing that no matter what digit you prepend to the primes in the list it wont result in a new prime being generated. The same goes for the right truncatable prime.

Since primeSet is sorted, we can BinarySearch it instead of checking every element with Contains.

Hi SuprDewd

Thanks for sharing that insight with me, I wasn’t aware of that piece of the API, but it is indeed great. You are absolutely right. Changing the isPrime function will lower the execution time. But for a slightly other reason.

Using the SortedSet list method in C# will result in using a binarysearch for the contain function. However, the add cuntion to SortedSet is rather expensive, and since we know that the list is sorted, there is no reason to create a sorted set just for that. So we can skip the step of creating a sorted set and use the BinarySearch directly.

This will cut the execution time to 29ms and 8ms depending on the function.

I have updated the post to incorporate your suggestions. Thanks again, this will prove most useful in the future.

/Kristian

Glad to share. 😀

Is “while (count < 11)" needed? I am curious if there is a way to determine this number (11) from calculations. Can it be demonstrated that there are only 11 such numbers?

I have included it since we are told that we need to find the one instance where that happens. So once we have found it we might as well break out and stop.

I honestly don’t know if that can be proven to be correct.

First, thanks a lot for all your very instructive posts. I learn a lot by you.

As you said, the problem is not properly resolved if we need to set a upper bound ourselves. Thus, we cannot generate the list of the primes numbers list we need since we don’t know the upper limit of this list. The only solution we have is to check for every number if it is prime or not, using a method like this (sorry for the java code) :

private boolean isPrime(int n){

if(n==0 || n==1) return false;

if(primes.contains(n)) return true;

boolean prime = true;

int max = (int) Math.sqrt(n);

for(int i=2; i<=max; i++){

if(n%i == 0){

prime = false;

break;

}

}

if(prime){

primes.add(n);

}

return prime;

}

where primes can be a cache list a prime number.

Fortunately, there is a lot of case when the number doesn’t need to be checked at all. This is when the number starts by 1, 4, 6, 8 or 9 and it finished by 1, 2, 4, 5, 6, 8 or 9. Considering this makes you win a lot of time.

there’s something wrong with the statements of the problem…

prime numbers 11, 13, 17, 23, 31, 37, 53, 71, 73, 113, 131 fit the requirements, but I didn’t eve get to 3797…

1 isn’t a prime, so out of the list you mention only 23, 37, 53, 73 are valid.

right, forgot that…

thx!

You are welcome 🙂

Hi Kristian,

Though we are given that there are 11 such primes, I feel like we should never include this piece of information within the code. If we did, it would become a critical parameter on which the whole program relies. So a solution that does not rely on this will be more preferable. My idea is to create right/left-truncatable primes by adding a digit to previous right/left-truncatable ones, and test whether they are left/right-truncatable. Below is a piece of Python code illustrating this idea by creating right-truncatable primes first.

The output shows that the 11 primes are 23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397.

PS. I don’t think there is a theoretic proof for 11 such primes. It is probably determined by experiments, such as the one shown above.

Hi,

For checking whether the number is prime or not. Is it advisible to use primality test method(fermat primaltiy and miller rabin) for large number of primes ?. Becoz I have been using it which is faster.

Any suggestions?. Thanks

Knowing there are only 11 such numbers, I actually found it easier to find these by hand 🙂 Since I only need to add few digits to the left to get the next one. Eliminating was fairly quick.

I just the program to sum them up, and check for primes.

I filled the prime list via the “Sieve of Eratosthenes”, but I used a BitSet for easy access.

public class P_037_TruncatablePrimes extends EulerProblemObject {

@Override

protected void processProblem() {

final int uBound = 1000000;

final int lBound = 10;

final BitSet primes = this.eSieveBS(uBound);

int tmpPrime = 0;

int tmpPrime2 = 0;

int mul = 1;

int sum = 0;

NextPrime:

for(int prime = primes.nextSetBit(lBound); prime >= 0; prime = primes.nextSetBit(prime+1)){

tmpPrime = prime;

tmpPrime2 = 0;

mul = 1;

while(tmpPrime > 10){

tmpPrime2 += mul*(tmpPrime%10);

tmpPrime /= 10;

mul *= 10;

if((!primes.get(tmpPrime)) || (!primes.get(tmpPrime2))){

continue NextPrime;

}

}

sum += prime;

this.addDebugMsg(prime);

}

this.appendMsgln(“Sum = ” + sum);

}

[/code>]

Seems like I used the wrong code tag before, sorry…

public class P_037_TruncatablePrimes extends EulerProblemObject {

`@Override`

protected void processProblem() {

final int uBound = 1000000;

final int lBound = 10;

final BitSet primes = this.eSieveBS(uBound);

int tmpPrime = 0;

int tmpPrime2 = 0;

int mul = 1;

int sum = 0;

`NextPrime:`

for(int prime = primes.nextSetBit(lBound); prime >= 0; prime = primes.nextSetBit(prime+1)){

tmpPrime = prime;

tmpPrime2 = 0;

mul = 1;

`while(tmpPrime > 10){`

tmpPrime2 += mul*(tmpPrime%10);

tmpPrime /= 10;

mul *= 10;

`if((!primes.get(tmpPrime)) || (!primes.get(tmpPrime2))){`

continue NextPrime;

}

}

`sum += prime;`

}

}

}

You could actually trim the possible cases even further down.

As you have already explained, it is evident that we cannot use the digits 0,2,4,5,6,8, since any number ending in one of those digits will not be prime (save for 2 and 5 as a single digit).

That leaves us with 1,3,7 and 9. The only reminders these have mod 3 is 0 and 1. Since the sum of the digits of a number has the same remainder mod 3 as the number itself, the digit sum cannot be divisible by 3. That gives us that we cannot have more than 2 digits being 7 or 1. If more than two digits were 7 or 1, at some point after truncating we would have a number consisting of some 3’s, 9’s and three 7’s and 1’s. The digit sum would here be divisible by 3, a contradiction.

Furhtermore, a number cannot be consisting of only 3’s and 9’s, since that would be divisible by 3.

We only have a couple of cases left now, one where the last digit is a 7 and one where the second last digit is 7 or 1. The same can be said for the first digit and the second digit.

The different possibilities have been noticeably trimmed down, however the extra conditions would probably add some extra lines of code.