Pierpont primes: Difference between revisions
Content added Content deleted
(→{{header|ALGOL 68}}: Removed unused declaration) |
|||
Line 1,369: | Line 1,369: | ||
250th Pierpont prime of the second kind: 4,111,131,172,000,956,525,894,875,083,702,271 |
250th Pierpont prime of the second kind: 4,111,131,172,000,956,525,894,875,083,702,271 |
||
</pre> |
|||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
Since we do not know how often 2^u * 3^v ± 1 is prime, we use an |
|||
adaptive approach based on adjusting the upper bounds for u and v |
|||
that we need consider. The idea is to avoid any hand-waving about the |
|||
correctness of the solution. Some "debug" statements that are |
|||
informative about the adaptive steps have been retained as comments. |
|||
The standard (C-based) implementation of jq does not support very large |
|||
integers, and the Go implementation, gojq, requires too much memory |
|||
to solve the stretch problem, so the code for the stretch task is |
|||
shown, but not executed. |
|||
'''Preliminaries''' |
|||
<lang jq>def is_prime: |
|||
. as $n |
|||
| if ($n < 2) then false |
|||
elif ($n % 2 == 0) then $n == 2 |
|||
elif ($n % 3 == 0) then $n == 3 |
|||
elif ($n % 5 == 0) then $n == 5 |
|||
elif ($n % 7 == 0) then $n == 7 |
|||
elif ($n % 11 == 0) then $n == 11 |
|||
elif ($n % 13 == 0) then $n == 13 |
|||
elif ($n % 17 == 0) then $n == 17 |
|||
elif ($n % 19 == 0) then $n == 19 |
|||
else {i:23} |
|||
| until( (.i * .i) > $n or ($n % .i == 0); .i += 2) |
|||
| .i * .i > $n |
|||
end; |
|||
# pretty-printing |
|||
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .; |
|||
def nwise($n): |
|||
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; |
|||
n; |
|||
def table($ncols; $colwidth): |
|||
nwise($ncols) | map(lpad($colwidth)) | join(" ");</lang> |
|||
'''Pierpont primes''' |
|||
<lang jq># Input: the target number of primes of the form p(u,v) == 2^u * 3^v ± 1. |
|||
# The main idea is to let u run from 0:m and v run from 0:n where n ~~ 0.63 * m. |
|||
# Initially we start with plausible values for m and n ($maxm and $maxn respectively), |
|||
# and then check whether these have been chosen conservatively enough. |
|||
# |
|||
def pierponts($firstkind): |
|||
. as $N |
|||
| (if $firstkind then 1 else -1 end) as $incdec |
|||
# Input: [$maxm, $maxn] |
|||
# Output: an array of objects of the form {p, m, n} |
|||
# where .p is prime and .m and .n are the corresponding powers of 2 and 3 |
|||
| def pp: |
|||
debug as [$maxm, $maxn] |
|||
| [ ({p2:1, m:0}, |
|||
(foreach range(0; $maxm) as $m (1; . * 2; {p2: ., m: ($m + 1)}))) as $a |
|||
| ({p3:1, n:0}, |
|||
(foreach range(0; $maxn) as $n (1; . * 3; {p3: ., n: ($n + 1)}))) as $b |
|||
| {p: ($a.p2 * $b.p3 + $incdec), m: $a.m, n: $b.n} |
|||
| select(.p|is_prime) ] |
|||
| unique_by(.p) |
|||
# | (length|debug) as $debug # informative |
|||
| .; |
|||
# input: output of pp |
|||
# check that length is sufficient, and that $maxm and $maxn are large enough |
|||
def adequate($maxm; $maxn): |
|||
# ( ".[$N-1].m is \(.[$N-1].m) vs $maxm=\($maxm)" | debug) as $debug | |
|||
# ( ".[$N-1].n is \(.[$N-1].n) vs $maxn=\($maxn)" | debug) as $debug | |
|||
length > $N |
|||
and .[$N-1].m < $maxm - 3 # -2 is not sufficient |
|||
and .[$N-1].n < $maxn - 3 # -2 is not sufficient |
|||
; |
|||
# If our search has not been `adequate` then increase $maxm and $maxn |
|||
# input: [maxm, maxn, ([maxm,maxn]|pp)] |
|||
# output: pp |
|||
def adapt: |
|||
. as [$maxm, $maxn, $one] |
|||
| if ($one|adequate($maxm; $maxn)) then $one |
|||
else [$maxm + 2, $maxn + 1.6] as $maxplus |
|||
# | ("retrying with \($maxplus)" | debug) as $debug |
|||
| ($maxplus|pp) as $two |
|||
| $maxplus + [$two] | adapt |
|||
end; |
|||
# We start by selecting m and n so that |
|||
# m*n >> $N, i.e., 0.63 * m^2 >> $N , so m >> sqrt(1.585 * $N) |
|||
# Using 7 as the constant to start with is sufficient to avoid too much rework. |
|||
((9 * $N) | sqrt) as $maxm |
|||
| (0.63 * $maxm + 1) as $maxn |
|||
| [$maxm, $maxn] as $max |
|||
| ($max | pp) as $pp |
|||
| ($max + [$pp]) | [adapt[:$N][].p] ; |
|||
# The stretch goal: |
|||
def stretch: |
|||
250 |
|||
| "\nThe \(.)th Pierpoint prime of the first kind is \(pierponts(true)[-1])", |
|||
"\nThe \(.)th Pierpoint prime of the second kind is \(pierponts(false)[-1])" ; |
|||
# The primary task: |
|||
50 |
|||
| "\nThe first \(.) Pierpoint primes of the first kind:", (pierponts(true) | table(10;8)), |
|||
"\nThe first \(.) Pierpoint primes of the second kind:", (pierponts(false) | table(10;8))</lang> |
|||
{{out}} |
|||
<pre> |
|||
The first 50 Pierpoint primes of the first kind: |
|||
2 3 5 7 13 17 19 37 73 97 |
|||
109 163 193 257 433 487 577 769 1153 1297 |
|||
1459 2593 2917 3457 3889 10369 12289 17497 18433 39367 |
|||
52489 65537 139969 147457 209953 331777 472393 629857 746497 786433 |
|||
839809 995329 1179649 1492993 1769473 1990657 2654209 5038849 5308417 8503057 |
|||
The first 50 Pierpoint primes of the second kind: |
|||
2 3 5 7 11 17 23 31 47 53 |
|||
71 107 127 191 383 431 647 863 971 1151 |
|||
2591 4373 6143 6911 8191 8747 13121 15551 23327 27647 |
|||
62207 73727 131071 139967 165887 294911 314927 442367 472391 497663 |
|||
524287 786431 995327 1062881 2519423 10616831 17915903 18874367 25509167 30233087 |
|||
</pre> |
</pre> |
||