The problem (https://projecteuler.net/problem=37) statement tells us that there are only 11 of these bi-truncable primes. WE can use that piece of information as a stopping criteria. However, what I'd like is to find another stopping criteria and then deduce that there are only 11 bi-truncable primes.
Bi-truncable primes, by definition, have at least 2 digits. Not just that, it's easy to see that they can't have any of the following digits anywhere in the number: 0, 4, 6, 8. Another remark is that the digits 2 and 5 can only appear as the left-most digit. If 2 or 5 appear somewhere but the left-most digit, then right-removing digits will reach an at least 2 digits number which ends in a 2 or in a 5, and then not a prime. So, the digits of a bi-truncable prime have to fit the following pattern necessarily (but not sufficiently, we expect): their first digit is one of 1, 3, 7, 9, 2, 5; and then their $n$-th digit has to be one of 1, 3, 7, 9, where $n \geq 2$.
When talking about a bi-truncable prime $P$, we'll use the notation $a_i$ for the amount of the digit $i$ $P$ has. We'll also say that $S$ is the sum of the digits of $P$, that is: $S = a_1 + 2a_2 + 5a_5 + 3a_3 + 9a_9 + 7a_7$. If $P$ is a candidate for being a bi-truncable prime (which is what I call any number that follows the pattern in the above paragraph), we know that $S \equiv 0 \mod 3$ can't be true. We know that $7 \equiv 1 \mod 3$ and that $2 \equiv 5 \mod 3$. Notice that $a_2a_5 = 0$ because we can have at most one digit two, and it must be in the left-most position. The same is true for digit 5. So we have at most one digit two, at most one digit five and if one is present, the other isn't. This explains why $a_2a_5 = 0$.
Let us first assume that $a_2 = a_5 = 0$. That gives that if $a_7 + a_1 \geq 3$, then if we start removing digits from either of the sides, at some moment, $a_7 + a_1 = 3$ and then $S \equiv 3a_3 + 9a_9 + 7a_7 + a_1 \equiv 3a_3 + 9a_9 + a_7 + a_1 \equiv 3a_3 + 9a_9 + 3 \equiv 0 \mod 3$, and then the candidate $P$ for a bi-truncable prime that we have isn't really a prime (it is divisible by $3$ because the sum of its digits is divisible by $3$). If $a_2 = 1$ or $a_5 = 1$, then the left most digit of $P$ is a 2, or a 5. Assume $a_7 + a_1 \geq 2$. At some moment, we'll reach, by removing digits from the right, $a_7 + a_1 = 1$ and thus have $S \equiv 0 \mod 3$.
So the above reasoning limits how many digits $7$ and $1$ a bi-truncable prime can have (together, their count can't reach 3). What about total counts of digits? Call $A = a_1 + a_7$. We know that $A \in \{0, 1, 2\}$.
If $A = 0$, then we must start with 2 or 5 because, if not, we'll have a left prefix of 33, 39, 93 or 99 (all non-primes) and our $P$ will fail to be a bi-truncable prime. If, however we start with a two or a five, we must have a total number of digits equal to 2 because if not, we'd have a 2 digits ending of 33, 39, 93 or 99.
Consider now the case in which $A = 1$. Again, assume for now that $a_2 = a_5 = 0$. If we have $4$ or more digits and start removing from the side closer to the non-$3$ and non-$9$ digit (if it's in the middle for an odd number of digits, then the number of digits is 5 or more, and you can start at any side -- it won't matter), then, at some point, we'll remove the digit $7$ or $1$ and we'll still have at least 2 digits, and all of them being a 3 or a 9. This implies the candidate $P$ we had for a bi-truncable prime isn't really one. So if $A = 1$, the total digits count is at most $3$ in the case of $a_2 = a_5 = 0$. In the case $a_2 = 1$ or $a_5 = 1$, we can't have $A = 1$ or else $S \equiv 0 \mod 3$.
It remains for us to find a bound on total digits count for when $A = 2$ (in here, we know that $a_2 = a_5 = 0$ necessarily). Denote by $x$ a digit that is $7$ or $1$ and by $a$ a digit that is $3$ or $9$. If we could find something like all patterns of the form $axaa$ isn't truncable by removing digits from the left (for example), that would help. This is because if the $x$ digit in the number where $A = 2$ isn't in the first, second, second-last or last positions, then the number can't be a bi-truncable prime (it has to digits of type $a$ in one of its ends). So one of the $x$ digits must be in the first or second positions and the other one must be in the last or second-last position. If we can then prove that all numbers of the form $axaa$ and $xaaa$ aren't truncable primes as we rmeove digits from the right, we can then conclude that this bi-truncable prime candidate must have $axa$, $ax$, $xa$, or $xaa$ pattern on its left and must be at most 5 digits long (2 more for the $ax$ or $xa$ in the end). The following python program attempts to do that.
import itertools
def is_prime(n):
i = 2
while i*i <= n:
if n % i == 0:
return False
i += 1
return True
def is_good_pattern_from_right(pat):
"""A pattern is a good pattern (from right)
if, at some moment (by following the process
of removing digits from its right-end), it
produces a non-prime number. For example, 3797
isn't a good patter, but 3397 is."""
P = 0
for i in range(len(pat)):
P *= 10
P += pat[i]
if not is_prime(P):
return True
return False
def compute_digit_pattern(starting_pieces):
pattern_pieces = starting_pieces.copy()
pattern_accepted = False
while pattern_accepted == False:
some_failed = False
for num in itertools.product(*pattern_pieces):
if not is_good_pattern_from_right(num):
some_failed = True
if some_failed:
pattern_pieces.append([3, 9])
else:
pattern_accepted = True
return pattern_pieces
digit_pattern1 = compute_digit_pattern([[3], [7, 1]])
digit_pattern2 = compute_digit_pattern([[7, 1], [3, 9]])
print(len(digit_pattern1), digit_pattern1)
print(len(digit_pattern2), digit_pattern2)
It worked! I know now that $P$ must have at most 9 digits. Not only that, we also know that one of the digits of type $x$ must be first or second and the other one must be last or second last.
From what we've concluded, we'll follow the following strategy. We'll have two pieces of code: one to find bi-truncable primes with 3 or less digits and another one for 4 or more digits. We know, in the second case, we don't have to worry about digits 2 and 5.
First, let's find all bi-truncable with 2 or 3 digits.
import itertools
def is_prime(n):
if n <= 1:
return False
i = 2
while i*i <= n:
if n % i == 0:
return False
i += 1
return True
def is_right_truncable(pat):
P = 0
for i in range(len(pat)):
P *= 10
P += pat[i]
if not is_prime(P):
return False
return True
def is_left_truncable(pat):
P = 0
pattern_size = len(pat)
for i in range(pattern_size):
P += pat[pattern_size-i-1] * (10**i)
if not is_prime(P):
return False
return True
def is_bi_truncable(pat):
return is_right_truncable(pat) and is_left_truncable(pat)
pattern_atom = [3, 7, 9, 1, 2, 5]
bi_truncables_case_1 = []
for num_digits in [2, 3]:
pattern_pieces = [pattern_atom]*num_digits
for num in itertools.product(*pattern_pieces):
if is_bi_truncable(num):
bi_truncables_case_1.append(num)
print(len(bi_truncables_case_1))
for num in bi_truncables_case_1:
print(num)
Now let's compute all bi-truncable primes with 4 digits or more (up to 9, as we know). In here, we know that $A = 2$ and that $a_2 = a_5 = 0$.
Another thing about bi-truncable primes is that its first digit and its last digit can't be $9$ and can't be $1$ (not primes on their own).
beginnings = [
[[3], [1, 7]], #ax
[[7], [3, 9]] #xa
]
endings = [
[[3, 9], [7]], #ax
[[1, 7], [3]] #xa
]
bi_truncables_case_2 = []
for middle_digits in range(6):
for beg in beginnings:
for end in endings:
pattern_pieces = [];
pattern_pieces.extend(beg)
pattern_pieces.extend([[3,9]]*middle_digits)
pattern_pieces.extend(end)
for num in itertools.product(*pattern_pieces):
if is_bi_truncable(num):
bi_truncables_case_2.append(num)
print(len(bi_truncables_case_2))
for num in bi_truncables_case_2:
print(num)
bi_truncable_primes = bi_truncables_case_1.copy()
bi_truncable_primes.extend(bi_truncables_case_2)
total_sum = 0
print("All bi-truncable primes.")
for pat in bi_truncable_primes:
P = 0
for d in pat:
P *= 10
P += d
print(P)
total_sum += P
print("Bi-truncable primes sum =", total_sum)
print("There are", len(bi_truncable_primes), "bi-truncable primes.")