\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}
\usepackage{graphicx}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math373}{Homework 1}{Due Wed, Jan. 18, 2023}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\item {} The Caesar cipher.
\begin{enumerate}
	\item Encrypt the message ``exchange all assets'' using a Caesar cipher with a forward shift of 5 characters.
	\item Decrypt the following message, which has been encoded with a Caesar cipher.
	\begin{center}
\begin{verbatim}
DPYLA OLTVU LFAVT VYYVD
\end{verbatim}
	\end{center}
\end{enumerate}

\item {} [JJJ 1.\{9,10\}.c] \textbf{Note: This problem is moved to HW2.}  Let $d=\gcd(16261,85652)$.  Use the extended Euclidean algorithm to find integers $u$ and $v$ such that $16261u + 85652v = d$.

\item {} \emph{Practice with large numbers.}  Define a sequence of numbers $a_0,a_1,a_2,\ldots$ recursively by $a_0 = a_1 = a_2 = 1$ and $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ for $n\ge 3$.  For example, $a_3 = a_2 + a_1 + a_0 = 1 + 1 + 1 = 3$ and $a_4 = a_3 + a_2 + a_1 = 3 + 1 + 1 = 5$.  Also, $a_{10} = 193$ and $a_{20} = 85525$.
\begin{enumerate}
	\item Consider the following recursive algorithm for computing $a_n$.
	\begin{algo}
		\textul{$A(n)$}:\+\\
			if $n \le 2$ then\+\\
				return 1\-\\
			\\
			return $A(n-1) + A(n-2) + A(n-3)$
	\end{algo}
	Comment on the efficiency of this code.  What is the run-time of this algorithm?  
	\item Give a more efficient algorithm to compute $a_n$.
	\item What are $a_{16}$ and $a_{55}$?  
	\item Define a new sequence $b_n$ such that $b_n$ is the sum of the digits in $a_n$.  For example, since $a_{10} = 193$, we have that $b_{10} = 1 + 9 + 3 = 13$ and since $a_{20} = 85525$, we have that $b_{20} = 8 + 5 + 5 + 2 + 5 = 25$.  What is $b_{20000}$?  Note: \texttt{fib.py} contains a function \texttt{digit\_sum(n)} that computes the sum of the digits in $n$.
\end{enumerate}

\end{enumerate}
\end{document}
