Penta-power prime seeds: Difference between revisions
Thundergnat (talk | contribs) m (→{{header|Raku}}: only check odds as noted on talk page. less than a 5% speed up but worth it) |
Thundergnat (talk | contribs) m (Add escape for language that can't reasonably reach task goal.) |
||
Line 7:
;Task
* Find and display the first thirty penta-power prime seeds. (Or as many as are reasonably supported by your languages math capability.)
|
Revision as of 20:43, 20 August 2022
Generate the sequence of penta-power prime seeds: positive integers n such that:
n0 + n + 1, n1 + n + 1, n2 + n + 1, n3 + n + 1 and n4 + n + 1 are all prime.
- Task
- Find and display the first thirty penta-power prime seeds. (Or as many as are reasonably supported by your languages math capability.)
- Stretch
- Find and display the position and value of first with a value greater than ten million.
- See also
I can find no mention or record of this sequence anywhere. Perhaps I've invented it.
ALGOL 68
This uses ALGOL 68G's LONG LONG INT during the Miller Rabin testing, under ALGOL 68G version three, the default precision of LONG LONG INT is 72 digits and LONG INT is 128 bit.
A sieve is used to (hopefully) quickly eliminate non-prime n+2 and 2n+1 numbers - Miller Rabin is used for n^2+n+1 etc. that are larger than the sieve.
This is about 10 times faster than the equivalent Quad-powwr prime seed program, possibly because even numbers are excluded and the n+2 test eliminates more numbers before the higher powers must be calculated..
NB: The source of the ALGOL 68-primes library is on a Rosetta Code code page linked from the above.
Note that to run this with ALGOL 68G under Windows (and probably Linux) a large heap size must be specified on the command line, e.g. -heap 1024M
.
<lang algol68>BEGIN # find some Penta power prime seeds, numbers n such that: #
# n^p + n + 1 is prime for p = 0. 1, 2, 3, 4 # PR read "primes.incl.a68" PR # include prime utilities # INT max prime = 22 000 000; # sieve the primes to max prime - 22 000 000 should be enough to allow # # checking primality of 2n+1 up to a little under 11 000 000 which should # # be enough for the task # [ 0 : max prime ]BOOL prime; FOR i FROM LWB prime TO UPB prime DO prime[ i ] := FALSE OD; prime[ 0 ] := prime[ 1 ] := FALSE; prime[ 2 ] := TRUE; FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD; FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD; FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO IF prime[ i ] THEN FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD FI OD; # returns TRUE if p is (probably) prime, FALSE otherwise # # uses the sieve if possible, Miller Rabin otherwise # PROC is prime = ( LONG INT p )BOOL: IF p <= max prime THEN prime[ SHORTEN p ] ELSE is probably prime( p ) FI; # attempt to find the numbers, note n^0 + n + 1 = n + 2 so n must be odd # BOOL finished := FALSE; INT count := 0; INT next limit := 1 000 000; INT limit increment = next limit; [ 10 ]INT first, limit, index; INT l count := 0; print( ( "First 30 Penta power prime seeds:", newline ) ); FOR n BY 2 WHILE NOT finished DO IF prime[ n + 2 ] THEN IF INT n1 = n + 1; prime[ n + n1 ] THEN # n^0 + n + 1 and n^1 + n + 1 are prime # LONG INT np := n * n; IF is prime( np + n1 ) THEN # n^2 + n + 1 is prime # IF is prime( ( np *:= n ) + n1 ) THEN # n^3 + n + 1 is prime # IF is prime( ( np * n ) + n1 ) THEN # n^4 + n + 1 is prime - have a suitable number # count +:= 1; IF n > next limit THEN # found the first element over the next limit # first[ l count +:= 1 ] := n; limit[ l count ] := next limit; index[ l count ] := count; next limit +:= limit increment; finished := l count >= UPB first FI; IF count <= 30 THEN # found one of the first 30 numbers # print( ( " ", whole( n, -8 ) ) ); IF count MOD 10 = 0 THEN print( ( newline ) ) FI FI FI FI FI FI FI OD; print( ( newline ) ); FOR i TO UPB first DO print( ( "First element over ", whole( limit[ i ], -10 ) , ": ", whole( first[ i ], -10 ) , ", index: ", whole( index[ i ], -6 ) , newline ) ) OD
END</lang>
- Output:
First 30 Penta power prime seeds: 1 5 69 1665 2129 25739 29631 62321 77685 80535 82655 126489 207285 211091 234359 256719 366675 407945 414099 628859 644399 770531 781109 782781 923405 1121189 1158975 1483691 1490475 1512321 First element over 1000000: 1121189, index: 26 First element over 2000000: 2066079, index: 39 First element over 3000000: 3127011, index: 47 First element over 4000000: 4059525, index: 51 First element over 5000000: 5279175, index: 59 First element over 6000000: 6320601, index: 63 First element over 7000000: 7291361, index: 68 First element over 8000000: 8334915, index: 69 First element over 9000000: 9100671, index: 71 First element over 10000000: 10347035, index: 72
Phix
with javascript_semantics include mpfr.e mpz {p,q} = mpz_inits(2) function isPentaPowerPrimeSeed(integer n) -- (we already know n+2 is prime) mpz_set_si(p,n) for i=1 to 4 do if i>1 then mpz_mul_si(p,p,n) end if mpz_add_ui(q,p,n+1) if not mpz_prime(q) then return false end if end for return true end function sequence ppps = {} integer pn = 1, m = 1, c = 0 string l = "" while m<=10 do integer n = get_prime(pn)-2 if isPentaPowerPrimeSeed(n) then c += 1 if c<31 then ppps &= n if c=30 then printf(1,"First thirty penta-power prime seeds:\n%s\n", {join_by(ppps,1,10," ",fmt:="%,9d")}) end if end if if n > m * 1e6 then l &= sprintf(" %5s million is %,d (the %s)\n", {ordinal(m,true), n, ordinal(c)}) m += 1 end if end if pn += 1 end while printf(1,"First penta-power prime seed greater than:\n%s",l)
- Output:
First thirty penta-power prime seeds: 1 5 69 1,665 2,129 25,739 29,631 62,321 77,685 80,535 82,655 126,489 207,285 211,091 234,359 256,719 366,675 407,945 414,099 628,859 644,399 770,531 781,109 782,781 923,405 1,121,189 1,158,975 1,483,691 1,490,475 1,512,321 First penta-power prime seed greater than: one million is 1,121,189 (the twenty-sixth) two million is 2,066,079 (the thirty-ninth) three million is 3,127,011 (the forty-seventh) four million is 4,059,525 (the fifty-first) five million is 5,279,175 (the fifty-ninth) six million is 6,320,601 (the sixty-third) seven million is 7,291,361 (the sixty-eighth) eight million is 8,334,915 (the sixty-ninth) nine million is 9,100,671 (the seventy-first) ten million is 10,347,035 (the seventy-second)
Raku
<lang perl6>use Lingua::EN::Numbers;
my @ppps = lazy (^∞).hyper(:5000batch).map(* × 2 + 1).grep: -> \n { my \k = n + 1; (1+k).is-prime && (n+k).is-prime && (n²+k).is-prime && (n³+k).is-prime && (n⁴+k).is-prime }
say "First thirty penta-power prime seeds:\n" ~ @ppps[^30].batch(10)».&comma».fmt("%9s").join: "\n";
say "\nFirst penta-power prime seed greater than:";
for 1..10 {
my $threshold = Int(1e6 × $_); my $key = @ppps.first: * > $threshold, :k; say "{$threshold.&cardinal.fmt: '%13s'} is the {ordinal-digit $key + 1}: {@ppps[$key].&comma}";
}</lang>
- Output:
First thirty penta-power prime seeds: 1 5 69 1,665 2,129 25,739 29,631 62,321 77,685 80,535 82,655 126,489 207,285 211,091 234,359 256,719 366,675 407,945 414,099 628,859 644,399 770,531 781,109 782,781 923,405 1,121,189 1,158,975 1,483,691 1,490,475 1,512,321 First penta-power prime seed greater than: one million is the 26th: 1,121,189 two million is the 39th: 2,066,079 three million is the 47th: 3,127,011 four million is the 51st: 4,059,525 five million is the 59th: 5,279,175 six million is the 63rd: 6,320,601 seven million is the 68th: 7,291,361 eight million is the 69th: 8,334,915 nine million is the 71st: 9,100,671 ten million is the 72nd: 10,347,035
Wren
<lang ecmascript>import "./gmp" for Mpz import "./fmt" for Fmt
var p = Mpz.new() var q = Mpz.one
var isPentaPowerPrimeSeed = Fn.new { |n|
p.setUi(n) var k = n + 1 return (q + k).probPrime(15) > 0 && (p + k).probPrime(15) > 0 && (p.mul(n) + k).probPrime(15) > 0 && (p.mul(n) + k).probPrime(15) > 0 && (p.mul(n) + k).probPrime(15) > 0
}
var ppps = [] var n = 1 while (ppps.count < 30) {
if (isPentaPowerPrimeSeed.call(n)) ppps.add(n) n = n + 2 // n must be odd
} System.print("First thirty penta-power prime seeds:") Fmt.tprint("$,9d", ppps, 10)
System.print("\nFirst penta-power prime seed greater than:") n = 1 var m = 1 var c = 0 while (true) {
if (isPentaPowerPrimeSeed.call(n)) { c = c + 1 if (n > m * 1e6) { Fmt.print(" $2d million is the $r: $,10d", m, c, n) m = m + 1 if (m == 11) return } } n = n + 2
}</lang>
- Output:
First thirty penta-power prime seeds: 1 5 69 1,665 2,129 25,739 29,631 62,321 77,685 80,535 82,655 126,489 207,285 211,091 234,359 256,719 366,675 407,945 414,099 628,859 644,399 770,531 781,109 782,781 923,405 1,121,189 1,158,975 1,483,691 1,490,475 1,512,321 First penta-power prime seed greater than: 1 million is the 26th: 1,121,189 2 million is the 39th: 2,066,079 3 million is the 47th: 3,127,011 4 million is the 51st: 4,059,525 5 million is the 59th: 5,279,175 6 million is the 63rd: 6,320,601 7 million is the 68th: 7,291,361 8 million is the 69th: 8,334,915 9 million is the 71st: 9,100,671 10 million is the 72nd: 10,347,035