Find largest left truncatable prime in a given base: Difference between revisions

A [[Truncatable primes|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.

 

Related Tasks:

* [[Miller-Rabin primality test]]

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

Uses the '''H'''uge '''I'''nteger '''M'''ath & '''E'''ncryption library from http://devotechs.com/

INSTALL @lib$+"HIMELIB"

PROC_himeinit("HIMEkey")

SWAP old%, new%

UNTIL old% = 0

'''Output:'''

<pre>

 

=={{header|C}}==

#include <gmp.h>

 

 

return 0;

{{out}}

<pre>

...

</pre>

=={{header|Eiffel}}==

As there is currently no implementation for arbitrary precision integers this example only works for base 3 to base 9. Respectively for bases where the Result fits into a INTEGER_64.

class

LARGEST_LEFT_TRUNCABLE_PRIME

 

end

{{out}}

<pre>

8: 14005650767869

9: 1676456897

</pre>

 

=={{header|Haskell}}==

Miller-Rabin test code from [http://www.haskell.org/haskellwiki/Testing_primality#Miller-Rabin_Primality_Test HaskellWiki], with modifications.

 

-- (eq. to) find2km (2^k * n) = (k,n)

| r == 1 = (k,m)

| otherwise = f (k+1) q

 

-- n is the number to test; a is the (presumably randomly chosen) witness

addDigit a = filter (is_prime [3]) $ map (a*b+) x

 

<pre>

(3,23)

=={{header|J}}==

 

probe=. i.1 0

while. #probe do.

end.

>./y#.have

 

Quick example:

 

3 23

4 4091

9 1676456897

10 992429121339693967

 

 

 

import java.util.*;

 

public static void main(String[] args)

{

for (int radix = 3; radix <= maxRadix; radix++)

{

}

 

'''Example:'''

 

n=3: 23 (in base 3): 212

n=4: 4091 (in base 4): 333323

 

=={{header|Julia}}==

 

This solution is limited to a base of 17, to keep the processing time to well under a minute (about 15 seconds on an old but decent quality notebook). (I've let it run to as high as 23, but that took something like 20 minutes as I was otherwise occupied.) I did attempt a few optimizations of this general approach (such as moving the logic of <tt>addmsdigit</tt> into <tt>lefttruncprime</tt> and being clever about identifying the maximum of a given generation) but none of these tweaks resulted in a significant improvement in efficiency.

q = p

for i in 1:(b-1)

return a

end

mlt = zero(BigInt)

s = one(BigInt)

while !isempty(a)

mlt = maximum(a)

for i in 1:length(a)

end

end

return mlt

end

lo, hi = 3, 17

for i in lo:hi

mlt = lefttruncprime(i)

end

<pre>

The largest left truncatable primes for bases 3 to 17.

</pre>

 

 

Max[NestWhile[{Select[

Flatten@Outer[Function[{a, b}, #[[2]] a + b],

Range[1, n - 1], #[[1]]], PrimeQ], n #[[2]]} &, {{0},

 

Example:

 

 

Output:

 

17 13563641583101</pre>

 

=={{header|PARI/GP}}==

Takes half a second to find the terms up to 10, with proofs of primality. The time can be halved without proofs (use <code>ispseudoprime</code> in place of <code>isprime</code>).

 

=={{header|Perl}}==

a(18) has a max candidate list of 1,449,405 entries and takes a bit over 20 minutes to solve.

{{libheader|ntheory}}

use Math::GMPz;

 

}

 

{{out}}

<pre>

</pre>

 

{{out}}

 

=={{header|Python}}==

 

def is_probable_prime(n,k):

for b in range(3,24):

print("%d:%d\n" % (b,largest_left_truncatable_prime(b)))

 

Output:

</pre>

 

 

=={{header|Ruby}}==

===Ruby Ruby===

# Compute the largest left truncatable prime

#

}

puts "The largest left truncatable prime #{"less than #{BASE ** MAX} " if MAX < 500}in base #{BASE} is #{stems.max}"

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.

 

===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:

# Compute the largest left truncatable prime

#

}

puts "\nThe largest left truncatable prime #{"less than #{BASE ** MAX} " if MAX < 500}in base #{BASE} is #{stems.max}"

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:

<pre>

That is going to be big!

 

 

 

 

 

 

 

 

 

=={{header|Tcl}}==

 

proc tcl::mathfunc::modexp {a b n} {

for {set i 3} {$i <= 20} {incr i} {

puts "$i: [max_left_truncatable_prime $i]"

{{out|Output up to base 12 (tab-indented parts are progress messages)}}

<pre>

</pre>

I think I'll need to find a faster computer to calculate much more of the sequence, but memory consumption is currently negligible so there's no reason to expect there to be any major problems.