Project Euler Solution #37: Truncatable primes

Problem 37

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.

Solution

We know that a truncatable prime will remain prime even if we strip digits from left to right. That means that stripping all digits from the right must leave one digit primes for the first place, which are 2, 3, 5 and 7. The same can be made from left to right, but 2 and 5 is not a valid last digits of a prime since numbers with these ending digits are divisible by 2 or 5. We could create numbers by concatenating all combinations and successively add digits between the first and last digit, beginning with no digits in between. All we need to do is checking if these created numbers conform the set constraints of being prime itself and also remain truncatable primes.

With this idea we can produce a better algorithm. Given a (theoretical) list of all primes we start with the first place and know that the digits 2, 3, 5 and 7 are possible primes, but not truncatable primes. By adding a second digit we get the primes 23, 29, 31, 37, 53, 59, 71, 73, 79. We can go on this way with the third digit, a fourth digit and so on. Since we need to find eleven of such numbers, we can stop as soon as we have found them by successively adding digits to the right. For every prime we constructed that way, we know that it's prime itsel and also left-truncatable. Checking i the number is right-truncatable can be done quickly. The problem of that approach is, that we need a fast data structure for the primes, like a prefix-tree.

From the list of two digit primes from above, we know the first number to check is 23 and we need to search for 11 primes having the stated property. Using the sieve from Problem 10, we can formulate a trivial brute force solution like the following, which is more than enough to solve the problem within a few milliseconds:

function isPrime(n) {
  return SIEVE[n] === 0
}

function solution() {
    
  var sum = 0
  var num = 0
  for (var i = 23; num < 11; i+= 2) {

    if (isPrime(i) && isTruncatable(i)) {
      num++
      sum+= i
    }
  }
  return sum
}
solution()

Checking if a number is a truncatable prime is the remaining task. Checking from right to left is easy, since we need to divide by 10 until we arrive at a one digit number. If all the quotients are prime, the right-truncatable property holds. Additionally we need to check for left-truncatable primes. We do this in reverse so that we can reuse the already stacked up power of ten counter:

function isTruncatable(p) {

  for (var div = 10; div < p; div*= 10) {

    if (!isPrime(p % div) || !isPrime(p / div | 0)) {
      return false
    }
  }
  return true
}