
\documentclass[11pt]{article}

%\usepackage{customizations}
\usepackage{listings}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[enableskew]{youngtab}
\usepackage{hyperref}
\usepackage{graphicx}
\newtheorem{theorem}{Theorem}
\usepackage{seqsplit}

\renewcommand{\mod}[1]{\ensuremath{\;\textrm{mod }{#1}}}
\usepackage[all]{xy}



\textwidth=15cm
\oddsidemargin=0.7cm
\voffset=-1cm
\textheight=20cm

\begin{document}

\newcommand{\x}{\times}

\title{
  MATH 157: Mathematics in the world \\
  \Large{Homework 4 (Due March 5th, 2019 at 1:00PM)}
}
\date{}

\maketitle

\vspace{-1cm}

\textbf{Please solve the first 4 problems completely. You can choose to solve 1 of the last 2 problems. The higher one will be scored if you decide to do both.}

If you run into any issues, please do not hesitate to consult the Python documentation and post in the ``Python questions'' discussion on Canvas.

\subsection*{Problem 1}

Write a paragraph explaining each of the following techniques in your own words:
\begin{enumerate}
\item
  proof by contradiction,
\item
  proof by induction.
\end{enumerate}


\subsection*{Problem 2}

\begin{enumerate}
\item If $p$ and $q$ are prime numbers greater than $3$, show that
\[
p^2 - q^2
\]
is divisible by $24$.
\footnote{
  Given an integer $n$, study the possible remainders of $n^2$ modulo $3$ and $8$.
}

\item Prove that if $ac = bc \mod p$ and $(c,p) = 1$, then $a = b \mod p$.

\end{enumerate}





\subsection*{Problem 3}

\begin{enumerate}
\item
  Find all primes of the form $n^3 - 1$ where $n$ is a positive integer.  
\item
  Find all primes of the form $n^3 + 1$ where $n$ is a positive integer.  
\end{enumerate}

In both parts, make sure to provide an argument showing your list is complete.



\subsection*{Problem 4}
In class, we discussed the RSA encryption algorithm.
To setup your own RSA encryption, one of the steps is to find $rs = 1 \mod (p-1)(q-1)$.

In this question, you are guided to use Euclid's algorithm to find the integer $s$ given $r$ and $m = (p-1)(q-1)$.

The following identity (see \url{https://en.wikipedia.org/wiki/Bézout\%27s_identity})
will be very handy:
\begin{theorem}[B\'ezout's identity]
Let $a$ and $b$ be integers with greatest common divisor $(a,b) = d$. Then, there exist integers $x$ and $y$ such that $ax + by = d$. More generally, the integers of the form $ax + by$ are exactly the multiples of $d$.
\end{theorem}

We will now use the following recursion to compute the coefficients $x, y$ in the B\'ezout's identity.
Let $a, b$ be two integers, which are not both $0$.
\begin{enumerate}
\item If $b = 0$, what are the values of $x, y, d$?
\item If $a = n*b + r$, and $bx' + r y' = d'$, what are the values of $x, y, d$ in terms of $x', y', d', a, b$?
\item Using the above recursive formula, write a python function \texttt{Egcd} which takes two integers $a, b$ as input, and produces $x, y$ and the GCD $(a,b)$ as output.
 	\footnote{You may use $a // b$ to find the largest $n$ so that $b*n \leq a$. Your code can be as short as 6 lines.} 
	
\item If $(r, m) = 1$, then we can find the integer $s$ such that $rs = 1 \mod m$ using the previous function \texttt{Egcd} by setting $a = r, b = m$.
Write a function \texttt{Inverse} which takes two integers $r, m$ as input, and produces $s$ such that $rs = 1 \mod m$ as output.
	\footnote{You may call the function \texttt{Egcd}. Your code can be as short as 3 lines.} 
	
\item Find the value $s$ for $r = 11189203$ and $m = 20192020$.
\end{enumerate}








\subsection*{Problem 5}

This exercise will help us count in how many ways we can arrange 8 peaceful queens on a chess board. Since the possible moves of a queen subsume those of a rook, it follows that an arrangement of peaceful queens is necessarily an arrangement of peaceful rooks as well. We already know that the latter correspond to the permutations of 8 elements, so it suffices to iterate through these and keep track of the arrangements which are also valid in the case of queens.

The second purpose of the problem is to introduce a number of Python constructs which make programming quicker, more natural, and closer to the way we think mathematically. Even though the code can be surprisingly short, I would encourage you to take sufficient time and understand its meaning. Read the footnotes for suggestions and hints.

\begin{enumerate}
\item
  Use \texttt{itertools.petmutations} to write a program which prints all permutations of $0$, $1$, and $2$.
  \footnote{See \url{https://docs.python.org/2/library/itertools.html\#itertools.permutations}. The idea here is to iterate through \texttt{itertools.permutations(range(3))}.}

\item
  Write a function \texttt{distinct\_elements} which verifies whether a list/tuple contains distinct elements.
  \footnote{Given an input $X$, the simplest solution is to convert it to a set and check that its size is the same as that of $X$. See \url{https://docs.python.org/2/library/stdtypes.html\#set}.}

\item
  Write a function \texttt{is\_peaceful} which verifies whether a permutation of size $n$ corresponds to a peaceful arrangement of $n$ queens on an $n \x n$ board.
  \footnote{Given a permutation, the arrangement it corresponds to already contains only one figure in every row and column. It suffices to check that each forward and backward diagonal contains a single figure each.

    Hint: If an arrangement is given as a permutation sequence $s_i$ for $i = 0, \dots, n-1$, what do the sequences $s_i + i$ and $s_i - i$ tell us about the diagonals? Don't forget to use comprehension to construct these. See \url{https://docs.python.org/2/tutorial/datastructures.html\#list-comprehensions}.}

\item
Write a function which counts the number of $n$ peaceful queen arrangements on a board of size $n$.

\item
  For each $n = 1, \dots, 10$, compute the number of $n$ peaceful queen arrangements on a board of size $n \x n$.
\end{enumerate}

\noindent\textbf{Remark.} The algorithm we described in this exercise is not optimal. The main shortcoming rests on the following observation. When enumerating the permutations of $\{1, \dots, n\}$ in lexicographic order, the first $(n-2)!$ entries start with $1,2$. All of these correspond to queen arrangements which exhibit a clash between the figures in the first two columns. Our current implementation does not recognize this optimization, and hence goes through all possible permutations.

\noindent A better solution uses backtracking to construct admissible arrangements step by step. See \url{http://en.wikipedia.org/wiki/Backtracking}.













\subsection*{Problem 6}

\href{http://en.wikipedia.org/wiki/Logo_\%28programming_language\%29}{Logo} is an educational programming language designed to introduce computers to children by using graphics. The premise is that you control a \href{http://en.wikipedia.org/wiki/Turtle_graphics}{turtle} which walks in the plane. As the turtle moves, we see the path it traces. For example, the following commands trace out a square.

%\lstinputlisting[language=Logo]{square.logo}

%\begin{center}
%  \includegraphics[width=0.5\textwidth]{square_logo.png}
%\end{center}

While Python is not the same as Logo, there is a \href{https://docs.python.org/2/library/turtle.html}{standard library} which has very similar functionality. The following program draws a square in Python.

%\lstinputlisting[language=Logo]{square.py}

Fractal curves are customarily used to teach recursion. In this exercise, we will learn how to draw the Koch curve shown below.

%\begin{center}
%  \includegraphics[width=0.5\textwidth]{koch_5.png}
%\end{center}

It looks complicated but turtle graphics make this quite easy. We will call the straight line, a Koch curve of order 0. To get to order 1, we subdivide the order 0 segment in three and replace the middle part with a triangle up. Note that the order 1 curve consists of four segments. We will use this shape as a template. In general, to construct an order $n$ Koch curve, we start with the template. Instead of drawing four segments, we place four curves of order $n-1$ in their place. The following table illustrates the first few Koch curves.

%\begin{center}
%  \begin{tabular}{cc}
%  \includegraphics[width=0.45\textwidth]{koch_0.png} &
%  \includegraphics[width=0.45\textwidth]{koch_1.png} \\
%  Order 0 &
%  Order 1 \\
%  \includegraphics[width=0.45\textwidth]{koch_2.png} &
%  \includegraphics[width=0.45\textwidth]{koch_3.png} \\
%  Order 2 &
%  Order 3 \\
%  \includegraphics[width=0.45\textwidth]{koch_4.png} &
%  \includegraphics[width=0.45\textwidth]{koch_5.png} \\
%  Order 4 &
%  Order 5
%  \end{tabular}
%\end{center}

\begin{enumerate}
\item
  Write a program which draws an equilateral triangle with side length $300$.

\item
  Write a function \texttt{koch} which takes two arguments, order and width, and draws a Koch curve with the appropriate specifications.
  \footnote{
    Hint: This sounds harder than it really is. If the order is 0, all we need to do is move the turtle forward the specified length. Otherwise, if the order is positive, we first draw a curve of one lower order and length a third of the specified one, rotate appropriately, draw another Koch curve of lower order, etc. In total, if the order is positive, you should make four calls to $\texttt{koch}$ with order one less.
  }
  Use your function to draw a Koch curve of order 4 and length 300. Include the graphics in your write-up.

\item
  Use your answers to the previous two parts to write a function \texttt{snowflake} which draws a \href{http://en.wikipedia.org/wiki/Koch_snowflake}{Koch snowflake} of a given order and length. Draw a snowflake of order 4 and length 300, and include the graphics in your write-up.

%  \begin{center}
%    \includegraphics[width=0.3\textwidth]{snowflake.png} \\
%    Koch snowflake
%  \end{center}

\item
  Let $P(n, \ell)$ be the Perimeter of a Koch curve of order $n$ and length $\ell$. What is $P(0, \ell)$? Find a recursive expression for $P(n, \ell)$ in terms of $P(n-1, \ell)$.

\item
  Find a closed formula for $P(n, \ell)$ and use it to find the perimeter of the snowflake you drew.

  \item
    (Extra credit)
    Draw up to 5 other curves. If you are looking for inspiration, you can try the \href{http://en.wikipedia.org/wiki/Hilbert_curve}{Hilbert curve}, the \href{http://en.wikipedia.org/wiki/Peano_curve}{Peano curve}, \href{https://en.wikipedia.org/wiki/Sierpi?ski_curve}{Sierpi\'nski arrowhead curve}, or one of the \href{http://en.wikipedia.org/wiki/Koch_snowflake#Variants_of_the_Koch_curve}{variants of the Koch curve}. Feel free to use colors and lines of different thickness. \textbf{Be creative!}

  \end{enumerate}





\end{document}
















