This question follows a previous one on the primality of Stirling numbers of the second kind ${n \brace k}$.
Gerry indicated a paper on the topic. In this paper it is shown that for ${n \brace k}$ to be prime $n$ must be composite and if $p$ is the largest prime smaller than $n$, then $k$ must satisfy either $$1\lt k \le n+1-p $$
or $$n\gt k\ge p+1$$
The numerical observation shows that if $k\ge p+1$, then ${n \brace k}$ seems to have at least one common factor with $n$, (hence would always be composite). It also seems to have only relatively small prime factors: all the prime factors of ${n \brace k}$ when $k\ge p+1$ seem to be always smaller than a small fraction of ${n \brace k}$. Moreover, this fraction gets smaller and smaller as $n$ grows.
My new question is: shouldn’t there be an “easy” demonstration that ${n \brace k}$ is always composite when $k$ is larger than the largest prime lesser than $n$? (Since in that case its factors seem to always be so small and numerous, relatively).
I have an argument for why ${n \brace n-k}$ should, for a given $k$, only take finitely many prime values, but it is not enough to prove the above statement. It is as follows: ${n \brace n-k}$ is a integer-valued polynomial function of $n$ of degree $2k$. (by induction).
$0,1,…,k$ necessarily are roots to that polynomial, therefore there exists a integer polynomial $P_{k-1}$ (from $\mathbb Z[X]$) of degree $k-1$ with a positive coefficient for the term of degree $k-1$, and a positive integer $D_k$ such that
$$D_k.{n \brace n-k}=n(n-1)…(n-k).P_{k-1}(n)$$ Since ${n \brace n-k}\gt n$ as soon as $n \gt 3$, (easy to prove) then if ${n \brace n-k}$ is prime then it divides $P_{k-1}(n)$ hence ${n \brace n-k} \le P_{k-1}(n)$. For a given $k$ this should only be possible for a finite number of values for $n$, since a polynomial of degree $2k$ eventually gets larger than one of degree $k-1$ (the coeff of largest degree being positive). Then above some value for $n$, all the ${n \brace n-k}$ are necessarily composite.
Other conjectures:
Actually, there is an integer $I_k=P_{k-1}(k+1)$, such that
$$I_k.{n \brace n-k}=\binom{n}{k+1}.P_{k-1}(n) $$ and moreover when $k$ is odd $$I_k.{n \brace n-k}=\binom{n}{k+1}.\binom{n-k+1}{2}.Q_{k-3}(n) $$ where $Q_{k-3}$ is an integer polynomial of degree $k-3$. And $I_k=Q_{k-3}(k+1)$
$I_k=P_{k-1}(k+1)$ apparently only has prime factors smaller than $n$.The latter factorization raises the hope that ${n \brace n-k}$ might be always composite when $k$ is odd.
On the other hand, it also seems that ${n \brace k}$ is always composite when $n$ is odd.
EDIT. It is proved here is that for all integers $k\ge0$, ${n \brace n-2k-1}$ is always divisible by $\binom{n-2k}{2}$. Or in other words $$(-1)^{n+m}=-1 \Longrightarrow{n \brace m}\equiv0 \; mod\binom{m+1}{2}$$
Together, these observations would let me think that in addition to the above conditions, for ${n \brace m}$ to be prime, both $n$ and $m$ would have to be even.
In particular, ${n \brace 3}$ might never be prime, contrarily to what is expected in the above paper.
Examples
${n \brace n-6}=\frac{1}{576}. \binom{n}{7}.(-152696+171150 n-73801 n^2+15435 n^3-1575 n^4+63 n^5)$
${n \brace n-7} =\frac{1}{144}. \binom{n}{8}.\binom{n-6}{2}.(6008-5182 n+1563 n^2-198 n^3+9 n^4)$
Any help or comments on all that stuff are welcome..
Original author of the paper here. Apologies if this isn't an "answer" per se, but just additional bits I've found. I picked up this project with an extra 15 years of software development under my belt, and wrote a much higher-performing implementation.
For $k \in (21, 84)$, $n \in (k, 200,000,000)$, there are zero candidates that pass the initial sieve. Further, Dr. DeMaio and I had discovered that each of these prime-based sieve patterns repeat not just as $n$ grows but also as $k$ does, forming a fractal structure that mimics a slanted Sierpinski triangle. We didn't pursue this aspect theoretically any further, but given that—even without incorporating this extra information into the sieve—there are no candidates, it seems unlikely that there would be many if any for higher values of $n$ or $k$.
There are seven candidates in this range of $n$ for $k = 20$, $n \in \{59898740, 60887000, 61095628, 63645140, 64605660, 118004060, 179749944\}$. The resulting $S(n, k)$ for these are between $2^{258877987}$ and $2^{776866273}$ making them all significantly larger than the current largest-known prime.
I have exhaustively tested $k = 4$, $n \le 100,000$ and $k \in (5, 20)$, $n \le 375,000$ and found no additional primes. My primary focus at the moment is specifically on the $k = 4$ strip as well as the $k \in (5, 13)$ region since those areas seem the most promising. I've only recently started this up so hopefully I'll have more to add shortly.
In the meantime, the overwhelming amount of computation is spent on running rounds of probabilistic tests on large $S(n, k)$. We test about 0.27% of $S(n, k)$ for $5 \le k \le 13$ and about 8% of $S(n, k)$ for $k = 4$. If you have any additional insight for proving that $S(n, k)$ is composite for smaller values of $k$, allowing those numbers to drop further, it would be invaluable.