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 08:31, 4 April 2017
, 7 years ago→{{header|Fortran}}: Multi-digit arithmetic...
(→{{header|Fortran}}: Multi-digit arithmetic...) |
|||
Line 298:
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 course 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", some array assignments rather than explicit DO-loops, and the special function MAXLOC to locate the index of the maximum value in an array.
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.
Line 324:
END IF !One could insted prepare some values, the primes being well-known.
WRITE (MSG,2) LBASE,NS,START(1:NS) !But, parameterisation is easy enough.
2 FORMAT ("Working in bases
* " single-digit primes: ",666(I0:", ")) !The : sez stop if the list is exhausted.
WRITE (MSG,3) !Produce a heading for the tabular output.
Line 385:
Results:
<pre>
Working in bases
Base Digits Count Max. Value = (in base)
Line 400:
13 8 4 Integer overflow! 815730721 -1993454625
</pre>
So, there being no type declarations such as INTEGER*600, multi-precision arithmetic is needed to go further. There is no universally-used library for this, but thanks to previous effort in [[Sequence_of_primorial_primes#Fortran]] a collection is available, another F90 "module". This however works with a fixed value of BIGBASE, which is expected to be a large number and a power of ten. While there would be no great difficulty in converting from the digit sequences in the current base into a BIGNUM in base BIGBASE, it is more interesting to work with the desired base so that the digit sequences are manipulated directly. Accordingly, a variation, with the module starting <lang Fortran> MODULE BIGNUMBERVB !Limited services: integers, no negative numbers, variable base possible.
INTEGER BIGORDER !A limited attempt at generality.
PARAMETER (BIGORDER = 1) !This is the order of the base of the big number arithmetic.
INTEGER BIGBASE,BIGLIMIT !Sized thusly.
c PARAMETER (BIGBASE = 10**BIGORDER, BIGLIMIT = 8888/BIGORDER) !Enough?
PARAMETER (BIGLIMIT = 666)
TYPE BIGNUM !So, a big number is simple.
INTEGER LAST !This many digits (of size BIGBASE) are in use.
INTEGER DIGIT(BIGLIMIT) !The digits, in ascending power order.
END TYPE BIGNUM !So much for that.
</lang>
As checked via earlier tests, using a fixed value for BIGLIMIT that is "surely big enough" enables faster execution that variable sizes. Now, BIGBASE is a variable, with a view to <code>DO BIGBASE = 3,17</code> and almost everything else remains the same, though with BIGBASE being a rather small number, there is no need to employ 64-bit variables via INTEGER*8 at certain places. The use of BIGORDER is disrupted and routines employing it should be avoided or adjusted, thus in BIGTASTE, adding <code> IF (MOD(BIGBASE,10).NE.0) STOP "BIGTASTE expects powers of 10" !Alas. Otherwise the "E" formalism fails.</code> for example. The changes produce <lang Fortran> SUBROUTINE BIGWRITE(F,B) !Show B.
INTEGER F !I/O unit number.
TYPE(BIGNUM) B !The number.
WRITE (F,1,ADVANCE="NO") B.DIGIT(B.LAST:1:-1) !Roll the digits in base BIGBASE.
1 FORMAT (666(I0:".")) !Not bothering with using letters for digits above nine.
END SUBROUTINE BIGWRITE !Simple, but messy.
SUBROUTINE BIGTEN(B,TEXT) !Produce a base ten digit string.
TYPE(BIGNUM) B !The number.
CHARACTER*(*) TEXT !The digits.
TYPE(BIGNUM) N !A copy I can mess with.
INTEGER L,D !Assistants.
N.LAST = B.LAST !So, make my copy.
N.DIGIT(1:N.LAST) = B.DIGIT(1:B.LAST) !Only the live digits are wanted.
TEXT = "" !Clear for action.
L = LEN(TEXT) !Find the far end.
10 D = BIGDIVRN(N,10) !Digits emerge from the low-order end of the number.
TEXT(L:L) = CHAR(ICHAR("0") + D) !Convert a digit to text, usual assumptions.
IF (N.LAST.EQ.1 .AND. N.DIGIT(1).EQ.0) RETURN !If zero, N is finished.
L = L - 1 !Otherwise, another digits will emerge.
IF (L.GT.0) GO TO 10 !If there is space, go for it.
TEXT(1:1) = "!" !Otherwise, signify overflow.
END SUBROUTINE BIGTEN !No negatives, so no sign is needed.
LOGICAL FUNCTION BIGISPRIME(B) !Ad-hoc report.
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.
</lang>
Which is to say that BIGWRITE will show the digits of a number as decimal numbers separated by periods rather than involving letters as additional digit symbols, while BIGTEN will prepare a text version in base ten, whatever BIGBASE is. Finally, BIGMRPRIME quits if BIGBASE is less than four, because it wants to test numbers not exceeding four by only inspecting a single digit of the big number, so that it can for larger numbers perform a direct test for divisibility by two and three without rejecting those numbers as primes just in case it is invoked for them. So ... <lang Fortran>Catch some annoying cases, to protect the direct tests for divisibility by two and three...
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 (NR.LE.4) THEN !Some special values are known.
BIGMRPRIME = NR.GE.2 .AND. NR.LE.3 !Like, the neighbours.
RETURN !Thus allow 2 to be reported as prime.
END IF !Yet, test for 2 as a possible factor for larger numbers.
END IF !Without struggling over SQRT and suchlike.
BIGMRPRIME = .FALSE. !Most numbers are not primes.
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.
</lang>
With all this in hand, the job can be done by <lang Fortran> USE PRIMEBAG !Gain access to NEXTPRIME and ISPRIME.
USE BIGNUMBERVB !Alas, INTEGER*600 is not available.
Calculates the largest "left-truncatable" digit sequence that is a prime number, in various bases.
INTEGER LBASE,MANY !Some sizes.
PARAMETER (LBASE = 17, MANY = 66666)
INTEGER NS,START(LBASE) !A list of single-digit prime numbers for starters.
TYPE(BIGNUM) HORDE(MANY) !A collection.
INTEGER N,NH,LH !Counters for the horde.
INTEGER L !The length of the digit sequence.
INTEGER I,D !Steppers.
CHARACTER*42 TEXT !A scratchpad, for decimal values.
REAL T0,T1 !In memory of lost time.
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.
N = 1 !Start looking for some primes.
1 N = NEXTPRIME(N) !Thus skipping non-primes.
IF (N.LE.LBASE) THEN !Beyond the limit?
NS = NS + 1 !No. Count another starter.
START(NS) = N !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, parameterisation is easy enough.
2 FORMAT ("Working in bases 3 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",29X," Maximum Value = (in base)") !See Format 31.
Chug through the various bases to be used for the numerology.
CALL CPU_TIME(T0) !Start the timing.
10 DO BIGBASE = 3,LBASE !Not really very BIG bases.
NH = 0 !The horde is empty.
DO I = 1,NS !Prepare the starters for base BIGBASE.
IF (START(I).GE.BIGBASE) EXIT !Like, they're single-digits in base BIGBASE which may exceed ten...
NH = NH + 1 !So, count another in.
HORDE(NH).DIGIT(1) = START(I) !Its numerical value.
HORDE(NH).LAST = 1 !Its digit count. Just one.
END DO !On to the next single-digit prime number in BIGBASE.
L = 1 !The numbers all have one digit.
Consider each starter for extension via another high-order digit, to be placed at DIGIT(L + 1).
20 L = L + 1 !We're about to add another digit, now at DIGIT(L).
IF (L.GT.BIGLIMIT) STOP "Too many digits!" !Hopefully, there's room.
HORDE(1:NH).LAST = L !There is. Advise the BIGNUM horde of this.
LH = NH !The live ones, awaiting extension.
DO I = 1,LH !Step through each starter.
DO D = 1,BIGBASE - 1 !Consider all possible lead digits.
HORDE(I).DIGIT(L) = D !Place it at the start of the number.
IF (BIGISPRIME(HORDE(I))) THEN !And if it is a prime, or seems likely to be ...
IF (NH.GE.MANY) STOP "Too many sequences!" !Add a sequence.
NH = NH + 1 !Count in a survivor.
HORDE(NH).LAST = L !Its digit count.
HORDE(NH).DIGIT(1:L) = HORDE(I).DIGIT(1:L) !Its digits.
END IF !So much for persistent primality.
END DO !On to the next lead digit.
END DO !On to the next starter.
Check for added entries and compact the collection if there are some.
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.
HORDE(I).LAST = HORDE(NH).LAST !From the tail end of the horde.
HORDE(I).DIGIT(1:L) = HORDE(NH).DIGIT(1:L) !Copying only the live digits.
NH = NH - 1 !One snipped off.
END DO !Thus fill the gap at the start.
NH = N !The new horde count.
GO TO 20 !See how it goes.
END IF !So much for further progress.
Cast forth the mostest of the starters.
30 HORDE(1:NH).LAST = L - 1 !The testing involved an extra digit, which was not accepted.
L = 1 !Now go looking for the mostest of the survivors.
DO I = 2,NH !By comparing all the rest.
IF (BIGSIGN(HORDE(L),HORDE(I)).LT.0) L = I !Consider A - B.
END DO !On to the next.
CALL BIGTEN(HORDE(L),TEXT) !Get a decimal digit string.
WRITE (MSG,31) BIGBASE,HORDE(L).LAST,NH,TEXT !Some auxiliary details.
31 FORMAT (I4,I7,I6,1X,A," = ",$) !See Format 3.
CALL BIGWRITE(MSG,HORDE(L)) !The number at last!
WRITE (MSG,*) !Finish the line.
END DO !On to the next base.
CALL CPU_TIME(T1) !Completed the run.
Closedown.
200 WRITE (MSG,201) !First, some statistics.
201 FORMAT (/,"The MR prime test makes a series of trials, "
1 "stopping early",/'only when a "definitely composite" ',
2 "result is encountered.")
WRITE (MSG,202) "Trial",(I,I = 1,BIGMRTRIALS) !Roll the trial number.
WRITE (MSG,202) "Count",BIGMRCOUNT !Now the counts.
202 FORMAT (A6,": ",666I8) !This should do.
WRITE (MSG,*) "CPU time:",T1 - T0 !The cost.
END !Simple enough.
</lang>
And the results...
<pre>
Working in bases 3 to 17 there are 7 single-digit primes: 2, 3, 5, 7, 11, 13, 17
Base Digits Count Maximum 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 17 1 4836525320399 = 1.4.1.4.1.5.1.1.4.1.4.4.5.1.4.3.5
7 7 1 817337 = 6.6.4.2.6.2.3
8 15 1 14005650767869 = 3.1.3.6.3.6.1.6.5.5.3.7.7.7.5
9 10 3 1676456897 = 4.2.8.4.4.8.4.4.6.5
10 24 1 357686312646216567629137 = 3.5.7.6.8.6.3.1.2.6.4.6.2.1.6.5.6.7.6.2.9.1.3.7
11 9 1 2276005673 = 10.6.8.8.2.2.8.2.7
12 32 1 13092430647736190817303130065827539 = 4.7.1.10.3.4.10.1.6.4.2.5.9.11.10.1.6.11.3.2.4.10.11.8.10.3.2.11.7.8.1.7
13 8 4 812751503 = 12.12.4.12.8.12.6.5
14 26 2 615419590422100474355767356763 = 13.9.6.7.12.12.13.6.3.3.8.8.5.2.2.6.1.9.8.8.3.10.7.13.2.3
15 22 1 34068645705927662447286191 = 6.12.6.12.2.12.14.2.12.14.14.14.10.4.8.2.6.14.6.4.2.11
16 25 1 1088303707153521644968345559987 = 13.11.12.7.15.11.10.2.4.15.14.6.10.14.12.4.6.2.10.11.15.6.3.11.3
17 11 1 13563641583101 = 6.12.6.6.12.12.4.12.12.8.3
The MR prime test makes a series of trials, stopping early
only when a "definitely composite" result is encountered.
Trial: 1 2 3 4 5 6
Count: 517641 235380 235380 235380 235380 235380
CPU time: 641.3438
</pre>
So, once again, it is plain that using a large BIGBASE is beneficial, probably more so than the convenience of messing with the individual digits in the given base. The plain number version first given works in the computer's own arithmetic base, and preparing such values from the digit strings in the given base is not difficult.
Going further will require MANY to be enlarged. Already, base twelve required just over nineteen thousand entries, and base eighteen overflowed MANY = 66666. This suggests that a lot of data is being shifted about, so some sort of linked-list scheme might reduce that. Incidentally, in <code>B.LAST = A.LAST; B.DIGIT(1:N) = A.DIGIT(1:N)</code> and similar, because the storage for .DIGIT immediately follows that for .LAST, one might hope that an advanced compiler would combine the two statements into one sequential copy... Alas, the Compaq F90/95 compiler produces two wads of code, of 20 operations and then 92. Bounds checking is active, but still...
=={{header|Haskell}}==
| |||