Python：精简棕色数字的代码

问题描述：

我很好奇你是否有人可以想出一个更简化的代码来计算棕色数字。截至目前，此代码在移动到爬网之前可以执行~650!。布朗数字计算认为方程n! + 1 = m**(2)凡M是一个整数Python：精简棕色数字的代码

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(" "))

@PM 2Ring公式对那个正确的方程做了修改，这是后期的错误。 –

答

一个优化我会做将实现围绕math.factorial一个“包装”功能缓存阶乘的先前值，以便为您的brownNum增加，阶乘没有太多的工作要做。这在计算机科学中被称为“memoization”。

编辑：发现了类似的意向另一个SO回答：Python: Is math.factorial memoized?

包装功能？ –

@ Z.B是的，如果你有一个你正在调用的函数（比如math.factorial），那么一个'wrapper'函数是一个函数，你可以写出_itself_最终会调用数学。阶乘，但是在调用math.factorial之前，您需要实现包装函数来将条目放入缓存。谢谢Senthil Kumaran： import math cache = {} def myfact（x）： return cache.setdefault（x，math.factorial（x）） –

答

你可能想：

预先计算出你的平方数，而不是测试他们的飞行
预先计算出你的阶乘迭代num_fac = math.factorial(brownNum)而不是多次呼叫
实施您自己的，memoized，阶乘

它应该让你跑到你机器的硬限位

答

你也应该更加接近初始化平方根。

e = int(math.log(n,4)) 
x = n//2**e

由于4**e <= n <= 4**(e+1)的平方根将x/2和x之间应当从在第一次循环得到苍鹭式的二次收敛。

答

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

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

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

i将只采取的math.factorial(brownNum)+1

价值无论如何，这是我的蛮力搜索的Brown numbers的Python 3代码。它快速找到仅有的3个已知配对，然后在2GHz 32位机器上在大约1.8秒内继续测试1000以下的所有其他数字。在此之后，你可以看到它放慢了速度（它在20秒左右达到2000点），但它会一直高高跳起，直到因子太大而不能容纳机器。

我将进度信息打印到stderr，以便它可以从Brown_number对输出中分离出来。另外，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

Python：精简棕色数字的代码

相关推荐