Find largest left truncatable prime in a given base
- 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>
- Compute the largest left truncatable prime
- Nigel_Galloway
- 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