Sequence of primorial primes: Difference between revisions

 

The sequence of primorial primes is given as the increasing values of n where [[Primorial numbers|primorial]](n) ± 1 is prime.

* This task asks for the primorial ''indices'' that create the final primorial prime numbers, so there should be no ten-or-more digit numbers in the program output (although extended precision integers ''will'' be needed for intermediate results).

* There is some confusion in the references, but for the purposes of this task the '''[[wp:Primorial prime|sequence]] begins with n = 1'''.

 

 

* [[wp:Primorial prime|Primorial prime]] Wikipedia.

* [https://primes.utm.edu/glossary/page.php?sort=PrimorialPrime Primorial prime] from The Prime Glossary.

* [https://oeis.org/A088411 Sequence A088411] from The On-Line Encyclopedia of Integer Sequences

 

 

 

=={{header|C}}==

{{libheader|GMP}}

#include <gmp.h>

 

mpz_clear(p);

}

{{out}}

<pre>

384

457

</pre>

 

=={{header|Clojure}}==

; Uses Java Interoop to use Java for 1) Prime Test and 2) Prime sequence generation

(ns example

(:gen-class))

(reductions *' primes)))) ; computes the lazy sequence of product of 1 prime, 2 primes, 3 primes, etc.

 

{{Out}}

<pre>

(1 2 3 4 5 6 11 13 24 66 68 75 167 171 172 287 310 352 384 457)

</pre>

=={{header|EchoLisp}}==

(lib 'timer) ;; for (every (proc t) interval)

(lib 'bigint)

(writeln 'HIT N )

(writeln N (date->time-string (current-date )))))

{{out}}

;; run in batch mode to make the browser happy

;; search next N every 2000 msec

458 "14:07:25"

459 "14:07:29"

 

=={{header|Fortran}}==

USE PRIMEBAG !Some prime numbers are wanted.

USE BIGNUMBERS !Just so.

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

END !So much for that.

Output, somewhat edited, because the limit on direct factorisation is soon exceeded: five lines such as "Passed the limit of 18000000 with 18000041, but Sqrt(n) = 0.43849291E+11:" and similar have been removed, corresponding to the five "?" reports.

<pre>

The direct factorisation assault was extended up to 18,000,000 because one factor was 17,515,703 and it was pleasing to have a definite result. However there is not much hope for this approach because the 32-bit integer limit is exceeded after Primorial(9) and the 64-bit limit after Primorial(15), so definitive factorisation in a reasonable time is out of reach. Already, bignumber arithmetic has been introduced to calculate this far, and only the first eight candidates have been found when the demand is for at least ten.

 

Although there would be no difficulty in principle in a Fortran compiler accepting syntax such as INTEGER*1000, this sort of ability is not required in the modern standard. Fortran II of 1957 on a decimal computer such as the IBM1620 allowed a control card to state how many digits were to be used for fixed-point numbers (i.e. integers) but although the hardware delivered integer arithmetic of arbitrary precision (up to memory limits), thousand-digit arithmetic probably was out of bounds, just as INTEGER*8 or perhaps INTEGER*16 is the upper limit for modern compilers. Thus, there is no "built-in" facility for arithmetic involving larger numbers available via a standard specification. So, one must devise appropriate routines.

 

Rather than always employing in-line arithmetic expressions of ever greater complexity, defining a function offers multiple advantages. This might be via an "arithmetic statement" function if it can be written as a single expression, but more generally, a function can be named and defined as a separate unit for compilation, and then used within arithmetic expressions. This is unexceptional, and easily understood. Whatever the parameters and workings of the function, its result is returned in the computer's accumulator, or top-of-stack, or a standard register. Thus, an expression such as ''y:=x;'' would produce code such as Load x; Store y; whereas with an expression such as ''y:=F(x);'' instead of the Load there is an invocation of the function which would perform its calculation then return, whereupon the code Store y; would be executed just as before. This is easily extended for usage within an expression such as ''y:=y + 7*F(x) - 3;'' and so forth.

 

DIMENSION A(*)

SUM = 0 !Unconditionally, clear SUM.

SUM = A(I) + SUM

END DO !Some early compilers executed a DO-loop at least once.

Prior to F90, there were compilers for which this did ''not'' work. If an assignment to SUM were to be regarded as an assignment to the accumulator, as above, then when that is ''not'' followed by a RETURN but by other statements, the value that had been saved in the accumulator will be lost by the accumulator's usage in the execution of the subsequent statements. Indeed, some compilers would not allow any usage of SUM within an expression. Thus, a local variable, perhaps called ASUM, would be defined and used instead, and then, before exiting the function (by whatever path) one must remember to have an assignment <code>SUM = ASUM</code>

 

Or, one could define SUBROUTINE UPPERCASE(TEXT) that produces its result in-place, and deal patiently with the requirement to convert a simple expression into a suitable sequence of subroutine calls.

 

The method taught in primary school is adequate, but variations are possible. For instance, instead of writing out the multi-line scheme of partial products then adding them in a second pass to produce the final product, the terms can be added as they are produced by working down a column rather than across a row - see the tableau in BIGMULT. This however requires an accumulator able to hold not just a two-digit number, but the sum of many such numbers given that the numbers have many digits. If calculations are proceeding with a base close to or equal to the word size of the computer's arithmetic, this becomes less convenient because then carries must be propagated to prevent overflow while working down a column rather than once after the column sum is complete. The expectation here is that the base will be some power of ten, and on a computer using binary arithmetic the word size will not be fully used.

 

 

 

In ''The Art of Comuter Programming'', volume 2 ''Seminumerical Algorithims'' Professor Knuth remarks "Here the ordinary pencil-and-paper method involves a certain amount of guesswork and ingenuity on the part of the person doing the division; we must either eliminate this guesswork from the algorithm or develop some theory to explain it more carefully."

 

As will be remembered from primary school, at each step the key lies in the choice of a value for Q, the trial quotient for subtracting Q*M from the working number, with the digits of Q shifted left to align with the current high-order digits of B. One makes an estimate from considering the leading digits of B and M, and annoyingly, misguesses: the paper soon becomes decorated with side calculations of 3*Q, 7*Q, ''etc.'' to avoid repeated mistakes. In base ten there can be only ten possible values for Q at each cycle, but in larger bases any such list becomes ridiculously long and anyway, the chance of a recurrence of a value for Q falls.

 

 

The plan then is to guess a value for Q by inspecting the first two digits of B and the first only of M by calculating <code>DD = B.Digit(B.Last)*BigBase + B.Digit(B.Last - 1)</code> - this is a double-digit value, where B.Last fingers the highest-order digit of B and thus (B.Last - 1) the second digit. Then calculate <code>Q = DD/M.Digit(M.Last)</code> Immediate difficulties arise: in base ten this might be 31/2 and thus Q is a gross over-estimate. The estimate can be restrained: <code>Q = MIN(DD/M.Digit(M.Last),BigBase - 1)</code> but this is not the only problem.

 

 

Equipped with a good estimate for Q, the next step is to subtract Q*M from the high-order digits of B that align with the digits of M. Because now the full value of M is employed, the result can be negative: overshoot. If so, add back one M to produce the reduced value of B, ready for the next attempt with M shifted over to again align with the high-order digits of B.

 

Although the intention of BIGMOD(B,M) is for the value of B to hold the result, changing the value of M is likely to be unexpected, even if it is later changed back to what it had been. M might even be a constant, protected from change. Similarly, the rescale for B may require another digit and storage for this may not be available. Copies to working variables could be made, but anyway, although small compared to the effort of BIGMOD, the rescaling of big numbers is not so trivial. Instead, recognising that in high-level languages there is no access to to the double/single features of the hardware mentioned above, one can rely on the availability of equal-sized division - that is, one word divided by one word, or double by double. Thus, there is the opportunity for DD to be the first two digits of B and MM the first two of M, and then <code>Q = DD/MM</code> The minimum accuracy of this calculation is always better than one digit since (in base ten) MM = 10 represents 100... to 109... and so no tricky adjustment checks are required. There is still the overflow issue with the required add back when using the full precision of M, but the overflow is always only by one extra M value and so the shift and add ploy discussed below is safe.

 

 

Alas, DD/MM sometimes yields zero, as in 1001/11 (where DD/M.Digit(M.Last) would yield 10, reduced by the MIN to 9) or 9800/99, or 4100/588, and many other cases. One could pre-emptively subtract M once and then engage in the overflow recovery procedure, or, shift M right one digit place and reconsider. This means calculating <code>Q = (DD*BIGBASE + B.DIGIT(L - 1))/MM</code> and proceeding with that, again at a risk of going one too far when using M instead of its approximation MM. Even if the first two digits of M exceed the first two digits of B, this shift is always possible because B > M is assured via the earlier test. However, this recalculation involves a ''three''-digit value (DD is already a two-digit value) and until now the working assumption has been for arithmetic of up to ''two''-digits only. This means the size of the big base is limited. The difficulty is that the proper value for Q is anything from zero to BIGBASE - 1, and with division by a two-digit number MM, for the higher values of Q to emerge, DD must have a three-digit number. This means that calculating a provisional Q value (from DD divided by the lead digit of M) then considering Q*MM - (top three digits of B) to determine an improved estimate will still have trouble. A multi-digit divide isn't available (as via recursion) since this ''is'' the multi-digit divide scheme and it is in trouble. Still further possibilities open up by considering the reciprocal of MM (calculated once at the start) so that DD/MM can be calculated using multiplication, but enough: accept a severe limitation on the possible base of arithmetic. For various powers of ten, when using two's complement signed integers,

 

Thus, when 64-bit signed integer arithmetic is available, the highest possible decimal base is one million if triple-digit numbers are contemplated, but if only double-digit numbers are needed, base one thousand million can be used, which is a reasonable fit in a 32-bit variable.

 

 

 

 

Just as the subtraction of Q*M could make zero multiple leading digits of B, not just one, so also can an overflow lead to multiple leading zero digits after the recovery. The extreme case is for a long M number, with the overflow being by just one in the units position of M as currently aligned with B. The overflow will manifest as complemented numbers in the high-order digits, a sequence such as 99999123 (in base ten) with an outstanding borrow, or C = -1. Rather than shifting M over one place for the add back, a multi-place shift will enable a single add back to clear many leading digits, though the shifts must go no further than aligning the units digit of M and B since only integers are in consideration.

In ''16-Bit Modern Microcomputers'', G.W. Corsline remarks "... multiplication and division are somewhat difficult and involve rather esoteric solutions in the general case." (p193) and "... although straightforward, are not short, simple, or easy to understand." (p124).

 

EQUIVALENCE (XFIELD(1),XLAST) !The count at the start.

This introduces ''three'' names, if in a systematic way... But such array indexing invites its own mistakes, especially when relying on lax bound checking. For example, an accidental assignment to XDIGIT(-1) would change XLAST.

 

INTEGER LAST !Count of digits in use.

INTEGER DIGIT(many) !The first digit is number one.

END TYPE BIGNUM

And in this case the X.LAST variable is not a part of the digit array and so can't be damaged via misindexing X.DIGIT as with the earlier attempt using EQUIVALENCE - providing that array bound checking ''is'' engaged. Thus, one gains the ability to use X in a way that is somewhat more self-documenting, but there is still the annoyance of deciding on how many digits will be enough, and further, the BIGNUM type allows for only a fixed size. A different size would entail a different type and thereby cause parameter mismatching - should that be checked...

 

Evidently, every reference to an allocatable-size array involves quite a lot more code. A test run up to primorial 80 with run-time allocations of BIGLIMIT took ~4·42 seconds while fixed-size runs took ~4·13, a 7% increase. This is discouraging.

 

<pre>

153: DO I = 1,B(0) !Step through the digits, upwards powers.

156: C = D/BIGBASE !Agony! TWO divisions per step!!

</pre>

<pre>

153: DO I = 1,B(0) !Step through the digits, upwards powers.

Store D

 

Since the BIGNUM type with fixed storage runs no slower but offers better documentation, the possibility of big numbers sized to fit is abandoned for demonstration purposes. Storage is plentiful these days, and can be expended with far less angst.

 

This uses the MODULE facilities of F90 to save on communication (though it seems that fixed-size work areas in COMMON may enable faster code) and although the DIGIT array could start with index zero so that the index value would correspond to the powers of the base, it starts at one so that the first digit, the units digit, is at index one. As ever, care is required with the various counting on digits.

 

Most of the source code is devoted to providing the BIGNUM facilities, since there is no built-in facility for this nor a universally-used library such as the "stdio.h" collection in C and similar languages. Via a great deal of additional syntax it is possible to extend F90 so as to provide the appearance of multi-precision arithmetic via the ordinary usage of expressions, as is exemplified for rational arithmetic in [[Arithmetic/Rational#Fortran]]. However, the "formula translation" that this invites will not work well for the likes of <code>MOD(A**B,M)</code> when the variables are hundred-digit numbers because A**B will overflow any possible storage scheme. The modulo arithmetic feature must be pushed into the calculation of A**B, and even if one has prepared a suitable routine such as BIGMODEXP, the language extension facilities are not going to recognise its suitability for calculating <code>MOD(A**B,M)</code> in a general context because they manifest "formula translation". One must employ explicit coding, as in BIGMRPRIME.

 

INTEGER BIGORDER !A limited attempt at generality.

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

INTEGER L,IT !Fingers.

INTEGER D,E !A digit and an exponent.

BIGLEAD = 0 !Scrub, on general principles.

L = MIN(BIGLEADN,B.LAST) !I'm looking to taste the leading digits; too few?.

 

END MODULE BIGNUMBERS !No fancy tricks.

 

USE PRIMEBAG !Some prime numbers are wanted.

USE BIGNUMBERS !Just so.

INTEGER MAXF !Largest factor to consider by direct division.

PARAMETER (MAXF = 1000000) !Some determination.

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

END !So much for that.

A slightly more complex scheme to interpret the more complex mumbling from BIGFACTOR, which is less sure of its reports in more ways.

 

A somewhat lesser upper bound for factoring leads to a faster run.

<pre>

CPU time: 4.125000

</pre>

 

Evidently, a candidate is denounced as definitely composite in the first trial, at least for these candidates. The following trials seem wasted effort...

Different-size bases have an effect, though not a regular one.

Base 10 100 1000 10000 100000 1000000

 

Converting from BIGDIVN(B,2) to BIGDIV2(B) had very little effect on the speed, but inspection of the code demonstrated that the Compaq compiler carried forward the result of expressions involving constants such as <code>IF (MOD(BIGBASE,2).EQ.0) THEN</code> at compile time so that no run-time test was made, and "dead code" for the ELSE option was not generated. Further, MOD(N,2) generated code involving an '''and''', so there is no need to mess about by coding an AND or fiddling with special syntax that would only work on a binary computer. With such a compiler, a sort of "conditional compilation" is available without needing the often grotesque syntax of systems explicitly offering such facilities.

 

Replacing BIGMULT(B,B) by BIGSQUARE(B) converted ~4·28 seconds to ~4·14 seconds for the test run; three percent.

 

=={{header|FreeBASIC}}==

{{libheader|GMP}}

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> 1, 2, 3, 4, 5, 6, 11, 13, 24, 66, 68, 75, 167, 171, 172, 287, 310, 352, 384, 457,</pre>

 

=={{header|Haskell}}==

 

primes :: [Integer]

 

isPrime :: Integer -> Bool

isPrime = isPrime_ primes

 

primorials :: [Integer]

 

primorialsPlusMinusOne :: [Integer]

 

sequenceOfPrimorialPrimes :: [Int]

 

main :: IO ()

{{out}}

2

3

13

24

 

=={{header|J}}==

 

 

This isn't particularly fast - J's current extended precision number implementation favors portability over speed.

Example use:

 

 

Note that the task specifies that index zero is not a part of the sequence for this task. So pretend you didn't see it.

 

=={{header|Java}}==

 

public class PrimorialPrimes {

return composite;

}

 

<pre>1 2 3 4 5 6 11 13 24 66 68 75 167 171 172 287 310 352 384 457</pre>

 

=={{header|Kotlin}}==

 

import java.math.BigInteger

p += 2

}

 

{{out}}

1 2 3 4 5 6 11 13 24 66 68 75 167 171 172 287 310 352 384 457

</pre>

 

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

This program, in principle, generates arbitrarily many primirial prime indices. Practically speaking it depends on your patience; it generates them up to 643 in about 5 seconds.

{{out}}

<pre>1, 2, 3, 4, 5, 6, 11, 13, 24, 66, 68, 75, 167, 171, 172, 287, 310, 352, 384, 457, 564, 590, 616, 620, 643, 849,</pre>

=={{header|Perl}}==

{{libheader|ntheory}}

my $i = 0;

for (1..1e6) {

last if ++$i >= 20;

}

{{out}}

<pre>1

457</pre>

 

{{out}}

 

=={{header|Python}}==

Uses the pure python library [https://pypi.python.org/pypi/pyprimes/0.1.1a pyprimes ]. Note that pyprimes.isprime switches to a fast and good probabilistic algorithm for larger integers.

 

 

def primorial_prime(_pmax=500):

pyprimes.warn_probably = False

for i, n in zip(range(20), primorial_prime()):

 

{{out}}

=={{header|Racket}}==

We use a memorized version of <code>primordial</code> to make it faster.

 

(require math/number-theory

(when (or (prime? (add1 pr)) (prime? (sub1 pr)))

(yield i))))])

{{out}}

<pre>1

384

457</pre>

 

=={{header|Sidef}}==

 

var k = 1

}

 

{{out}}

<pre>

[1, 2, 3, 4, 5, 6, 11, 13, 24, 66, 68, 75, 167, 171, 172, 287, 310, 352, 384, 457]

</pre>

 

{{trans|C}}

Uses libGMP (GNU MP Bignum Library)

p,s,i,n:=BN(1),BN(1), 0,0;

do{ n+=1;

i+=1;

}

{{out}}

<pre>