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

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?

• Two trivial observations: it might be profitable to rewrite $S_n = \sum_{m=1}^n (\frac{n}{m} \mod 1) \cdot \frac{1}{(m-1)!}$, and plotting $S_n$ shows enough approximate periodicity to suggest that Fourier techniques might be of use. Dec 23, 2020 at 14:44
• The two initial directions I had in mind were 1) factor $n$ and compute the residues modulo prime powers, $n \mod p^{r_i}$, use the divisibility criteria to reduce the number of summands, and the Chinese Remainder Theorem. 2) rewrite $n \mod m = n - m \lfloor \frac{n}{m} \rfloor$, and rewrite the floor using a Fourier series to get $n-m\left(\frac{n}{m}-1/2+\frac{1}{\pi}\sum_{k=1}^{\infty}\frac{\sin(2\pi kn/m)}{k}\right) = \frac{m}{2}-\frac{m}{\pi}\sum_{k=1}^{\infty}\frac{\sin(2\pi kn/m)}{k}$. Rearranging to get an exponential sum would be the next guess, but not confident w/o abs. conv. Dec 24, 2020 at 2:49
• It smells to me like Poisson summation might afford a foothold on your Fourier series Dec 24, 2020 at 3:03

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?
• Thanks, that's helpful. This question got some more traction on SE (math.stackexchange.com/questions/3960138/…). As you say, it does seem to be the case that the output is large, though it's not obvious how to prove that the numerator doesn't cancel the denominator. As $1/m!$ is small, you really only need around 21 terms for an accurate 64-bit approximation, which is fine for what I was doing. Jan 26, 2021 at 23:31