Giuga Numbers in Java
The giuga number is a composite number N for which each of its prime distinct divisors P will divide (N/P – 1) exactly.
To date, there are only 13 giuga numbers that are known. The sequence of giuga numbers is given below.
30, 858, 1722, 66198, 2214408306, 24423128562, ...
From the above sequence, we can easily observe that all the giuga numbers are even. All the known giuga numbers are even numbers, but there may or may not be any odd giuga numbers known in the future.
Given a number N, we need to determine if the given number is a giuga number. If it is a giuga number, then return true; else, return false.
Example 1:
Input: N = 30
Output: true
Explanation:
The number 30 is a giuga number as it is a composite number where every prime divisor P {2, 3, 5} will divide (N/P – 1).
2 will divide (30/ 2 – 1) = 14
3 will divide (30/ 3 – 1) = 9
5 will divide (30/5 – 1) = 5
Example 2:
Input: N = 858
Output: true
Explanation:
The number 858 is a giuga number as it is a composite number where every prime divisor P {2, 3, 11, 13} will divide (N/P – 1).
2 will divide (858/ 2 – 1) = 428
3 will divide (858/ 3 – 1) = 285
11 will divide (858/11 – 1) = 77
13 will divide (858/13 – 1) = 65
Example 3:
Input: N = 21
Output: false
Explanation:
The number 21 is not a giuga number as (21 / 7 – 1) = 2 will not divide 7.
Example 4:
Input: N = 1722
Output: true
Explanation:
The number 1722 is a giuga number as it is a composite number where every prime divisor P {2, 3, 7, 41} will divide (N/P – 1).
2 will divide (1722/ 2 – 1) = 860
3 will divide (1722/ 3 – 1) = 573
7 will divide (1722/7 – 1) = 245
41 will divide (1722/41 – 1) = 41
Check for Giuga Number
In this program, we will check if the given number is a giuga number. The approach is to check if the given number N is composite. If it is not a composite number, then return false.
If the given number is composite, then find all its prime divisors. For each of its prime divisors P, Check if the (N/P – 1) is valid or not.
FileName: GiugaNumber.java
// Java program to check if the given number is giuga number public class GiugaNumber{ // method to check if the given number is composite static boolean isCompositeNumber(int n) { if (n <= 1) return false; if (n <= 3) return false; if (n % 2 == 0 || n % 3 == 0) return true; for (int k = 5; k * k <= n; k = k + 6) if (n % k == 0 || n % (k + 2) == 0) return true; return false; } // method to check for giuga number static boolean isGiugaNumber(int n) { // to be a giuga number // first, it should be a composite number if (!(isCompositeNumber(n))) return false; int N = n; while (n % 2 == 0) { if ((N / 2 - 1) % 2 != 0) return false; n = n / 2; } for(int i = 3; i <= Math.sqrt(n); i = i + 2) { while (n % i == 0) { if ((N / i - 1) % i != 0) return false; n = n / i; } } //It will handle the condition // when n is a prime number less than 2 if (n > 2) if ((N / n - 1) % n != 0) return false; return true; } // main method public static void main(String[] args) { int n = 858; //calling the method if (isGiugaNumber(n)) { System.out.println(n +" is a Giuga Number"); } else { System.out.println(n +" is not a Giuga Number"); } n = 23; //calling the method if (isGiugaNumber(n)) { System.out.println(n +" is a Giuga Number"); } else { System.out.println(n +" is not a Giuga Number"); } n = 1722; //calling the method if (isGiugaNumber(n)) { System.out.println(n +" is a Giuga Number"); } else { System.out.println(n +" is not a Giuga Number"); } } }
Output:
858 is a Giuga Number 23 is not a Giuga Number 1722 is a Giuga Number
Sequence of Giuga Numbers
In this program, we will print the sequence of the first four giuga numbers. The basic approach for the program is based on the fact that the giuga numbers cannot be square and should not be semi-prime. It also does not assume that the giuga number must be even and checks for all the possibilities.
FileName: GiugaNumbersSequence.java
// Java program to print a sequence of the first four giuga numbers import java.util.Collections; import java.util.List; import java.util.ArrayList; public class GiugaNumbersSequence { //stores the prime numbers static List<Integer> primeNumbers; //stores the prime divisors of a number static List<Integer> primeDivisors; //stores the giuga numbers static List<Integer> answer = new ArrayList<>(); // method to check for giuga numbers static void isGiugaNumber(List<Integer> aPrimeDivisor) { int multiply = aPrimeDivisor.stream().reduce(1, Math::multiplyExact); for ( int divisor : aPrimeDivisor ) { int aDivisor = divisor * divisor; if ( ( multiply - divisor ) % aDivisor != 0 ) { return; } } answer.add(multiply); } // creates combinations of numbers to check for giuga numbers static void combinations(int primeNumberCount, int index, int level) { if ( level == primeNumberCount ) { isGiugaNumber(primeDivisors); return; } for (int i = index; i < primeNumbers.size(); i++ ) { primeDivisors.set(level, primeNumbers.get(i)); combinations(primeNumberCount, i + 1, level + 1); } } // main method public static void main(String[] args) { primeNumbers = List.of(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 ); List<Integer> primeNumberCounts = List.of( 3, 4, 5 ); for ( int primeNumberCount : primeNumberCounts ) { primeDivisors = new ArrayList<>(Collections.nCopies(primeNumberCount, 0)); combinations(primeNumberCount, 0, 0); } Collections.sort(answer); System.out.println("The sequence of first four Giuga Numbers is: " +answer); } }
Output:
The sequence of the first four Giuga Numbers is: [30, 858, 1722, 66198]