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.

{{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>

 

=={{header|F_Sharp|F#}}==

(* Find some probable candidates for The Largest Left Trucatable Prime in a given base

Nigel Galloway: April 25th., 2017 *)

if (Array.isEmpty g) then n else (fi g (i*Fbase))

pZ |> Array.Parallel.map (fun n -> fi [|n|] Fbase)|>Seq.concat|>Seq.max

{{out}}

<pre>

The source file uses the F90 style, mainly because module PRIMEBAG (from [[Extensible_prime_generator#Fortran]]) is available to supply some prime numbers and check whether a number is prime or not. This works up to the 32-bit integer limit: although INTEGER*8 variables are available, that seemed a reasonable stopping point. Otherwise, the source is older-style, except for a few conveniences: the use of "CYCLE" rather than a "GO TO", some array assignments rather than explicit DO-loops, and the special function MAXLOC to locate the index of the maximum value in an array. Although F90 also allows arrays of compound data, the entries are stored via a two-dimensional array, and to keep related digits adjacent in storage the indexing is (digit,entry) rather than (entry,digit) since fortran uses that ordering.

 

Calculates the largest "left-truncatable" digit sequence that is a prime number, in various bases.

INTEGER LBASE,MANY,ENUFF !Some sizes.

 

END DO !On to the next base.

 

Results:

</pre>

 

INTEGER BIGORDER !A limited attempt at generality.

PARAMETER (BIGORDER = 1) !This is the order of the base of the big number arithmetic.

INTEGER DIGIT(BIGLIMIT) !The digits, in ascending power order.

END TYPE BIGNUM !So much for that.

 

INTEGER F !I/O unit number.

TYPE(BIGNUM) B !The number.

BIGISPRIME = ABS(BIGFACTOR(B,2800)).EQ.1 !Condensed report.

END FUNCTION BIGISPRIME !Can't be bothered with ISPRIME from PRIMEBAG.

IF (N.LAST.LE.2) THEN !A smallish number? I want to compare to four, but BIGBASE might be two.

NR = BIGVALUE(N) !Surely so.

IF (BIGMOD2(N).EQ.0) RETURN !A single expression using .OR. risks always evaluating BOTH parts, damnit,

IF (BIGMODN(N,3).EQ.0) RETURN !Even for even numbers. Possibly doing so "in parallel" is no consolation.

USE BIGNUMBERVB !Alas, INTEGER*600 is not available.

Calculates the largest "left-truncatable" digit sequence that is a prime number, in various bases.

WRITE (MSG,*) "CPU time:",T1 - T0 !The cost.

END !Simple enough.

 

And the results, slightly edited to remove six columns of spaces...

Count: 97667 44905 44904 44904 44904 44904

CPU time: 111.2656

</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)

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

 

Representation of a current longer effort:

 

3 23

4 4091

17 13563641583101

18 571933398724668544269594979167602382822769202133808087

 

=={{header|Java}}==

'''Code:'''

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.

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.math.BigInteger

println("${largest.toString().padEnd(35)} -> ${largest.toString(radix)}")

}

 

{{out}}

Base = 17 : 13563641583101 -> 6c66cc4cc83

</pre>

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

 

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|Sidef}}==

{{trans|Perl}}

var b = 1

var best = nil

 

while (v) {

for i in (3..17) {

printf("%2d %s\n", i, lltp(i))

{{out}}

<pre>

17 13563641583101

</pre>

 

=={{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.

 

=={{header|zkl}}==

fcn largest_lefty_prime(base){

primes,p:=List(),BN(1); while(p.nextPrime()<base){ primes.append(p.copy()) }

}

 

I've included 18,19 & 20 here but 18 & 20 are very very slow to compute, it is seconds to compute all the others.

{{out}}