python 逆向 Collatz 猜想

Question

程序应该做的是采取步骤和一个数字，然后输出你有多少个独特的序列正好有 x steps 来创建 number。

有人知道我可以如何节省一些内存吗 - 因为我应该在 4 秒的限制内为相当大的数字工作。

def IsaacRule(steps, number):
    if number in IsaacRule.numbers:
        return 0
    else:
        IsaacRule.numbers.add(number)
    if steps == 0:
        return 1
    counter = 0
    if ((number - 1) / 3) % 2 == 1:
        counter += IsaacRule(steps-1, (number - 1) / 3)
    if (number * 2) % 2 == 0:
        counter += IsaacRule(steps-1, number*2)

    return counter

IsaacRule.numbers = set()

print(IsaacRule(6, 2))

如果有人知道带有记忆功能的版本，我将不胜感激，现在可以使用了，但仍有改进的余地。

Answer 1

基线：IsaacRule(50, 2) 需要 6.96 秒

0) 使用 LRU 缓存

这使得代码花费了更长的时间，并给出了不同的最终结果

1）消除if条件：`(number * 2) % 2 == 0`到`True`

IsaacRule(50, 2) 耗时 0.679 秒。感谢 Pm2Ring 的这个。

2) 将`((number - 1) / 3) % 2 == 1`简化为`number % 6 == 4`并尽可能使用floor除法：

IsaacRule(50, 2) 耗时 0.499s

真相table：

| n | n-1 | (n-1)/3 | (n-1)/3 % 2 | ((n-1)/3)%2 == 1 |
|---|-----|---------|-------------|------------------|
| 1 | 0   | 0.00    | 0.00        | FALSE            |
| 2 | 1   | 0.33    | 0.33        | FALSE            |
| 3 | 2   | 0.67    | 0.67        | FALSE            |
| 4 | 3   | 1.00    | 1.00        | TRUE             |
| 5 | 4   | 1.33    | 1.33        | FALSE            |
| 6 | 5   | 1.67    | 1.67        | FALSE            |
| 7 | 6   | 2.00    | 0.00        | FALSE            |

代码：

def IsaacRule(steps, number):
    if number in IsaacRule.numbers:
        return 0
    else:
        IsaacRule.numbers.add(number)
    if steps == 0:
        return 1
    counter = 0
    if number % 6 == 4:
        counter += IsaacRule(steps-1, (number - 1) // 3)
    counter += IsaacRule(steps-1, number*2)

    return counter

3) 使用集合重写代码

IsaacRule(50, 2) 需要 0.381 秒

这让我们可以利用对集合所做的任何优化。基本上我在这里进行广度优先搜索。

4) 打破循环，这样我们就可以跳过对以前状态的跟踪。

IsaacRule(50, 2) 耗时 0.256 秒

我们只需要添加一个检查 number != 1 来打破唯一已知的循环。这样可以加快速度，但是如果您从 1 开始，则需要添加一个特殊情况。感谢 Paul 的建议！

START = 2
STEPS = 50

# Special case since we broke the cycle
if START == 1:
    START = 2
    STEPS -= 1

current_candidates = {START} # set of states that can be reached in `step` steps

for step in range(STEPS):
    # Get all states that can be reached from current_candidates
    next_candidates = set(number * 2 for number in current_candidates if number != 1) | set((number - 1) // 3 for number in current_candidates if number % 6 == 4)

    # Next step of BFS
    current_candidates = next_candidates
print(len(next_candidates))

python 逆向 Collatz 猜想

python Reverse Collatz Conjecture

python

collatz

0) 使用 LRU 缓存

1）消除if条件：`(number * 2) % 2 == 0`到`True`

2) 将`((number - 1) / 3) % 2 == 1`简化为`number % 6 == 4`并尽可能使用floor除法：

3) 使用集合重写代码

4) 打破循环，这样我们就可以跳过对以前状态的跟踪。

python 逆向 Collat​​z 猜想

python Reverse Collatz Conjecture

python

collatz

0) 使用 LRU 缓存

1）消除if条件：(number * 2) % 2 == 0到True

2) 将((number - 1) / 3) % 2 == 1简化为number % 6 == 4并尽可能使用floor除法：

3) 使用集合重写代码

4) 打破循环，这样我们就可以跳过对以前状态的跟踪。

python 逆向 Collatz 猜想

1）消除if条件：`(number * 2) % 2 == 0`到`True`

2) 将`((number - 1) / 3) % 2 == 1`简化为`number % 6 == 4`并尽可能使用floor除法：