Sequence of primorial primes: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|zkl}}: while to do)
(added FreeBASIC)
Line 144: Line 144:
459 "14:07:29"
459 "14:07:29"
</lang>
</lang>
=={{header|FreeBASIC}}==
{{libheader|GMP}}
<lang freebasic>' version 23-10-2016
' compile with: fbc -s console

#Define max 9999 ' max number for the sieve

#Include Once "gmp.bi"

Dim As mpz_ptr p, p1
p = Allocate(Len(__mpz_struct)) : Mpz_init_set_ui(p, 1)
p1 = Allocate(Len(__mpz_struct)) : Mpz_init(p1)

Dim As UInteger i, n, x
Dim As Byte prime(max)

' Sieve of Eratosthenes
For i = 4 To max Step 2
prime(i) = 1
Next
For i = 3 To Sqr(max) Step 2
If prime(i) = 1 Then Continue For
For n = i * i To max Step i * 2
prime(n) = 1
Next
Next

n = 0 : x = 0
For i = 2 To max
If prime(i) = 1 Then Continue For
x = x + 1
mpz_mul_ui(p, p, i)
mpz_sub_ui(p1, p, 1)
If mpz_probab_prime_p(p1, 25) > 0 Then
Print Using "####"; x; : Print ",";
n += 1
If n >= 20 Then Exit For
Continue For
End If
mpz_add_ui(p1, p, 1)
If mpz_probab_prime_p(p1, 25) > 0 Then
Print Using "####"; x; : Print ",";
n += 1
If n >= 20 Then Exit For
End If
Next

Print
mpz_clear(p)
mpz_clear(p1)

' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</lang>
{{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}}==
=={{header|Haskell}}==

Revision as of 17:58, 23 October 2016

Sequence of 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.

The sequence of primorial primes is given as the increasing values of n where primorial(n) ± 1 is prime.

Noting that the n'th primorial is defined as the multiplication of the smallest n primes, the sequence is of the number of primes, in order that when multiplied together is one-off being a prime number itself.


Task

Generate and show here the first ten values of the sequence.


Optional extended task

Show the first twenty members of the series.


Notes
  • 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 sequence begins with n = 1.


Cf.


Related tasks



C

Library: GMP

<lang c>

  1. include <gmp.h>

int main(void) { 

   mpz_t p, s;
   mpz_init_set_ui(p, 1);
   mpz_init_set_ui(s, 1);

   for (int n = 1, i = 0; i < 20; n++) {
       mpz_nextprime(s, s);
       mpz_mul(p, p, s);

       mpz_add_ui(p, p, 1);
       if (mpz_probab_prime_p(p, 25)) {
           mpz_sub_ui(p, p, 1);
           gmp_printf("%d\n", n);
           i++;
           continue;
       }

       mpz_sub_ui(p, p, 2);
       if (mpz_probab_prime_p(p, 25)) {
           mpz_add_ui(p, p, 1);
           gmp_printf("%d\n", n);
           i++;
           continue;
       }

       mpz_add_ui(p, p, 1);
   }

   mpz_clear(s);
   mpz_clear(p);

} </lang>

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

EchoLisp

<lang lisp> (lib 'timer) ;; for (every (proc t) interval) (lib 'bigint)

memoize primorial

(define p1000 (cons 1 (primes 1000))) ; remember first 1000 primes (define (primorial n) 

   (if(zero? n) 1 
   (* (list-ref p1000 n) (primorial (1- n)))))

(remember 'primorial)

(define N 0)

search one at a time

(define (search t) ;; time parameter, set by (every), not used (set! N (1+ N)) (if (or (prime? (1+ (primorial N))) (prime? (1- (primorial N)))) (writeln 'HIT N ) 

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

</lang>

Output:

<lang lisp>

run in batch mode to make the browser happy
search next N every 2000 msec

(every 2000 search) 

   →
   HIT     1    
   HIT     2    
   HIT     3    
   HIT     4    
   HIT     5    
   HIT     6    
   7     "13:47:03"    
   HIT     11    
   HIT     13    
   HIT     24      
   HIT     66     
   HIT     68    
   HIT     75    
   HIT     167    
   HIT     171    
   HIT     172    
   HIT     287    
   HIT     310    
   HIT     352    
   HIT     384      
   455     "14:07:08"    
   456     "14:07:12"    
   HIT     457    
   458     "14:07:25"    
   459     "14:07:29"

</lang>

FreeBASIC

Library: GMP

<lang freebasic>' version 23-10-2016 ' compile with: fbc -s console

  1. Define max 9999 ' max number for the sieve
  1. Include Once "gmp.bi"

Dim As mpz_ptr p, p1 p = Allocate(Len(__mpz_struct)) : Mpz_init_set_ui(p, 1) p1 = Allocate(Len(__mpz_struct)) : Mpz_init(p1)

Dim As UInteger i, n, x Dim As Byte prime(max)

' Sieve of Eratosthenes For i = 4 To max Step 2 

 prime(i) = 1

Next For i = 3 To Sqr(max) Step 2 

 If prime(i) = 1 Then Continue For
 For n = i * i To max Step i * 2
   prime(n) = 1
 Next

Next

n = 0 : x = 0 For i = 2 To max 

 If prime(i) = 1 Then Continue For
 x = x + 1
 mpz_mul_ui(p, p, i)
 mpz_sub_ui(p1, p, 1)
 If mpz_probab_prime_p(p1, 25) > 0 Then
   Print Using "####"; x; : Print ",";
   n += 1
   If n >= 20 Then Exit For
   Continue For
 End If
 mpz_add_ui(p1, p, 1)
 If mpz_probab_prime_p(p1, 25) > 0 Then
   Print Using "####"; x; : Print ",";
   n += 1
   If n >= 20 Then Exit For
 End If

Next

Print mpz_clear(p) mpz_clear(p1)

' empty keyboard buffer While Inkey <> "" : Wend Print : Print "hit any key to end program" Sleep End</lang>

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

Haskell

<lang Haskell> import Data.List (scanl1, findIndices, nub)

primes :: [Integer] primes = 2 : filter isPrime [3,5..]

isPrime :: Integer -> Bool isPrime = isPrime_ primes 

 where isPrime_ :: [Integer] -> Integer -> Bool
       isPrime_ (p:ps) n
         | p * p > n      = True
         | n `mod` p == 0 = False
         | otherwise      = isPrime_ ps n

primorials :: [Integer] primorials = 1 : scanl1 (*) primes

primorialsPlusMinusOne :: [Integer] primorialsPlusMinusOne = concatMap (\n -> [n-1, n+1]) primorials

sequenceOfPrimorialPrimes :: [Int] sequenceOfPrimorialPrimes = tail $ nub $ map (`div` 2) $ findIndices (==True) bools 

 where bools = map isPrime primorialsPlusMinusOne

main :: IO () main = mapM_ print $ take 10 sequenceOfPrimorialPrimes </lang>

Output:
1
2
3
4
5
6
11
13
24
66

J

<lang J>primoprim=: [: I. [: +./ 1 p: (1,_1) +/ */\@:p:@i.</lang>

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

Example use:

<lang J> primoprim 600x 0 1 2 3 4 5 10 12 23 65 67 74 166 170 171 286 309 351 383 456 563 589</lang>

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.

Java

<lang java>import java.math.BigInteger;

public class PrimorialPrimes { 

   final static int sieveLimit = 1550_000;
   static boolean[] notPrime = sieve(sieveLimit);

   public static void main(String[] args) {

       int count = 0;
       for (int i = 1; i < 1000_000 && count < 20; i++) {
           BigInteger b = primorial(i);
           if (b.add(BigInteger.ONE).isProbablePrime(1)
                   || b.subtract(BigInteger.ONE).isProbablePrime(1)) {
               System.out.printf("%d ", i);
               count++;
           }
       }
   }

   static BigInteger primorial(int n) {
       if (n == 0)
           return BigInteger.ONE;

       BigInteger result = BigInteger.ONE;
       for (int i = 0; i < sieveLimit && n > 0; i++) {
           if (notPrime[i])
               continue;
           result = result.multiply(BigInteger.valueOf(i));
           n--;
       }
       return result;
   }

   public static boolean[] sieve(int limit) {
       boolean[] composite = new boolean[limit];
       composite[0] = composite[1] = true;

       int max = (int) Math.sqrt(limit);
       for (int n = 2; n <= max; n++) {
           if (!composite[n]) {
               for (int k = n * n; k < limit; k += n) {
                   composite[k] = true;
               }
           }
       }
       return composite;
   }

}</lang> 

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

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. <lang parigp>n=0; P=1; forprime(p=2,, P*=p; n++; if(ispseudoprime(P+1) || ispseudoprime(P-1), print1(n", ")))</lang>

Output:
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,

Perl

Library: ntheory

<lang perl>use ntheory ":all"; my $i = 0; for (1..1e6) { 

 my $n = pn_primorial($_);
 if (is_prime($n-1) || is_prime($n+1)) {
   print "$_\n";
   last if ++$i >= 20;
 }

}</lang>

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

Perl 6

<lang perl6>constant @primes = |grep *.is-prime, 2..*; constant @primorials = [\*] 1, @primes;

my @pp_indexes := |@primorials.pairs.map: { 

   .key if ( .value + any(1, -1) ).is-prime

};

say ~ @pp_indexes[ 0 ^.. 20 ]; # Skipping bogus first element.</lang>

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

Python

Uses the pure python library pyprimes . Note that pyprimes.isprime switches to a fast and good probabilistic algorithm for larger integers.

<lang python>import pyprimes

def primorial_prime(_pmax=500): 

   isprime = pyprimes.isprime
   n, primo = 0, 1
   for prime in pyprimes.nprimes(_pmax):
       n, primo = n+1, primo * prime
       if isprime(primo-1) or isprime(primo+1):
           yield n

if __name__ == '__main__': 

   # Turn off warning on use of probabilistic formula for prime test
   pyprimes.warn_probably = False  
   for i, n in zip(range(20), primorial_prime()):
       print('Primorial prime %2i at primorial index: %3i' % (i+1, n))</lang>
Output:
Primorial prime  1 at primorial index:   1
Primorial prime  2 at primorial index:   2
Primorial prime  3 at primorial index:   3
Primorial prime  4 at primorial index:   4
Primorial prime  5 at primorial index:   5
Primorial prime  6 at primorial index:   6
Primorial prime  7 at primorial index:  11
Primorial prime  8 at primorial index:  13
Primorial prime  9 at primorial index:  24
Primorial prime 10 at primorial index:  66
Primorial prime 11 at primorial index:  68
Primorial prime 12 at primorial index:  75
Primorial prime 13 at primorial index: 167
Primorial prime 14 at primorial index: 171
Primorial prime 15 at primorial index: 172
Primorial prime 16 at primorial index: 287
Primorial prime 17 at primorial index: 310
Primorial prime 18 at primorial index: 352
Primorial prime 19 at primorial index: 384
Primorial prime 20 at primorial index: 457

Racket

We use a memorized version of primordial to make it faster. <lang Racket>#lang racket

(require math/number-theory 

        racket/generator)

(define-syntax-rule (define/cache (name arg) body ...) 

 (begin
   (define cache (make-hash))
   (define (name arg)
     (hash-ref! cache arg (lambda () body ...)))))

(define/cache (primorial n) 

 (if (zero? n)
    1
    (* (nth-prime (sub1 n))
       (primorial (sub1 n)))))

(for ([i (in-range 20)] 

     [n (in-generator (for ([i (in-naturals 1)])
                        (define pr (primorial i))
                        (when (or (prime? (add1 pr)) (prime? (sub1 pr)))
                          (yield i))))])
 (displayln n))</lang>
Output:
1
2
3
4
5
6
11
13
24
66
68
75
167
171
172
287
310
352
384
457

Sidef

<lang ruby>func primorial_primes(n) { 

   var k = 1
   var p = 2
   var P = 2

   var seq = []
   for (var i = 0; i < n; ++k) {

       if (is_prime(P-1) || is_prime(P+1)) {
           seq << k
           ++i
       }

       p.next_prime!
       P *= p
   }

   return seq

}

say primorial_primes(20)</lang>

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

zkl

Translation of: C

Uses libGMP (GNU MP Bignum Library) <lang zkl>var [const] BN=Import("zklBigNum"); // libGMP p,s,i,n:=BN(1),BN(1), 0,0; do{ n+=1; 

   s.nextPrime();	// in place, probabilistic
   p.mul(s);		// in place
   if((p+1).probablyPrime() or (p-1).probablyPrime()){
      println("%3d  %5d digits".fmt(n,p.len()));
      i+=1;
   }

}while(i<20);</lang>

Output:
  1      1 digits
  2      1 digits
  3      2 digits
  4      3 digits
  5      4 digits
  6      5 digits
 11     12 digits
 13     15 digits
 24     35 digits
 66    131 digits
 68    136 digits
 75    154 digits
167    413 digits
171    425 digits
172    428 digits
287    790 digits
310    866 digits
352   1007 digits
384   1116 digits
457   1368 digits
Retrieved from "https://rosettacode.org/wiki/Sequence_of_primorial_primes?oldid=259339"