Giuga numbers

Definition

A Giuga number is a composite number n which is such that each of its distinct prime factors f divide (n/f - 1) exactly.

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

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:

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:

Wren

Library: Wren-math

Library: Wren-seq

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