7

Since the sum $\sum_{n=1}^{\infty} (n! \: \text{mod} \: k)$ will be zero beyond $k-1$, the series could be interpreted as an finite sum of length $k-1$. Also, the max value of $n! \: \text{mod} \: k$ is naturally $k-1$.

Taken together one has a max value of:

$$ \sum_{k=2}^{\infty} \frac{(k-1)^2}{2^{k-1}} = 6 $$

Mathematica gives the value of $$ \sum_{k=2}^{\infty} \frac{1}{2^{k-1}} \sum_{n=1}^{\infty} (n! \: \text{mod} \: k) \approx 3.005674093 $$ so my upper bound is clearly quite crude. What would be a better upper bound?

Edit: To be clear my upper bound is $\frac{x (x+1)}{(1-x)^3}$ for $ \sum_{k=2}^{\infty} x^{k-1} \sum_{n=1}^{\infty} (n! \: \text{mod} \: k)$.

DecarbonatedOdes
  • 968
  • 2
    Not an upper bound but a heuristic argument: if you assume that the values of $n! \bmod k$ are approximately uniformly distributed then heuristically their sum is $(k - 1)$ times the average value $\frac{k-1}{2}$, which gives an estimate of $3$ for the total sum and as we see this estimate is accurate with an error of a bit more than 0.1%. I don't have a heuristic explanation of why this is an understimate as opposed to an overestimate. – Qiaochu Yuan Jul 02 '22 at 00:27

2 Answers2

2

For even $k\geq 6$, all terms in the sum after $\frac{k}{2}-1$ drop out because the factorial will have factors of $2$ and $\frac{k}{2}$. Thus, we can separate the sum into $2$ parts (along with the $k=2$ and $k=4$ terms), with the even sum having a better upper bound:

$$\underbrace{\sum_{p=1}^{\infty}\frac{((2p+1)-1)^{2}}{2^{(2p+1)-1}}}_{\color{red}{\text{odd }k}} + \underbrace{\sum_{q=3}^{\infty}\frac{(q-1)(2q-1)}{2^{2q-1}}}_{\color{red}{\text{even }k}} +\underbrace{\frac{1}{2}}_{\color{red}{k=2}} + \underbrace{\frac{5}{8}}_{\color{red}{k=4}}= \frac{505}{108} \approx 4.676$$

You could improve the bound further by adding in divisibility by $3$, $5$, etc. However, this would create difficulties as you would have to account for divisibility by more than one of those numbers.

Another way to improve the bound is by grouping factorial terms together, for instance $(k-1)! + (k-2)! = k(k-2)!$ gives $(k-1)!\pmod{k} + (k-2)!\pmod{k} \leq k$.

Joshua Wang
  • 6,103
2

Calculate more terms we could reach more accurate bound. Since $\sum_{k=n}^{\infty}\frac{(k-1)^2}{2^{k-1}}= \frac{(n-1)^2}{2^{n-4}}-\frac{2n^2-6n+3}{2^{n-3}}+\frac{(n-2)^2}{2^{n-2}}$ So we have the sum is between $\sum_{k=2}^{h-1}\frac1{2^{k-1}}\sum_{n=1}^{\infty}n!\pmod k$ and $\left(\sum_{k=2}^{h-1}\frac1{2^{k-1}}\sum_{n=1}^{\infty}n!\pmod k\right) +\frac{(h-1)^2}{2^{h-4}}-\frac{2h^2-6h+3}{2^{h-3}}+\frac{(h-2)^2}{2^{h-2}}$.

For example when h=10, we have the result is between $\frac{93}{32} \approx2.91$ and $\frac{423}{128}\approx3.30$; when h=20, the result is between $\frac{393939}{131072}\approx3.0055$ and $\frac{98535}{32768}\approx3.0070$.

Zhaohui Du
  • 1,816