如何在 Java 中生成 Collatz 树？

Question

我绝望地试图通过无限循环生成 collatz 序列中的所有数字。该程序应该从一个开始并打印所有可能的 collatz，直到用户停止，或者我们得到一个内存 overflow.So 我们必须是一个反 collatz 函数。逻辑是这样的：（如果n是偶数，如果n/3是一个整数，我们做逆运算，奇数运算。）

import java.math.BigInteger;

public class InverseColatz {
    public static void main(String args[]) throws InterruptedException{
        BigInteger n = BigInteger.valueOf(2);
        System.out.println(1);
        while(true){
            if(n.mod(BigInteger.valueOf(3)).equals(BigInteger.ZERO)){
                n = n.divide(BigInteger.valueOf(3));
                n = n.subtract(BigInteger.ONE);
                System.out.println(n);
               Thread.sleep(500);
            }
            if(n.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
                n = n.multiply(BigInteger.valueOf(2));
                System.out.println(n);
                Thread.sleep(500);
            }
        } 
    }
}

问题是我只是生成偶数序列 (n*2)，但我无法生成奇数序列 ((n/3)-1)，因为这段代码永远不会达到奇数条件，因为正在生成的所有数字都不匹配第一个 condition.Can 有人请赐教吗？提前致谢。

Answer 1

首先，请原谅我的排版问题，我无法使用图像来显示方程式，因为这是我的第一个 post。

让我们先来看看Collatz Conjecture。我们知道所涉及的系列被称为 Halestone 系列，参考所有数字 2ⁿ 的行为，其中 n 是一个正整数。该系列是通过根据值是奇数还是偶数递归修改值来定义的。

If the number is even, divide it by two.

If the number is odd, triple it and add one.

为了扭转这个过程，一个数字可能有两个结果。例如，5 和 32 的计算结果都是 16。

5 is odd, (3 * 5) + 1 = 16

32 is even, 32 / 2 = 16

要找到反函数，我们需要考虑到每个数字可能有两个答案。我们还需要定义什么是有效答案。反函数 的有效答案必须 为正整数。

现在我们做一些代数来求逆。将 a 定义为 Halestone 级数一次迭代的结果。

求解 n :
n̲
3n + 1 = a 2 = a

a̲ ̲-̲ ̲1̲
n= 3 n = 2a

现在我们有了新规则。我们知道 n = 2a 的计算结果始终为正整数，因此该表达式始终为真。但是，如果 a - 1 可以被 3 整除，则另一个方程的计算结果仅为正整数。其他所有实例都不会 return 一个完整的整数，而是被无限多的三或六拖尾。这些十进制数字是不可接受的，将被丢弃。请注意输入值 4 returns 1 如何作为答案之一

要开始考虑代码，我们应该将提议的树分解成层。类似于this image的水平分层。对于每次迭代，每个分支都有可能分成两个独立的分支。这意味着我们需要在迭代树时存储未知数量的数字。

这是我想到的。本质上，它仍然只是需要格式化为可读内容的数据流。当堆栈大小用完或并发分支数超过 2³¹ - 1 时，它应该会失败。这是由于数组的性质。

public static void main(String args[]) throws InterruptedException {
    ArrayList<BigInteger> tree = new ArrayList<BigInteger>();
    tree.add(BigInteger.valueOf(2));
    System.out.println(1);
    while (true) {
        // Store a snapshot of the current tree so new branches created don't mess with
        // the iteration process.
        BigInteger[] originalTree = tree.toArray(new BigInteger[tree.size()]);

        // Keep track of new branches added during each step for index alignment in
        // the stepping method.
        int newBranchCount = 0;

        // Iterate over the values of the original tree.
        for(int i = 0; i < originalTree.length; i++) {
            // Evaluate branch
            stepBranch(tree, originalTree[i], i + newBranchCount);

            // Update branch count after step.
            newBranchCount = tree.size() - originalTree.length;
        }
    }
}

/*
 * Given the tree to mutate, a value from a mutation free version of the tree,
 * and the current working index of the tree:
 * Evaluate whether or not to add a new odd valued branch and report new value(s).
*/
public static void stepBranch(ArrayList<BigInteger> tree, BigInteger branch, int index) throws InterruptedException {

    // If (n + 1) is divisible by three, do so and create a new branch to store the new value
    if (branch.subtract(BigInteger.ONE).mod(BigInteger.valueOf(3)).equals(BigInteger.ZERO)) {

        // If the input is 4, the output is 1 which appears earlier, therefore requires no attention.
        if(!branch.equals(BigInteger.valueOf(4))) {
            // Create new value. 
            BigInteger odd = branch.subtract(BigInteger.ONE).divide(BigInteger.valueOf(3));

            // If the output is even, it doesn't fit the requirements for an odd cell.
            if(!odd.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
                tree.add(index + 1, odd);
                System.out.println(tree.get(index + 1));
            }
        } else {
            System.out.println(1);
        }
        Thread.sleep(500);
    }

    // The original branch, not considering a new branch if one was created, is
    // multiplied by 2 so as to check for a new odd node in the next iteration.
    tree.set(index, branch.multiply(BigInteger.valueOf(2)));
    System.out.println(tree.get(index));
    Thread.sleep(500);
}

希望对您有所帮助！

如何在 Java 中生成 Collat​​z 树？

How to Generate the Collatz tree in Java?

java

collatz

如何在 Java 中生成 Collatz 树？