Giuga numbers: Difference between revisions
Content added Content deleted
(Added ABC) |
|||
Line 852: | Line 852: | ||
<pre> |
<pre> |
||
Found Giuga numbers: [30, 858, 1722, 66198] |
Found Giuga numbers: [30, 858, 1722, 66198] |
||
</pre> |
|||
=={{header|jq}}== |
|||
'''Works with jq, the C implementation of jq''' |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
'''Works with jaq, the Rust implementation of jq''' |
|||
The algorithm used here is naive but suffices to find the first four Giuga numbers |
|||
in a reasonable amount of time whether using the C, Go, or Rust |
|||
implementations. On my machine, gojq is fastest at about 12s. |
|||
<syntaxhighlight lang="jq"> |
|||
# `div/1` is defined firstly to take advantage of gojq's infinite-precision |
|||
# integer arithmetic, and secondly to ensure jaq returns an integer. |
|||
def div($j): |
|||
(. - (. % $j)) / $j | round; # round is for the sake of jaq |
|||
# For convenience |
|||
def div($i; $j): $i|div($j); |
|||
def is_giuga: |
|||
. as $m |
|||
| sqrt as $limit |
|||
| {n: $m, f: 2} |
|||
| until(.ans; |
|||
if (.n % .f) == 0 |
|||
then if ((div($m; .f) - 1) % .f) != 0 then .ans = 0 |
|||
else .n = div(.n; .f) |
|||
| if .f > .n then .ans = 1 end |
|||
end |
|||
else .f += 1 |
|||
| if .f > $limit then .ans = 0 end |
|||
end) |
|||
| .ans == 1 ; |
|||
limit(4; range(4; infinite) | select(is_giuga)) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
30 |
|||
858 |
|||
1722 |
|||
66198 |
|||
</pre> |
</pre> |
||