Giuga numbers: Difference between revisions
→{{header|jq}}
(Added Algol W) |
|||
| (14 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>
Line 472 ⟶ 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}}==
Line 747 ⟶ 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 804 ⟶ 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 842 ⟶ 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,648 ⟶ 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,702 ⟶ 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,712 ⟶ 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,783 ⟶ 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
| |||