Aliquot Sequence in Java
Introduction:
An aliquot sequence is a fascinating mathematical concept that involves generating a sequence of numbers where each term is derived from the sum of the proper divisors of the previous term. A proper divisor of a number is a positive integer that divides the number evenly, excluding the number itself. The aliquot sequence explores the iterative nature of this process, leading to patterns and behaviors that can be intriguing to study.
Example:
Input
int N =12
Output
Aliquot sequence is 12, 16, 15, 9, 4, 3, 1, 0.
Explanation:
The aliquot sum of a number N is the sum of its proper divisors. For example, the proper divisors of 12 are 1, 2, 3, 4, and 6. The sum of 12 is 1 + 2 + 3 + 4 + 6 = 16.
The proper divisors of 16 are 1, 2, 4, 8. The sum is 1 + 2 + 4 + 8 = 15.
The proper divisors of 15 are 1, 3, 5. The sum is 1 + 3 + 5 = 9.
The proper divisors of 9 are 1, 3. The sum is 1 + 3 = 4.
The proper divisors of 4 are 1, 2. The sum is 1 + 2 = 3.
The proper divisors of 3 are 1. The sum is 1.
Hence, there are no proper divisors for 1. The sum is 0.
Finally, the sequence is 12, 16, 15, 9, 4, 3, 1, 0.
Approach: Brute Force Approach
Brute force approach starts with the given number, repeatedly calculates the sum of its proper divisors, and adds these sums as sequence terms. The sequence generation continues for a specified length, avoiding repeated occurrences of 1. The approach is straightforward but not optimized for larger numbers.
Algorithm:
Step 1: Import the necessary library (ArrayList and List) for working with lists of integers.
Step 1.1: Set the startingNumber and sequenceLength to determine the starting number of the sequence and the desired length of the sequence.
Step 2: Call the generateAliquotSequence method with startingNumber and sequenceLength as arguments.
Step 2.1: Store the generated sequence in the aliquotSequence list. Print a header indicating "Aliquot Sequence." Iterate through the aliquotSequence list and print each term in the sequence.
Step 3: Initialize an empty list called sequence to store the generated sequence. Add the startingNumber to the sequence. Initialize currentNumber with startingNumber.
Step 4: Start a loop with i from 1 to sequenceLength - 1 (since we've already added one term). Calculate nextNumber by calling the sumOfProperDivisors method with currentNumber as the argument.
Step 5: Check if nextNumber is 1. If yes, add 1 to the sequence (to avoid repeated occurrences of 1). Break out of the loop.
Step 5.1: If nextNumber is not 1, add it to the sequence. Update currentNumber to nextNumber. Add 0 to the sequence (to end with a zero). Return the sequence.
Step 6: Initialize sum with 1 (since all numbers have 1 as a divisor). Start a loop with i from 2 to the square root of num.
Step 7: Check if num is divisible by i. If yes, add i to the sum. Also, if i is not equal to num / i, add num / i to the sum. Return the final sum.
Filename: AliquotSequence.java
import java.util.ArrayList;
import java.util.List;
public class AliquotSequence {
public static void main(String[] args) {
int startingNumber = 12; // Starting number of the sequence
int sequenceLength = 10; // Number of terms in the sequence
List aliquotSequence = generateAliquotSequence(startingNumber, sequenceLength);
System.out.println("Aliquot Sequence:");
for (int num : aliquotSequence) {
System.out.println(num);
}
}
public static List generateAliquotSequence(int start, int length) {
List sequence = new ArrayList<>();
sequence.add(start);
int currentNumber = start;
for (int i = 1; i < length; i++) {
int nextNumber = sumOfProperDivisors(currentNumber);
if (nextNumber == 1) {
// Stop generating terms if the next term is 1
sequence.add(1);
break;
}
sequence.add(nextNumber);
currentNumber = nextNumber;
}
sequence.add(0); // Add zero at the end
return sequence;
}
public static int sumOfProperDivisors(int num) {
int sum = 1; // Start with 1 because all numbers have 1 as a divisor
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
sum += i;
if (i != num / i) {
sum += num / i;
}
}
}
return sum;
}
}
Output:
Aliquot Sequence: 12 16 15 9 4 3 1 0
Time Complexity:
In generating aliquot sequence, the time complexity isO(sequenceLength)
The sumOfProperDivisors method calculates the sum of proper divisors for a given number. It runs in approximately O(sqrt(n)), where n is the input number.
The overall time complexity can be approximated as O(sequenceLength * sqrt(n)).
Space Complexity:
The aliquotSequence list stores the generated sequence, which has a length of sequenceLength. The variables used for iteration (i, currentNumber, nextNumber) and calculations (sum) consume constant space.
The overall space complexity is O(sequenceLength).