*Due by 11:59pm on Wednesday, 10/2*

**Due date extended.** This homework was originally due Tuesday, 10/1. Due to
problems with the submission system, the deadline was extended a day.

**Submission.** See the online submission instructions.
We have provided a hw3.py starter file for the questions below.

**Readings.** Section 1.7 of the online textbook.

**Q1.** A mathematical function `G` on positive integers is defined by two cases:

`G(n) = n, if n <= 3`

`G(n) = G(n - 1) + 2 * G(n - 2) + 3 * G(n - 3), if n > 3`

Write a recursive function `g` that computes `G(n)`. Then, write an
iterative function `g_iter` that also computes `G(n)`:

def g(n): """Return the value of G(n), computed recursively. >>> g(1) 1 >>> g(2) 2 >>> g(3) 3 >>> g(4) 10 >>> g(5) 22 """ "*** YOUR CODE HERE ***" def g_iter(n): """Return the value of G(n), computed iteratively. >>> g_iter(1) 1 >>> g_iter(2) 2 >>> g_iter(3) 3 >>> g_iter(4) 10 >>> g_iter(5) 22 """ "*** YOUR CODE HERE ***"

**Q2.** Write a function `has_seven` that takes a positive integer `n` and
returns whether `n` contains the digit 7. *Do not use any assignment
statements*:

def has_seven(k): """Has a has_seven >>> has_seven(3) False >>> has_seven(7) True >>> has_seven(2734) True >>> has_seven(2634) False >>> has_seven(734) True >>> has_seven(7777) True """ "*** YOUR CODE HERE ***"

**Q3.** The ping-pong sequence counts up starting from 1 and is always either
counting up or counting down. At element k, the direction switches if k is a
multiple of 7 or contains the digit 7. The first five direction changes are
after . The first 30 elements of the ping-pong sequence are listed below, with
direction swaps marked using brackets at the 7th, 14th, 17th, 21st, 27th, and
28th elements:

"1 2 3 4 5 6 [7] 6 5 4 3 2 1 [0] 1 2 [3] 2 1 0 [-1] 0 1 2 3 4 [5] [4] 5 6"

Implement a function `pingpong` that returns the nth element of the ping-pong
sequence. *Do not use any assignment statements*.

*Hint*: If you're stuck, try implementing `pingpong` first using assignment
and a `while` statement, then try a recursive implementation without
assignment:

def pingpong(n): """Return the nth element of the ping-pong sequence. >>> pingpong(7) 7 >>> pingpong(8) 6 >>> pingpong(15) 1 >>> pingpong(21) -1 >>> pingpong(22) 0 >>> pingpong(30) 6 >>> pingpong(68) 2 >>> pingpong(69) 1 >>> pingpong(70) 0 >>> pingpong(71) 1 >>> pingpong(72) 0 >>> pingpong(100) 2 """ "*** YOUR CODE HERE ***"

**Q4.** Write a function that takes a positive integer `n` and returns the
number of ten-pairs it contains. A ten-pair is a pairs of digits within `n`
that sum to 10. *Do not use any assignment statements.*

The number 7,823,952 has 3 ten-pairs. The first and fourth digits sum to 7+3=10, the second and third digits sum to 8+2=10, and the second and last digit sum to 8+2=10:

def ten_pairs(n): """Return the number of ten-pairs within positive integer n. >>> ten_pairs(7823952) 3 >>> ten_pairs(55055) 6 >>> ten_pairs(9641469) 6 """ "*** YOUR CODE HERE ***"

**Q5.** Once the machines take over, the denomination of every coin will be a
power of two: 1-cent, 2-cent, 4-cent, 8-cent, 16-cent, etc. There will be
no limit to how much a coin can be worth.

A set of coins makes change for `n` if the sum of the values of the coins is `n`. For example, the following sets make change for `7`:

- 7 1-cent coins
- 5 1-cent, 1 2-cent coins
- 3 1-cent, 2 2-cent coins
- 3 1-cent, 1 4-cent coins
- 1 1-cent, 3 2-cent coins
- 1 1-cent, 1 2-cent, 1 4-cent coins

Thus, there are 6 ways to make change for `7`. Write a function
`count_change` that takes a positive integer `n` and returns the number of
ways to make change for `n` using these coins of the future:

def count_change(amount): """Return the number of ways to make change for amount. >>> count_change(7) 6 >>> count_change(10) 14 >>> count_change(20) 60 >>> count_change(100) 9828 """ "*** YOUR CODE HERE ***"

**Q6.** (Extra for experts) The recursive factorial function can be written as
a single expression by using a conditional expression.

>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1))) >>> fact(5) 120

However, this implementation relies on the fact (no pun intended) that `fact`
has a name, to which we refer in the body of `fact`. To write a recursive
function, we have always given it a name using a `def` or assignment
statement so that we can refer to the function within its own body. In this
question, your job is to define fact recursively without giving it a name!

Write an expression that computes `n` factorial using only call expressions,
conditional expressions, and lambda expressions (no assignment or def
statements). The `sub` and `mul` functons from the operator module are the
only built-in function required to solve this problem:

from operator import sub, mul def make_anonymous_factorial(): """Return the value of an expression that computes factorial. >>> make_anonymous_factorial()(5) 120 """ return YOUR_EXPRESSION_HERE