Let's define $Cay_n$ as the minimal possible number $m$, such that every group of order $n$ is isomorphic to a subgroup of $S_m$. Is there some sort of explicit formula for $Cay_n$?
What do I know about this problem:
First of all
$$Cay_n \leq n$$
However, if a group $G$ is not embeddable into $S_{|G|-1}$, then it is either a cyclic $p$-group, or a generalised quaternion group, or $C_2 \times C_2$. And that means that $Cay_n = n$ iff $n$ is a prime power. Thus a better bound is possible.
However for a number with prime decomposition $p_1^{k_1}...p_n^{k_n}$ we have
$$Cay_{p_1^{k_1}...p_n^{k_n}} \geq p_1^{k_1} + ... + p_n^{k_n}$$
as cyclic groups of that order can not be embedded into smaller symmetric groups.
If an explicit formula is too hard to find, then the asymptotic of $\inf\{Cay_k|k \leq n\}$ will also do.