\documentclass[12pt]{article}
\usepackage{comment}
\usepackage{bm}

\begin{document}

\centerline{\bf Homework 6 MORALLY Due Mar 28 at 9:00AM}
\newcommand{\implies}{\Rightarrow}
\newcommand{\MOD}{{\rm MOD}}
\newcommand{\PRIMES}{{\rm PRIMES}}
\newcommand{\NSQ}{{\rm NSQ}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}

\newcommand{\NCU}{{\rm NCU}}
\newcommand{\NCUZ}{{\rm NCUZ}}


\centerline{\bf WARNING: THIS HW IS SIX PAGES LONG!!!!!!!!!!!!!!!!!}

\begin{enumerate}

\item 
(0 points but please DO IT)
What is your name?

\item
(40 points)
Given $x,y,z$ 
$a_n(x,y,z)$ be defined by

$a_1=x$

$a_2=y$

$a_3=z$ 

$(\forall n\ge 4)[a_n = a_{n-1} + 2a_{n-2} + 3a_{n-3}].$


\begin{enumerate}
\item 
(20 points)
Find $\alpha$ (AN APPROXIMATION TO 5 PLACES! THE CLOSED FORM IS UGLY!) such that 

$(\forall n\ge 1)[a_n \sim \alpha^n]$

This $\alpha$ should only depend on the recurrence and not on $x,y,z$. 

(You will get three values of $\alpha$. Two of them will be complex
numbers of length $<1$ so as $n$ goes to infinity they are negligible.
The third will be a real $>1$ and that is what we want.) 

\item 
(0 points but you will need this)
Write a program that will, given $x,y,z,n$, generate 
$$a_1,a_2,\ldots,a_n$$

\item
(0 points but you will need this)
Write a program that will, given $n$, generate 
$$\alpha^1,\alpha^2,\ldots,\alpha^n.$$

\item
(0 points but you will need this)
Write a program that will, given $x,y,z,n$, run the two programs above
and then generate

$$ \frac{\alpha^1}{a_1}, \frac{\alpha^2}{a_2}, \ldots, \frac{\alpha^n}{a_n}.$$

This sequence should be roughly constant. Call that constant $C(x,y,z)$. 

\vfill

\centerline{\bf GOTO NEXT PAGE} 

\newpage

\item
(20 points) 
For $1\le x , y , z \le 5$ find $C(x,y,z)$. Put it into a table like this:

\[
\begin{array}{|c|c|c|c|}
\hline 
x & y & z & C(x,y,z) \cr 
\hline 
1 & 1 & 1 &          \cr 
1 & 1 & 2 &          \cr 
\vdots & \vdots & \vdots & \vdots \cr 
 5 & 5 & 5 &          \cr
\hline
\end{array}
\]

(You will not have the $\vdots$ and you will have the $C(x,y,z)$ column filled in. 

\item
(0 points) Which of $x,y,z$ affects $C(x,y,z)$ the most? In what direction? 
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(40 points) 
Given $n$ we want to write $n$ as a sum of cubes of INTEGERS. Note that 

\begin{itemize}
\item
23 is the sum of 9 cubes of NATURALS, but NOT 8. 
\item
23 is the sum of 5 cubes of INTEGERS: $23=3^3+(-1)^3 + 4\times (-1)^3$.
\end{itemize} 

Let $n\in\N$. $\NCUZ(n)$ is the least number such that $n$ can be written as the sum
of $\NCUZ(n)$ cubes of INTEGERS. Clearly $\NCUZ(n)\le n$.

In this problem you will write a programs that will,
given $n\in\N$, find $A[n]$, a bound on $\NCUZ(n)$. 

Note the following:

{\it $n$ can be written as the sum of $k$ cubes IFF $-n$ can be written as the sum of $k$ cubes.}

Consider the following thought experiment:

You want to find $A[23]$. So you look at using

$1^3$: So then the answer would be $1+A[23-1^3]=1+A[22]$. 

$2^3$: So then the answer would be $1+A[23-2^3]=1+A[15]$. 

$3^3$: So then the answer would be $1+A[23-3^3]=1+A[-4]=1+A[4]$. 

$4^3$: So then the answer would be $1+A[23-4^3]=1+A[-41]=1+A[41]$.

CAN'T USE THIS- we do not know $A[41]$ while doing $A[23]$. 

We can use $j^3$ so long as $|23-j^3|\le 22$. 

More generally, while looking at $A[i]$ can use $j$ such that $|i-j^3]\le i-1$. 

On the next page we ask the question we want formally. 

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage

\begin{enumerate}
\item
(10 points) Show that if $-n$ is the sum of $k$ integer cubes, then $n$ is the sum of $k$ integer cubes. 
\item 
(0 points but you need to do this for the next part.) 
Write a program that will, given $n$, find, for all $0\le i\le n$, 
a number $A[i]$ such that $i$ can be written as the sum of $A[i]$ cubes of INTEGERS. 

Here is how the program will work. 

\begin{itemize}
\item
$A[0]\leftarrow 0$ (0 can be written as the sum of 0 cubes).
\item
$A[1]\leftarrow 1$ (1 can be written as the sum of 1 cube).
\item 
For $i\leftarrow 2$ to $n$

$$A[i] = 1+ \min\{ A[|i-j^3|] \colon 0\le |i-j^3| \le i-1 \}.$$
\end{itemize}


\item
(10 points)
Run the program on $n=10000$, so you get $A[1]$,$\ldots$,$A[10000]$. 
\begin{enumerate}
\item
How many numbers took 1 cube? 
(For how many $1\le i\le 10000$ is $A[i]=1$?)
\item
How many numbers took 2 cubes?
(For how many $1\le i\le 10000$ is $A[i]=2$?)
\item
How many numbers took 3 cubes?
(For how many $1\le i\le 10000$ is $A[i]=3$?)
\item
ETC-  until no numbers required that many cubes.
\end{enumerate}

\item
(20 points) Email your code to Emily. She will run it on many numbers so
make sure it is correct 

\end{enumerate}

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage


\item
(20 points) On April Fools Day Bill wants to pull the following trick on Emily:

Bill gives Emily a sequence $1,2,3,$ asks her to guess the next number.

She will (quite reasonably) guess 4. 

Bill will then produce a polynomial $p$ such that 

$p(1)=1$

$p(2)=2$

$p(3)=3$

$p(4)=1000$

and then say FOOLED YOU! The answer was 1000. (Emily will then roll her eyes.) 

Help Bill out! Give a polynomial $p$ with those values. Try to make the degree as low as possible. 

You CAN use tools on the web. If so, tell us what they are. 


\vfill

\centerline{\bf GOTO NEXT PAGE}


\newpage
\item
(Extra Credit) 
\begin{enumerate}
    \item Prove 
for all $n$, for all $a \ge 2^n$, DUP wins 
$(L_{2^n},\N+\Z+\N^*;n)$ 

\item Prove for all $n$, for all $a \ge 2^n$, DUP wins 
$(L_{2^n},\N+\Z+ \Z+\N^*;n)$ 

\end{enumerate}
\end{enumerate}
\end{document}