% -*- compile-command: "rubber -d --unsafe hw-01-GCD.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage[num=1,date={September 4},topic=GCD\ and\ Induction]{algorithms-hw}
\begin{document}
\coversheet
This assignment has several questions that warrant proofs. Try to
emulate the proof style that we have used in class, and edit your
proofs to make sure they read well. Abstraction is crucial: that is,
identify and isolate common ideas. Write clearly and concisely or use
\LaTeX \ to typeset your solutions.
\marginnote{\qrcode{This\ is\ a\ hint!}} On homework assignments
throughout the semester, hints will be provided in QR codes in the
margin, numbered by their corresponding question.
\marginnote{\textbf{Important note}: the hints are just text, not
links! QR code readers sometimes insist on treating the text as a
link, by \emph{e.g.} using the text to do a Google search. You
should just look at the text of the hint, not the results of a
Google search. If your QR code reader does this, see if you can
turn it off in the settings. Try reading the above QR code; it
should say ``This is a hint!''} Some questions may have multiple
hints; generally the hints are in order of hintiness. If you do not
have a device capable of reading QR codes, you can find the hints in
the \verb|.tex| source for this document, linked from the course
webpage.
\section{The Euclidean Algorithm, Again}
\label{sec:euclidean}
In class we considered the problem of finding the \emph{greatest
common divisor} of two positive integers. We explored two ways to
compute the GCD:
\begin{description}
\item[Method 1] Factor the two numbers into their unique prime factorizations,
and find the biggest subset of primes contained in both; this is the
factorization of the GCD.
\item[Method 2] Run the Euclidean Algorithm.
\end{description}
In this first question, you will consider the difference
between these methods.
\begin{question}[5 points] \mbox{} \label{q:factor}
\begin{enumerate}[label=(\alph*)]
\item Use your brain, a calculator, Wolfram
Alpha\sidenote{\url{http://www.wolframalpha.com/}; try typing
\texttt{factor 170520}. You may find Wolfram Alpha to be a
helpful resource for this class; just remember to cite it when
you use its results.}, and/or some other
appropriate computational system to factor 170520 into its prime factors.
\item Now factor $522522$, and use the results to find $\gcd(170520,
522522)$ by Method 1.
\item Trace the execution of the Euclidean Algorithm on
$(170520, 522522)$. Compare and contrast the two methods of
computing the GCD of these two numbers.
\item Now try to factor the number $m$ shown below, using whatever
methods you like (for example, try using Wolfram Alpha). What
happens?
\[ m =
308903627938612635213051732991863520976852479109400884338832430641564115236537. \]
\end{enumerate}
I would be willing to bet some money that you did not succeed in
factoring $m$---though not a large amount, since there do exist
algorithms that can factor numbers of this size in a matter of hours
or even minutes\sidenote[][-2em]{On my computer,
\url{https://www.alpertron.com.ar/ECM.HTM} was able to factor $m$
in 12m13s using a self-initializing quadratic sieve (SIQS)
algorithm.}; but in any case factoring a number with, say, four
times as many digits as this would require more like
centuries. Factoring is widely believed to be a rather difficult
computational problem.\footnote{The security of your bank account probably
depends on it!}
\begin{enumerate}[label=(\alph*),resume]
\item Now, suppose I tell you that there are in fact three prime
numbers $p$, $q$, and $r$, such that
\begin{align*}
m &= p \cdot q =
308903627938612635213051732991863520976852479109400884338832430641564115236537
\\
n &= p \cdot r = 235051426595377535232357646935740625119338466495681619002059053022377525089111
\end{align*}
(this is the same number $m$ from part (a)).
\marginnote{\emph{\ref{q:factor}(e)}\quad\qrcode{Implement\ GCD\
yourself,\ or\ figure\ out\ how\ to\ call\ it\ in\ your\
favorite\ programming\ language.}} Find $p$, $q$, and $r$.
\item What does this suggest about the relative
efficiency of the two methods for computing the GCD?
\end{enumerate}
\end{question}
\section{Analyzing the Euclidean Algorithm}
From now on, when referring to the Euclidean Algorithm, we will
specifically work with the recursive implementation, \textsf{GCDR},
reproduced for convenience in Figure \ref{fig:euclidean}.
\begin{marginfigure}
\begin{acode}
\> GCDR($a$,$b$) = \\
\> \tb \> !if $b = 0$ \\
\> \> \tb \> !then \> $a$ \\
\> \> \> !else \> GCDR($b$, $a \bmod b$)
\end{acode}
\caption{The Euclidean Algorithm} \label{fig:euclidean}
\end{marginfigure}
In addition, when discussing $\gcd(a,b)$ from now on we will assume
that $a > b$. This is not a real restriction, since
$\gcd(a,b) = \gcd(b,a)$, so we can always switch the arguments if they
are in the wrong order, and if the arguments are the same,
$\gcd(a,a) = a$.
Recall that the \emph{Fibonacci numbers} $F_n$ are defined as follows:
\marginnote{You might also occasionally see a definition with $F_0 =
F_1 = 1$, but there are very good reasons for preferring the definition
with $F_0 = 0$. For example, with this definition we have nice
properties such as $m \mid n$ iff $F_m \mid F_n$, and, if we extend
to negative Fibonacci numbers in the obvious way, $F_{-n} = (-1)^{n+1} F_n$.}
\begin{align*}
F_0 &= 0 \\
F_1 &= 1 \\
F_{n+2} &= F_{n+1} + F_n
\end{align*}
That is, the first two Fibonacci numbers are $0, 1$, and then each
subsequent Fibonacci number is the sum of the previous two, so the
first few are $0, 1, 1, 2, 3, 5, 8, 13, \dots$
\begin{question}[5 points] \mbox{}
\begin{enumerate}[label=(\alph*)]
\item Compute $F_9$ and $F_{10}$, and trace the execution of the Euclidean
Algorithm to compute $\gcd(F_{10}, F_9)$. What happens?
\item Prove by induction on $n$ that $\gcd(F_{n+1}, F_n) = 1$ for all
$n \geq 0$.\marginnote{In fact, it turns out that something much
stronger is true: $\gcd(F_m, F_n) = F_{\gcd(m,n)}$! Proving
this would be well outside the scope of this assignment, but you
might be interested to explore it later.}
\item Explain why your proof also shows that the Euclidean Algorithm
requires $n$ recursive steps to compute $\gcd(F_{n+1}, F_n) = 1$.
\end{enumerate}
\end{question}
\newpage
\begin{question}[5 points] \label{q:fib-smallest} In fact, more is true:
consecutive Fibonacci numbers $(F_{n+1}, F_n)$ are in some sense a
\emph{worst-case} input for the Euclidean Algorithm: they are the
\emph{smallest} numbers for which the Euclidean Algorithm needs $n$
steps.
\begin{enumerate}[label=(\alph*)]
\item \marginnote{\emph{\ref{q:fib-smallest}}(a)\quad\qrcode{Be\
very\ careful\ to\ state\ the\ correct\ induction\
hypothesis.\ Come\ ask\ for\ help\ if\ you\ are\ unsure!}}
\marginnote[0.3em]{\emph{\ref{q:fib-smallest}}(a)\quad\qrcode{Show\
that\ a\ >=\ b\ +\ a\ mod\ b.}} Prove by induction on $n$: if
$a > b$ and the Euclidean Algorithm requires $n$ steps to compute
$\gcd(a,b)$, then $a \geq F_{n+1}$ and $b \geq F_n$.
\item Conclude that if $a \leq F_{n+1}$ then the Euclidean Algorithm
requires at most $n$ steps.
\end{enumerate}
\end{question}
\begin{question}[5 points] \label{q:fib-approx}
How big are Fibonacci numbers? Let's find out:
\begin{enumerate}[label=(\alph*)]
\item Solve $x^2 = x + 1$ for $x$ and call the positive solution
$\varphi$ (this is often known as the \emph{golden ratio}) and the
negative solution $\hat{\varphi}$.
\item Explain why we know that $\varphi^2 = \varphi + 1$ and
$\hat{\varphi}^2 = \hat{\varphi} + 1$. (You will need to use these
equations in the next part.)
\item Prove by induction on $n$ that
$F_n = \frac{1}{\sqrt 5}(\varphi^n -
\hat{\varphi}^n)$.\marginnote{Hints for (c): don't forget that you need two
base cases; you will want to show that $\varphi - \hat{\varphi} = \sqrt 5$.}
\item Conclude that $F_n \approx \varphi^n/\sqrt 5$.\marginnote{Hint
for (d): what can you say about $\hat{\varphi}^n$ as $n$ gets large?}
\end{enumerate}
\end{question}
\begin{question}[5 points]
Suppose we want to run the Euclidean Algorithm to compute
$\gcd(a,b)$, again assuming $a > b$. Let $F_{n+1}$ be the smallest
Fibonacci number which is greater than or equal to $a$. Then we
know from question \ref{q:fib-smallest} that the Euclidean Algorithm
takes at most $n$ steps to run, with the worst case being when
$a = F_{n+1}$. We want to figure out how $n$ relates to $a$.
Starting from $a = F_{n+1}$ (since this is the \emph{worst} case),
and using the result from the previous question, solve
(approximately) for $n$ in terms of $a$.\marginnote{One
(not-so-secret) purpose of this question is to serve as a review
of logarithms, which will feature prominently in this course.
Please come ask if you need help remembering how to work with
logarithms to solve this question!} Your final answer should be of
the form
\[ n \approx k_1 \log_{10} a + k_2 \] for suitable constants $k_1$
and $k_2$; you should give $k_1$ and $k_2$ in approximate, decimal
form.\marginnote{This is (essentially) known as Lam\'e's Theorem,
and was first proved by Gabriel Lam\'e in 1844. It was
significant in being one of the first ``practical'' applications
of the Fibonacci numbers, and one of the first results in what we
would now call the theory of algorithms.} Conclude that the
Euclidean Algorithm requires, \emph{in the worst case}, a number of
steps proportional to the number of digits in the base-ten
representation of $a$.
\end{question}
\begin{question}[\textbf{Optional Extra Credit} (3 points)]
The jellybean game is a game for two players. There is a row of $n$
jars, numbered $1$ to $n$ from left to right, each of which starts
out containing some number of jellybeans (possibly zero). We assume
that these are magical jars which can hold an \emph{unlimited
number} of jellybeans, so we don't have to worry about the jars
getting too full. (Note, however, that the jars cannot hold
\emph{infinitely} many beans---each jar must always have some finite
number of jellybeans in it, but that number can be as big as we
want.) We also assume that there is an unlimited supply of extra
jellybeans (such as a jellybean factory or a magical
jellybean-pooping unicorn).
The players alternate turns. On a player's turn, she must:
\begin{enumerate}
\item Pick a nonempty jar, call it jar $k$.
\item \emph{Remove} one jellybean from jar $k$.
\item \emph{Add} as many jellybeans as she wants (possibly zero) to
each of the jars $1 \dots (k-1)$ to the left of her chosen jar.
\end{enumerate}
For example, suppose there are five jars which currently hold
\[ 1 \quad 3 \quad 0 \quad 2 \quad 6. \] One possible valid turn is
to pick jar 4 and remove one jellybean from it, then add 6, 29, and
one billion jellybeans to jars $1$, $2$, and $3$ respectively,
resulting in \[ 7 \quad 32 \quad 10^9 \quad 1 \quad 6. \]
The winner is the player who removes the last jellybean. Put
another way, the loser is the first player who is unable to move
because all the jars are empty.
\begin{enumerate}[label=(\alph*)]
\item Prove that the jellybean game always ends eventually. That is,
even if the players conspire to try to make the game last forever,
they cannot (as long as they follow the rules).\marginnote{Of
course, they certainly \emph{can} make the game take a very,
\emph{very} long time\dots}
\item Describe a winning strategy for the jellybean game.
\end{enumerate}
\end{question}
\end{document}