Giuga numbers: Difference between revisions
→{{header|jq}}
(Added second C++ solution) |
|||
| (44 intermediate revisions by 20 users not shown) | |||
Line 1:
{{
;Definition
Line 25:
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">
F isGiuga(m)
V n = m
V f = 2
V l = sqrt(n)
L
I n % f == 0
I ((m I/ f) - 1) % f != 0
R 0B
n I/= f
I f > n
R 1B
E
f++
I f > l
R 0B
V n = 3
V c = 0
print(‘The first 4 Giuga numbers are:’)
L c < 4
I isGiuga(n)
c++
print(n)
n++
</syntaxhighlight>
{{out}}
<pre>
The first 4 Giuga numbers are:
30
858
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>
=={{header|ALGOL 68}}==
As with the Wren and other samples, assumes the first four Giuga numbers are even and also uses the fact that no prime squared can be a divisor of a Giuga number.
<syntaxhighlight lang="algol68">
BEGIN # find some Giuga numbers, composites n such that all their distinct #
# prime factors f exactly divide ( n / f ) - 1 #
# find the first four Giuga numbers #
# 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 #
INT g count := 0;
FOR n FROM 2 BY 4 WHILE g count < 4 DO # assume the numbers are all even #
INT v := n OVER 2;
BOOL is giuga := TRUE;
INT f count := 1;
FOR f FROM 3 BY 2 WHILE f <= v AND is giuga DO
IF v MOD f = 0 THEN
# have a prime factor #
f count +:= 1;
is giuga := ( ( n OVER f ) - 1 ) MOD f = 0;
v OVERAB f
FI
OD;
IF is giuga THEN
# n is still a candidate, check it is not prime #
IF f count > 1 THEN
g count +:= 1;
print( ( " ", whole( n, 0 ) ) )
FI
FI
OD
END
</syntaxhighlight>
{{out}}
<pre>
30 858 1722 66198
</pre>
=={{header|ALGOL W}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="algolw">
begin % find some Giuga numbers, composites n such that all their distinct %
% prime factors f exactly divide ( n / f ) - 1 %
% find the first four Giuga numbers %
% 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 %
integer gCount, n;
gCount := 0;
n := -2;
while begin n := n + 4;
gCount < 4
end
do begin % assume the numbers are all even %
integer v, f, fCount;
logical isGiuga;
v := n div 2;
isGiuga := TRUE;
fCount := 1;
f := 1;
while begin f := f + 2;
f <= v and isGiuga
end
do begin
if v rem f = 0 then begin
% have a prime factor %
fCount := fCount + 1;
isGiuga := ( ( n div f ) - 1 ) rem f = 0;
v := v div f
end if_v_rem_f_eq_0
end while_f_le_v_and_isGiuga ;
if isGiuga then begin
% n is still a candidate, check it is not prime %
if fCount > 1 then begin
gCount := gCount + 1;
writeon( i_w := 1, s_w := 0, " ", n )
end if_fCount_gt_1
end if_isGiuga
end while_gCount_lt_4
end.
</syntaxhighlight>
{{out}}
Same as Algol 68
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">giuga?: function [n]->
and? -> not? prime? n
-> every? factors.prime n 'f
-> zero? (dec n/f) % f
print.lines select.first:4 1..∞ => giuga?</syntaxhighlight>
{{out}}
<pre>30
858
1722
66198</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f GIUGA_NUMBER.AWK
BEGIN {
n = 3
stop = 4
printf("Giuga numbers 1-%d:",stop)
while (count < stop) {
if (is_giuga(n)) {
count++
printf(" %d",n)
}
n++
}
printf("\n")
exit(0)
}
function is_giuga(m, f,l,n) {
n = m
f = 2
l = sqrt(n)
while (1) {
if (n % f == 0) {
if (((m / f) - 1) % f != 0) { return(0) }
n /= f
if (f > n) { return(1) }
}
else {
if (++f > l) { return(0) }
}
}
}
</syntaxhighlight>
{{out}}
<pre>
Giuga numbers 1-4: 30 858 1722 66198
</pre>
=={{header|BASIC}}==
==={{header|BASIC256}}===
<syntaxhighlight lang="vb">n = 3
c = 0
limit = 4
print "The first"; limit; " Giuga numbers are: ";
do
if isGiuga(N) then c += 1: print n; " ";
n += 1
until c = limit
end
function isGiuga(m)
n = m
f = 2
l = sqr(n)
while True
if n mod f = 0 then
if ((m / f) - 1) mod f <> 0 then return false
n /= f
if f > n then return true
else
f += 1
if f > l then return false
end if
end while
end function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="vbnet">Function isGiuga(m As Uinteger) As Boolean
Dim As Uinteger n = m, f = 2, l = Sqr(n)
Do
If n Mod f = 0 Then
If ((m / f) - 1) Mod f <> 0 Then Return False
n /= f
If f > n Then Return True
Else
f += 1
If f > l Then Return False
End If
Loop
End Function
Dim As Uinteger n = 3, c = 0, limit = 4
Print "The first "; limit; " Giuga numbers are: ";
Do
If isGiuga(n) Then c += 1: Print n; " ";
n += 1
Loop Until c = limit</syntaxhighlight>
{{out}}
<pre>The first 4 Giuga numbers are: 30 858 1722 66198</pre>
==={{header|Gambas}}===
<syntaxhighlight lang="vbnet">Public Sub Main()
Dim n As Integer = 3, c As Integer = 0, limit As Integer = 4
Print "The first "; limit; " Giuga numbers are: ";
Do
If isGiuga(n) Then
c += 1
Print n; " ";
Endif
n += 1
Loop Until c = limit
End
Function isGiuga(m As Integer) As Boolean
Dim n As Integer = m, f As Integer = 2, l As Integer = Sqr(n)
Do
If n Mod f = 0 Then
Dim q As Integer = (m / f)
If (q - 1) Mod f <> 0 Then Return False
n /= f
If f > n Then Return True
Else
f += 1
If f > l Then Return False
End If
Loop
End Function</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|PureBasic}}===
<syntaxhighlight lang="vb">Procedure.b isGiuga(m.i)
Define.i n = m, f = 2, l = Sqr(n)
While #True
If Mod(n, f) = 0:
If Mod(((m / f) - 1), f) <> 0: ProcedureReturn #False: EndIf
n = n / f
If f > n: ProcedureReturn #True: EndIf
Else
f + 1
If f > l: ProcedureReturn #False: EndIf
EndIf
Wend
EndProcedure
OpenConsole()
Define.i n = 3, c = 0, limit = 4
Print("The first " + Str(limit) + " Giuga numbers are: ")
Repeat
If isGiuga(N):
c + 1
Print(Str(n) + " ")
EndIf
n + 1
Until c = limit
Input()
CloseConsole()</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|C++}}==
===Brute force===
Based on the Go solution. Takes 26 minutes on my system (Intel Core i5 3.2GHz).
<
// Assumes n is even with exactly one factor of 2.
Line 60 ⟶ 389:
}
}
}</
{{out}}
Line 75 ⟶ 404:
{{libheader|Boost}}
{{trans|Wren}}
<
#include <algorithm>
Line 163 ⟶ 492:
for (uint64_t n = 3; n < 7; ++n)
giuga_numbers(n);
}</
{{out}}
Line 173 ⟶ 502:
</pre>
=={{header|
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
function IsGiugaNumber(N: integer): boolean;
var IA: TIntegerDynArray;
var I,V: integer;
begin
Result:=False;
if IsPrime(N) then exit;
GetPrimeFactors(N,IA);
for I:=0 to High(IA) do
begin
V:=N div IA[I] - 1;
if (V mod IA[I])<>0 then exit;
end;
Result:=True;
end;
procedure ShowGiugaNumbers(Memo: TMemo);
var I,Cnt: integer;
begin
Cnt:=0;
for I:=4 to High(integer) do
if IsGiugaNumber(I) then
begin
Inc(Cnt);
Memo.Lines.Add(IntToStr(I));
if Cnt>=4 then break;
end;
end;
</syntaxhighlight>
{{out}}
<pre>
30
858
1722
66198
Elapsed Time: 4.991 Sec.
</pre>
=={{header|EasyLang}}==
{{trans|Python}}
<syntaxhighlight lang="easylang">
func giuga m .
n = m
for f = 2 to sqrt n
while n mod f = 0
if (m div f - 1) mod f <> 0
return 0
.
n = n div f
if f > n
return 1
.
.
.
.
n = 3
while cnt < 4
if giuga n = 1
cnt += 1
print n
.
n += 1
.
</syntaxhighlight>
=={{header|Euler}}==
Uses the C style for loop procedure from the [[Sieve of Eratosthenes]] task
'''begin'''
'''new''' for; '''new''' n; '''new''' gCount;
for <- ` '''formal''' init; '''formal''' test; '''formal''' incr; '''formal''' body;
'''begin'''
'''label''' again;
init;
again: '''if''' test '''then''' '''begin''' body; incr; '''goto''' again '''end''' '''else''' 0
'''end'''
'
;
gCount <- 0;
for( ` n <- 2 ', ` gCount < 4 ', ` n <- n + 4 '
, ` '''begin'''
'''new''' v; '''new''' f; '''new''' isGiuga; '''new''' fCount;
v <- n % 2;
isGiuga <- '''true''';
fCount <- 1;
for( ` f <- 3 ', ` f <= v '''and''' isGiuga ', ` f <- f + 2 '
, ` '''if''' v '''mod''' f = 0 '''then''' '''begin'''
fCount <- fCount + 1;
isGiuga <- [ [ n % f ] - 1 ] '''mod''' f = 0;
v <- v % f
'''end''' '''else''' 0
'
);
'''if''' isGiuga '''then''' '''begin'''
'''if''' fCount > 1 '''then''' '''begin'''
gCount <- gCount + 1;
'''out''' n
'''end''' '''else''' 0
'''end''' '''else''' 0
'''end'''
'
)
'''end''' $
=={{header|Go}}==
{{trans|Wren}}
I thought I'd see how long it would take to 'brute force' the fifth Giuga number and the answer (without using parallelization, Core i7) is about 1 hour 38 minutes.
<
import "fmt"
Line 274 ⟶ 693:
fmt.Println("The first", limit, "Giuga numbers are:")
fmt.Println(giuga)
}</
{{out}}
Line 280 ⟶ 699:
The first 5 Giuga numbers are:
[30 858 1722 66198 2214408306]
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">
--for obvious theoretical reasons the smallest divisor of a number bare 1
--must be prime
primeFactors :: Int -> [Int]
primeFactors n = snd $ until ( (== 1) . fst ) step (n , [] )
where
step :: (Int , [Int] ) -> (Int , [Int] )
step (n , li) = ( div n h , li ++ [h] )
where
h :: Int
h = head $ tail $ divisors n --leave out 1
divisors :: Int -> [Int]
divisors n = [d | d <- [1 .. n] , mod n d == 0]
isGiuga :: Int -> Bool
isGiuga n = (divisors n /= [1,n]) && all (\i -> mod ( div n i - 1 ) i == 0 )
(primeFactors n)
solution :: [Int]
solution = take 4 $ filter isGiuga [2..]</syntaxhighlight>
{{out}}
<pre>
[30,858,1722,66198]
</pre>
Line 286 ⟶ 732:
We can brute force this task building a test for giuga numbers and checking the first hundred thousand integers (which takes a small fraction of a second):
<
<
30 858 1722 66198</
These numbers have some interesting properties but there's an issue with guaranteeing correctness of more sophisticated approaches. That said, here's a translation of the pari/gp implementation on the talk page:
<
giuga=: {{
Line 331 ⟶ 777:
end.
r
}}</
Example use:<
giuga 2
Line 344 ⟶ 790:
66198
giuga 6
24423128562 2214408306</
=={{header|Java}}==
Algorithm uses the mathematical facts that a Giuga number must be square-free and cannot be a semi-prime.
It does not assume that a Giuga number is even, and exhaustively tests all possible candidates
up to approximately 147,000 in around 20 milliseconds.
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public final class GiugaNumbers {
public static void main(String[] aArgs) {
primes = List.of( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 );
List<Integer> primeCounts = List.of( 3, 4, 5 );
for ( int primeCount : primeCounts ) {
primeFactors = new ArrayList<Integer>(Collections.nCopies(primeCount, 0));
combinations(primeCount, 0, 0);
}
Collections.sort(results);
System.out.println("Found Giuga numbers: " + results);
}
private static void checkIfGiugaNumber(List<Integer> aPrimeFactors) {
final int product = aPrimeFactors.stream().reduce(1, Math::multiplyExact);
for ( int factor : aPrimeFactors ) {
final int divisor = factor * factor;
if ( ( product - factor ) % divisor != 0 ) {
return;
}
}
results.add(product);
}
private static void combinations(int aPrimeCount, int aIndex, int aLevel) {
if ( aLevel == aPrimeCount ) {
checkIfGiugaNumber(primeFactors);
return;
}
for ( int i = aIndex; i < primes.size(); i++ ) {
primeFactors.set(aLevel, primes.get(i));
combinations(aPrimeCount, i + 1, aLevel + 1);
}
}
private static List<Integer> primes;
private static List<Integer> primeFactors;
private static List<Integer> results = new ArrayList<Integer>();
}
</syntaxhighlight>
{{ out }}
<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>
=={{header|Julia}}==
<
isGiuga(n) = all(f -> f != n && rem(n ÷ f - 1, f) == 0, factor(Vector, n))
Line 362 ⟶ 914:
getGiuga(4)
</
<pre>
30
Line 370 ⟶ 922:
</pre>
=== Ad hoc faster version ===
<
function getgiugas(numberwanted, verbose = true)
Line 392 ⟶ 944:
@time getgiugas(2, false)
@time getgiugas(6)
</
<pre>
30 (elapsed: 0.0)
Line 402 ⟶ 954:
432.066249 seconds (235 allocations: 12.523 KiB)
</pre>
=={{header|Lua}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="lua">
do --[[ find the first 4 Giuga numbers, composites n such that all their
distinct prime factors f exactly divide ( n / f ) - 1
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
]]
local gCount, n = 0, 2
while gCount < 4 do
n = n + 4 -- assume the numbers are all even
local fCount, f, isGiuga, v = 1, 1, true, math.floor( n / 2 )
while f <= ( v - 2 ) and isGiuga do
f = f + 2
if v % f == 0 then -- have a prime factor
fCount = fCount + 1
isGiuga = ( math.floor( n / f ) - 1 ) % f == 0
v = math.floor( v / f )
end
end
if isGiuga then -- n is still a candidate, check it is not prime
if fCount > 1 then
gCount = gCount + 1
io.write( " ", n )
end
end
end
end</syntaxhighlight>
{{out}}
<pre>
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}}==
<syntaxhighlight lang="maxima">
/* Predicate function that checks wether an integer is a Giuga number or not */
giugap(n):=if not primep(n) then block(ifactors(n),map(lambda([x],mod((n/x)-1,x)=0),map(first,%%)),
if length(unique(%%))=1 and apply(lhs,unique(%%))=0 then true)$
/* Function that returns a list of the first len Giuga integers */
giuga_count(len):=block(
[i:1,count:0,result:[]],
while count<len do (if giugap(i) then (result:endcons(i,result),count:count+1),i:i+1),
result)$
/* Test case */
giuga_count(4);
</syntaxhighlight>
{{out}}
<pre>
[30,858,1722,66198]
</pre>
=={{header|Nim}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="Nim">import std/math
func isGiuga(m: Natural): bool =
var n = m
var f = 2
var l = int(sqrt(n.toFloat))
while true:
if n mod f == 0:
if (m div f - 1) mod f != 0:
return false
n = n div f
if f > n:
return true
else:
inc f
if f > l:
return false
var n = 3
var c = 0
const Limit = 4
stdout.write "The first ", Limit, " Giuga numbers are: "
while true:
if n.isGiuga:
inc c
stdout.write n, " "
if c == Limit: break
inc n
echo()
</syntaxhighlight>
{{out}}
<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}}==
Line 408 ⟶ 1,109:
That means always factors 2,3 and minimum one of 5,7,11.<br>
<br>
<
{$IFDEF FPC}
Line 636 ⟶ 1,337:
writeln;
writeln(OutPots(@PrimeDecomp,n));
end.</
{{out|@home AMD 5600G ( 4,4 Ghz ) fpc3.2.2 -O4 -Xs}}
<pre>
Line 654 ⟶ 1,355:
Generating recursive squarefree numbers of ascending primes and check those numbers.<BR>
2*3 are set fixed. 2*3*5 followed 2*3*7 than 2*3*11. Therefor the results are unsorted.
<
{
30 = 2 * 3 * 5.
Line 852 ⟶ 1,553:
writeln;
end.
</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
Line 897 ⟶ 1,598:
=={{header|Perl}}==
<
use strict; # https://rosettacode.org/wiki/Giuga_numbers
Line 908 ⟶ 1,609:
my $n = $_;
all { ($n / $_ - 1) % $_ == 0 } factor $n and print "$n\n";
} 4, 67000;</
{{out}}
<pre>
Line 918 ⟶ 1,619:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
Line 932 ⟶ 1,633:
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first %d Giuga numbers are: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">giuga</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 939 ⟶ 1,640:
===Faster version===
{{trans|Wren}}
<!--<
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\Giuga_number.exw
Line 995 ⟶ 1,696:
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">({</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span><span style="color: #000000;">giuga</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 1,004 ⟶ 1,705:
</pre>
You can (almost) push things a little further on 64-bit:
<!--<
<span style="color: #008080;">if</span> <span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">64</span> <span style="color: #008080;">then</span> <span style="color: #000000;">giuga</span><span style="color: #0000FF;">(</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</
and get
<pre>
Line 1,012 ⟶ 1,713:
</pre>
It took about 3 minutes for those to show, but then carried on in a doomed quest for an hour before I killed it.
=={{header|PL/M}}==
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)
Only finds 3 Giuga numbers as the fourth is larger than 65535, the largest integer supported by the 8080 PL/M compiler.
<syntaxhighlight lang="plm">
100H: /* FIND SOME GIUGA NUMBERS, COMPOSITES N SUCH THAT ALL THEIR DISTINCT */
/* PRIME FACTORS F EXACTLY DIVIDE ( N / F ) - 1 */
/* CP/M BDOS SYSTEM CALL AND I/O ROUTINES */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PR$NL: PROCEDURE; CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END;
PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR$STRING( .N$STR( W ) );
END PR$NUMBER;
/* TASK */
/* FIND THE FIRST THREE GIUGA NUMBERS (THE FOURTH IS > 65535) */
/* EACH PRIME FACTOR CAN ONLY APPEAR ONCE, E.G.,: FOR 2: */
/* (( N / 2 ) - 1) MOD 2 = 0 => N / 2 IS ODD => N NOT DIVISIBLE BY 4 */
/* SIMILARLY FOR OTHER PRIMES */
DECLARE ( N, V, FCOUNT, F ) ADDRESS;
DECLARE IS$GIUGA BYTE;
N = 2;
DO WHILE N < 65000; /* ASSUME THE NUMEBRS ARE ALL EVEN */
V = N / 2;
IS$GIUGA = 1;
FCOUNT = 1;
F = 1;
DO WHILE ( F := F + 2 ) <= V AND IS$GIUGA;
IF V MOD F = 0 THEN DO;
/* HAVE A PRIME FACTOR */
FCOUNT = FCOUNT + 1;
IS$GIUGA = ( ( N / F ) - 1 ) MOD F = 0;
V = V / F;
END;
END;
IF IS$GIUGA THEN DO;
IF FCOUNT > 1 THEN DO;
/* N IS NOT PRIME, SO IS GIUGA */
CALL PR$CHAR( ' ' );CALL PR$NUMBER( N );
END;
END;
N = N + 4;
END;
EOF
</syntaxhighlight>
{{out}}
<pre>
30 858 1722
</pre>
=={{header|Python}}==
{{trans|FreeBASIC}}
<
from math import sqrt
Line 1,044 ⟶ 1,808:
c += 1
print(n)
n += 1</
=={{header|Quackery}}==
<code>dpfs</code> is Distinct Prime Factors.
<syntaxhighlight lang="Quackery"> [ [] swap
dup times
[ dup i^ 2 + /mod
0 = if
[ nip dip
[ i^ 2 + join ]
[ dup i^ 2 + /mod
0 = iff
nip again ] ]
drop
dup 1 = if conclude ]
drop ] is dpfs ( n --> [ )
[ dup dpfs
dup size 2 < iff
[ 2drop false ]
done
true unrot
witheach
[ 2dup / 1 -
swap mod 0 != if
[ dip not
conclude ] ]
drop ] is giuga ( n --> b )
[] 0
[ 1+ dup giuga if
[ tuck join swap ]
over size 4 = until ]
drop
echo</syntaxhighlight>
{{out}}
<pre>[ 30 858 1722 66198 ]</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku"
print 'First four Giuga numbers: ';
Line 1,058 ⟶ 1,861:
$n if all .map: { ($n / $_ - 1) %% $_ };
}
}</
{{out}}
<pre>First 4 Giuga numbers: 30 858 1722 66198</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
see "working..." + nl
see "The first 4 Giuga numbers are:" + nl
load "stdlibcore.ring"
Comp = []
num = 0
n = 1
while true
n++
if not isPrime(n)
Comp = []
for p = 1 to n
if isPrime(p) AND (n % p = 0)
add(Comp,p)
ok
next
flag = 1
for ind = 1 to len(Comp)
f = Comp[ind]
res = (n/f)- 1
if res % f != 0
flag = 0
exit
ok
next
if flag = 1
see "" + n + " "
num++
ok
if num = 4
exit
ok
ok
end
see nl + "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
working...
The first 4 Giuga numbers are:
30 858 1722 66198
done...
</pre>
=={{header|RPL}}==
{{works with|HP|49}}
≪ DUP → n
≪ FACTORS 1 SF
1 OVER SIZE '''FOR''' j
DUP j GET
n OVER / 1 -
'''IF''' SWAP MOD '''THEN''' 1 CF '''END'''
2 '''STEP''' DROP
1 FS?
≫ ≫ '<span style="color:blue">GIUGA?</span>' STO
≪ { } 4
'''WHILE''' OVER SIZE 4 < '''REPEAT'''
'''IF''' DUP <span style="color:blue">GIUGA?</span> '''THEN''' LOOK SWAP OVER + SWAP '''END'''
2 +
'''END''' DROP
≫ '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: {30 858 1722 66198}
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby" line>require 'prime'
giuga = (1..).lazy.select do |n|
pd = n.prime_division
pd.sum{|_, d| d} > 1 && #composite
pd.all?{|f, _| (n/f - 1) % f == 0}
end
p giuga.take(4).to_a
</syntaxhighlight>
{{out}}
<pre>[30, 858, 1722, 66198]
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
use prime_tools ;
fn prime_decomposition( mut number : u32) -> Vec<u32> {
let mut divisors : Vec<u32> = Vec::new( ) ;
let mut divisor : u32 = 2 ;
while number != 1 {
if number % divisor == 0 {
divisors.push( divisor ) ;
number /= divisor ;
}
else {
divisor += 1 ;
}
}
divisors
}
fn is_giuga( num : u32 ) -> bool {
let prime_factors : Vec<u32> = prime_decomposition( num ) ;
! prime_tools::is_u32_prime( num ) &&
prime_factors.into_iter( ).all( |n : u32| (num/n -1) % n == 0 )
}
fn main() {
let mut giuga_numbers : Vec<u32> = Vec::new( ) ;
let mut num : u32 = 2 ;
while giuga_numbers.len( ) != 4 {
if is_giuga( num ) {
giuga_numbers.push( num ) ;
}
num += 1 ;
}
println!("{:?}" , giuga_numbers ) ;
}</syntaxhighlight>
{{out}}
<pre>
[30, 858, 1722, 66198]
</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
object GiugaNumbers {
private var results: List[Int] = List()
def main(args: Array[String]): Unit = {
val primes: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59)
val primeCounts: List[Int] = List(3, 4, 5)
for (primeCount <- primeCounts) {
var primeFactors: List[Int] = List.fill(primeCount)(0)
combinations(primes, primeCount, 0, 0, primeFactors)
}
val sortedResults = results.sorted
println(s"Found Giuga numbers: $sortedResults")
}
private def checkIfGiugaNumber(primeFactors: List[Int]): Unit = {
val product: Int = primeFactors.reduce(Math.multiplyExact)
for (factor <- primeFactors) {
val divisor: Int = factor * factor
if ((product - factor) % divisor != 0) {
return
}
}
results :+= product
}
private def combinations(primes: List[Int], primeCount: Int, index: Int, level: Int, primeFactors: List[Int]): Unit = {
if (level == primeCount) {
checkIfGiugaNumber(primeFactors)
return
}
for (i <- index until primes.length) {
val updatedPrimeFactors = primeFactors.updated(level, primes(i))
combinations(primes, primeCount, i + 1, level + 1, updatedPrimeFactors)
}
}
}
</syntaxhighlight>
{{out}}
<pre>
Found Giuga numbers: List(30, 858, 1722, 66198)
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">4..Inf `by` 2 -> lazy.grep {|n|
n.factor.all {|p| p `divides` (n/p - 1) }
}.first(4).say</syntaxhighlight>
{{out}}
<pre>
[30, 858, 1722, 66198]
</pre>
=={{header|Wren}}==
Line 1,067 ⟶ 2,055:
Takes only about 0.05 seconds to find the first four Giuga numbers but finding the fifth would take many hours using this approach, so I haven't bothered.
<
var inc = [4, 2, 4, 2, 4, 6, 2, 6]
Line 1,126 ⟶ 2,114:
}
System.print("The first %(limit) Giuga numbers are:")
System.print(giuga)</
{{out}}
Line 1,138 ⟶ 2,126:
{{libheader|Wren-rat}}
This is a translation of the very fast Pari-GP code in the talk page. Only takes 0.015 seconds to find the first six Giuga numbers.
<
import "./rat" for Rat
Line 1,181 ⟶ 2,169:
giuga.call(n)
System.print()
}</
{{out}}
Line 1,201 ⟶ 2,189:
=={{header|XPL0}}==
<
int N0;
int N, F, Q1, Q2, L;
Line 1,228 ⟶ 2,216:
N:= N+1;
];
]</
{{out}}
| |||