# Tree class (binary trees with internal values)
# (Originally in 22.py)

class Tree(object):
    """A tree with internal values."""

    def __init__(self, entry, left=None, right=None):
        self.entry = entry
        self.left = left
        self.right = right

    def __repr__(self):
        args = repr(self.entry)
        if self.left or self.right:
            args += ', {0}, {1}'.format(repr(self.left), repr(self.right))
        return 'Tree({0})'.format(args)

def fib_tree(n):
    """Return a Tree that represents a recursive Fibonacci calculation.

    >>> fib_tree(3)
    Tree(1, Tree(0), Tree(1))
    """
    if n == 1:
        return Tree(0)
    if n == 2:
        return Tree(1)
    left = fib_tree(n-2)
    right = fib_tree(n-1)
    return Tree(left.entry + right.entry, left, right)

def count_entries(tree):
    """Return the number of entries in a Tree.

    >>> count_entries(fib_tree(6))
    15
    """
    if tree is None:
        return 0
    return 1 + count_entries(tree.left) + count_entries(tree.right)

# Counting factors

from math import sqrt

def count_factors(n):
    """Count the positive integers that evenly divide n.

    >>> count_factors(576)
    21
    """
    factors = 0
    for k in range(1, n+1):
        if n % k == 0:
            factors += 1
    return factors

def count_factors_fast(n):
    """Count the positive integers that evenly divide n.

    >>> count_factors_fast(576)
    21
    """
    sqrt_n = sqrt(n)
    k, factors = 1, 0
    while k < sqrt_n:
        if n % k == 0:
            factors += 2
        k += 1
    if k * k == n:
        factors += 1
    return factors

# Exponentiation

def exp(b, n):
    """Return b to the n.

    >>> exp(2, 10)
    1024
    """
    if n == 0:
        return 1
    return b * exp(b, n-1)

def square(x):
    return x*x

def fast_exp(b, n):
    """Return b to the n.

    >>> fast_exp(2, 10)
    1024
    """
    if n == 0:
        return 1
    if n % 2 == 0:
        return square(fast_exp(b, n//2))
    else:
        return b * fast_exp(b, n-1)