# 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]$. ### 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{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{n}$ is irrational (i.e., that it can not be true that $\sqrt{n} - \sqrt{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{27}=3$. Thus $\sqrt{n} - \sqrt{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:
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