Python: Streamlining Code for Brown Numbers

Question

I was curious if any of you could come up with a more streamline version of code to calculate Brown numbers. as of the moment, this code can do ~650! before it moves to a crawl. Brown Numbers are calculated thought the equation n! + 1 = m**(2) Where M is an integer

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 The formula does to that correct equation, That was an error in the post. — Z.B, Nov 12 '16 at 00:04

score 3 · Answer 1 · answered Nov 12 '16 at 02:00

Sorry, I don't understand the logic behind your code.

I don't understand why you calculate math.factorial(brownNum) 4 times with the same value of brownNum each time through the while True loop. And in the for loop:

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

i will only take on the value of math.factorial(brownNum)+1

Anyway, here's my Python 3 code for a brute force search of Brown numbers. It quickly finds the only 3 known pairs, and then proceeds to test all the other numbers under 1000 in around 1.8 seconds on this 2GHz 32 bit machine. After that point you can see it slowing down (it hits 2000 around the 20 second mark) but it will chug along happily until the factorials get too large for your machine to hold.

I print progress information to stderr so that it can be separated from the Brown_number pair output. Also, stderr doesn't require flushing when you don't print a newline, unlike stdout (at least, it doesn't on 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

score 2 · Answer 2 · answered Nov 11 '16 at 23:54

You might want to:

pre calculate your square numbers, instead of testing for them on the fly
pre calculate your factorial for each loop iteration num_fac = math.factorial(brownNum) instead of multiple calls
implement your own, memoized, factorial

that should let you run to the hard limits of your machine

score 1 · Answer 3 · edited May 23 '17 at 11:53

1

one optimization i would make would be to implement a 'wrapper' function around math.factorial that caches previous values of factorial so that as your brownNum increases, factorial doesn't have as much work to do. this is known as 'memoization' in computer science.

edit: found another SO answer with similar intention: Python: Is math.factorial memoized?

edited May 23 '17 at 11:53

Community

1
1

answered Nov 11 '16 at 23:46

matias elgart

1,123
12
18

Wrapper function? – Z.B Nov 12 '16 at 00:00
@Z.B yes, if you have a function that you're calling (like math.factorial), a 'wrapper' function is a function that you write that _itself_ would eventually call math.factorial, but you'd implement the wrapper function to get/put entries into a cache before calling math.factorial. here's an example from the link i pasted in , thanks to Senthil Kumaran: import math cache = {} def myfact(x): return cache.setdefault(x,math.factorial(x)) – matias elgart Nov 12 '16 at 00:06

score 1 · Answer 4 · answered Nov 11 '16 at 23:58

You should also initialize the square root more closely to the root.

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

Because of 4**e <= n <= 4**(e+1) the square root will be between x/2 and x which should yield quadratic convergence of the Heron formula from the first iteration on.

Python: Streamlining Code for Brown Numbers

4 Answers4