An NFA with $\Sigma = \{1\}$ with $x^2$ accepting runs on strings $1^x$ for all $x \geq 0$ - how to construct? One of my homework assignments requires us to construct an NFA over the alphabet $\{1\}$ which has exactly $x^2 + 3$ accepting runs over the input string 1^x for all $x \in \mathbb{N}$. Now, the +3 part is simple - I've got LaTeX code for a state diagram for this using tikz automata:

(Now with a pretty diagram!)
However, the $x^2$ part is proving really hard for me to figure out. I'm not sure how to do this with a finite number of states, and because this is an NFA, this is especially tricky. Any and all suggestions of how to think about this and what approach to take would be very helpful.

There's no such NFA.
Assume there was an NFA over the alphabet ${1}$ which accepts all strings whose length is $n^2 + 3$ for some $n \in \mathbb{N}$. I.e., the NFS is supposed to accept strings of lengths $3,4,7,12,19,28,39,\ldots$.
If there was such an NFS, the language $$
  \Omega = \left\{\underline{1}^{n^2+3} \,:\, n \in \mathbb{N}\right\}
$$
would be regular. According to the pumping lemma for regular languages, we'd then have an $N$ such that if $x \in \Omega$ and $|x| \geq N$, then there are $x_l,x_2,x_3$ with $|x_2| > 0$, $x_1x_2x_3=x$ and $x_1\underbrace{x_2\ldots x_2}_{k\text{ times}}x_3 = x_1x_2^kx_3 \in \Omega$ for all $k \geq 1$.
For our language, that implies there there's an $N$ such that if for some $x > N$ there's an $n \in \mathbb{N}$ with $x = n^2 + 3$, then the same thing works for $x + mx_2$ ($x_2 \neq 0$) for all $m \geq 1$. Set $z = x-3$, then the statement is $$
  z \geq N, z \text{ is a square} \implies \exists{x_2\in\mathbb{N}^+}:\, \forall m \geq 1:\, z + mx_2 \text{ is a square}\text{.}
$$
That's obviously impossible, since the distance between two consecutive squares gets larger and larger, and once it get's larger than $x_2$, the right-hand side cannot hold.
