Python：简化Brown数字的代码

Question

我很好奇你们中是否有人能想出一个更精简的版本来计算布朗数。到目前为止，此代码可以在移动到爬网之前执行~650!。布朗数的计算公式是n! + 1 = m**(2)，其中M是一个整数

brownNum = 8
import math
def squareNum(n):
        x = n // 2
        seen = set([x])
        while x * x != n:
                x = (x + (n // x)) // 2
                if x in seen: return False
                seen.add(x)
        return True
while True:
        for i in range(math.factorial(brownNum)+1,math.factorial(brownNum)+2):
                if squareNum(i) is True:
                        print("pass")
                        print(brownNum)
                        print(math.factorial(brownNum)+1)
                        break
                else:
                        print(brownNum)
                        print(math.factorial(brownNum)+1)
                        brownNum = brownNum + 1
                        continue

                break
print(input(" "))

Answer 1

您可能想：

• 预先计算你的平方数，而不是在飞行中测试它们
• 为每个循环迭代num_fac = math.factorial(brownNum)而不是多个调用预先计算阶乘
• 实现你自己的，记忆的，阶乘的

这样你就可以跑向你机器的极限了

Answer 2

对不起，我不明白你代码背后的逻辑。你知道吗

我不明白为什么每次通过while True循环用相同的brownNum值计算math.factorial(brownNum)4次。在for循环中：

for i in range(math.factorial(brownNum)+1,math.factorial(brownNum)+2):

i将仅具有math.factorial(brownNum)+1的值

总之，这里是我的python3代码，用于对Brown numbers进行暴力搜索。它会很快找到仅有的3对已知数字，然后在这台2GHz 32位机器上，在大约1.8秒内测试1000以下的所有其他数字。在这一点之后，你可以看到它在减速（它在20秒左右达到2000），但它会很高兴地前进，直到阶乘变得太大，你的机器无法容纳。你知道吗

我将进度信息打印到stderr，这样它就可以从Brown\u数字对输出中分离出来。另外，当您不打印换行符时，stderr不需要刷新，这与stdout不同（至少在Linux上不需要）。你知道吗

import sys

# Calculate the integer square root of `m` using Newton's method.
# Returns r: r**2 <= m < (r+1)**2
def int_sqrt(m):
    if m <= 0:
        return 0
    n = m << 2
    r = n >> (n.bit_length() // 2)
    while True:
        d = (n // r - r) >> 1
        r += d
        if -1 <= d <= 1:
            break
    return r >> 1

# Search for Browns numbers
fac = i = 1
while True:
    if i % 100 == 0: 
        print('\r', i, file=sys.stderr, end='')
    fac *= i
    n = fac + 1
    r = int_sqrt(n)
    if r*r == n:
        print('\nFound', i, r)
    i += 1

Answer 3

我要做的一个优化就是实现一个“包装器”函数数学.阶乘它会缓存factorial以前的值，这样随着brownNum的增加，factorial就没有那么多工作要做了。这在计算机科学中被称为“记忆化”。你知道吗

编辑：找到另一个具有类似意图的SO答案：Python: Is math.factorial memoized?