Return to Question

Consider the following recurrence relation: $$T(n) = 0 \text{ when } n \leq 0\\ T(n) = 1+\sum_{p=0}^{\infty}T\left(\left\lfloor\frac{n}{2^p}\right\rfloor - 1\right)$$ The first few integers generated by this relation are as follows: $$0, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 83, 101, 119, 142, 165, 195, 225, 262, 299$$ This was calculated using the following Python function:

def T(n):
    if n <= 0:
        return 0
    else:
        total = 1
        while True:
            if n <= 0:
                break
            total += T(n - 1)
            n = n >> 1
        return total

I have the following questions:

• Does this relation have a closed form (or how might one attack finding such a form)? The OEIS does not appear to know this sequence yet.
• How does this function behave in the limit? It appears to be growing slightly faster than polynomial.

Consider the following recurrence relation: $$T(n) = 0 \text{ when } n \leq 0\\ T(n) = 1+\sum_{p=0}^{\infty}T\left(\left\lfloor\frac{n}{2^p}\right\rfloor - 1\right)$$ The first few integers generated by this relation are as follows: $$0, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 83, 101, 119, 142, 165, 195, 225, 262, 299$$ This was calculated using the following Python function:

def T(n):
    if n <= 0:
        return 0
    else:
        total = 1
        while n > 0:
            total += T(n - 1)
            n = n >> 1
        return total

I have the following questions:

• Does this relation have a closed form (or how might one attack finding such a form)? The OEIS does not appear to know this sequence yet.
• How does this function behave in the limit? It appears to be growing slightly faster than polynomial.

Consider the following recurrence relation: $$T(n) = 0 \text{ when } n \leq 0\\ T(n) = 1+\sum_{p=0}^{\infty}T\left(\left\lfloor\frac{n}{2^p}\right\rfloor - 1\right)$$ The first few integers generated by this relation are as follows: $$0, 1, 2, 4, 7, 11, 17, 23, 32, 42, 56, 70, 90, 110, 136, 162, 197, 233, 279, 325, 385, 445, 519, 593, 687, 781, 895$$ I have the following questions:

• Does this relation have a closed form (or how might one attack finding such a form)? The OEIS does not appear to know this sequence yet.
• How does this function behave in the limit? It appears to be growing slightly faster than polynomial.

Consider the following recurrence relation: $$T(n) = 0 \text{ when } n \leq 0\\ T(n) = 1+\sum_{p=0}^{\infty}T\left(\left\lfloor\frac{n}{2^p}\right\rfloor - 1\right)$$ The first few integers generated by this relation are as follows: $$0, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 83, 101, 119, 142, 165, 195, 225, 262, 299$$ This was calculated using the following Python function:

def T(n):
    if n <= 0:
        return 0
    else:
        total = 1
        while True:
            if n <= 0:
                break
            total += T(n - 1)
            n = n >> 1
        return total

I have the following questions:

• Does this relation have a closed form (or how might one attack finding such a form)? The OEIS does not appear to know this sequence yet.
• How does this function behave in the limit? It appears to be growing slightly faster than polynomial.