Find number of subsets in $\{1!, 2!, \ldots, k!\}$ such that the sum is divisible by $k$ Question: Find number of subsets in $\{1!, 2!, \ldots, k!\}$ such that the sum is divisible by $k$
Context: Watched a 3b1b video yesterday, thought this question would be interesting
Attempt:
For $k > 3$:
$$2! = 3!  \mod 4$$
$$1! = 3!  \mod 5$$
$$3! = 4! \mod 6$$
$$1! = 5! \mod 7$$
and so on and so forth, my point is there will be numbers $a$, $b$ such that $a! = b! \mod k$ where $a, b < k$ and $k > 3$
how do I continue without knowing what are the numbers described above?
 A: I strongly suspect, after computing the count for lots of values of $k$, that there is no closed-form (i.e. "nice") answer.
A couple observations:

*

*For prime $k$, the answer tends to be very close to $2^k/k$, as one would expect (if every subset has sum divisible by $k$ with "probability" $k$). It actually seems to be a lot closer than I would expect -- if you take a random list of $k$ integers in $[0,k)$ and compute the number of subsets (out of the $2^k$) with sum $0\pmod k$, you'd expect it to differ from $2^k/k$ by about $\sqrt{2^k/k}$, but the difference seems to be closer to $2^{k/6}$ for large $k$, or even smaller. I'm not sure why this is; it would be very interesting to have a reason.


*For composite $k$, most of the numbers $\{1!,2!,\dots,k!\}$ are $0$ modulo $k$, so the number of subsets is $2^{\text{number of zeros}}$ times some small-ish number. This observation allows computation of the exact number in some cases. For example, when $k=j!$, only the first $j-1$ terms are nonzero modulo $k$; since
$$1!+2!+3!+\cdots+(j-1)!<j!,$$
the only possible sums are those containing some subset of $\{j!,\dots,k!\}$, and thus there are exactly $2^{k-j+1}=2^{j!-j+1}$ subsets with zero sum modulo $k$. The same argument works for numbers like $k=j!/2$ for $j>3$.

Here is a quick way to compute the count given $k$, which runs in $O(k^2)$ time (assuming all computations are $O(1)$; when $k$ is very large, this is probably an unreasonable assumption, and the runtime should bump up to about $O(k^3)$):

*

*Compute the list $[1!\bmod k,2!\bmod k,3!\bmod k,\dots,k!\bmod k]$, since all that matters for whether subset sums are divisible by $k$ is their residues modulo $k$.


*Initialize a list $Q_0=[1,0,\dots,0]$ of length $k$. For each $0\leq j<k$ and $0\leq i\leq k$, the entry $Q_i[j]$ will store the number of subsets of $\{1!,2!,\dots,i!\}$ have sum $j\bmod k$.


*For each $0\leq i<k$, compute $Q_{i+1}$ from $Q_i$, by setting
$$Q_{i+1}[j]=Q_i[j]+Q_i[(j-i!)\bmod k],$$
using the precomputed residue $i!\bmod k$. The $Q_i[j]$ term counts subsets that do not contain $i!$, while the other term counts subsets that contain $i!$.


*Once $Q_k$ has been computed, the answer is $Q_k[0]$.
This can be sped up for many $k$ by counting the number $N$ of $0$s in the list $[1!\bmod k,\dots,k!\bmod k]$, ignoring those $i$ for which $k\mid i!$ in step 3, and multiplying by $2^N$ at the end, since all those $i$ do is double every element of the array in step 3. This reduces the time significantly for $k$ with lots of prime factors, since
For prime $k$ about $2000$ (where the last speedup is irrelevant), an implementation of this algorithm in Python runs in about one second on my computer, and it's much faster for smaller $k$. For numbers with a lot of prime factors, like powers of $2$, this can be pushed up much higher: my program takes about five seconds on $k=2^{20}$, which is about one million.
