Midterm 1 Review

Complete the following questions.

Standard imports

In [ ]:
import numpy as np
import matplotlib.pyplot as plt
import math as m
from mpmath import mp, iv

1. Working with lists.

Write a function odd_sublist(lst) which takes as input a list lst of integers and returns a list containing only the odd integers, in the same order.

In [ ]:
# Tests: Should not produce errors
assert odd_sublist([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) == [1, 3, 5, 7, 9]
assert odd_sublist([1, 1, 2, 3, 5, 8, 13, 21]) == [1, 1, 3, 5, 13, 21]
assert odd_sublist([101, 1001, 10001]) == [101, 1001, 10001]
assert odd_sublist([2, 4, 8, 16, 32, 64]) == []

2. Volume of a cylinder

Write a function cylinder_volume(r, h) which returns the volume of a cylinder of radius $r>0$ and height $h>0$.

In [ ]:
# Tests that should be passed
assert abs(cylinder_volume(1, 1) - 3.141592653589793) < 10**-8
assert abs(cylinder_volume(0.5641895835477563, 5) - 5) < 10**-8
assert abs(cylinder_volume(10, 2) - 628.3185307179587) < 10**-8
assert abs(cylinder_volume(10, 10) - 3141.5926535897934) < 10**-8

3. Function plotting

Use matplotlib to plot the function $sin(\frac{1}{x})$ using $10001$ values of $x$ equally spaced in the interval $[0.00001, 1.00001]$.

**Check your work:** Your plot should look something like this:

4. Counting the elements in a list.

Write a function count_small_elements(lst, epsilon) which takes as input a list lst of real numbers and an $\epsilon>0$, and returns the number of real numbers $x$ in lst such that $|x|<\epsilon$.

For example count_small_elements([0.1, 0.5, 1.1, 2], 1) should return $2$.

In [ ]:
# Tests:
assert count_small_elements([0.1, 0.5, 1.1, 2], 1) == 2
assert count_small_elements(list(range(100)), 50) == 50
assert count_small_elements([x/4 for x in range(-100,101)], 3.7) == 29

5. Evaluating a series

Consider the series $$\sum_{k=0}^\infty \frac{1}{1+\sqrt{k}}.$$ Let $S_N$ be the partial sum consisting of the sum of the first $N$ terms. Compute the smallest $N$ such that $$|S_N - S_{N-1}| < \frac{1}{30 \pi}.$$ Store the value of $N$ in the variable N_stop and store the value of $S_N$ in the variable partial_sum_stop.

In [ ]:
assert N_stop == 8696, "N_stop is wrong."
assert (partial_sum_stop - 178.06448) < 10**-3, "partial_sum_stop is wrong."

6. Working with different bases

Write a function base7(n) which takes as input an integer $n > 0$ and converts it to a string storing its representation in base $7$. The returned string will consist only of the characters in the set $\{0,1,2,3,4,5,6\}$.

For example, the number $67$ in base $7$ is is given by 124 since $$67 = 1 \cdot 7^2 + 2 \cdot 7 + 4.$$ Thus base7(67) should return the string '124'.

In [ ]:
# Tests
assert base7(6) == '6', 'Failed for n = 6.'
assert base7(49) == '100', 'Failed for n = 49.'
assert base7(67) == '124', 'Failed for n = 67.'
assert base7(151235) == '1166630', 'Failed for n = 151235.'
assert base7(6723477342423466) == '4062124131215314042', 'Failed for n = 6723477342423466.'

7. Rigorous comparisons

Write a function root_difference_less_than(n, p, q) which takes as input integers $n$, $p$, and $q$ and returns True if $$\sqrt{n} - \sqrt[3]{n} < \frac{p}{q}.$$ The function should return False if the inequality is not true. You can assume that $q \neq 0$ and that the quantity $\sqrt{n} - \sqrt[3]{n}$ is irrational (i.e., that it can not be true that $\sqrt{n} - \sqrt[3]{n}=\frac{p}{q}$.)

Use interval arithmetic at increasing precision to be sure that your answer is always correct, even if the integers involved are very large.

For example root_difference_less_than(27, 2, 1) should return False since $\sqrt{27} \in (5,6)$ while $\sqrt[3]{27}=3$. Thus $\sqrt{n} - \sqrt[3]{n}$ lies in the interval $(2,3)$, and we are comparing to the fraction $2/1$.

In [ ]:
# Tests
assert not root_difference_less_than(27, 2, 1)
assert root_difference_less_than(27, 9, 4)
assert not root_difference_less_than(2, 39167, 253849)
assert not root_difference_less_than(3, 266312747, 918949655)
assert not root_difference_less_than(5, 3503460365364981558547916427985849, 
                                     6659405883574539501104899156429155)
assert not root_difference_less_than(6, 
    12937268231607778583821492269711419883137751358, 
    20458411408288108829612787097012200189720135111)

8. Significant digits

Find the value of $\frac{22}{7} - \pi$ to $20$ significant digits. Store the answer as a string in the variable pi_approx_difference. Do not use exponential notation.

Your answer should differ be within one least significant digit from the true value. Note the true value has the form $0.00126\ldots$, so differing by one least significant digit means that abs(\frac{22}{7} - pi - pi_approx_difference) should be less than $10^{-22}$.

In [ ]:
# Tests:
# The correct answer is '0.0012644892673496186802' but nearby answers are acceptable:
assert '0.0012644892673496186802' == pi_approx_difference or \
    '0.0012644892673496186801' == pi_approx_difference or \
    '0.0012644892673496186803' == pi_approx_difference

9. ArcTan

Inverse tangent is an analytic function. It's Taylor series centered at the origin is given by $$\tan^{-1}(x) = x - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7} +\ldots.$$ This series converges for values of $x \in [-1,1]$.

Write a function arctan_partial_sum(x, d) which takes as input a float $x \in [-1,1]$ and an integer $d$ and returns the Taylor polynomial of degree $d$ evaluated at $x$. Use Python's built in floats to carry out the calculation.

In [ ]:
assert abs(arctan_partial_sum(0.5, 0)) < 10**-8, "Error with input (0.5, 0)."
assert abs(arctan_partial_sum(0.3,1)-0.3) < 10**-8, "Error with input (0.3,1)."
assert abs(arctan_partial_sum(0.7,2)-0.7) < 10**-8, "Error with input (0.7,2)."
assert abs(arctan_partial_sum(0.5,10)-0.46368427579365) < 10**-8, \
    "Error with input (0.5,10)."
assert abs(arctan_partial_sum(1,100) - 0.7803986631477527) < 10**-8, \
    "Error with input (1,100)."

10. ArcTan, continued

The usual form for the remainder in the Taylor series is not immediately useful, since it requires us to control high order derivatives of $\tan^{-1}$.

However, observe that the degree $d$ term of the Taylor series for $\tan^{-1}$ has absolute value less than $|x|^d$. Thus the remainder $R_d(x)-\tan^{-1}(x)$ satisfies $$-\sum_{k=d+1}^\infty |x|^k < R_d(x) < \sum_{k=d+1}^\infty |x|^k.$$ Observe that $\sum_{k=d+1}^\infty |x|^k$ is a geometric series and can be evaluated by a standard formula.

Write a function arc_tan_degree(x, epsilon) which takes as input an $x \in (-1,1)$ and an $\epsilon>0$ and returns an integer $d$ such that $|R_d(x)|<\epsilon$.

Use your function to compute $\tan^{-1}(\frac{1}{2})$ correct to $8$-significant digits. Store the result as a float in the variable arc_tan_half.

You can use floats and ignore the effects of round off error.

**Remark:** This problem would be too hard and time consuming for a test, but it is still good practice.

In [ ]:
## Tests
assert abs(arc_tan_half - m.atan(0.5)) < 10**-8
assert arc_tan_degree(0.25, 100) == 0
assert abs(arctan_partial_sum(0.25, arc_tan_degree(0.25, 0.5*10**-4)) - m.atan(0.25)) < 10**-4
assert abs(arctan_partial_sum(0.75, arc_tan_degree(0.75, 0.5*10**-6)) - m.atan(0.75)) < 10**-6

11. Fibonacci numbers

The Fibonacci numbers are defined inductively by $F_0=1$, $F_1=1$ and $$F_{n+1}=F_n + F_{n-1} \quad \text{for all $n \geq 1$.}$$

Write a function fibonacci(n) which computes the number $F_n$ for integers $n \geq 0$.

The first few values are printed below: $$F_0 = 1,~F_1 = 1,~F_2 = 2,~F_3 = 3,~F_4 = 5,~F_5 = 8,~F_6 = 13,~F_7 = 21,~F_8 = 34,~F_9 = 55.$$

In [ ]:
# Tests
assert fibonacci(0) == 1
assert fibonacci(1) == 1
assert fibonacci(2) == 2
assert fibonacci(3) == 3
assert fibonacci(4) == 5
assert fibonacci(5) == 8
assert fibonacci(6) == 13
assert fibonacci(7) == 21
assert fibonacci(8) == 34
assert fibonacci(9) == 55
assert fibonacci(10) == 89
assert fibonacci(11) == 144
assert fibonacci(12) == 233
assert fibonacci(13) == 377
assert fibonacci(14) == 610
assert fibonacci(15) == 987
assert fibonacci(16) == 1597
assert fibonacci(17) == 2584
assert fibonacci(18) == 4181
assert fibonacci(19) == 6765
assert fibonacci(20) == 10946
assert fibonacci(21) == 17711
assert fibonacci(22) == 28657
assert fibonacci(23) == 46368
assert fibonacci(24) == 75025
assert fibonacci(25) == 121393
assert fibonacci(26) == 196418
assert fibonacci(27) == 317811
assert fibonacci(28) == 514229
assert fibonacci(29) == 832040

12. Inductive Proof

Inductively prove that if $n \geq 7$, then $F_n > 1.5^n$.

Hint: Show by computation that $F_7 > 1.5^7$ and $F_8 > 1.5^8$. Argue that if $F_n > 1.5^n$ and $F_{n-1} > 1.5^{n-1}$, then $F_{n+1} > 1.5^{n+1}$ using the fact that $F_{n+1}=F_n+F_{n-1}$.

13. Series involving Fibonacci numbers

Consider the series $$X = \sum_{n=0}^\infty \frac{1}{F_n}$$ where $F_n$ is the $n$th Fibonacci number. Let $S_N$ be the partial sum consisting of the first $N$ terms. Write a function fibonacci_partial_sum(N) which returns $S_N$.

In [ ]:
# Tests
assert abs(fibonacci_partial_sum(1) - 1.0) < 10**-8
assert abs(fibonacci_partial_sum(2) - 2.0) < 10**-8
assert abs(fibonacci_partial_sum(3) - 2.5) < 10**-8
assert abs(fibonacci_partial_sum(4) - 2.8333333333333335) < 10**-8
assert abs(fibonacci_partial_sum(5) - 3.0333333333333337) < 10**-8
assert abs(fibonacci_partial_sum(6) - 3.1583333333333337) < 10**-8
assert abs(fibonacci_partial_sum(7) - 3.2352564102564108) < 10**-8
assert abs(fibonacci_partial_sum(8) - 3.282875457875458) < 10**-8
assert abs(fibonacci_partial_sum(9) - 3.3122872225813405) < 10**-8

14. Approximation of series.

Use the fact that $F_n > 1.5^n$ for $n \geq 7$ to compute an upper bound on the remainder $R_N = X - S_N$ for value of $N \geq 7$.

Note that all terms are positive, so $R_N>0$.

Use what you learned to write a function series_approx(epsilon) which takes as input an $\epsilon>0$ and returns a real number $Y$ such that $|X-Y|<\epsilon$ where $X=\sum_{n=0}^\infty \frac{1}{F_n}$.

Hint: If you know $R_N < 2 \epsilon$, then $S_N+\epsilon$ is within $\epsilon$ of the limit $X$ (i.e., $|X - (S_N+\epsilon)|<\epsilon$.)

You can use floating point arithmetic and ignore the effects of round of error.

Use your function to compute the value of $X$ to $8$ significant digits. Store the result as a float in the variable X_approx.

In [ ]:
## TESTS:
assert abs(X_approx - 3.3598857) < 1.1*10**-7
assert abs(series_bound(0.5*10**-12) - 3.359885666243673) < 1.1*10**-12