Python recursive program

Question

I'm relatively newcomer on programming as I'm educated a mathematician and have no experience on Python. I would like to know how to solve this problem in Python which appeared as I was studying one maths problem on my own:

Program asks a positive integer m. If m is of the form 2^n-1 it returns T(m)=n*2^{n-1}. Otherwise it writes m to the form 2^n+x, where -1 < x < 2^n, and returns T(m)=T(2^n-1)+x+1+T(x). Finally it outputs the answer.

Could you post what you have tried? That way, others can point out where you went wrong (much better learning experience than just having someone post some code, IMO). — Bart Kiers, May 09 '10 at 18:43
As a hint, if you write a function decompose(m) that returns n, x where m = 2^n + x (-1 <= x < 2^n) then you're 99% of the way there. — , May 09 '10 at 19:09
This might be helpful: http://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence-in-python — jathanism, May 09 '10 at 21:45

score 0 · Answer 1 · answered Jul 15 '12 at 23:49

I thought this was a neat problem so I attempted a solution. As far as I can tell, this satisfies the parameters in the original question.

#!/usr/bin/python

import math

def calculate(m: int) -> int:
    """
    >>> calculate(10)
    20
    >>> calculate(100)
    329
    >>> calculate(1.2)
    >>> calculate(-1)
    """
    if (m <= 0 or math.modf(m)[0] != 0):
        return None
    n, x = decompose(m + 1)
    if (x == 0):
        return n * 2**(n - 1)
    else:
        return calculate(2**n - 1) + x + 1 + calculate(x)


def decompose(m: int) -> (int, int):
    """
    Returns two numbers (n, x), where
    m = 2**n + x and -1 < x < 2^n
    """
    n = int(math.log(m, 2))
    return (n, m - 2**n)


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = True)

Assuming the numbers included in the calculate function's unit tests are the correct results for the problem, this solution should be accurate. Feedback is most welcome, of course.

Python recursive program

1 Answers1