Fast algorithm for computing $\sum_m (n \mod m)/m!$

Question

I'm interested in quickly computing an embedding of the profinite integers $\widehat{\mathbb{Z}}$ into the unit interval $\left[0,1\right]$.

$\widehat{\mathbb{Z}}$ can be represented as compatible sequences $(a_1,a_2,a_3,\dots)$ where by compatible we mean $m|n \Rightarrow a_m \equiv a_n \mod m$. This is exactly the relation that holds when the sequences come from integers, i.e. $a_m=m$, and encodes facts like if $n$ is even, then $n \equiv 0,2 \mod 4$. In this way we have an embedding $\mathbb{Z} \subset \widehat{\mathbb{Z}}$ where $n \mapsto (n \mod 1, n \mod 2, n \mod 3,\dots)$.

One can imagine a tree with branching degree increasing by one each layer down. Each sequence corresponds to a path starting at the root of the tree. To place the leaves of the tree in the interval $[0,1]$ in a natural way, subdivide the interval into two pieces, those segments into three pieces, and so on all the way down. The map is then

$$n \mapsto \sum_{m=1}^{\infty} \frac{(n\mod m)}{m!}$$

This is simply using the fractional values in the mixed radix factorial number system, i.e. the sequence $(a_1, a_2, a_3,\dots)$ corresponds to $0.a_1 a_2 a_3 \dots$.

As the sequence $n \mod m$ is constant and equal to $n$ when $m>n$, we can compute the "remainder" $R_n$ quickly:

$$R_n = \sum_{m=n+1}^{\infty} \frac{n}{m!} = e\cdot n-\frac{e \Gamma(1+n,1)}{\Gamma(n)} = e\cdot n - \frac{\lfloor e\cdot n!\rfloor}{(n-1)!}$$

Let $\displaystyle S_n = \sum_{m=1}^n \frac{(n\mod m)}{m!}$ be the $n$-th partial sum of the series, a rational number.

Simply computing $n \% m$ for each $m$ and summing is $\mathcal{O}(n)$, so exponential in the number of digits. Is there a faster way to compute this?

Answer 1

Given that your denominators get up to $(n-1)$, which has $\approx n\log{n}$ digits, I don't see how you can possibly do better than $O(n)$.

That being said, let's look at your original map: \begin{equation} n \rightarrow f_n \equiv \sum_{m=1}^\infty \frac{(n \pmod{m})}{m!} \end{equation} Turn it into a generating function. \begin{equation} F(x) \equiv \sum_{n=1}^{\infty} f_n x^n \,. \end{equation} We then have the following recursion: \begin{equation} F(x) = \frac{(e-1)x}{1-x} + xF(x) - \sum_n \sum_{d|n} \frac{x^n}{(d-1)!} \\ = \frac{(e-1)x}{1-x} + xF(x) - \sum_d \sum_{k=1}^\infty \frac{x^{kd}}{(d-1)!} \\ = \frac{(e-1)x}{1-x} + xF(x) - \sum_d \frac{x^d}{(d-1)! (1-x^d)} \,. \end{equation} The first line comes from $(n+1 \pmod{m}) = (n \pmod{m}) + 1 - mI_{m|n}$, which gives a recursion on the $f_n$. I can't simplify the last line further, but maybe you can do something with that?