Primorial primes: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Raku}}: Add a Raku example)
(Add Factor)
Line 99: Line 99:
11: 11# + 1 = 200560490131
11: 11# + 1 = 200560490131
12: 13# - 1 = 304250263527209
12: 13# - 1 = 304250263527209
</pre>

=={{header|Factor}}==
{{works with|Factor|0.99 2022-04-03}}
<lang factor>USING: formatting kernel math math.factorials math.parser
math.primes sequences ;

: .p ( n i sgn p -- )
[ >dec "p" "#" surround ] 2dip
"%2d:%6s %s 1 = %d\n" printf ;

[let
1 0 :> ( i! p! )
[ i 12 <= ] [
p primorial 1 - :> a
a 2 + :> b
a prime? [ i p "-" a .p i 1 + i! ] when
b prime? [ i p "+" b .p i 1 + i! ] when
p 1 + p!
] while
]</lang>
{{out}}
<pre>
1: p0# + 1 = 2
2: p1# + 1 = 3
3: p2# - 1 = 5
4: p2# + 1 = 7
5: p3# - 1 = 29
6: p3# + 1 = 31
7: p4# + 1 = 211
8: p5# - 1 = 2309
9: p5# + 1 = 2311
10: p6# - 1 = 30029
11: p11# + 1 = 200560490131
12: p13# - 1 = 304250263527209
</pre>
</pre>


Revision as of 07:07, 14 August 2022

Primorial primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Definition

A primorial prime is a prime number that is one less or one more than a primorial.

In other words a non-negative integer n corresponds to a primorial prime if either pn# - 1 or pn# + 1 is prime where pn# denotes the product of the first n primes.

Examples

4 corresponds to the primorial prime p4# + 1 = 2 x 3 x 5 x 7 + 1 = 211.

6 corresponds to the primorial prime p6# - 1 = 210 x 11 x 13 - 1 = 30029.

Task

Find and show here the first 12 primorial primes. As well as the prime itself show the primorial number pn to which it corresponds and whether 1 is to be added or subtracted.

As p0# (by convention) is 1 and p1# is 2, start counting from p0#.

Stretch

If your language supports arbitrary sized integers, do the same for at least the next 12 primorial primes.

As it can take a long time to demonstrate that a large number (above say 2^64) is definitely prime, you may instead use a function which shows that a number is probably prime to a reasonable degree of certainty. Most 'big integer' libraries have such a function.

If a number has more than 40 digits, do not show the full number. Show instead the first 20 and the last 20 digits and how many digits in total the number has.

References
Related task



ALGOL 68

Basic task. Assumes LONG INT is at least 64 bit. Similar to the Factorial primes#ALGOL_68 sample. <lang algol68>BEGIN # find some primorial primes - primes that are p - 1 or p + 1 # 

     #      for some primorial p                                        #
  1. is prime PROC based on the one in the primality by trial division task #
 PROC is prime = ( LONG INT p )BOOL:
   IF p <= 1 OR NOT ODD p THEN
     p = 2
   ELSE
     BOOL prime := TRUE;
     FOR i FROM 3 BY 2 TO SHORTEN ENTIER long sqrt(p) WHILE prime := p MOD i /= 0 DO SKIP OD;
     prime
   FI;
  1. end of code based on the primality by trial divisio task #
   # construct a sieve of primes up to 200                              #
   [ 0 : 200 ]BOOL primes;
   primes[ 0 ] := primes[ 1 ] := FALSE;
   primes[ 2 ] := TRUE;
   FOR i FROM 3 BY 2 TO UPB primes DO primes[ i ] := TRUE  OD;
   FOR i FROM 4 BY 2 TO UPB primes DO primes[ i ] := FALSE OD;
   FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB primes ) DO
       IF primes[ i ] THEN
           FOR s FROM i * i BY i + i TO UPB primes DO primes[ s ] := FALSE OD
       FI
   OD;

   PROC show primorial prime = ( INT p number, INT n, CHAR p op, LONG INT p )VOID:
      print( ( whole( p number, -2 ), ":", whole( n, -4 )
             , "# ", p op, " 1 = ", whole( p, 0 )
             , newline
             )
           ); 

   LONG INT pn      := 1;
   INT      p count := 0;
   INT      p pos   := 0;
   # starting from primorial 0, which is defined to be 1                #
   FOR n FROM 0 WHILE p count < 12 DO
       IF  LONG INT p = pn - 1;
           is prime( p )
       THEN
           show primorial prime( p count +:= 1, n, "-", p )
       FI;
       IF  LONG INT p = pn + 1;
           is prime( p )
       THEN
           show primorial prime( p count +:= 1, n, "+", p )
       FI;
       # find the next prime                                            #
       WHILE NOT primes[ p pos +:= 1 ] DO SKIP OD;
       pn *:= p pos
   OD

END</lang>

Output:
 1:   0# + 1 = 2
 2:   1# + 1 = 3
 3:   2# - 1 = 5
 4:   2# + 1 = 7
 5:   3# - 1 = 29
 6:   3# + 1 = 31
 7:   4# + 1 = 211
 8:   5# - 1 = 2309
 9:   5# + 1 = 2311
10:   6# - 1 = 30029
11:  11# + 1 = 200560490131
12:  13# - 1 = 304250263527209

Factor

Works with: Factor version 0.99 2022-04-03

<lang factor>USING: formatting kernel math math.factorials math.parser math.primes sequences ;

.p ( n i sgn p -- )
   [ >dec "p" "#" surround ] 2dip
   "%2d:%6s %s 1 = %d\n" printf ;

[let 

   1 0 :> ( i! p! )
   [ i 12 <= ] [
       p primorial 1 - :> a
       a 2 + :> b
       a prime? [ i p "-" a .p i 1 + i! ] when
       b prime? [ i p "+" b .p i 1 + i! ] when
       p 1 + p!
   ] while

]</lang>

Output:
 1:   p0# + 1 = 2
 2:   p1# + 1 = 3
 3:   p2# - 1 = 5
 4:   p2# + 1 = 7
 5:   p3# - 1 = 29
 6:   p3# + 1 = 31
 7:   p4# + 1 = 211
 8:   p5# - 1 = 2309
 9:   p5# + 1 = 2311
10:   p6# - 1 = 30029
11:  p11# + 1 = 200560490131
12:  p13# - 1 = 304250263527209

J

Compare with the j factorial prime implementation. Columns here are primorial prime number cardinal number, primorial prime, primorial index number, and offset from the corresponding primorial to the prime: <lang J> P=: 1,*/\ p:i.15 NB. primorials represented as fixed width 64 bit integers 

  (,.~ #\)(,. (-{&P)/"1) (,. P I. <:) /:~(#~ 1 p: ]) ,P+/1 _1
1               2  0  1
2               3  1  1
3               5  2 _1
4               7  2  1
5              29  3 _1
6              31  3  1
7             211  4  1
8            2309  5 _1
9            2311  5  1

10 30029 6 _1 11 200560490131 11 1 12 304250263527209 13 _1</lang>

Raku

<lang perl6>my @primorials = 1, |[\*] (2..*).grep: &is-prime; sub abr ($_) { .chars < 41 ?? $_ !! .substr(0,20) ~ '..' ~ .substr(*-20) ~ " ({.chars} digits)" }

my $limit;

for ^∞ { 

   my \p = @primorials[$_];
   ++$limit and printf "%2d: %5s - 1 = %s\n", $limit, "p$_#", abr p -1 if (p -1).is-prime;
   ++$limit and printf "%2d: %5s + 1 = %s\n", $limit, "p$_#", abr p +1 if (p +1).is-prime;
   exit if $limit >= 30

}</lang>

Output:
 1:   p0# + 1 = 2
 2:   p1# + 1 = 3
 3:   p2# - 1 = 5
 4:   p2# + 1 = 7
 5:   p3# - 1 = 29
 6:   p3# + 1 = 31
 7:   p4# + 1 = 211
 8:   p5# - 1 = 2309
 9:   p5# + 1 = 2311
10:   p6# - 1 = 30029
11:  p11# + 1 = 200560490131
12:  p13# - 1 = 304250263527209
13:  p24# - 1 = 23768741896345550770650537601358309
14:  p66# - 1 = 19361386640700823163..29148240284399976569 (131 digits)
15:  p68# - 1 = 21597045956102547214..98759003964186453789 (136 digits)
16:  p75# + 1 = 17196201054584064334..62756822275663694111 (154 digits)
17: p167# - 1 = 19649288510530675457..35580823050358968029 (413 digits)
18: p171# + 1 = 20404068993016374194..29492908966644747931 (425 digits)
19: p172# + 1 = 20832554441869718052..12260054944287636531 (428 digits)
20: p287# - 1 = 71488723083486699645..63871022000761714929 (790 digits)
21: p310# - 1 = 40476351620665036743..10663664196050230069 (866 digits)
22: p352# - 1 = 13372477493552802137..21698973741675973189 (1007 digits)
23: p384# + 1 = 78244737296323701708..84011652643245393971 (1115 digits)
24: p457# + 1 = 68948124012218025568..25023568563926988371 (1368 digits)
25: p564# - 1 = 12039145942930719470..56788854266062940789 (1750 digits)
26: p590# - 1 = 19983712295113492764..61704122697617268869 (1844 digits)
27: p616# + 1 = 13195724337318102247..85805719764535513291 (1939 digits)
28: p620# - 1 = 57304682725550803084..81581766766846907409 (1953 digits)
29: p643# + 1 = 15034815029008301639..38987057002293989891 (2038 digits)
30: p849# - 1 = 11632076146197231553..78739544174329780009 (2811 digits)

Wren

Basic

Library: Wren-math
Library: Wren-fmt

<lang ecmascript>import "./math" for Int import "./fmt" for Fmt

var limit = 12 var c = 0 var i = 0 var primes = Int.primeSieve(99) // more than enough var p = 1 System.print("First %(limit) primorial primes:") while (true) { 

   if (Int.isPrime(p-1)) {
       var pi = "p%(i)#"
       Fmt.print("$2d: $4s - 1 = $d", c = c + 1, pi, p - 1)
       if (c == limit) return
   }
   if (Int.isPrime(p+1)) {
       var pi = "p%(i)#"
       Fmt.print("$2d: $4s + 1 = $d", c = c + 1, pi, p + 1)
       if (c == limit) return
   }
   p = p * primes[i]
   i = i + 1

}</lang>

Output:
First 12 primorial primes:
 1:  p0# + 1 = 2
 2:  p1# + 1 = 3
 3:  p2# - 1 = 5
 4:  p2# + 1 = 7
 5:  p3# - 1 = 29
 6:  p3# + 1 = 31
 7:  p4# + 1 = 211
 8:  p5# - 1 = 2309
 9:  p5# + 1 = 2311
10:  p6# - 1 = 30029
11: p11# + 1 = 200560490131
12: p13# - 1 = 304250263527209

Stretch

Library: Wren-gmp

This takes about 53.4 seconds to reach the 30th primorial prime on my machine (Core i7) with the final one taking 35 seconds of this. Likely to be very slow after that as the next primorial prime is p1391# + 1. <lang ecmascript>import "./gmp" for Mpz import "./math" for Int import "./fmt" for Fmt

var limit = 30 var c = 0 var i = 0 var primes = Int.primeSieve(9999) // more than enough var p = Mpz.one var two64 = Mpz.two.pow(64) System.print("First %(limit) factorial primes:") while (true) { 

   var r = (p < two64) ? 1 : 0  // test for definite primeness below 2^64
   if ((p-1).probPrime(15) > r) {
       var s = (p-1).toString
       var sc = s.count
       var digs = sc > 40 ? "(%(sc) digits)" : ""
       var pn = "p%(i)#"
       Fmt.print("$2d: $5s - 1 = $20a $s", c = c + 1, pn, s, digs)
       if (c == limit) return
   }
   if ((p+1).probPrime(15) > r) {
       var s = (p+1).toString
       var sc = s.count
       var digs = sc > 40 ? "(%(sc) digits)" : ""
       var pn = "p%(i)#"
       Fmt.print("$2d: $5s + 1 = $20a $s", c = c + 1, pn, s, digs)
       if (c == limit) return
   }
   p.mul(primes[i])
   i = i + 1

}</lang>

Output:
First 30 factorial primes:
 1:   p0# + 1 = 2  
 2:   p1# + 1 = 3  
 3:   p2# - 1 = 5  
 4:   p2# + 1 = 7  
 5:   p3# - 1 = 29  
 6:   p3# + 1 = 31  
 7:   p4# + 1 = 211  
 8:   p5# - 1 = 2309  
 9:   p5# + 1 = 2311  
10:   p6# - 1 = 30029  
11:  p11# + 1 = 200560490131  
12:  p13# - 1 = 304250263527209  
13:  p24# - 1 = 23768741896345550770650537601358309  
14:  p66# - 1 = 19361386640700823163...29148240284399976569 (131 digits)
15:  p68# - 1 = 21597045956102547214...98759003964186453789 (136 digits)
16:  p75# + 1 = 17196201054584064334...62756822275663694111 (154 digits)
17: p167# - 1 = 19649288510530675457...35580823050358968029 (413 digits)
18: p171# + 1 = 20404068993016374194...29492908966644747931 (425 digits)
19: p172# + 1 = 20832554441869718052...12260054944287636531 (428 digits)
20: p287# - 1 = 71488723083486699645...63871022000761714929 (790 digits)
21: p310# - 1 = 40476351620665036743...10663664196050230069 (866 digits)
22: p352# - 1 = 13372477493552802137...21698973741675973189 (1007 digits)
23: p384# + 1 = 78244737296323701708...84011652643245393971 (1115 digits)
24: p457# + 1 = 68948124012218025568...25023568563926988371 (1368 digits)
25: p564# - 1 = 12039145942930719470...56788854266062940789 (1750 digits)
26: p590# - 1 = 19983712295113492764...61704122697617268869 (1844 digits)
27: p616# + 1 = 13195724337318102247...85805719764535513291 (1939 digits)
28: p620# - 1 = 57304682725550803084...81581766766846907409 (1953 digits)
29: p643# + 1 = 15034815029008301639...38987057002293989891 (2038 digits)
30: p849# - 1 = 11632076146197231553...78739544174329780009 (2811 digits)
Retrieved from "https://rosettacode.org/wiki/Primorial_primes?oldid=322058"