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 25p(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:


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:


Happy coding <3.