1. Overview
The juggler sequence stands out for its intriguing behavior and elegant simplicity.
In this tutorial, we’ll understand the juggler sequence and explore how to generate the sequence using a given initial number in Java.
2. Understanding the Juggler Sequence
Before we dive into the code to generate juggler sequences, let’s quickly understand what a juggler sequence is.
In number theory, a juggler sequence is an integer sequence defined recursively as follows:
- Start with a positive integer n as the first term of the sequence.
- If n is even, the next term is n1/2, rounded down to the nearest integer.
- If n is odd, then the next term is n3/2, rounded down to the nearest integer.
This process continues until it reaches 1, where the sequence terminates.
It’s worth mentioning that both n1/2 and n3/2 can be transformed into square root calculations:
- n1/2 is the square root of n. Therefore n1/2 = sqrt(n)
- n3/2 = n1 * n1/2 = n * sqrt(n)
An example may help us to understand the sequence quickly:
Given number: 3
-----------------
3 -> odd -> 3 * sqrt(3) -> (int)5.19.. -> 5
5 -> odd -> 5 * sqrt(5) -> (int)11.18.. -> 11
11 -> odd -> 11 * sqrt(11)-> (int)36.48.. -> 36
36 -> even -> sqrt(36) -> (int)6 -> 6
6 -> even -> sqrt(6) -> (int)2.45.. -> 2
2 -> even -> sqrt(2) -> (int)1.41.. -> 1
1
sequence: 3, 5, 11, 36, 6, 2, 1
It’s worth noting that it’s conjectured that all juggler sequences eventually reach 1, but this conjecture has not been proven. Therefore, we’re effectively blocked from completing a Big O time complexity analysis.
Now that we know how a juggler sequence is generated, let’s implement some sequence generation methods in Java.
3. The Loop-Based Solution
Let’s first implement a loop-based generation method:
class JugglerSequenceGenerator {
public static List<Integer> byLoop(int n) {
if (n <= 0) {
throw new IllegalArgumentException("The initial integer must be greater than zero.");
}
List<Integer> seq = new ArrayList<>();
int current = n;
seq.add(current);
while (current != 1) {
int next = (int) (Math.sqrt(current) * (current % 2 == 0 ? 1 : current));
seq.add(next);
current = next;
}
return seq;
}
}
The code looks pretty straightforward. Let’s quickly pass through the code and understand how it works:
- First, validate the input n, as the initial number must be a positive integer.
- Then, create the seq list to store the result sequence, assign the initial integer to current, and add it to seq.
- A while loop is responsible for generating each term and appending it to the sequence based on the calculation we discussed earlier.
- Once the loop terminates (when current becomes 1), the generated sequence stored in the seq list is returned.
Next, let’s create a test method to verify whether our loop-based approach can generate the expected result:
assertThrows(IllegalArgumentException.class, () -> JugglerSequenceGenerator.byLoop(0));
assertEquals(List.of(3, 5, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byLoop(3));
assertEquals(List.of(4, 2, 1), JugglerSequenceGenerator.byLoop(4));
assertEquals(List.of(9, 27, 140, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byLoop(9));
assertEquals(List.of(21, 96, 9, 27, 140, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byLoop(21));
assertEquals(List.of(42, 6, 2, 1), JugglerSequenceGenerator.byLoop(42));
4. The Recursion-Based Solution
Alternatively, we can generate a juggler sequence from a given number recursively. First, let’s add the byRecursion() method to the JugglerSequenceGenerator class:
public static List<Integer> byRecursion(int n) {
if (n <= 0) {
throw new IllegalArgumentException("The initial integer must be greater than zero.");
}
List<Integer> seq = new ArrayList<>();
fillSeqRecursively(n, seq);
return seq;
}
As we can see, the byRecursion() method is the entry point of another juggler sequence generator. It validates the input number and prepares the result sequence list. However, the main sequence generation logic is implemented in the fillSeqRecursively() method:
private static void fillSeqRecursively(int current, List<Integer> result) {
result.add(current);
if (current == 1) {
return;
}
int next = (int) (Math.sqrt(current) * (current % 2 == 0 ? 1 : current));
fillSeqRecursively(next, result);
}
As the code shows, the method calls itself recursively with the next value and the result list. This means that the method will repeat the process of adding the current number to the sequence, checking termination conditions, and calculating the next term until the termination condition (current == 1) is met.
The recursion approach passes the same test:
assertThrows(IllegalArgumentException.class, () -> JugglerSequenceGenerator.byRecursion(0));
assertEquals(List.of(3, 5, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byRecursion(3));
assertEquals(List.of(4, 2, 1), JugglerSequenceGenerator.byRecursion(4));
assertEquals(List.of(9, 27, 140, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byRecursion(9));
assertEquals(List.of(21, 96, 9, 27, 140, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byRecursion(21));
assertEquals(List.of(42, 6, 2, 1), JugglerSequenceGenerator.byRecursion(42));
5. Conclusion
In this article, we first discussed what a juggler sequence is. It’s important to note that it’s not yet proven that all juggler sequences eventually reach 1.
Also, we explored two approaches to generate the juggler sequence starting from a given integer.
As always, the complete source code for the examples is available over on GitHub.
