CS 307: 2. Playing Peano and Gambling
Due: Wednesday, September 12, 2001.
- Write a function (sum-squares n) that will recursively add up
the squares of the integers from 1 to n.
- The mathematician Giuseppe Peano (1858 - 1932) showed that all
arithmetic operations on natural numbers (nonnegative integers) could be
reduced to a single constant (0) and an operation successor, which in
Lisp traditionally is called 1+ .
``Peano was one of the first to use what we now call symbolic logic.
He introduced, for instance, the use of the symbols `(E x)' to mean
`there is an x such that'; and he habitually wrote out all of his
lecture notes in his new symbolism. He was teaching at a military
academy at the time, and his students were so incensed by his
formalistic approach to mathematics that they rebelled (despite his
promises to pass them all) and got him fired. Subsequently he found a
more congenial setting at the University of Turin.'' -- Rudy Rucker,
Goedel's Incompleteness Theorems, p. 289.
The functions (1+ n) and (1- n), which add and
subtract 1 from an integer, are provided in the file
Write a function (peano+ x y), using only 1+ and 1-
to perform arithmetic, according to the following definition:
Can you think of an invariant (property that is always true)
of peano+? (Hint: trace the function and run it on an example.)
This function is tail-recursive.
peano+(x, y) = || x || , if y = 0 |
|| peano+(x + 1, y - 1) || , otherwise.
- Write a function (peano* x y) that uses only peano+,
1+, and 1- to perform arithmetic and is written in a
recursive style similar to that of peano+. For peano*,
use an auxiliary function and an auxiliary variable to accumulate the result
so that it will be tail-recursive.
- Test your functions on several sets of positive integer arguments
to verify that they perform addition and multiplication.
- The mathematical notation ,
read ``n choose k'',
is used to denote the number of distinct subsets of k items that can be
chosen from a set of n distinct objects. It can be shown that:
Although the factorial function could be used in implementing
n choose k, this would be inefficient for large values of
n and small k. We can algebraically
rewrite the definition into the following form for k > 0:
Write a function (choose n k), using a tail-recursive auxiliary
function, to compute n choose k without using the
function. Can you prove that the result of your auxiliary function
is always an integer? This would be a good invariant for
your recursive function: although non-integer intermediate results will
work in Lisp, they would not work in most languages.
- The Texas lottery involves a choice of 6 numbers from a set of 54.
Use your function to compute 54 choose 6 to determine the probability of
winning the jackpot.
- If you buy 20 lottery chances (for $20) every week for the next
50 years, what is the probability that you will win the jackpot?
Assuming that the jackpot averages $8 million and that the jackpot is the only
prize, what is your expected return (probability of winning times amount won)?
- Write a recursive function (invest amt time int)
to calculate the return on an investment of amount amt
for time time periods at an interest rate of int.
Assume that the starting principal is 0. At the end of each
time step, the value of the principal becomes the value of the original
principal times (1 + int), where int is the interest rate
per time period, plus the amount amt of the new contribution.
- If instead of buying lottery tickets, you invest $20 per week for
50 years at an interest rate of 6.0% per year, what is the value of your
investment at the end of 50 years? You may do the calculation on a
yearly basis, i.e., $1040 per year as the contribution per year.