Find largest left truncatable prime in a given base

Find largest left truncatable prime in a given base is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

ref 1: https://oeis.org/A103443

related task 1: http://rosettacode.org/wiki/Truncatable_primes

Obviously the right most digit must be prime, so in base 10 candidate 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 carnations in Hitchickers come into existance only to be extinguished before they have time to realize it. 13,17, ... 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. 12 = 5 which is prime, 22 = 8 which is not so 12 is the only candidate. 112 = 14 which is not prime, 212 = 23 which is, so 212 is the only candidate. 1212 = 50 which is not prime, 2212 = 77 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 ref 1 as you are able.

Haskell

Primes generation stolen from Sieve of Eratosthenes.

<lang haskell>primes = 2 : 3 : gaps 5 (unionAll [[p*p, p*p+2*p..] | p <- tail primes])

gaps k s@(x:xs) | k < x = k:gaps (k+2) s

               | otherwise =   gaps (k+2) xs 

unionAll ((x:xs):t) = x : union xs (unionAll (pairs t)) where pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t

union a@(x:xs) b@(y:ys) = case compare x y of LT -> x : union xs b EQ -> x : union xs ys GT -> y : union a ys

isPrime n = all ((/=0).(n`mod`)) $ takeWhile ((<=n).(^2)) primes

left_trunc base = maximum $ expand base $ takeWhile (<base) primes where expand b x = if null d then x else expand (b*base) d where d = filter isPrime $ concatMap (addDigit b) x addDigit b x = map ((+x).(*b)) [1..base-1]

main = mapM_ print $ map (\x->(x, left_trunc x)) ([3..9]++[11,13])</lang>

Ruby

Ruby Ruby

<lang ruby>

1. Compute the largest left truncatable prime
3. Nigel_Galloway
4. September 15th., 2012.

require 'prime' BASE = 3 MAX = 500 stems = Prime.each(BASE-1).to_a (1..MAX-1).each {|i|

 t = []
 b = BASE ** i
 stems.each {|z|
   (1..BASE-1).each {|n|
     c = n*b+z
     t.push(c) if c.prime?
 }}
 break if t.empty?
 stems = t

} puts "The largest left truncatable prime #{"less than #{BASE ** MAX} " if MAX < 500}in base #{BASE} is #{stems.max}" </lang> By changing BASE from 3 to 13 this produces:

The largest left truncatable prime in base 3 is 23

The largest left truncatable prime in base 4 is 4091

The largest left truncatable prime in base 5 is 7817

The largest left truncatable prime in base 6 is 4836525320399

The largest left truncatable prime in base 7 is 817337

The largest left truncatable prime in base 8 is 14005650767869

The largest left truncatable prime in base 9 is 1676456897

The largest left truncatable prime in base 11 is 2276005673

The largest left truncatable prime in base 13 is 812751503

The maximum left truncatable prime in bases 10 , 12, and 14 are very large. By changing MAX from 6 to 11 (note that 6 solves related task 1) the following are produced quickly with BASE = 10:

The largest left truncatable prime less than 1000000 in base 10 is 998443
 
The largest left truncatable prime less than 10000000 in base 10 is 9986113

The largest left truncatable prime less than 100000000 in base 10 is 99979337

The largest left truncatable prime less than 1000000000 in base 10 is 999962683

The largest left truncatable prime less than 10000000000 in base 10 is 9987983617

The largest left truncatable prime less than 100000000000 in base 10 is 999783972
83

JRuby

I require a fast probably prime test. Java has one, is it any good? Let's find out. Ruby can borrow from Java using JRuby. Modifying the Ruby solution: <lang Ruby>

1. Compute the largest left truncatable prime
3. Nigel_Galloway
4. September 15th., 2012.

require 'prime' require 'java' BASE = 10 MAX = 500 stems = Prime.each(BASE-1).to_a (1..MAX-1).each {|i|

 print "#{stems.length} "
 t = []
 b = BASE ** i
 stems.each {|z|
   (1..BASE-1).each {|n|
     c = n*b+z
     t.push(c) if java.math.BigInteger.new(c.to_s).isProbablePrime(100)
 }}
 break if t.empty?
 stems = t

} puts "\nThe largest left truncatable prime #{"less than #{BASE ** MAX} " if MAX < 500}in base #{BASE} is #{stems.max}" </lang> Produces all the reults in 'Number of left truncatable primes in a given base' on the discussion page. For bases 18, 20, and 22 I changed the confidence level from 100 to 5 and checked the final answer. Even so base 18 takes a while. For base 24:

9 87 677 3808 17096 63509 199432 545332 1319708 2863180 Error: Your application
used more memory than the safety cap of 500m.
Specify -J-Xmx####m to increase it (#### = cap size in MB).
Specify -w for full OutOfMemoryError stack trace

That is going to be big!