Generate Juggler Sequence in Java – 在 Java 中生成 Juggler 序列

最后修改: 2024年 3月 5日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

The juggler sequence stands out for its intriguing behavior and elegant simplicity.

juggler 序列以其引人入胜的行为和优雅简洁的风格脱颖而出。

In this tutorial, we’ll understand the juggler sequence and explore how to generate the sequence using a given initial number in Java.

在本教程中，我们将了解戏法序列，并探索如何使用给定的初始数字在 Java 中生成序列。

2. Understanding the Juggler Sequence

2.了解戏法序列

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. 

这个过程一直持续到 1，然后序列终止。

It’s worth mentioning that both n1/2 and n3/2 can be transformed into square root calculations:

值得一提的是，n1/2 和n3/2都可以转化为平方根计算：

  • 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.

值得注意的是，有猜想认为所有杂耍者序列最终都会达到 1，但这一猜想尚未得到证明。因此，我们实际上无法完成 Big O 时间复杂性分析。

Now that we know how a juggler sequence is generated, let’s implement some sequence generation methods in Java.

既然我们已经知道了戏法序列是如何生成的，那就让我们用 Java 来实现一些序列生成方法吧。

3. The Loop-Based Solution

3.基于循环的解决方案

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

4.基于递归的解决方案

Alternatively, we can generate a juggler sequence from a given number recursively. First, let’s add the byRecursion() method to the JugglerSequenceGenerator class:

另外，我们还可以从给定的数字 递归生成一个杂耍序列。首先，让我们在 JugglerSequenceGenerator 类中添加 byRecursion() 方法：

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:

我们可以看到，byRecursion() 方法是另一个杂耍序列生成器的入口点。它验证输入数字并准备结果序列列表。不过，主要的序列生成逻辑是在 fillSeqRecursively() 方法中实现的：

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.

如代码所示，该方法使用 next 值和 result 列表递归调用自身。这意味着该方法将重复向序列中添加 current 数字、检查终止条件和计算下一个项的过程，直到满足终止条件（current ==1）为止。

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

5.结论

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.

在本文中，我们首先讨论了什么是杂耍数列。需要注意的是，目前还没有证明所有的戏法序列最终都会达到 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.

与往常一样，这些示例的完整源代码可在 GitHub 上获取。