\documentclass[12pt]{article} \usepackage{amsmath} \usepackage{amssymb} \usepackage{url} \begin{document} \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{\I}{{\sf I}} \newcommand{\Rpos}{{\sf R}^+} \centerline{\bf 250 MIDTERM-UNTIMED PART} \centerline{\bf Morally Due Monday Feb 26, 10:00AM} \centerline{\bf Submit on Gradescope Just Like a HW} \bigskip {\bf READ THE INSTRUCTIONS} \vspace{-2mm} \thispagestyle{myheadings} \begin{enumerate} \addtolength{\itemsep}{-2mm} % reduced space between lines \item This is an OPEN BOOK, OPEN WEB, TAKE HOME exam If you have a question, email or post on piazza. \item There are 3 problems which add up to 50 points. The exam is MORALLY due Feb 26, 10:00AM. Since the timed exam is on Feb 29 you are well advised to finish the untimed exam by the Moral Due date to give you time to study for the timed exam. \item This part must be \textbf{typed} \item For each question show all of your work \end{enumerate} \newpage \begin{enumerate} \item (25 points) Let $n\in\N$. $\NSQ(n)$ is the least number such that $n$ can be written as the sum of $\NSQ(n)$ squares. Clearly $\NSQ(n)\le n$ since $$n= 1^2 + \cdots + 1^2.$$ \noindent It is known that $\NSQ(n)\le 4$. In this problem you will write and run two programs that will, given $n\in\N$, find a bound on $\NSQ(n)$. \vspace{0.5cm} \begin{enumerate} \item (0 points but you need this for later problems) Write a program that will, given $n$, does the following: \begin{itemize} \item Find the largest $n_1$ such that $n_1^2\le n$. If $n-n_1^2=0$ then you are done: $n=n_1^2$ so output 1. If not then go to the next step. \item Find the largest $n_2$ such that $n_2^2\le n-n_1^2$. If $n-n_1^2=0$ then you are done: $n=n_1^2 + n_2^2$ so output 2. If not then $\ldots$ \item Keep going like this until there is an output. \end{itemize} \vspace{0.5cm} \item (0 points but you need this for later problems) Write a program that will, given $n$, find, for all $1\le i\le n$, a number $A[i]$ such that $i$ can be written as the sum of $A[i]$ squares. \begin{itemize} \item $A[0]\leftarrow 0$ (0 can be written as the sum of 0 squares). \item $A[1]\leftarrow 1$ (1 can be written as the sum of 1 square). \item For $i\leftarrow 2$ to $n$ $$A[i]\leftarrow 1+ \min\{A[i-j^2] \colon i-j^2\ge 0\}$$ \end{itemize} \newpage \item (5 points) Run the first program on $n=1,2,\ldots, 1000$. List out all of the $n$ where the answer was $\ge 5$. \vspace{0.5cm} \item (0 points) How would you fill in the following sentence \vspace{0.5cm} {\it The first program on input $n$ outputs a number $\ge 5$ iff BLANK.} \vspace{0.5cm} \item (5 points) Run the second program on $n=1000$ (so we now know the answers for $1,\ldots,1000$). List all of the $n$ where $A[n]$ differs from the first program on $n$. \vspace{0.5cm} \item (0 points) How would you fill in the following sentence {\it The first and second differ on $n$ iff BLANK.} \vspace{0.5cm} \item (5 points) List all of the $n$ such that $A[n]=4$. \vspace{0.5cm} \item (5 points) How would you fill in the following sentence with a SIMPLE property BLANK. {\it if $n$ has property BLANK then $A[n]=4$} (It does not need to be the case that if $A[n]=4$ then it has property BLANK.) \vspace{0.5cm} \item (0 points) Use your second program, and the PRIMES function in Python, to list out all odd primes $p\le 200$ such that $A[p]=2$. \vspace{0.5cm} \item (5 points) How would you fill in the following sentence with a SIMPLE property BLANK. {\it if $n$ is prime and has property BLANK then $A[n]=2$} (It does not need to be the case that if $A[n]=2$ then it has property BLANK.) \end{enumerate} \newpage \item (12 points--3 points each) For each of the following sentences say if they are TRUE or FALSE and JUSTIFY your answer. ADVICE: The FIRST thing your answer should have is either the word TRUE or the word FALSE. Let $\I=\R-\Q$, the set of irrationals, for this problem. \begin{enumerate} \item $(\forall x,y\in\I)[x