Project Euler 37: Find the sum of all eleven primes that are both truncatable from left to right and right to left

Written by on 23 April 2011

Topics: Project Euler

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.

11 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

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

    private bool IsPrime(int number) {
        return Array.BinarySearch(primeSet, number) >= 0;
    }
    
  2. Kristian says:

    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

  3. SuprDewd says:

    Glad to share. :D

  4. Monica Muranyi says:

    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?

  5. Kristian says:

    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.

  6. Cevantime says:

    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.

  7. ejfori says:

    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…

  8. Kristian says:

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

  9. ejfori says:

    right, forgot that…
    thx!

  10. Darren says:

    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.

    def func():
        """Find the sum of the only eleven primes that are both truncatable from 
        left to right and right to left.
        """
        # start with these digits; others are infeasible
        candidates = [2, 3, 5, 7]
        # other digits are infeasible to appear in the middle or at the end
        digits_to_add = [1, 3, 7, 9]
        summ = 0
        while candidates:
            prime = candidates.pop(0)
            for digit in digits_to_add:
                temp = prime * 10 + digit
                if is_prime(temp):
                    # included in the candidate list even if 
                    # temp may not be left-truncatable (e.g. 379)
                    candidates.append(temp)
                    if left_truncatable(temp):
                        print(temp)
                        summ += temp
        return summ
    

    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.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.