Pierpont primes: Difference between revisions
→{{header|jq}}
(→{{header|ALGOL 68}}: Removed unused declaration) |
|||
Line 1,369:
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>
| |||