Find largest left truncatable prime in a given base: Difference between revisions
Find largest left truncatable prime in a given base (view source)
Revision as of 12:29, 2 April 2017
, 7 years ago→{{header|Haskell}}: Add Fortran.
SqrtNegInf (talk | contribs) m (→{{header|Perl 6}}: fixed array concatenation) |
(→{{header|Haskell}}: Add Fortran.) |
||
Line 292:
9: 1676456897
</pre>
=={{header|Fortran}}==
The initial idea is to see how far 32-bit integers will suffice, to try out the logic for the search. The basic idea is to maintain a "horde" of digit sequences that represent a prime number, then for each survivor in the horde, try adding a possible digit at the high-order end and checking that the resulting number is a prime. If so, add this sequence to the horde. When all trials have been made, if there was an addition, purge the earlier entries, and have another go, which is the next level up. If no addition had been made, then the sequence is ended, and the largest value amongst the survivors is printed.
Fortran does not offer a "list" data structure, so as ever, fiddling with arrays is needed. The situation at the end of a level is that there are entries 1:LH, the "starters" for that level, and following that are entries LH + 1:NH, the added entries. The "starters" are no longer needed and to save on storage, this hole is to be filled. The entire horde could be shifted down LH slots, but there could be many of them. Instead, the tail end entries are copied from the end into the hole. There are of cource many variations possible, such as using linked-lists with an "available entry" list so that only links need be messed with rather than copying content, etc.
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", and an array assignment, rather than an explicit DO-loop.
Unfortunately, the modernisers have abandoned a feature of First Fortran (1957): the <code>IF OVERFLOW ... </code> statement, or similar. In its place are ad-hoc tests on whether a number has suddenly become zero or negative: there is roughly a 50:50 chance that an overflow in two's-complement integer arithmetic will produce such a result - if positive, the value will still be wrong after an overflow. Such checks are tedious, but not bothering to check will mean that odd behaviour will ensue, and worse, incorrect results. <lang Fortran> USE PRIMEBAG !Gain access to NEXTPRIME and ISPRIME.
Calculates the largest "left-truncatable" digit sequence that is a prime number, in various bases.
INTEGER LBASE,MANY,ENUFF !Some sizes.
PARAMETER (LBASE = 13, MANY = 66666, ENUFF = 66)
INTEGER NS,START(LBASE) !A list of single-digit prime numbers for starters.
INTEGER NH,LH !Counters for the horde.
INTEGER N,HORDEN(MANY) !Numerical value of a digit sequence.
INTEGER*1 HORDED(ENUFF,MANY) !Single-digit values only.
INTEGER B,D,DB !The base, a digit, some power of the base.
INTEGER L !The length of the digit sequence: DB = B**L.
INTEGER P !Possibly a prime number.
INTEGER I !A stepper.
MSG = 6 !I/O unit number for "standard output".
IF (.NOT.GRASPPRIMEBAG(66)) STOP "Gan't grab my file!" !Attempt in hope.
NS = 0 !No starters.
P = 1 !Start looking for some primes.
1 P = NEXTPRIME(P) !Thus skipping non-primes.
IF (P.LE.LBASE) THEN !Beyond the limit?
NS = NS + 1 !No. Count another starter.
START(NS) = P !Save its value.
GO TO 1 !And seek further.
END IF !One could insted prepare some values, the primes being well-known.
WRITE (MSG,2) LBASE,NS,START(1:NS) !But, paramaterisation is easy enough.
2 FORMAT ("Working in bases 2 to ",I0," there are ",I0, !Announce the known.
* " single-digit primes: ",666(I0:", ")) !The : sez stop if the list is exhausted.
WRITE (MSG,3) !Produce a heading for the tabular output.
3 FORMAT (/"Base Digits Count Max. Value = (in base)")
10 DO B = 3,LBASE !Work through the bases.
NH = 0 !The horde is empty.
DO I = 1,NS !Prepare the starters for base B.
IF (START(I).GE.B) EXIT !Like, they're single-digits in base B.
NH = NH + 1 !So, count another in.
HORDEN(NH) = START(I) !Its numerical value.
HORDED(1,NH) = START(I) !Its digits. Just one.
END DO !On to the next single-digit prime number.
L = 0 !Syncopation. The length of the digit sequences.
DB = 1 !The power for the incoming digit.
20 L = L + 1 !We're about to add another digit.
IF (L.GE.ENUFF) STOP "Too many digits!" !Hopefully, there's room.
DB = DB*B !The new power of B.
IF (DB.LE.0) GO TO 29 !Integer overflow?
LH = NH !The live ones, awaiting extension.
DO I = 1,LH !Step through each starter.
N = HORDEN(I) !Grab its numerical value.
DO D = 1,B - 1 !Consider all possible lead digits.
P = D*DB + N !Place it at the start of the number.
IF (P.LE.0) GO TO 29 !Oh for IF OVERFLOW ...
IF (ISPRIME(P)) THEN !And if it is a prime,
IF (NH.GE.MANY) STOP "Too many sequences!" !Add a sequence.
NH = NH + 1 !Count in a survivor.
HORDEN(NH) = P !The numerical value.
HORDED(1:L,NH) = HORDED(1:L,I) !The digits.
HORDED(L + 1,NH) = D !Plus the added high-order digit.
END IF !So much for persistent primality.
END DO !On to the next lead digit.
END DO !On to the next starter.
N = NH - LH !The number of entries added to the horde.
IF (N.GT.0) THEN !Were there any?
DO I = 1,MIN(LH,N) !Yes. Overwrite the starters.
HORDEN(I) = HORDEN(NH) !From the tail end of the horde.
HORDED(1:L + 1,I) = HORDED(1:L + 1,NH) !Digit sequences as well.
NH = NH - 1 !One snipped off.
END DO !Thus fill the gap at the start.
NH = N !The new horde count.
LH = NH !All are starters for the next level.
GO TO 20 !See how it goes.
END IF !So much for further progress.
GO TO 30 !But if none, done.
29 WRITE (MSG,28) B,L,NH,DB,P !Curses. Offer some details.
28 FORMAT (I4,I7,I6,28X,"Integer overflow!",2I12)
CYCLE !Or, GO TO the end of the loop.
30 I = MAXLOC(HORDEN(1:NH),DIM = 1) !Finger the mostest number.
WRITE (MSG,31) B,L,NH,HORDEN(I),HORDED(L:1:-1,I) !Results!
31 FORMAT (I4,I7,I6,I11," = "666(I0:".")) !See Format 3.
END DO !On to the next base.
END !Simple enough.</lang>
Results:
<pre>
Working in bases 2 to 13 there are 6 single-digit primes: 2, 3, 5, 7, 11, 13
Base Digits Count Max. Value = (in base)
3 3 1 23 = 2.1.2
4 6 3 4091 = 3.3.3.3.2.3
5 6 1 7817 = 2.2.2.2.3.2
6 11 42 Integer overflow! 362797056 -2138904587
7 7 1 817337 = 6.6.4.2.6.2.3
8 10 27 Integer overflow! 1073741824 -1763182509
9 9 5 Integer overflow! 387420489 -1971761312
10 9 546 Integer overflow! 1000000000 -1299575929
11 8 2 Integer overflow! 214358881 -2107742185
12 8 7712 Integer overflow! 429981696 -1718612639
13 8 4 Integer overflow! 815730721 -1993454625
</pre>
=={{header|Haskell}}==
Line 303 ⟶ 412:
| 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
| |||