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
Miller-Rabin test code comes from HaskellWiki (license seems to allow the use here) with very small changes. <lang haskell>primesTo100 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
-- (eq. to) find2km (2^k * n) = (k,n) find2km :: Integral a => a -> (a,a) find2km n = f 0 n
where
f k m
| r == 1 = (k,m)
| otherwise = f (k+1) q
where (q,r) = quotRem m 2
-- n is the number to test; a is the (presumably randomly chosen) witness millerRabinPrimality :: Integer -> Integer -> Bool millerRabinPrimality n a
| a <= 1 || a >= n-1 = True
| n < 2 = False
| even n = False
| b0 == 1 || b0 == n' = True
| otherwise = iter (tail b)
where
n' = n-1
(k,m) = find2km n'
b0 = powMod n a m
b = take (fromIntegral k) $ iterate (squareMod n) b0
iter [] = False
iter (x:xs)
| x == 1 = False
| x == n' = True
| otherwise = iter xs
-- (eq. to) pow' (*) (^2) n k = n^k pow' :: (Num a, Integral b) => (a->a->a) -> (a->a) -> a -> b -> a pow' _ _ _ 0 = 1 pow' mul sq x' n' = f x' n' 1
where
f x n y
| n == 1 = x `mul` y
| r == 0 = f x2 q y
| otherwise = f x2 q (x `mul` y)
where
(q,r) = quotRem n 2
x2 = sq x
mulMod :: Integral a => a -> a -> a -> a mulMod a b c = (b * c) `mod` a squareMod :: Integral a => a -> a -> a squareMod a b = (b * b) `rem` a
-- (eq. to) powMod m n k = n^k `mod` m powMod :: Integral a => a -> a -> a -> a powMod m = pow' (mulMod m) (squareMod m)
isPrime n | n < 100 = n `elem` primesTo100 | otherwise = all (millerRabinPrimality n) primesTo100
left_trunc base = maximum $ extend base $ takeWhile (<base) primesTo100 where extend b x = if null d then x else extend (b*base) d where d = filter isPrime (concatMap addDigit x) addDigit x = map ((+x).(*b)) [1..base-1]
main = mapM_ print $ map (\x->(x, left_trunc x)) [3..20]</lang> Output (only 3-17, 18 is taking forever)
(3,23) (4,4091) (5,7817) (6,4836525320399) (7,817337) (8,14005650767869) (9,1676456897) (10,357686312646216567629137) (11,2276005673) (12,13092430647736190817303130065827539) (13,812751503) (14,615419590422100474355767356763) (15,34068645705927662447286191) (16,1088303707153521644968345559987) (17,13563641583101)
Perl 6
Using the Miller-Rabin definition of is_prime from [1]: <lang perl6>for 3..* -> $base {
say "Starting base $base...";
my @stems = grep { is_prime($_, 100)}, ^$base;
my @runoff;
for 1 .. * -> $digits {
print ' ', @stems.elems;
my @new;
my $place = $base ** $digits;
my $tries = 1; # one try seems to be sufficient
for @stems -> $stem {
for 1 ..^ $base -> $digit { my $new = $digit * $place + $stem; @new.push($new) if is_prime($new, $tries);
}
}
push @runoff if @new < @stems and @new < 10;
last unless @new;
@stems = @new;
}
push @runoff, @stems;
for @runoff.sort(-*) -> $finalist {
my $b = $finalist.base($base); say "\n Checking :$base\<", $b, '>'; my $ok = True; for $base ** 2, $base ** 3, $base ** 4 ... $base ** $b.chars -> $place { my $f = $finalist % $place; if not is_prime($f, 100) { say " Oops, :$base\<", $f.base($base), '> is not a prime!!!'; $ok = False; last; } } next unless $ok;
say " Largest ltp in base $base = $finalist"; last;
}
}</lang>
- Output:
Starting base 3... 1 1 1 Checking :3<212> Largest ltp in base 3 = 23 Starting base 4... 2 2 3 3 4 4 Checking :4<333323> Largest ltp in base 4 = 4091 Starting base 5... 2 4 5 5 1 1 Checking :5<222232> Largest ltp in base 5 = 7817 Starting base 6... 3 4 12 25 45 56 64 67 63 54 38 21 13 9 3 2 1 Checking :6<14141511414451435> Largest ltp in base 6 = 4836525320399 Starting base 7... 3 6 7 5 2 1 1 Checking :7<6642623> Largest ltp in base 7 = 817337 Starting base 8... 4 12 29 50 66 77 61 51 38 27 17 8 3 2 1 Checking :8<313636165537775> Largest ltp in base 8 = 14005650767869 Starting base 9... 4 9 16 19 27 17 10 6 5 3 Checking :9<4284484465> Largest ltp in base 9 = 1676456897 Starting base 10... 4 12 39 99 192 327 430 521 545 517 448 354 276 212 117 72 42 24 13 6 5 4 3 1 Checking :10<357686312646216567629137> Largest ltp in base 10 = 357686312646216567629137 Starting base 11... 4 9 16 18 15 8 4 2 1 Checking :11<A68822827> Largest ltp in base 11 = 2276005673 Starting base 12... 5 23 120 418 1146 2547 4831 7862 11449 15119 17678 19161 19359 17910 15460 12327 9472 6765 4547 2935 1827 1131 616 353 185 104 49 19 8 2 1 1 Checking :12<471A34A164259BA16B324AB8A32B7817> Largest ltp in base 12 = 13092430647736190817303130065827539 Starting base 13... 5 13 21 24 17 11 7 4 Checking :13<CC4C8C65> Largest ltp in base 13 = 812751503 Starting base 14... 6 28 108 321 724 1392 2238 3215 3987 4454 4450 4056 3407 2708 2015 1348 827 535 338 172 105 60 30 15 7 3 Checking :14<D967CCD63388522619883A7D23> Largest ltp in base 14 = 615419590422100474355767356763 Starting base 15... 6 22 80 212 399 655 950 1192 1293 1179 1049 828 617 427 261 142 74 45 25 13 7 1 Checking :15<6C6C2CE2CEEEA4826E642B> Largest ltp in base 15 = 34068645705927662447286191 Starting base 16... 6 32 132 362 811 1395 2148 2934 3506 3820 3649 3253 2752 1996 1395 955 605 353 193 102 54 27 11 5 1 Checking :16<DBC7FBA24FE6AEC462ABF63B3> Largest ltp in base 16 = 1088303707153521644968345559987 Starting base 17... 6 22 43 55 74 58 41 31 23 8 1 Checking :17<6C66CC4CC83> Largest ltp in base 17 = 13563641583101
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|
print "#{stems.length} "
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 14 this produces the solutions in 'Number of left truncatable primes in a given base' on the Discussion Page for bases except 10, 12 and 14.
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>
- Compute the largest left truncatable prime
- Nigel_Galloway
- 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!