\documentclass[12pt]{article}

\begin{document}

\centerline{\bf Homework 5, MORALLY Due March 4} 
\newcommand{\implies}{\Rightarrow}
\newcommand{\goes}{\Rightarrow}
\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}^+}

\begin{enumerate}
\item 
(25 points) 
Let $p$ be a prime. Show that $\sqrt{p}\notin\Q$ using Unique Factorization. 


\newpage 

\item
(25 points)
Let $c\in \N$ with $c\ge 2$.
Let $p$ be a prime.
Show that $p^{1/c}\notin\Q$.


\newpage 

\item
(25 points)
\begin{enumerate}
\item
(0 points but you'll need it)
Write a program that will, given $n$, tell if $n$ is prime.
(If this is a library in Python, thats fine.) 
\item 
(0 points but you'll need it)
Write a program that will, given $n$, return the NUMBER OF PRIMES $\le n$. 
We call this $\pi(n)$. (This has nothing to do with $\pi$ but its traditional.) 
\item
(0 points but you'll need it)
Write a program that will, given $N$ and $L$ produce a table of $\pi(L)$, $\pi(2L)$, $\ldots$, $\pi(LN)$. 
For example, if $N=10$ and $L=4$ then the output is

\[
\begin{array}{|c|c|}
\hline
x & \pi(x) \cr 
\hline
4 & 2 \cr
8 & 4 \cr
12 & 5 \cr 
16 & 6 \cr
20 & 8 \cr
24 & 9 \cr
28 & 9 \cr
32 & 11 \cr
36 & 11 \cr
40 & 12 \cr
\hline
\end{array}
\]

\item
(0 points but you'll need it)
Write a program that will, given $N$ and $L$ produce a table of $\pi(L)/L$, $\pi(2L)/2L$, $\ldots$, $\pi(LN)/LN$. 
For example, if $N=10$ and $L=4$ then the output is

\[
\begin{array}{|c|c|}
\hline
x & x/\pi(x) \cr 
\hline
4 & 0.5 \cr
8 & 0.5 \cr
12 & 0.42 \cr 
16 & 0.38 \cr
20 & 0.35 \cr
24 & 0.38 \cr
28 & 0.32 \cr
32 & 0.34 \cr
36 & 0.31 \cr
40 & 0.3 \cr
\hline
\end{array}
\]

\item
(25 points) 
Run the program in the last problem on $N=10,000$ and $L=10$. Plot it.
Optional: See if you can find an equation that approximates it.
\end{enumerate}

\newpage

\item 
Let

$$D= \{ 4n+1 \colon n\in\N\}.$$

We list out the first few elements and note if they are primes, units, or composites IN $D$.

\begin{tabular}{|c|c|c|}
\hline
$4n+1$ & status & factorization if composite \cr 
\hline
1  & unit & \cr
5 & prime & \cr
9 & prime, really! &  \cr
13 & prime & \cr 
17 & prime & \cr 
21 & prime, really! & \cr 
25 & comp, finally! & $5\times 5$ \cr 
29 & prime & \cr
33 & prime, really! & \cr 
37 & prime & \cr
41 & prime & \cr
45 & comp & $5\times 9$ \cr 
\hline
\end{tabular} 

Gee, there {\it seem} to be lots more primes in $D$ then in $\N$.
But is this true for large $N$? Yes, but HOW true is it? 

\begin{enumerate}
\item
(0 points but you'll need it) 
Write a program that will, given $x$, tell if $n$ is prime IN $D$.
(NOTE- the program must also test if $x\in D$.) 
\item 
(0 points but you'll need it) 
Write a program that will, given $n$, return the NUMBER OF PRIMES IN $D$ that are $\le n$. 
We call this $\pi_D(n)$. 

\[
\begin{array}{|c|c|}
\hline
x & \pi_D(x) \cr 
\hline
4 & 0 \cr
8 & 1 \cr
12 & 2 \cr 
16 & 3 \cr
20 & 4 \cr
24 & 5 \cr
28 & 5 \cr
32 & 6 \cr
36 & 7 \cr
40 & 8 \cr
\hline
\end{array}
\]

\item
(0 points but you'll need it) 
Write a program that will, given $N$ and $L$ produce a table of $\pi(L)/(L/4)$, $\pi(2L)/(2L/4)$, $\ldots$, $\pi(LN)/(LN/4)$. 
(We divide by $kL/4$ instead of of just by $kL$ since the number of elements of $D$ that are $\le L$ is roughly $L/4$. 
For example, if $N=10$ and $L=4$ then the output is

\[
\begin{array}{|c|c|}
\hline
x & \pi_D(x)/(x/4) \cr 
\hline
4 & 0 \cr
8 & 0.5 \cr
12 & 0.66 \cr 
16 & 0.75 \cr
20 & 1 \cr
24 & 0.83 \cr
28 & 0.71 \cr
32 & 0.75 \cr
36 & 0.77 \cr
40 & 0.8 \cr
\hline
\end{array}
\]


\item
(25 points) 
Run the program in the last problem on $N=10,000$ and $L=10$. Plot it.
Optional: See if you can find an equation that approximates it.

\end{enumerate}

\end{enumerate}

\end{document}