Inspired from my status on Facebook:
The prime number 73939133 is very special, if removing each digit from right to left of that number we get another prime numbers: 7393913, 739391, 73939, 7393, 739, 73 and 7.
One of my friends gave a challenge:
Can you write a program reading a number N from keyboard then finding the nearest prime number to N that satisfies the characteristics of 73939133?
As promised him, I would solve this challenge.
In order to find out an algorithm, we try to do math analysis first.
Suppose p(k) is the prime, satisfies the characteristics of righttruncatable prime, has k digits: a(1), a(2),…,a(k), value of each digit is in set {0, 9}:
\[p(k) = \overline {a(1)a(2)…a(k)}\]
Removes one digit from right to left of the number p(i), with i = 1..k, we get: \[p(k1) = \overline {a(1)a(2)…a(k1)}\] \[p(k2) = \overline {a(1)a(2)…a(k2)}\] \[…\] \[p(2) = \overline {a(1)a(2)}\] \[p(1) = \overline {a(1)}\]
p(1) is prime number therefore the value of a(1) must be 2, 3, 5 or 7.
Represent the p(k) in base 10, we get:
\[p(k) = 10^{(k1)}a(1) + 10^{(k2)}a(2) +…+ 10^1a(k1) + a(k)\]
\[= 10(10^{(k2)}a(1) + 10^{(k3)}a(2)+…+a(k1)) + a(k)\]
The expression: \[10^{(k2)}a(1) + 10^{(k3)}a(2)+…+a(k1)\] is actually p(k1), so we get:
\[p(k) = 10p(k1) + a(k)\]
p(k) is prime therefore a(k) and 10p(k1), or 2*5*p(k1), must not have common divisors. This leads to value of a(k) must be 1, 3, 7 or 9.
From above analysis we have an algorithm to find the largest righttruncatable prime:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
Algorithm of Finding Largest RightTruncatable Prime (Input: N) (1) Let K = number of digits of N (2) Initialize A = {2, 3, 5, 7}, B = {1, 3, 7, 9}, MAX_PRIME (3) For i = 2, 3,... up to K: Let P = empty list, this list stores primes are found for each i With each a in A With each b in B: Calculate p = 10*a + b If p > n: Exit loop (3) If p is prime: Set MAX_PRIME = p Add p to P If P is empty: Exit loop (3) Else: Set A = P (4) Return MAX_PRIME 
In step (3), in order to check if a number is prime we can use different algorithms such as: Eratosthenes, Atkin, AKS and MillerRabin. I choose MillerRabin for testing large input number.
Below is a program I wrote in Python to implement the algorithm. The algorithm can be optimized for more efficient but I leave it for now as an exercise for whom is interested in.


Modifies above program a little bit, we can print out all righttruncatable prime numbers:
1 2 3 4 5 6 7 8 
23, 29, 31, 37, 53, 59, 71, 73, 79, 233, 239, 293, 311, 313, 317, 373, 379, 593, 599, 719, 733, 739, 797, 2333, 2339, 2393, 2399, 2939, 3119, 3137, 3733, 3739, 3793, 3797, 5939, 7193, 7331, 7333, 7393, 23333, 23339, 23399, 23993, 29399, 31193, 31379, 37337, 37339, 37397, 59393, 59399, 71933, 73331, 73939, 233993, 239933, 293999, 373379, 373393, 593933, 593993, 719333, 739391, 739393, 739397, 739399, 2339933, 2399333, 2939999, 3733799, 5939333, 7393913, 7393931, 7393933, 23399339, 29399999, 37337999, 59393339, 73939133 
Happy coding <3.