A truncatable prime is one where all non-empty substrings that finish at the end of the number (right-substrings) are also primes when understood as numbers in a particular base. The largest such prime in a given (integer) base is therefore computable, provided the base is larger than 2.

Let's consider what happens in base 10. Obviously the right most digit must be prime, so in base 10 candidates are 2,3,5,7. Putting a digit in the range 1 to base-1 in front of each candidate must result in a prime. So 2 and 5, like the whale and the petunias in The Hitchhiker's Guide to the Galaxy, come into existence only to be extinguished before they have time to realize it, because 2 and 5 preceded by any digit in the range 1 to base-1 is not prime. Some numbers formed by preceding 3 or 7 by a digit in the range 1 to base-1 are prime. So 13,17,23,37,43,47,53,67,73,83,97 are candidates. Again, putting a digit in the range 1 to base-1 in front of each candidate must be a prime. Repeating until there are no larger candidates finds the largest left truncatable prime.

Let's work base 3 by hand:

0 and 1 are not prime so the last digit must be 2. 123 = 510 which is prime, 223 = 810 which is not so 123 is the only candidate. 1123 = 1410 which is not prime, 2123 = 2310 which is, so 2123 is the only candidate. 12123 = 5010 which is not prime, 22123 = 7710 which also is not prime. So there are no more candidates, therefore 23 is the largest left truncatable prime in base 3.

The task is to reconstruct as much, and possibly more, of the table in the OEIS as you are able.

Related Tasks:

 Miller-Rabin primality test


 
class
	LARGEST_LEFT_TRUNCABLE_PRIME
 
create
	make
 
feature
 
	make
			-- Tests find_prime for different bases.
		local
			i: INTEGER
			decimal: INTEGER_64
		do
			from
				i := 3
			until
				i = 10
			loop
				largest := 0
				find_prime ("", i)
				decimal := convert_to_decimal (largest, i)
				io.put_string (i.out + ":%T" + decimal.out)
				io.new_line
				i := i + 1
			end
		end
 
	find_prime (right_part: STRING; base: INTEGER)
			-- Largest left truncable prime for a given 'base'.
		local
			i, larger, larger_dec: INTEGER_64
			right: STRING
			prime: BOOLEAN
		do
			from
				i := 1
			until
				i = base
			loop
				create right.make_empty
				right.deep_copy (right_part)
				right.prepend (i.out)
				larger := right.to_integer_64
				if base /= 10 then
					larger_dec := convert_to_decimal (larger, base)
					if larger_dec < 0 then
						io.put_string ("overflow")
						prime := False
					else
						prime := is_prime (larger_dec)
					end
				else
					prime := is_prime (larger)
				end
				if prime = TRUE then
					find_prime (larger.out, base)
				else
					if right_part.count > 0 and right_part.to_integer_64 > largest then
						largest := right_part.to_integer_64
					end
				end
				i := i + 1
			end
		end
 
	largest: INTEGER_64
 
	convert_to_decimal (given, base: INTEGER_64): INTEGER_64
			-- 'given' converted to base ten.
		require
		local
			n, i: INTEGER
			st_digits: STRING
			dec: REAL_64
		do
			n := given.out.count
			dec := 0
			st_digits := given.out
			from
				i := 1
			until
				n < 0 or i > given.out.count
			loop
				n := n - 1
				dec := dec + st_digits.at (i).out.to_integer * base ^ n
				i := i + 1
			end
			Result := dec.truncated_to_integer_64
		end
 
	is_prime (n: INTEGER_64): BOOLEAN
			--Is 'n' a prime number?
		require
			positiv_input: n > 0
		local
			i: INTEGER
			max: REAL_64
			math: DOUBLE_MATH
		do
			create math
			if n = 2 then
				Result := True
			elseif n <= 1 or n \\ 2 = 0 then
				Result := False
			else
				Result := True
				max := math.sqrt (n)
				from
					i := 3
				until
					i > max
				loop
					if n \\ i = 0 then
						Result := False
					end
					i := i + 2
				end
			end
		end
 
end
 