Giuga numbers: Difference between revisions
→{{header|jq}}
(Add Scala implementation) |
|||
| (3 intermediate revisions by 2 users not shown) | |||
Line 63:
1722
66198
</pre>
=={{header|ABC}}==
Based on the Algol 68 sample,
<syntaxhighlight lang="abc">
HOW TO REPORT is.giuga n:
\ each prime factor must appear only once, e.g.: for 2:
\ [ ( n / 2 ) - 1 ] mod 2 = 0 => n / 2 is odd => n isn't divisible by 4
\ similarly for other primes
PUT 1, 3, 1, floor( n / 2 ) IN f.count, f, giuga, v
WHILE f <= v AND giuga = 1:
IF v mod f = 0:
PUT f.count + 1 IN f.count
IF ( ( floor( n / f ) ) - 1 ) mod f <> 0: PUT 0 IN giuga
PUT floor( v / f ) IN v
PUT f + 2 IN f
IF giuga = 1: \ n is still a candidate, check it is not prime
IF f.count = 1: FAIL \ only 1 factor - it is prime so not giuga
REPORT giuga = 1
PUT 0, -2 IN g.count, n
WHILE g.count < 4:
PUT n + 4 IN n \ assume the numbers are all even
IF is.giuga n:
PUT g.count + 1 IN g.count
WRITE n
</syntaxhighlight>
{{out}}
<pre>
30 858 1722 66198
</pre>
Line 822 ⟶ 852:
<pre>
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>
Line 916 ⟶ 990:
30 858 1722 66198
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
{{trans|Julia}}
<syntaxhighlight lang="Mathematica">
IsGiuga[n_Integer] := Module[{factors},
factors = FactorInteger[n];
AllTrue[factors, Function[{f},
Mod[Quotient[n, f[[1]]] - 1, f[[1]]] == 0 && f[[1]] != n]]
]
GetGiuga[N_Integer] := Module[{giugaNumbers = {}, i = 4},
While[Length[giugaNumbers] < N,
If[IsGiuga[i], AppendTo[giugaNumbers, i]];
i++
];
giugaNumbers
]
Print[GetGiuga[4]]
</syntaxhighlight>
{{out}}
<pre>
{30, 858, 1722, 66198}
</pre>
=={{header|Maxima}}==
Line 973 ⟶ 1,073:
<pre>The first 4 Giuga numbers are: 30 858 1722 66198
</pre>
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
is_giuga(n) = {
my(factors = factor(n));
for (i = 1, #factors[,1],
if (factors[i,1] == n, return(0));
if (Mod(n \ factors[i,1] - 1, factors[i,1]) != 0, return(0));
);
return(1);
}
get_giuga(N) = {
my(giugaNumbers = [], i = 4);
while(#giugaNumbers < N,
if (is_giuga(i), giugaNumbers = concat(giugaNumbers, i));
i++;
);
giugaNumbers
}
print(get_giuga(4))
</syntaxhighlight>
{{out}}
<pre>
[30, 858, 1722, 66198]
</pre>
=={{header|Pascal}}==
| |||