Rosetta Code

Quad-power prime seeds: Difference between revisions

Page Discussion

Quad-power prime seeds (view source)

Revision as of 22:45, 15 December 2023

15,279 bytes added ,  5 months ago
Added Sidef
(Quad-power prime seeds in FreeBASIC)
(Added Sidef)
 
(13 intermediate revisions by 9 users not shown)
Line 1:
{{draft task}}
 
Generate the sequence of quad-power prime seeds: positive integers '''n''' such that:
Line 135:
77685 79646 80535 82655 85251 86996 91014 96566 97739 105939
108240 108681 119754 122436 123164 126489 140636 150480 153179 163070</pre>
 
=={{header|C}}==
{{trans|Wren}}
{{libheader|GMP}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdbool.h>
#include <locale.h>
#include <gmp.h>
 
mpz_t p, p2;
 
bool isQuadPowerPrimeSeed(unsigned int n) {
int i;
mpz_set_ui(p, n);
unsigned int k = n + 1;
mpz_add_ui(p2, p, k);
if (!mpz_probab_prime_p(p2, 15)) return false;
for (i = 0; i < 3; ++i) {
mpz_mul_ui(p, p, n);
mpz_set(p2, p);
mpz_add_ui(p2, p2, k);
if (!mpz_probab_prime_p(p2, 15)) return false;
}
return true;
}
 
const char *ord(int c) {
int m = c % 100;
if (m >= 4 && m <= 20) return "th";
m %= 10;
return (m == 1) ? "st" :
(m == 2) ? "nd" :
(m == 3) ? "rd" : "th";
}
 
int main() {
unsigned int n;
int c = 0, m = 1;
mpz_init(p);
mpz_init(p2);
setlocale(LC_NUMERIC, "");
printf("First fifty quad-power prime seeds:\n");
for (n = 1; c < 50; ++n) {
if (isQuadPowerPrimeSeed(n)) {
printf("%'7u ", n);
if (!((++c) % 10)) printf("\n");
}
}
 
printf("\nFirst quad-power prime seed greater than:\n");
while (1) {
if (isQuadPowerPrimeSeed(n)) {
++c;
if (n > 1000000 * m) {
printf(" %2d million is the %d%s: %'10u\n", m, c, ord(c), n);
if (++m == 11) break;
}
}
++n;
}
return 0;
}</syntaxhighlight>
 
{{out}}
<pre>
First fifty quad-power prime seeds:
1 2 5 6 69 131 426 1,665 2,129 2,696
5,250 7,929 9,689 13,545 14,154 14,286 16,434 19,760 25,739 27,809
29,631 36,821 41,819 46,619 48,321 59,030 60,500 61,955 62,321 73,610
77,685 79,646 80,535 82,655 85,251 86,996 91,014 96,566 97,739 105,939
108,240 108,681 119,754 122,436 123,164 126,489 140,636 150,480 153,179 163,070
 
First quad-power prime seed greater than:
1 million is the 141st: 1,009,286
2 million is the 234th: 2,015,496
3 million is the 319th: 3,005,316
4 million is the 383rd: 4,004,726
5 million is the 452nd: 5,023,880
6 million is the 514th: 6,000,554
7 million is the 567th: 7,047,129
8 million is the 601st: 8,005,710
9 million is the 645th: 9,055,151
10 million is the 701st: 10,023,600
</pre>
 
=={{header|F_Sharp|F#}}==
Line 184 ⟶ 268:
 
=={{header|FreeBASIC}}==
{{libheader|GMP}}
<syntaxhighlight lang="vb">#include "isprime.bas"
<syntaxhighlight lang="freebasic">' version 13-04-2023
' compile with: fbc -s console
 
#Include "gmp.bi"
Function isQuadPowerPrime(n As Uinteger) As Boolean
#Define sieve_max 20050000
Dim As Uinteger p(n)
Dim As Uinteger k = n + 1
Return isPrime(n+n+1) And isPrime((n*n)+(n+1)) And _
isPrime((n*n*n)+(n+1)) And isPrime((n^4)+(n+1))
End Function
 
Dim As UintegerMpz_ptr nn2 = 1,Allocate cont = 1(Len(__mpz_struct))
Dim As DoubleMpz_ptr t0n3 = TimerAllocate (Len(__mpz_struct))
Dim As Mpz_ptr n4 = Allocate (Len(__mpz_struct))
Print "First fifty quad-power prime seeds:"
Mpz_init(n2) : Mpz_init(n3) : Mpz_init(n4)
While cont < 50
 
If isQuadPowerPrime(n) Then
Dim As ULongInt i, j
Print Using "###,###"; n;
ReDim As boolean sieve(sieve_max)
If cont Mod 10 = 0 Then Print
 
cont += 1
' default value on initialization is FALSE
sieve(2) = TRUE
' set all odd numbers to TRUE
For i = 3 To sieve_max Step 2
sieve(i) = TRUE
Next
For i = 3 To Sqr(sieve_max) Step 2
If sieve(i) = TRUE Then
For j = i * i To sieve_max Step i * 2
sieve(j) = FALSE
Next
End If
Next
 
Dim As ULongInt n, count, k
Dim As LongInt si = 15
 
Print "The first fifty quad-power prime seeds are:"
While count < 50
n += 1
k = n +1
If sieve(n + k) Then ' skip if n + k is not prime
Mpz_ui_pow_ui(n4, n , 4)
Mpz_add_ui(n4, n4, k)
If Mpz_probab_prime_p(n4, si) < 1 Then Continue While ' skip if not prime
Mpz_ui_pow_ui(n3, n, 3)
Mpz_add_ui(n3, n3, k)
If Mpz_probab_prime_p(n3, si) < 1 Then Continue While ' skip if not prime
Mpz_ui_pow_ui(n2, n, 2)
Mpz_add_ui(n2, n2, k)
If Mpz_probab_prime_p(n2, si) >= 1 Then ' if prime then print n
Print Using "########"; n;
count += 1
If (count Mod 10) = 0 Then Print
End If
End If
Wend
Print: Print Timer - t0
 
Dim As ULongInt m = 1, million = 1000000
Print !"\nFirst quad-power prime seed greater than:"
 
Dim As Uinteger m = 1, c = 50
Print !"\n\nFirst quad-power prime seed greater than:"
Do
While m < 11
If isQuadPowerPrime(n) Then
cn += 1
k If= n > m * 1e6 Then+1
If sieve(n + k) Then ' skip Printif Usingn "+ ## millionk is thenot ###: ##########"; m; c; nprime
Mpz_ui_pow_ui(n4, n , m += 14)
Mpz_add_ui(n4, n4, k)
If m = 11 Then Exit Do
If Mpz_probab_prime_p(n4, si) < 1 Then Continue While ' skip if not prime
Mpz_ui_pow_ui(n3, n, 3)
Mpz_add_ui(n3, n3, k)
If Mpz_probab_prime_p(n3, si) < 1 Then Continue While ' skip if not prime
Mpz_ui_pow_ui(n2, n, 2)
Mpz_add_ui(n2, n2, k)
If Mpz_probab_prime_p(n2, si) >= 1 Then
count += 1
If n > million Then
Print Using " ## million is #########, at index ### "; m; n; count
m += 1
million = m * 1000000
End If
End If
End If
Wend
n += 1
Loop
 
Mpz_clear(n4) : Mpz_clear(n3) : Mpz_clear(n2)
Sleep</syntaxhighlight>
 
 
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
{{out}}
<pre>The first fifty quad-power prime seeds are:
1 2 5 6 69 131 426 1665 2129 2696
5250 7929 9689 13545 14154 14286 16434 19760 25739 27809
29631 36821 41819 46619 48321 59030 60500 61955 62321 73610
77685 79646 80535 82655 85251 86996 91014 96566 97739 105939
108240 108681 119754 122436 123164 126489 140636 150480 153179 163070
 
 
First quad-power prime seed greater than:
1 million is 1,009,286 at index 141
2 million is 2,015,496 at index 234
3 million is 3,005,316 at index 319
4 million is 4,004,726 at index 383
5 million is 5,023,880 at index 452
6 million is 6,000,554 at index 514
7 million is 7,047,129 at index 567
8 million is 8,005,710 at index 601
9 million is 9,055,151 at index 645
10 million is 10,023,600 at index 701</pre>
 
=={{header|Go}}==
{{trans|Wren}}
{{libheader|GMP(Go wrapper)}}
{{libheader|Go-rcu}}
<syntaxhighlight lang="go">package main
 
import (
"fmt"
big "github.com/ncw/gmp"
"rcu"
)
 
var p, p2 *big.Int
 
func isQuadPowerPrimeSeed(n uint64) bool {
nn := new(big.Int).SetUint64(n)
p.Set(nn)
k := new(big.Int).SetUint64(n + 1)
p2.Add(p, k)
if !p2.ProbablyPrime(15) {
return false
}
for i := 0; i < 3; i++ {
p.Mul(p, nn)
p2.Set(p)
p2.Add(p2, k)
if !p2.ProbablyPrime(15) {
return false
}
}
return true
}
 
func ord(c int) string {
m := c % 100
if m > 4 && m <= 20 {
return "th"
}
m %= 10
switch m {
case 1:
return "st"
case 2:
return "nd"
case 3:
return "rd"
default:
return "th"
}
}
 
func main() {
p = new(big.Int)
p2 = new(big.Int)
c := 0
m := 1
n := uint64(1)
fmt.Println("First fifty quad-power prime seeds:")
for ; c < 50; n++ {
if isQuadPowerPrimeSeed(n) {
fmt.Printf("%7s ", rcu.Commatize(int(n)))
c++
if c%10 == 0 {
fmt.Println()
}
}
}
 
fmt.Println("\nFirst quad-power prime seed greater than:")
for {
if isQuadPowerPrimeSeed(n) {
c++
if n > 1000000*uint64(m) {
ns := rcu.Commatize(int(n))
fmt.Printf(" %2d million is the %d%s: %10s\n", m, c, ord(c), ns)
m++
if m == 11 {
break
}
}
}
n++
}
}</syntaxhighlight>
 
{{out}}
<pre>
First fifty quad-power prime seeds:
1 2 5 6 69 131 426 1,665 2,129 2,696
5,250 7,929 9,689 13,545 14,154 14,286 16,434 19,760 25,739 27,809
29,631 36,821 41,819 46,619 48,321 59,030 60,500 61,955 62,321 73,610
77,685 79,646 80,535 82,655 85,251 86,996 91,014 96,566 97,739 105,939
108,240 108,681 119,754 122,436 123,164 126,489 140,636 150,480 153,179 163,070
 
First quad-power prime seed greater than:
1 million is the 141st: 1,009,286
2 million is the 234th: 2,015,496
3 million is the 319th: 3,005,316
4 million is the 383rd: 4,004,726
5 million is the 452nd: 5,023,880
6 million is the 514th: 6,000,554
7 million is the 567th: 7,047,129
8 million is the 601st: 8,005,710
9 million is the 645th: 9,055,151
10 million is the 701st: 10,023,600
</pre>
 
=={{header|J}}==
<syntaxhighlight lang="j"> quadpower =. (5 = (] >:)^:((5 > ]) *. 1 p: 1 + [ + ^)^:_"0) & 1x
_10 ]\ I. quadpower i. 170000
1 2 5 6 69 131 426 1665 2129 2696
5250 7929 9689 13545 14154 14286 16434 19760 25739 27809
29631 36821 41819 46619 48321 59030 60500 61955 62321 73610
77685 79646 80535 82655 85251 86996 91014 96566 97739 105939
108240 108681 119754 122436 123164 126489 140636 150480 153179 163070</syntaxhighlight>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
 
public final class QuadPowerPrimeSeeds {
 
public static void main(String[] args) {
System.out.println("The first 50 quad-power prime seeds:");
int index = 0;
int number = 1;
while ( index < 50 ) {
if ( isQuadPowerPrimeSeed(number) ) {
index += 1;
System.out.print(String.format("%7d%s", number, ( index % 10 == 0 ? "\n" : " " )));
}
number += 1;
}
System.out.println();
System.out.println("The first quad-power prime seed greater than:");
int multiple = 1;
while ( multiple <= 3 ) {
if ( isQuadPowerPrimeSeed(number) ) {
index += 1;
if ( number > multiple * 1_000_000 ) {
System.out.println(" " + multiple + " million is " + number + " at index " + index);
multiple += 1;
}
}
number += 1;
}
}
private static boolean isQuadPowerPrimeSeed(long number) {
BigInteger p = BigInteger.valueOf(number);
BigInteger nPlus1 = BigInteger.valueOf(number + 1);
for ( int i = 1; i <= 4; i++ ) {
if ( ! p.add(nPlus1).isProbablePrime(15) ) {
return false;
}
p = p.multiply(BigInteger.valueOf(number));
}
return true;
}
 
}
</syntaxhighlight>
{{ out }}
<pre>
The first 50 quad-power prime seeds:
1 2 5 6 69 131 426 1665 2129 2696
5250 7929 9689 13545 14154 14286 16434 19760 25739 27809
29631 36821 41819 46619 48321 59030 60500 61955 62321 73610
77685 79646 80535 82655 85251 86996 91014 96566 97739 105939
108240 108681 119754 122436 123164 126489 140636 150480 153179 163070
 
The first quad-power prime seed greater than:
1 million is 1009286 at index 141
2 million is 2015496 at index 234
3 million is 3005316 at index 319
</pre>
 
=={{header|Julia}}==
{{trans|Python}}
<syntaxhighlight lang="julia">using Primes, Formatting
 
isquadpowerprime(x) = all(isprime, [2x + 1, x^2 + x + 1, x^3 + x + 1, x^4 + x + 1])
 
const qpprimes = filter(isquadpowerprime, Int128(1):10_100_000)
 
foreach(n -> print(lpad(qpprimes[n], 9), n % 10 == 0 ? "\n" : ""), 1:50)
 
for j in 1_000_000:1_000_000:10_000_000
for p in qpprimes
if p > j
println("The first quad-power prime seed over ", format(j, commas = true),
" is ", format(p, commas = true))
break
end
end
end
 
</syntaxhighlight>{{out}}
<pre>
1 2 5 6 69 131 426 1665 2129 2696
5250 7929 9689 13545 14154 14286 16434 19760 25739 27809
29631 36821 41819 46619 48321 59030 60500 61955 62321 73610
77685 79646 80535 82655 85251 86996 91014 96566 97739 105939
108240 108681 119754 122436 123164 126489 140636 150480 153179 163070
The first quad-power prime seed over 1,000,000 is 1,009,286
The first quad-power prime seed over 2,000,000 is 2,015,496
The first quad-power prime seed over 3,000,000 is 3,005,316
The first quad-power prime seed over 4,000,000 is 4,004,726
The first quad-power prime seed over 5,000,000 is 5,023,880
The first quad-power prime seed over 6,000,000 is 6,000,554
The first quad-power prime seed over 7,000,000 is 7,047,129
The first quad-power prime seed over 8,000,000 is 8,005,710
The first quad-power prime seed over 9,000,000 is 9,055,151
The first quad-power prime seed over 10,000,000 is 10,023,600
</pre>
 
=={{header|Nim}}==
{{libheader|Nim-Integers}}
<syntaxhighlight lang="Nim">import std/[strformat, strutils]
import integers
 
func isQuadPowerPrimeSeeds(n: Integer): bool =
var p = newInteger(n)
var n1 = n + 1
for _ in 1..4:
if not isPrime(p + n1): return false
p *= n
result = true
 
const N = 1_000_000
 
echo "First 30 quad-power prime seeds:"
var count = 0
var n = 1
var limit = N
while true:
if n.isQuadPowerPrimeSeeds():
inc count
if count <= 50:
stdout.write &"{n:7}"
stdout.write if count mod 10 == 0: '\n' else: ' '
if count == 50: echo()
elif n > limit:
echo &"First quad-power prime seed greater than {insertSep($limit)} " &
&"is {insertSep($n)} at position {count}."
inc limit, N
if limit > 3 * N: break
inc n
</syntaxhighlight>
 
{{out}}
<pre>First 30 quad-power prime seeds:
1 2 5 6 69 131 426 1665 2129 2696
5250 7929 9689 13545 14154 14286 16434 19760 25739 27809
29631 36821 41819 46619 48321 59030 60500 61955 62321 73610
77685 79646 80535 82655 85251 86996 91014 96566 97739 105939
108240 108681 119754 122436 123164 126489 140636 150480 153179 163070
 
First quad-power prime seed greater than 1_000_000 is 1_009_286 at position 141.
First quad-power prime seed greater than 2_000_000 is 2_015_496 at position 234.
First quad-power prime seed greater than 3_000_000 is 3_005_316 at position 319.
</pre>
 
=={{header|Perl}}==
Line 388 ⟶ 807:
nine million is the 645th: 9,055,151
ten million is the 701st: 10,023,600</pre>
 
=={{header|RPL}}==
{{works with|HP|49}}
« { } 1
'''WHILE''' OVER SIZE 50 < '''REPEAT'''
1 SF
1 4 '''FOR''' j
DUP j ^ OVER + 1 +
'''IF''' ISPRIME? NOT '''THEN''' 1 CF 4 'j' STO '''END'''
'''NEXT'''
'''IF''' 1 FS? '''THEN''' SWAP OVER + SWAP '''END '''
1 +
'''END'''
» '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: {1 2 5 6 69 131 426 1665 2129 2696 5250 7929 9689 13545 14154 14286 16434 19760 25739 27809 29631 36821 41819 46619 48321 59030 60500 61955 62321 73610 77685 79646 80535 82655 85251 86996 91014 96566 97739 105939 108240 108681 119754 122436 123164 126489 140636 150480 153179 163070}
</pre>
Runs in around 8 minutes on an IOS-based emulator.
 
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">require 'openssl'
 
quad_pow_primes = (1..).lazy.select{|n| (1..4).all?{|exp| OpenSSL::BN.new(n**exp + n + 1).prime?} }
 
n = 50
puts "The first #{n} quad-power prime seeds:"
quad_pow_primes.take(n).each_slice(10){|s| puts "%8s"*s.size % s}</syntaxhighlight>
{{out}}
<pre>The first 50 quad-power prime seeds:
1 2 5 6 69 131 426 1665 2129 2696
5250 7929 9689 13545 14154 14286 16434 19760 25739 27809
29631 36821 41819 46619 48321 59030 60500 61955 62321 73610
77685 79646 80535 82655 85251 86996 91014 96566 97739 105939
108240 108681 119754 122436 123164 126489 140636 150480 153179 163070
</pre>
 
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">var qpps = (1..Inf -> by(2).lazy.grep { .is_prime }.map {|n| (n-1)>>1 }.grep {|n|
is_prime(n**2 + n + 1) && all_prime(n**3 + n + 1, n**4 + n + 1)
})
 
with (50) {|n|
say "First #{n} quad-power prime seeds:"
qpps.first(n).each_slice(10, {|*s| say s.map{ '%6s' % _ }.join(' ') })
}</syntaxhighlight>
{{out}}
<pre>
First 50 quad-power prime seeds:
1 2 5 6 69 131 426 1665 2129 2696
5250 7929 9689 13545 14154 14286 16434 19760 25739 27809
29631 36821 41819 46619 48321 59030 60500 61955 62321 73610
77685 79646 80535 82655 85251 86996 91014 96566 97739 105939
108240 108681 119754 122436 123164 126489 140636 150480 153179 163070
</pre>
 
=={{header|Wren}}==
Line 393 ⟶ 867:
{{libheader|Wren-fmt}}
GMP allows us to stretch a little more.
<syntaxhighlight lang="ecmascriptwren">import "./gmp" for Mpz
import "./fmt" for Fmt
 
Trizen
2,747

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/339029...355768"