def factors_slow(n): """Count the number of factors of a positive integer n. >>> factors_slow(4) 3 >>> factors_slow(28) 6 """ total = 0 i = 1 while i <= n: if n % i == 0: total += 1 i += 1 return total def factors_fast(n): """Count the number of factors of a positive integer n. >>> factors_fast(4) 3 >>> factors_fast(28) 6 """ total = 0 i = 1 while i * i < n: if n % i == 0: total += 2 i += 1 if i * i == n: total += 1 return total def fib(n): """Return the nth Fibonacci number. >>> fib(1) 1 >>> fib(8) 21 """ if n == 0 or n == 1: return n else: return fib(n - 2) + fib(n - 1) def overlap(m, n): count = 0 for i in range(m): for j in range(n): count += 1 return count def fib_iter(n): """Return the nth Fibonacci number. >>> fib_iter(1) 1 >>> fib_iter(8) 21 """ i = 0 curr, next = 0, 1 while i < n: curr, next = next, curr + next i += 1 return curr def exp_slow(b, n): """Calculate b to the power n where n is a nonnegative integer. >>> exp_slow(2, 4) 16 >>> exp_slow(2, 10) 1024 """ if n == 0: return 1 else: return b * exp_slow(b, n - 1) sq = lambda x: x * x def exp_fast(b, n): """Calculate b to the power n where n is a nonnegative integer. >>> exp_fast(2, 4) 16 >>> exp_fast(2, 10) 1024 """ if n == 0: return 1 elif n % 2 == 0: return sq(exp_fast(b, n // 2)) else: return b * exp_fast(b, n - 1) def sum_naturals(n): """Calculates 1 + 2 + 3 + ... + n. >>> sum_naturals(2) 3 >>> sum_naturals(5) 15 """ total = 0 for i in range(1, n + 1): total += i return total def sum_powers_of_two(n): """Calculates 1 + 2 + 4 + 8 + ... + 2^n. >>> sum_powers_of_two(1) 3 >>> sum_powers_of_two(4) 31 """ total = 0 for i in range(n + 1): total += 2 ** i return total