Consider the following problem:
Prove or disprove that if $n\in \mathbb{N}$, then $n$ is prime iff $(n-1)!+n$ is prime.
If $n$ is composite and greater than $1$, then $n$ have a divisor less than $n-1$, therefore $(n-1)!$ and $n$ have a common factor. Thus "$\Leftarrow$" is true. To proof the other direction we can consider the more general problem:
Let $n\in\mathbb{N}$. Consider the set $C(n)=\{m\in\mathbb{N}:n+m\text{ is composite}\}.$ How we can characterize the elements of $C(n)$?
The ideal answer would be describe all elements in $C(n)$ in terms of only $n$. But, is that possible? I have asked this question to my professors and they simply smile (is not fun for me, I mean, is a serious question, or not?) and then say $C(n)=\{jk-n:j,k\in\mathbb{N}\}.$ But, this is obvious and don't help me. I tell you all this history because I want to know what do you think about it, and if exist literature that mention something like this problem.
As a first approximation to solve this, we can start by defining for $n,p\in\mathbb{N}$: $A(n,p)= \{ m\in\mathbb{N}:n+m\equiv 0\pmod{p} \}.$ After of some observations we can prove that $A(n,p)=\{(\lceil n/p \rceil + k)p - n:k\in \mathbb{N}\}$ and then $A(n,p)$ is the range of a function of the form $f_{n,p}:\mathbb{N}\to \mathbb{N}$. From this $C(n)=\bigcup_{p=2}^\infty A(n,p),$ But this still far from a characterization in terms of $n$. What do you think that is the better that we can do or the best we can hope?
Edit: I really want to know what do you think about the problem of characterize the elements of $C(n)$ or $\mathbb{N}\setminus C(n)$. Any opinions, suggestions, corrections, comments and/or references are greatly appreciated.