Giuga numbers: Difference between revisions
→{{header|jq}}
m (Added language identifier.) |
|||
| (20 intermediate revisions by 8 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>
=={{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 #
Line 71 ⟶ 102:
# 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 :=
f count +:= 1;
v OVERAB f
FI
IF is giuga THEN
g count +:=
print( ( " ",
FI
FI
OD
Line 113 ⟶ 132:
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}}==
Line 434 ⟶ 501:
n = 6: 24423128562 2214408306
</pre>
=={{header|Delphi}}==
{{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}}==
Line 670 ⟶ 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 727 ⟶ 953:
24423128562 (elapsed: 432.06500005722046)
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>
Line 765 ⟶ 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}}==
Line 1,375 ⟶ 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}}==
Line 1,508 ⟶ 1,909:
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>
Line 1,562 ⟶ 1,987:
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>
Line 1,572 ⟶ 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.
<syntaxhighlight lang="
var inc = [4, 2, 4, 2, 4, 6, 2, 6]
Line 1,643 ⟶ 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.
<syntaxhighlight lang="
import "./rat" for Rat
| |||