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
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]