Table of Contents

cs12ps23as12: Generator Functions and Infinite Sequences

Goals


Prerequisites

This assignment requires familiarity with the lecture materials presented in class through week 12.


Background

Fibonacci Numbers and the Golden Ratio

The Fibonacci spiral: an approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling

We know that the Fibonacci sequence is defined as a sequence in which each number is the sum of the two preceding numbers, i.e.:

$$ \begin{aligned} F_{0} &= 0 \\ F_{1} &= 1 \\ F_{n} &= F_{n-1} + F_{n-2} \text{ for n > 1} \end{aligned} $$

The beginning of the Fibonacci sequence is then: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

The Fibonacci sequence is closely related to the golden ratio (φ) in various ways. One relationship is that the ratio of consecutive Fibonacci numbers gets closer and closer to (i.e., converges to) φ as n increases. That is,

$$ \begin{aligned} φ &\approx \frac{F_{n+1}}{F_{n}} & \text{more precise as n increases}\\ &= \lim_{n\to\infty}\frac{F_{n+1}}{F_n} & \text{formally via limit notation} \end{aligned} $$

The golden ratio is an irrational number and therefore can't be expressed as the ratio of two integers. However, it can be expressed in the following forms and approximations:

$$ \begin{aligned} φ &= \frac{1 + \sqrt{5}}{2} & \text{as a closed-form solution} \\ &= \sqrt{1 + \sqrt{1 + \sqrt{1 + \cdots}}} & \text{as a nested radical} \\ &\approx 1.618033988749895 & \text{as an approximate decimal value} \\ \end{aligned} $$

Padovan and Perrin Numbers and the Plastic Number

Spiral of equilateral triangles with side lengths which follow the Padovan sequence.

Spiral of equilateral triangles with side lengths which follow the Perrin sequence.

Two other sequences, very similar to the Fibonacci sequence, exhibit some similar characteristics. The Padovan sequence and the Perrin sequence are identical except for their starting points:

$$ \begin{aligned} Padovan_{0} &= 1 \\ Padovan_{1} &= 1 \\ Padovan_{2} &= 1 \\ Padovan_{n} &= Padovan_{n-2} + Padovan_{n-3} \text{ for n > 2} \end{aligned} $$

The beginning of the Padovan sequence is then: 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, …

$$ \begin{aligned} Perrin_{0} &= 3 \\ Perrin_{1} &= 0 \\ Perrin_{2} &= 2 \\ Perrin_{n} &= Perrin_{n-2} + Perrin_{n-3} \text{ for n > 2} \end{aligned} $$

The beginning of the Perrin sequence is then: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, …

These sequences are related to the plastic number (ρ) much like the Fibonacci sequence is related to the golden ratio. One relationship is that the ratio of consecutive Padovan or Perrin numbers gets closer and closer to (i.e., converges to) ρ as n increases. That is,

$$ \begin{aligned} ρ &\approx \frac{Padovan_{n+1}}{Padovan_{n}} & \text{more precise as n increases} \\ &= \lim_{n\to\infty}\frac{Padovan_{n+1}}{Padovan_n} & \text{formally via limit notation} \\ &\approx \frac{Perrin_{n+1}}{Perrin_{n}} & \text{more precise as n increases} \\ &= \lim_{n\to\infty}\frac{Perrin_{n+1}}{Perrin_n} & \text{formally via limit notation} \end{aligned} $$

The plastic number is an irrational number and therefore can't be expressed as the ratio of two integers. However, it can be expressed in the following forms and approximations:

$$ \begin{aligned} ρ &= \sqrt[3]{\frac{9+\sqrt{69}}{18}}+\sqrt[3]{\frac{9-\sqrt{69}}{18}} & \text{as a closed-form solution} \\ &= \sqrt[3]{1 + \sqrt[3]{1 + \sqrt[3]{1 + \cdots}}} & \text{as a nested radical} \\ &\approx 1.324717957244746 & \text{as an approximate decimal value} \\ \end{aligned} $$


Assignment

You shall implement the functions described in module recurrence.py below. Pay close attention to the function docstrings as well as the doctests within the docstrings that illustrate the expected behavior.

  • Use exponentiation to calculate square and cube roots. As of Python 3.11 there is a math.cbrt() function in addition to math.sqrt(), but since we don't have 3.11 on the server just yet, stick with exponentiation:
    2**(1 / 2)  # square root of 2
    2**(1 / 3)  # cube root of 2
  • Take advantage of the embedded doctests to test your work. You can run them by telling the interpreter to use the doctest module as the main module and giving it recurrence.py to test:
    python -m doctest recurrence.py     # output only failed tests
    python -m doctest -v recurrence.py  # verbose output

Starter Code

recurrence.py
"""
This module implements several functions in order to practice with generators.
 
Function docstrings also have extended info on parameters and return values, as well as doctests,
which are a way of embedding runnable tests in docstrings.
https://docs.python.org/3/library/doctest.html
 
python -m doctest recurrence.py     # output only failed tests
python -m doctest -v recurrence.py  # verbose output
"""
 
from typing import Generator, Callable
 
 
def fibonacci() -> Generator[str, None, None]:
  """
  Yields an infinite sequence of Fibonacci numbers.
  See: https://en.wikipedia.org/wiki/Fibonacci_number
 
  >>> [fib for (idx, fib) in zip(range(10), fibonacci())]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
  """
  # We did this in class, so it's good to go:
  previous, current = 0, 1
  yield previous
  yield current
  while True:
    previous, current = current, previous + current
    yield current
 
 
def padovan() -> Generator[str, None, None]:
  """
  Yields an infinite sequence of Padovan numbers.
  See: https://en.wikipedia.org/wiki/Padovan_sequence
 
  >>> [pad for (idx, pad) in zip(range(10), padovan())]
  [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
  """
  pass  # TODO
 
 
def perrin() -> Generator[str, None, None]:
  """
  Yields an infinite sequence of Perrin numbers.
  See: https://en.wikipedia.org/wiki/Perrin_number
 
  >>> [per for (idx, per) in zip(range(10), perrin())]
  [3, 0, 2, 3, 2, 5, 5, 7, 10, 12]
  """
  pass  # TODO
 
 
def phi(terms: int) -> float:
  """
  Recursively calculates the golden ratio (often denoted as the Greek letter ϕ, i.e. "phi")
  via its nested radical representation.
  See: https://en.wikipedia.org/wiki/Golden_ratio
 
  :param terms: the number of formula terms to calculate, assumed to be positive
  :return: phi calculated to the requested number of terms
 
  >>> phi(1) == 1**(1 / 2)
  True
  >>> phi(2) == (1 + 1**(1 / 2))**(1 / 2)
  True
  >>> phi(3) == (1 + (1 + 1**(1 / 2))**(1 / 2))**(1 / 2)
  True
  >>> phi(4) == (1 + (1 + (1 + 1**(1 / 2))**(1 / 2))**(1 / 2))**(1 / 2)
  True
  """
  pass  # TODO
 
 
def rho(terms: int) -> float:
  """
  Calculates the plastic number (often denoted as the Greek letter ρ, i.e. "rho")
  via its nested radical representation.
 
  :param terms: the number of formula terms to calculate, assumed to be positive
  :return: rho calculated to the requested number of terms
 
  >>> rho(1) == 1**(1 / 3)
  True
  >>> rho(2) == (1 + 1**(1 / 3))**(1 / 3)
  True
  >>> rho(3) == (1 + (1 + 1**(1 / 3))**(1 / 3))**(1 / 3)
  True
  >>> rho(4) == (1 + (1 + (1 + 1**(1 / 3))**(1 / 3))**(1 / 3))**(1 / 3)
  True
  """
  pass  # TODO
 
 
def most_precise(function: Callable):
  """
  Calls a function with successively larger positive integer arguments (starting from 1)
  until the function returns the same value twice in succession. Meant to work with
  functions like rho and phi in this module, e.g. most_precise(rho) will repeatedly call rho
  requesting more terms in the calculationuntil two successive calls return the same value.
 
  :param function: the function to call with successively larger arguments
  :return: the first repeated return value
 
  >>> most_precise_phi = most_precise(phi)
  >>> most_precise_phi == phi(32)  # nested-radical phi should hit peak precision at 32 terms
  True
  >>> most_precise_phi == (1 + 5**(1 / 2)) / 2  # closed-form solution should be equal
  True
  >>> # verify the relationship between Fibonacci sequence and phi (30 terms, within a billionth)
  >>> fib_30 = [fib for (idx, fib) in zip(range(30), fibonacci())]
  >>> abs(fib_30[-1] / fib_30[-2] - most_precise_phi) < 1e-9
  True
  >>>
  >>> most_precise_rho = most_precise(rho)
  >>> most_precise_rho == rho(24)  # nested-radical rho should hit peak precision at 24 terms
  True
  >>> most_precise_rho == ((9 - 69**(1 / 2)) / 18)**(1 / 3) + (
  ...       (9 + 69**(1 / 2)) / 18)**(1 / 3)  # closed-form solution should be equal
  True
  >>> # verify the relationship between the Padovan/Perrin sequences and rho
  >>> padovan_60 = [pad for (idx, pad) in zip(range(60), padovan())]
  >>> abs(padovan_60[-1] / padovan_60[-2] - most_precise_rho) < 1e-9
  True
  >>> perrin_60 = [per for (idx, per) in zip(range(60), perrin())]
  >>> abs(perrin_60[-1] / perrin_60[-2] - most_precise_rho) < 1e-9
  True
  """
  pass  # TODO

Submission

Submit recurrence.py via turnin.

Feedback Robot

This project has a feedback robot that will run some tests on your submission and provide you with a feedback report via email within roughly one minute.

Please read the feedback carefully.

Due Date and Point Value

Due at 23:59:59 on the date listed on the syllabus.

Assignment 12 is worth 60 points.

Possible point values per category:
---------------------------------------
phi()                                12
rho()                                12
padovan()                            12
perrin()                             12
most_precise()                       12
Possible deductions:
  Style and practices            10–20%
---------------------------------------