Due by 9:00pm on 11/16

Instructions

Download hw11.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.

Submission: When you are done, submit the homework by uploading the `hw11.py` file to okpy.org. You may submit more than once before the deadline; only the final submission will be scored.

Readings: This homework relies on following references:

Question 1: Scale

Implement the generator function `scale(s, k)`, which yields elements of the given iterable `s`, scaled by `k`.

``````def scale(s, k):
"""Yield elements of the iterable s scaled by a number k.

>>> s = scale([1, 5, 2], 5)
>>> type(s)
<class 'generator'>
>>> list(s)
[5, 25, 10]

>>> m = scale(naturals(), 2)
>>> [next(m) for _ in range(5)]
[2, 4, 6, 8, 10]
"""

Use OK to test your code:

``python3 ok -q scale --local``

Question 2: Merge

Implement `merge(s0, s1)`, which takes two iterables `s0` and `s1` whose elements are ordered. `merge` yields elements from `s0` and `s1` in sorted order, eliminating repetition. You may also assume `s0` and `s1` represent infinite sequences; that is, their iterators never raise `StopIteration`.

See the doctests for example behavior.

``````def merge(s0, s1):
"""Yield the elements of strictly increasing iterables s0 and s1 and
make sure to remove the repeated values in both.
You can also assume that s0 and s1 represent infinite sequences.

>>> twos = scale(naturals(), 2)
>>> threes = scale(naturals(), 3)
>>> m = merge(twos, threes)
>>> type(m)
<class 'generator'>
>>> [next(m) for _ in range(10)]
[2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
"""
i0, i1 = iter(s0), iter(s1)
e0, e1 = next(i0), next(i1)

Use OK to test your code:

``python3 ok -q merge --local``

Question 3: Remainder generator

Like functions, generators can also be higher-order. For this problem, we will be writing `remainders_generator`, which yields a series of generator objects.

`remainders_generator` takes in an integer `m`, and yields `m` different generators. The first generator is a generator of multiples of `m`, i.e. numbers where the remainder is 0. The second, a generator of natural numbers with remainder 1 when divided by `m`. The last generator yield natural numbers with remainder `m - 1` when divided by `m`.

``````def remainders_generator(m):
"""
Takes in an integer m, and yields m different remainder groups
of m.

>>> remainders_mod_four = remainders_generator(4)
>>> for rem_group in remainders_mod_four:
...     for _ in range(3):
...         print(next(rem_group))
0
4
8
1
5
9
2
6
10
3
7
11
"""

Note that if you have implemented this correctly, each of the generators yielded by `remainder_generator` will be infinite - you can keep calling `next` on them forever without running into a `StopIteration` exception.

Hint: Consider defining an inner generator function. What arguments should it take in? Where should you call it?

Use OK to test your code:

``python3 ok -q remainders_generator --local``

Question 4: Primes

Write a generator that generates prime numbers. Fill out the `is_prime` helper function and use that to create your generator.

``````def is_prime(n):
"""
Return True if n is prime, false otherwise.

>>> is_prime(1)
False
>>> is_prime(2)
True
>>> is_prime(19)
True
"""
``````def primes():
"""
An infinite generator that outputs primes.

>>> p = primes()
>>> for i in range(3):
...     print(next(p))
...
2
3
5
"""
``python3 ok -q is_prime --local``
``python3 ok -q primes --local``