Sequence of primorial primes: Difference between revisions
(Added Kotlin) |
|||
Line 339: | Line 339: | ||
<pre>1 2 3 4 5 6 11 13 24 66 68 75 167 171 172 287 310 352 384 457</pre> |
<pre>1 2 3 4 5 6 11 13 24 66 68 75 167 171 172 287 310 352 384 457</pre> |
||
=={{header|Kotlin}}== |
|||
<lang scala>// version 1.0.6 |
|||
import java.math.BigInteger |
|||
const val LIMIT = 20 // expect a run time of about 2 minutes on a typical laptop |
|||
fun isPrime(n: Int): Boolean { |
|||
if (n < 2) return false |
|||
if (n % 2 == 0) return n == 2 |
|||
if (n % 3 == 0) return n == 3 |
|||
var d : Int = 5 |
|||
while (d * d <= n) { |
|||
if (n % d == 0) return false |
|||
d += 2 |
|||
if (n % d == 0) return false |
|||
d += 4 |
|||
} |
|||
return true |
|||
} |
|||
fun main(args: Array<String>) { |
|||
println("The first $LIMIT primorial indices in the sequence are:") |
|||
print("1 ") |
|||
var primorial = 1 |
|||
var count = 1 |
|||
var p = 3 |
|||
var prod = BigInteger.valueOf(2L) |
|||
while(true) { |
|||
if (isPrime(p)) { |
|||
prod *= BigInteger.valueOf(p.toLong()) |
|||
primorial++ |
|||
if ((prod + BigInteger.ONE).isProbablePrime(1) || (prod - BigInteger.ONE).isProbablePrime(1)) { |
|||
print("$primorial ") |
|||
count++ |
|||
if (count == LIMIT) { |
|||
println() |
|||
break |
|||
} |
|||
} |
|||
} |
|||
p += 2 |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
The first 20 primorial indices in the sequence are: |
|||
1 2 3 4 5 6 11 13 24 66 68 75 167 171 172 287 310 352 384 457 |
|||
</pre> |
|||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
Revision as of 22:48, 9 January 2017
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.
- Primorial prime Wikipedia.
- Primorial prime from The Prime Glossary.
- Sequence A088411 from The On-Line Encyclopedia of Integer Sequences
- Related tasks
C
<lang c>
- 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
Clojure
- Uses Java Interoop to use Java for 1) Prime Test and 2) Prime sequence generation
<lang lisp> (ns example
(:gen-class))
- Lazy Sequence of primes (starting with number 2)
(def primes (iterate #(.nextProbablePrime %) (biginteger 2)))
(defn primorial-prime? [v]
" Test if value is a primorial prime " (let [a (biginteger (inc v)) b (biginteger (dec v))] (or (.isProbablePrime a 16) (.isProbablePrime b 16))))
- Generate indexes for first 20 primorial primes
(println (take 20 (keep-indexed ; take the first 20
#(if (primorial-prime? %2) (inc %1)) ; filters out non-primorials, passing on the index + 1 (since sequence begins with 1 (not 0) (reductions *' primes)))) ; computes the lazy sequence of product of 1 prime, 2 primes, 3 primes, etc.
</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
<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>
- 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
Kotlin
<lang scala>// version 1.0.6
import java.math.BigInteger
const val LIMIT = 20 // expect a run time of about 2 minutes on a typical laptop
fun isPrime(n: Int): Boolean {
if (n < 2) return false if (n % 2 == 0) return n == 2 if (n % 3 == 0) return n == 3 var d : Int = 5 while (d * d <= n) { if (n % d == 0) return false d += 2 if (n % d == 0) return false d += 4 } return true
}
fun main(args: Array<String>) {
println("The first $LIMIT primorial indices in the sequence are:") print("1 ") var primorial = 1 var count = 1 var p = 3 var prod = BigInteger.valueOf(2L) while(true) { if (isPrime(p)) { prod *= BigInteger.valueOf(p.toLong()) primorial++ if ((prod + BigInteger.ONE).isProbablePrime(1) || (prod - BigInteger.ONE).isProbablePrime(1)) { print("$primorial ") count++ if (count == LIMIT) { println() break } } } p += 2 }
}</lang>
- Output:
The first 20 primorial indices in the sequence are: 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
<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
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