\documentclass[12pt,HW250,ifthen]{article}
\usepackage{comment}
\newcommand{\NOBET}{{\rm NOBET}}
\newcommand{\ONEFOUR}{{\rm ONEFOUR}}
\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{\st}{\mathrel{:}}
\usepackage{amsmath}

\begin{document}

\centerline{\bf Homework 06, Morally due Mon Mar 29, 9:00AM}


For Programming Problems: Send your code to Emily by email. Send the actual .java/.py/ect file. You need to use your .umd email address or it will not send. In your pdf, you must have the output your code provides. You can screenshot this or type it in. Hint: Use Python.

\begin{enumerate} 

\item
(0 points but if you miss the second midterm that means you got this wrong retroactively
and you will lose a lot of points).
When is the SECOND midterm? By what day do you need to tell Dr. Gasarch that you cannot make
the midterm (if you cannot and know ahead of time)? 

HINT: The date of the second midterm has been CHANGED. It is now 
Thursday April 8, 2021.
(We did this so that we could have a HW due and gone over BEFORE it.) 

\centerline{\bf GOTO NEXT PAGE} 

\newpage

\item 
(0 points but you will need this for the next problem.)

Let $\ONEFOUR$ be the set

$$\{ n \st n\equiv 1 \pmod 4\}.$$

Write a program that will, given a natural number $n\ge 1$ do the following.

For $i=1$ to $n$ 
\begin{enumerate} 
\item 
$A[i]=4i+1$. 
\item
$B[i]$ is the factorization of $A[i]$ in $\ONEFOUR$.
\item
Count how many elements of $A[1],\ldots,A[n]$ are PRIME, are
the product of 2 primes, are the product of 3 primes, etc.
Store that list in $C[i]$. 
\end{enumerate}

Example: 

$A[1]=5$, $B[1]=(5)$, $C[1]=(1)$.

$A[2]=9$, $B[2]=(9)$, $C[2]=(2)$.

$A[3]=13$, $B[3]=(13)$, $C(3)=(3)$.

$A[4]=17$, $B[4]=(17)$, $C(4)=(4)$.

$A[5]=21$, $B[5]=(21)$, $C(5)=(5)$. 

$A[6]=25$, $B[6]=(5,5)$, $C(6)=(5,1)$. 

\centerline{\bf GOTO NEXT PAGE} 

\newpage


\item
(20 points)
Graph the following functions and try to see what they look like. 
\begin{enumerate}
\item 
$f_1(i)$ is the number of primes in $\ONEFOUR$ of the first
$i$ elements of $\ONEFOUR$ (so the first coordinate of $C[i])$. 
\item 
$f_2(i)$ is the number of products of 2 primes in $\ONEFOUR$ of the first
$i$ elements of $\ONEFOUR$ (so the second coordinate of $C[i]$. 
\item
Etc.
\end{enumerate}

\centerline{\bf GOTO NEXT PAGE}

\newpage

\item 
(20 points)
Complete this sentence and prove it:

{\it If $n_1\equiv 5 \pmod {10}$ and $n_2\equiv 10 \pmod {20}$ then $n_1n_2\equiv X \pmod Y$}



\newpage

\item 
(20 points) 
For this problem all numbers mentioned are in $\R$ unless
otherwise restricted. So, for example, 

$x\notin \Q$ means $x\in \R-\Q$. 


For this problem you may assume $\pi\notin\Q$. 

\begin{enumerate}
\item
(7 points) 
Prove or disprove: 

For all $x,y\in\Q-\{0\}$, $x\pi+y\notin\Q$. 

\item
(7 points) 
Prove or Disprove: 

$$(\forall x,z\in \Q)[x<z\into (\exists y\notin \Q)[x<y<z]$$



\item 
(6 points)
Prove or Disprove: 

$$(\forall x,z\notin \Q)(\exists y\in \Q)[x<y<z]$$

\end{enumerate}

\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(20 points) 
Bill tells Alice and Bob to do the following:

{\it If you're happy and you know it clap your hands}

(If you Google that phrase on You Tube you will hear a very annoying song.)

Alice and Bob follow Bill's command. 

\begin{itemize}
\item
Alice is clapping her hands.
\item
Bill is NOT clapping his hands.
\end{itemize}

What you can conclude about Alice? About Bob? 


\centerline{\bf GOTO NEXT PAGE}

\newpage
\item 
(20 points)
Let $x_1,x_2,y_1,y_2,m\in\N$. $m\ge 2$. 
ALL $\equiv$ are mod $m$. 
Assume $x_1\equiv x_2$ and $y_1\equiv y_2$.
(Hence 

$x_1=x_2+k_xm$ for some $k_x\in \Z$

and 

 $y_1=y_2+k_ym$ for some $k_y\in \Z$.

)
\begin{enumerate}
\item
(7 points) 
Prove or disprove: $x_1+y_1\equiv x_2+y_2$. 


\item
(7 points) 
Prove or disprove: $x_1y_1\equiv x_2y_2$. 


\item
(7 points) 
Prove or disprove: $x_1^{y_1}\equiv x_2^{y_2}$. 


\end{enumerate}


\end{enumerate}

\end{document}