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

Question

我無望地試圖在collat​​z序列中生成一個無限循環的所有數字。 該程序應該從一開始打印所有可能的collat​​z，直到用戶停止，或者我們得到一個內存溢出。所以我們必須是一個逆collat​​z函數。 邏輯是這樣的：（當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），因爲此代碼從未達到奇數條件，因爲所有數字都是生成的不符合第一個條件。有人請給我一些啓示嗎？ 在此先感謝。

Answer 1

首先，請原諒我的格式，我不能使用圖像來顯示方程式，因爲這是我的第一篇文章。

讓我們先看看Collatz Conjecture。我們知道所涉及的系列被稱爲Halestone系列，參考所有數字的行爲2 ⁿ其中n是正整數。該系列是通過基於值是奇數還是偶數來遞歸修改該值來定義的。

• 如果數字是偶數，則除以2。
• 如果該數字是奇數，則將其三倍並添加一個。

要扭轉這個過程，對於一個數字可能有兩個結果。例如，既5和32計算爲16

• 5是奇數，（3 * 5）+ 1 = 16
• 32爲偶數時，32/2 = 16

要找到反函數，我們需要考慮到可能存在的每一個數字的兩個答案。我們還需要定義什麼是有效的答案。來自反函數的有效答案必須是是一個正整數。

現在我們做一些代數來得到逆。定義a作爲Halestone系列迭代的結果。

解決對於n：
                                        Ñ
        3N + 1 =                 2 =

                一個 - 1
        N =                           N = 2A

所以現在我們有了新的規則。我們知道n = 2a將始終評估爲正整數，因此此表達式始終爲真。然而，如果a - 1可被3整除，則其他方程式僅評估爲正整數。每個其他實例不會返回整數，而是無限數量的三元或六元。這些十進制數字是不可接受的，將被拋出。請注意輸入值4如何返回1作爲其中一個答案

要開始思考代碼，我們應該將提議的樹分解爲多個層。類似於this image的水平分層。對於每一次迭代，每個分支都有可能分成兩個獨立的分支。這意味着我們需要在迭代樹時存儲未知數量的數字。

這就是我想出來的。從本質上講，它仍然只是一個數據流，需要被格式化爲可讀的內容。當堆棧大小用完或者併發分支數量超過2時，它會失敗。這是由於數組的性質造成的。

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); 
} 

希望這有助於！