Hofstadter equation related code in python

Question

There was this question in a university assignment related to Hofstadter sequence. It basically say that it is a integer sequence blah blah and there are two values for a given index n. A male value [M(n)] and a female value [F(n)].

They are defined as:

• M(0)=0
• F(0)=1
• M(n)=n-F(M(n-1))
• F(n)=n-M(F(n-1))

And we were asked to write a program in python to find the Male and Female values of the sequence of a given integer.

So the code I wrote was:

def female(num):
    if num == 0:
        return 1
    elif num >0:
        return num - male(female(num-1))
def male(num):
    if num==0:
        return 0
    elif num >0:
        return num - female(male(num-1))

And when executed with a command like print male(5)
It works without a fuss. But when I try to find the value of n = 300, the program gives no output. So I added a print method inside one of the functions to find out what happens to the num value

[ elif num>0: print num ...]

And it shows that the num value is decreasing until 1 and keeps hopping between 1 and 2 at times reaching values like 6.

I can’t figure out why it happens. Any insight would be nice. Also what should I do to find the values relevant to bigger integers. Thanks in advance. Cheers.

Answer 1

The code is theoretically fine. What you underestimate is the complexity of the computation. Formula

M(n)=n-F(M(n-1))

actually means

tmp = M(n-1)
M(n) = n - F(tmp)

So if you represent this calculation as a tree of necessary calls, you might see that its a binary tree and you should go through all its nodes to calculate the results. Given that M(n) and F(n) are about n/2 I'd estimate the total number of the nodes to be of order 2^(n/2) which becomes a huge number once you put n = 300 there. So the code works but it just will take a very very long time to finish.

The one way to work this around is to employ caching in a form of memoization. A code like this:

femCache = dict()
def female(num):
      #print("female " + str(num))
      global femCache
      if num in femCache:
        return femCache[num];
      else:
        res = 1 # value for num = 0
        if num > 0:
             res = num - male(female(num-1))
        femCache[num] = res
        return res

maleCache = dict()
def male(num):
      #print("male " + str(num))
      global maleCache
      if num in maleCache:
        return maleCache[num];
      else:
        res = 0 # value for num = 0
        if num > 0:
             res = num - female(male(num-1))
        maleCache[num] = res
        return res

print(male(300))

should be able to compute male(300) in no time.