\documentclass[12pt,ifthen]{article}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{hyperref}
\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}

\centerline{\bf Morally due March 12 by 3:30pm}

\section{Small NFAs for $L_n$}

Let $L_n$ be defined as

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

\noindent
From the slides 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}$.
We will also take $x<y$. 
\item
$M$ is an NFA with 
(1) a chain of size $c = n-m$ from the start state to a final state $q$,  
(2) a loop around $q$ of size $y$, and
(3) a transition from the $x$th state in the loop back to state $q$. 

{\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: Integer $n$ \\
Output: The parameters $(x,y,c,\ell,p_1,\ldots,p_\ell)$ and the number of states $s$ in your NFA. (The number of states must be strictly less than $n$. \\
Constraint: $100 \le n \le 10^{12}$
\begin{enumerate}
\item Your program may be written in any programming language supported by Codeforces.
\item You are permitted to use any built-in libraries of your chosen language.
\item Create an account on \href{https://codeforces.com/}{\textbf{Codeforces}}, click on this \href{https://codeforces.com/contestInvitation/ea16d3870f8701a4867d7543e1b0f5dc33178ac3}{\textbf{link}}, and submit your solution to the specified problem.
\item The assessment consists of $200$ tests; for each test passed, you will receive a score of $0.5$.
\item Submissions must be your original work.
\item Submissions will be automatically graded, and results will be available immediately after submission.
\item Upload a screenshot of your submission, showing the grade you are satisfied with, to Gradescope (submissions will be accepted until the dead-cat deadline). Your score will be recorded accordingly.
\item Your code will be awarded points only if it executes in under 10 seconds. \textbf{(Hint: Easily achievable in $O(\sqrt{n})$ time complexity!)}
\item \textbf{Modifying the website by changing its HTML to alter the submission screenshot is strictly prohibited and will be considered academic dishonesty. Such actions will be thoroughly investigated.}
\end{enumerate}

\end{document}