\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}