Timeline for Fast algorithm for computing $\sum_m (n \mod m)/m!$
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jan 2, 2021 at 16:06 | history | bounty ended | CommunityBot | ||
| S Jan 2, 2021 at 16:06 | history | notice removed | CommunityBot | ||
| Dec 28, 2020 at 22:21 | answer | added | Craig | timeline score: 1 | |
| S Dec 25, 2020 at 14:12 | history | bounty started | Jackson Walters | ||
| S Dec 25, 2020 at 14:12 | history | notice added | Jackson Walters | Draw attention | |
| Dec 24, 2020 at 3:03 | comment | added | Steve Huntsman | It smells to me like Poisson summation might afford a foothold on your Fourier series | |
| Dec 24, 2020 at 2:49 | comment | added | Jackson Walters | 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 23, 2020 at 14:44 | comment | added | Steve Huntsman | 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 2:24 | history | edited | Jackson Walters | CC BY-SA 4.0 |
used the word simply twice
|
| S Dec 23, 2020 at 2:10 | history | suggested | RobPratt | CC BY-SA 4.0 |
changed mod to \mod
|
| Dec 23, 2020 at 2:06 | review | Suggested edits | |||
| S Dec 23, 2020 at 2:10 | |||||
| Dec 23, 2020 at 1:35 | history | asked | Jackson Walters | CC BY-SA 4.0 |