CSE 1729 Introduction to Principles of Programming December 8, 2016 Problem Set 10
Note that this problem set is due on a Thursday night. It is the last one of the semester, so have a ball!
Steams, streams, and more streams.
Remember to use the stream code that was supplied for the last lab. I stream, you stream, we all stream…
1.
Define implicitly the stream of factorials: 0!,1!,2!,…. Remember that an implicit definition of a stream is a define where the resulting stream is the thing being defined, but also shows up in the form that the thing is being defined to. See the lecture slides.
Define implicitly the stream of the negative powers of 2, i.e. 1, 1, 1, 1 ,…. 2 4 8 16
Define sin-stream, the stream corresponding to the sequence: k x2k+1
(−1) (2k+1)!for x =0,1,2,…
This is a stream of values dependent on x, so you should write a function (sin-stream x)
that returns this stream.
2.
3. (a)
4. (a)
Write function (stream-merge str1 str2) that takes 2 streams in increasing order, and returns the stream that contains all of those values in sorted (increasing) order without repeats. Note that each input stream is sorted without repeats, but the same element could occur in both lists.
5.
(b) Useyourmergefunctiontoproducethesortedstreamofpositiveintegerswhoseprimefactors are2,3and5only. i.e. allnumbersoftheform2i3j5k,fori≥0,j≥0,k≥0
Remember the golden ratio φ from homework 3? We used the identity φ = 1 + 1 to develop a φ
recursive expansion of the continued fraction φ=1+ 1
1+1 1+…
1
(b) Useyourpartialsumfunctionandthesequencein3atoproduceastreamcontainingsuccessive approximations to sin(x):
.
n (−1)k
k=0
x 2 k + 1 (2k + 1)!
for n = 0,1,2,…
specifically defining a recursive function (phi n) defined as Φ1 =2,
Φn = 1 + 1 for n > 1. Φn−1
Write a function (golden-stream) that evaluates to the infinite stream of these approximations, that is, Φ1,Φ2,Φ3,…. Hint: there are multiple ways to do this – you could use helper functions, or you could define the stream implicitly – your choice.
6. Suppose we want to generate all (i, j) pairs, such that i and j are positive integers. If ints is the stream of integers 0, 1, 2, 3, . . ., then we could use the following code:
(define (interleave s1 s2) (if (stream-null? s1)
s2
(cons-stream (stream-car s1)
(interleave s2 (stream-cdr s1)))))
(define (pairs s t) (cons-stream
(list (stream-car s) (stream-car t)) (interleave
(stream-map (lambda (x) (list (stream-car s) x)) (stream-cdr t))
(pairs (stream-cdr s) (stream-cdr t)))))
(define pairs-stream (pairs (stream-cdr ints)(stream-cdr ints)))
Try this code, and examine the order of the pairs in pairs-stream.
It would be nice to be able to generate streams in which the pairs appear in some useful order, rather than in the order that results from an ad hoc interleaving process. We can use a technique similar to the merge procedure from the last lab, if we define a way to say that one pair of integers is “less than” another. One way to do this is to define a “weighting function” W and stipulate that x < y if if W(x) < W(y). To compare pairs, W must be a function that takes one pair as a parameter and returns some numeric value.
- (a) Write a procedure merge-weighted that is like merge, except that merge-weighted takes an additional argument weight, which is a procedure that computes the weight of a stream el- ement, and is used to determine the order in which elements should appear in the resulting merged stream. Notice that although merge-weighted should not allow duplicates, it may be the case that W(x) = W(y) for some x and y values, even though x and y are not dupli- cates. As with merge, you can assume that the inputs are sorted with respect to the weighting function.
- (b) Using merge-weighted, generalize pairs to a function weighted-pairs that takes two streams, together with a procedure that computes a weighting function, and generates the stream of pairs, ordered according to weight.
2
(c) Use your weighted-pairs procedure to generate the stream of all pairs of positive integers (i,j) with the pairs ordered according to the sum i + j.
(d) Numbers that can be expressed as the sum of two cubes in more than one way are sometimes called Ramanujan numbers, in honor of the mathematician Srinivasa Ramanujan. Ordered streams of pairs provide an elegant solution to the problem of computing these numbers. To find a number that can be written as the sum of two cubes in two different ways, we need only generate the stream of pairs of integers (i, j) weighted according to the sum i3 + j3, then search the stream for two consecutive pairs with the same weight. Write a function (ramanujan n) that returns the nth Ramanujan number. The first such number is 1729 (What a coincidence!). What are the next five?
Hint: an incremental approach is best for this last one – first write code to generate the stream of pairs ordered by sum of cubes, and work from there. The most elegant way to write (ramanujan n) would be to use stream-nth on the stream of Ramanujan numbers, but alternative approaches are possible.
3