\documentclass[12pt,ifthen]{article}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[margin=1in]{geometry}
\newif{\ifshowsoln}
\showsolntrue

\begin{document}

\newcommand{\Z}{\sf Z}
\newcommand{\N}{\sf N}
\newcommand{\Q}{\sf Q}
\newcommand{\R}{\sf R}
\newcommand{\C}{\sf C}
\newcommand{\into}{\rightarrow}
\newcommand{\st}{\mathrel{:}}


\centerline{\bf CMSC 452 Project 1}

\centerline{\bf MORALLY DUE March 31 by 11:00AM (No dead Cat)}

\centerline{\bf WARNING: Midterm is 3/31 so you REALLY should do}
\centerline{\bf this by 3/24 so you have time to study for the midterm.}
\centerline{\bf PLUS you have all of Spring Break to work on the project.}
\centerline{\bf PLUS it is easy---it took Saadiq 10 minutes to do.}


\section{Small NFAs for $L_n$}

Let $L_n$ be defined as

$$L_n = \{ a^i \st i\ne n\}.$$

\noindent
From the notes you know that there are NFAs for $L_n$ of size
much smaller than $n$. How do you find such an NFA? How do you represent it? Here is the procedure:

\begin{enumerate}
\item
Find $(x, y)$ relatively prime such that $m=xy-x-y \le n$,  but you want to make $m$ not
too much smaller than $n$. We will formalize this as $0\le n- (xy-x-y) \le 4\sqrt{n}$.
\item
$M$ is an NFA with (1) a chain of size $c = n-m$ from the start state to
a final state $q$ and (2) a loop around $q$ of size $\max(x,y)$. {\bf Note} that $q$ is considered part of the big loop and not part of the chain, but that the start state is considered part of the chain.
\item
$\varepsilon$-transitions to states that have loops of size $p_1,\ldots,p_\ell$
(where the $p_i$'s are all prime)
where 
$$p_1 \times \cdots \times p_\ell\ge n$$ 
but you want to keep
$p_1+\cdots+p_\ell$ small.
One easy way is to just take the least $\ell$ such that
$$p_1 \times \cdots \times p_\ell\ge n$$ and
$$p_1 \times \cdots \times p_{\ell - 1} < n.$$
\item
On those loops you need to have as final states all states corresponding
to $\not\equiv n \pmod {p_i}$.
\end{enumerate}

So the only parameters you need to specify the NFA are
\begin{itemize}
\item
$x,y$
\item
$c$, the size of the chain
\item
$p_1,\ldots,p_\ell$ primes
\end{itemize}

The number of states $s$ in the NFA is $s = \max(x,y)+c+p_1+\cdots+p_\ell$.

\section{Project Requirements}

Write a program that will do the following: \\
\noindent
Input: $n\in\N$ where $n\ge 200$ \\
Output: $s$, the number of states in the SMALLEST possible small NFA using the procedure outlined above.
\begin{enumerate}
\item Your program must accept a SINGLE ARGUMENT ($n$) in the command line and it must print $s$ and a new line (not return $s$) to standard output. 
\item Your program must be written in Python 3 and called \verb|small_nfa.py|. 
\item You may use \verb|numpy| and \verb|argparse|, but no other Python libraries. 
\item Submit your single \verb|small_nfa.py| file to Gradescope. You have unlimited submissions until the dead cat deadline but we will only run tests on your most recent submission.
\item As a sanity check, the smallest NFA for $L_{200}$ using this procedure has 37 states.
So running \verb|python small_nfa.py 200| should yield 37.
\item You may find the \verb|sum|, \verb|prod|, and \verb|sqrt| functions in \verb|numpy| useful.
\item Here is a link to \verb|argparse| documentation: https://docs.python.org/3/library/argparse.html
\item You must submit your own code.
\end{enumerate}
\end{document}