\documentclass[12pt]{article}

\usepackage{comment}
\usepackage{amsmath}
\usepackage{amssymb}  % for \nmid

\newcommand{\D}{{\mathbb D}}
\newcommand{\G}{{\mathbb G}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\succc}{{\rm succ}}
\newcommand{\pred}{{\rm pred}}

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

\begin{document}


\centerline{Homework 05, MORALLY Due March 03} 

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}
\item
(40 points)
For this problem FIRST write the program and make conjectures THEN
look up whats true. 

A prime $p$ such that $p$ and $\frac{p-1}{2}$ are both prime is called a {\it safe prime} 

\begin{enumerate}
\item
(0 points) 
Write a program that will, given a number $n$,
test if $n$ is prime, using the naive algorithm
of testing if $2,3,4,\ldots,\ceil{\sqrt{n}}$ divides $n$.
(Do not hand anything in.)
\item
(0 points)
Write a program that will, given a number $n$,
test if both $n$ and $\frac{n-1}{2}$ are prime
(use the program in Part 1). 
(Do not hand anything in.)
\item
(4 points)
Find the following numbers
\begin{itemize}
\item
The number of primes in $\{1,\ldots,10000\}$. The number of safe primes.
\item
The number of primes in $\{1,\ldots,20000\}$. The number of safe primes. 
\item
$\vdots$
\item
The number of primes in $\{1,\ldots,200000\}$. The number of safe primes.
\end{itemize}
Hand in a table of the following form--- we give the first two lines and they
are likely incorrect. 

\begin{tabular}{|c|c|c|}
\hline
$n$  & Numb of Primes in $\{1,\ldots,n\}$ & Numb of Safe Primes in $\{1,\ldots,n\}$\cr
\hline
10,000 & 100 & 10 \cr
20,000 & 200 & 20 \cr
\hline
\end{tabular}

\item 
(8 points) 
It is known that the number of primes $\le n$ is ROUGHLY $\frac{n}{\ln n}$. 
Using your data make a conjecture about what the value of $A$ is such that
the number of primes is around $\frac{An}{\ln n}$. 
\item
(8 points)
Find some function $f$ so that the following statement fits your data pretty well:

{\it The number of safe primes $\le n$ is roughly $f(n)$ } 

\vfill

\centerline{\bf GO TO NEXT PAGE FOR THE REST OF THIS PROBLEM}

\newpage

\item 
(0 points) Write a program that will, given $p$, $g$, 

a) Test if $p$ is a safe prime. If not then output NO.

b) ($p$ is a safe prime) Test if $g$ is a generator (see slides). 

(Do not hand anything in)


\item 
(4 points) 
Find the first 20 safe primes after 100,000. Call them $p_1,\ldots,p_{20}$. 
Hand them in.

\item
(8 points) 
Hand in a table of the following form documenting the first 20 safe primes.
We give the first two lines.
We assume the first two safe primes over 100,000 are 100,001 and 100,003
(this might not be true).

\begin{tabular}{|c|c|c|}
\hline
$p$  & Numb of generators in $\{1,\ldots,p\}$ & fraction that are gen \cr 
\hline
100,001 & 20,000 & 0.199\cr
100,003 & 21,000 & 0.210\cr
\hline
\end{tabular}

\item 
(8 points) 
Based on your data make a conjecture of the following form:
For large safe primes $p$, the number of generators in $\{1,\ldots,p\}$
is $\alpha p$ where $\alpha$ is FILL IT IN

\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(30 points) 
This problem has six parts.
However, the first three are worth 0.
Do them but don't hand them in.
They are a review of what we did in class briefly. 
\begin{enumerate}
\item
(0 points---Do not hand in)
Compute the following mod 8: 
$0^2, 1^2,\ldots, 7^2$.
\item 
(0 points---Do not hand in)
Use Part 1 to find {\bf all} sums of 3 squares mod 8. 
\item
(0 points---Do not hand in)
Use Part 2 to 
prove that there are an infinite number of
natural numbers that cannot be written as
the sum of 3 squares.
\item
(10 points) 
Compute the following mod 16: 
$0^4, 1^4,\ldots, 15^4$.
\item
(10 points) 
Use Part 4 to find {\bf all} sums of 15 fourth powers mod 16. 
\item
(10 points) 
Use Part 5 to
prove that there are an infinite number of
natural numbers that {\bf cannot} be written as
the sum of 15 fourth powers.
\end{enumerate}


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(30 points)


\begin{enumerate}
\item
(15 points) 
Find a set $\D\subseteq\R$ such that the following all hold:

\begin{itemize}
\item
Every element $x\in \D$ has both a successor element $\succc(x)$ (so $x<\succc(x)$ 
and there is nothing strictly between $x$ and $\succc(x)$)
and a predecessor element $\pred(x)$ (so $\pred(x)<x$ and there is nothing strictly
inbetween $\pred(x)$ and $x$). 
\item 
There exists $x,y\in\D$ such that:  

i) $x<y$ and 

ii) $\succc(x)\ne y$, $\succc(\succc(x))\ne y$, $\ldots$. 

\end{itemize}

\item
(15 points) 
Find a set $\D\subseteq\R$ such that the following all hold:

\begin{itemize}
\item
Every element $x\in \D$ has both a successor element $\succc(x)$ (so $x<\succc(x)$ 
and there is nothing strictly between $x$ and $\succc(x)$)
and a predecessor element $\pred(x)$ (so $\pred(x)<x$ and there is nothing strictly
inbetween $\pred(x)$ and $x$). 
\item 
There exists an infinite number of pairs $(x_1, y_1), (x_2, y_2), \ldots \in D$ such that,
for all $i\in\N$: 

1)  $x_1 < y_1$ and $\succc(x_1) \neq y_1$, $\succc(\succc(x_1)), \neq y_1, \ldots$ 
 
2) $x_2 < y_2$ and $\succc(x_2) \neq y_2$, $\succc(\succc(x_2)), \neq y_2, \ldots$  \\ \vdots

i) $x_i < y_i$ and $\succc(x_i) \neq y_i$, $\succc(\succc(x_i)), \neq y_i, \ldots$ \\ \vdots

and so on 

\end{itemize}
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(Honors Homework which you must do)
Leo showed that every planar graph is 5-colorable.
It is known that every planar graph is 4-colorable
(this was a hard result).

A graph has {\it crossing number $c$} if there is a way
to draw it so that if you REMOVE $c$ edges, the graph is planar.

Planar graphs have crossing number 0.

For each of the statements fill in the FILL IN and prove the
result. 

You may use that every planar graph is 4-colorable. 

\begin{enumerate}
\item
Every graph that has crossing number 1 can be XXX-colored.

\item
Every graph that has crossing number 17 can be YYY-colored.

\item
Every graph that has crossing number $c$ can be $f(c)$-colored.
(You need to find the function $f$.)
\end{enumerate}

\end{enumerate}

\end{document}