Fermat pseudoprimes: Difference between revisions
Content added Content deleted
(New post.) |
|||
Line 552: | Line 552: | ||
The first 20: 21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059 |
The first 20: 21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059 |
||
</pre> |
</pre> |
||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
gojq supports infinite-precision integer arithmetic and is thus |
|||
suitable for the given tasks, including the stretch task: |
|||
the illustration below includes thresholds up to 100,000. |
|||
<syntaxhighlight lang="jq"> |
|||
### Generic functions |
|||
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .; |
|||
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
|||
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 sqrt as $s |
|||
| 23 |
|||
| until( . > $s or ($n % . == 0); . + 2) |
|||
| . > $s |
|||
end; |
|||
# The input to the power $exp modulo $mod, which is assumed to be positive |
|||
def modPow($exp; $mod): |
|||
{ base: (. % $mod), |
|||
exp: $exp, |
|||
r: 1 |
|||
} |
|||
| until( .exp == 0; |
|||
if .base == 0 then .r = 0 | .exp = 0 |
|||
else if .exp % 2 == 1 then .r = (.r * .base) % $mod end |
|||
| .exp |= ((. / 2) | trunc) |
|||
| .base |= (. * .) % $mod |
|||
end ) |
|||
| .r; |
|||
### Fermat Pseudoprimes |
|||
def isFermatPseudoprime($a): |
|||
if is_prime then false |
|||
else . as $x |
|||
| ($a | modPow($x-1; $x)) == 1 |
|||
end; |
|||
def display($n): |
|||
"First \($n) Fermat pseudoprimes:", |
|||
(range(1; $n+1) as $a |
|||
| { x: 2, count: 0 } |
|||
| until (.count >= 20; |
|||
if .x | isFermatPseudoprime($a) |
|||
then .first20 += [.x] |
|||
| .count += 1 |
|||
end |
|||
| .x += 1 ) |
|||
| "Base \($a|lpad(2)): \(.first20|map(lpad(5))|join(" "))" ) ; |
|||
def task($limits): |
|||
def heading: "\nCount <= \($limits | map(lpad(6)) | join(" "))"; |
|||
heading as $heading |
|||
| $heading, |
|||
"-" * ($heading|length - 1), |
|||
(range(1; 21) as $a |
|||
| "Base \($a|lpad(2)): " + |
|||
([foreach $limits[] as $limit ( {x: 2, count: 0 }; |
|||
until (.x > $limit; |
|||
if .x | isFermatPseudoprime($a) then .count += 1 end |
|||
| .x += 1 ) ) |
|||
| .count |
|||
| lpad(6) ] |
|||
| join(" ") ) ) ; |
|||
display(20), |
|||
task( [12000, 25000, 50000, 100000] ) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
As for [[#Wren|Wren]]. |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Line 585: | Line 674: | ||
Base 20 up to 50000: 66 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059] |
Base 20 up to 50000: 66 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059] |
||
</pre> |
</pre> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |