Giuga numbers
A Giuga number is a composite number n which is such that each of its distinct prime factors f divide (n/f - 1) exactly.
- Definition
All known Giuga numbers are even though it is not known for certain that there are no odd examples.
- Example
30 is a Giuga number because its distinct prime factors are 2, 3 and 5 and:
- 30/2 - 1 = 14 is divisible by 2
- 30/3 - 1 = 9 is divisible by 3
- 30/5 - 1 = 5 is divisible by 5
- Task
Determine and show here the first four Giuga numbers.
- Stretch
Determine the fifth Giuga number and any more you have the patience for.
- References
FreeBASIC
<lang freebasic>Function isGiuga(m As Uinteger) As Boolean
Dim As Uinteger n = m
Dim As Uinteger 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</lang>
- Output:
The first 4 Giuga numbers are: 30 858 1722 66198
Go
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 around 2 hours 40 minutes. <lang go>package main
import (
"fmt" "rcu"
)
func main() {
const limit = 5
var giuga []int
for n := 4; len(giuga) < limit; n += 2 {
factors := rcu.PrimeFactors(n)
if len(factors) > 2 {
isSquareFree := true
for i := 1; i < len(factors); i++ {
if factors[i] == factors[i-1] {
isSquareFree = false
break
}
}
if isSquareFree {
isGiuga := true
for _, f := range factors {
if (n/f-1)%f != 0 {
isGiuga = false
break
}
}
if isGiuga {
giuga = append(giuga, n)
}
}
}
}
fmt.Println("The first", limit, "Giuga numbers are:")
fmt.Println(giuga)
}</lang>
- Output:
The first 5 Giuga numbers are: [30 858 1722 66198 2214408306]
J
We can brute force this task building a test for giuga numbers and checking the first hundred thousand integers:
<lang J>giguaP=: {{ (1<y)*(-.1 p:y)**/(=<.) y ((_1+%)%]) q: y }}"0</lang>
<lang J> 1+I.giguaP 1+i.1e5 30 858 1722 66198</lang>
These numbers have some interesting properties but there's an issue with guaranteeing correctness of more sophisticated approaches.
Julia
<lang ruby>using Primes
isGiuga(n) = all(f -> f != n && rem(n ÷ f - 1, f) == 0, factor(Vector, n))
function getGiuga(N)
gcount = 0
for i in 4:typemax(Int)
if isGiuga(i)
println(i)
(gcount += 1) >= N && break
end
end
end
getGiuga(4)
</lang>
- Output:
30 858 1722 66198
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Giuga_numbers use warnings; use ntheory qw( factor forcomposites ); use List::Util qw( all );
forcomposites
{
my $n = $_;
all { ($n / $_ - 1) % $_ == 0 } factor $n and print "$n\n";
} 4, 67000;</lang>
- Output:
30 858 1722 66198
Phix
with javascript_semantics constant limit = 4 sequence giuga = {} integer n = 4 while length(giuga)<limit do sequence pf = prime_factors(n) for f in pf do if remainder(n/f-1,f) then pf={} exit end if end for if length(pf) then giuga &= n end if n += 2 end while printf(1,"The first %d Giuga numbers are: %v\n",{limit,giuga})
- Output:
The first 4 Giuga numbers are: {30,858,1722,66198}
Python
<lang python>#!/usr/bin/python
from math import sqrt
def isGiuga(m):
n = m
f = 2
l = sqrt(n)
while True:
if n % f == 0:
if ((m / f) - 1) % f != 0:
return False
n /= f
if f > n:
return True
else:
f += 1
if f > l:
return False
if __name__ == '__main__':
n = 3
c = 0
print("The first 4 Giuga numbers are: ")
while c < 4:
if isGiuga(n):
c += 1
print(n)
n += 1</lang>
Raku
<lang perl6>my @primes = (3..60).grep: &is-prime;
print 'First four Giuga numbers: ';
put sort flat (2..4).map: -> $c {
@primes.combinations($c).map: {
my $n = [×] 2,|$_;
$n if all .map: { ($n / $_ - 1) %% $_ };
}
}</lang>
- Output:
First 4 Giuga numbers: 30 858 1722 66198
Wren
Simple brute force but assumes all Giuga numbers will be even, must be square-free and can't be semi-prime.
Takes only about 0.1 seconds to find the first four Giuga numbers but finding the fifth would take many hours using this approach, so I haven't bothered. Hopefully, someone can come up with a better method. <lang ecmascript>import "./math" for Int import "./seq" for Lst
var limit = 4 var giuga = [] var n = 4 while (giuga.count < limit) {
var factors = Int.primeFactors(n)
var c = factors.count
if (c > 2) {
var factors2 = Lst.prune(factors)
if (c == factors2.count && factors2.all { |f| (n/f - 1) % f == 0 }) {
giuga.add(n)
}
}
n = n + 2
} System.print("The first %(limit) Giuga numbers are:") System.print(giuga)</lang>
- Output:
The first 4 Giuga numbers are: [30, 858, 1722, 66198]
XPL0
<lang XPL0>func Giuga(N0); \Return 'true' if Giuga number int N0; int N, F, Q1, Q2, L; [N:= N0; F:= 2; L:= sqrt(N); loop [Q1:= N/F;
if rem(0) = 0 then \found a prime factor
[Q2:= N0/F;
if rem((Q2-1)/F) # 0 then return false;
N:= Q1;
if F>N then quit;
]
else [F:= F+1;
if F>L then return false;
];
];
return true; ];
int N, C; [N:= 3; C:= 0; loop [if Giuga(N) then
[IntOut(0, N); ChOut(0, ^ );
C:= C+1;
if C >= 4 then quit;
];
N:= N+1;
];
]</lang>
- Output:
30 858 1722 66198