Sequence of primorial primes: Difference between revisions

From Rosetta Code
Content added Content deleted
(C Solution Addition)
m (→‎{{header|Perl}}: changed "say" to "print" for backwards compatibility)
Line 268: Line 268:
my $n = pn_primorial($_);
my $n = pn_primorial($_);
if (is_prime($n-1) || is_prime($n+1)) {
if (is_prime($n-1) || is_prime($n+1)) {
say;
print "$_\n";
last if ++$i >= 20;
last if ++$i >= 20;
}
}

Revision as of 16:05, 23 September 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>

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
Retrieved from "https://rosettacode.org/wiki/Sequence_of_primorial_primes?oldid=259335"