I found what seems to be a Fourier transform formula for the sum-of-divisors function. $$\sigma(x)=\sum_{d|x}d$$ The "trick" is that it requires a limit. I don't know if this matters or not but something doesn't seem quite right. Here it is. $$\sigma(x)=\frac{c(x^2+x)+\sum_{b=1}^xf(b)}{2c+1}$$ $$f(b)=\lim\limits_{m\to\infty}b\left(1-\frac{2}{\pi}\sum_{n=1}^m\frac{r}{n}\right)$$ $$r=\sin\left(2\pi n\frac{x}{b}\right)+\sin\left(2\pi n\left(1+\frac{1}{2m+2}\right)\right)-\sin\left(2\pi n\left(\frac{x}{b}+\frac{1}{2m+2}\right)\right)$$ $$c=\lim\limits_{m\to\infty}\left(\frac{1}{2m+2}-\frac{1}{2}+\frac{1}{\pi}\sum_{n=1}^m\frac{\sin\left(2\pi n\left(1+\frac{1}{2m+2}\right)\right)}{n}\right)\approx 0.089489$$ Please excuse that I didn't provide a proof. But from here could someone help by maybe giving some advice for simplifying or improving on this or perhaps provide another direction that I could take with this?

Edit: I was able to simplify this to $$\sigma(x)=\lim\limits_{m\to\infty}\frac{1}{2c+1}\left(\frac{x^2+x}{2m+2}+\frac{2}{\pi}\sum_{b=1}^x\sum_{n=1}^\infty\frac{bt}{n}\right)$$ where $$t=\sin\left(2\pi n\left(\frac{x}{b}+\frac{1}{2m+2}\right)\right)-\sin\left(2\pi n\frac{x}{b}\right)$$ After eliminating some of the $m$s by taking the limit this can be further simplified to $$\sigma(x)=\lim\limits_{m\to\infty}\frac{1}{k}\sum_{b=1}^x\sum_{n=1}^\infty\frac{bt}{n}$$ where $$k=\lim\limits_{m\to\infty}\sum_{n=1}^\infty\frac{\sin\left(2\pi n\left(1+\frac{1}{2m+2}\right)\right)}{n}\approx 1.8519367$$ Although this converges slower.


Computing the sum-of-divisors function $\sigma_1(n)$ is at least as hard as determining whether or not $n$ is prime, since $n$ is prime iff $\sigma_1(n) = n + 1$. Computing with any fancy formula you write down to do this therefore ends up doing at least as much work as running a primality test, and usually it will be a bad one (e.g. trial division).

Edit: Also, if $n = pq$ is a product of two distinct primes, then computing $\sigma_1(n) = pq + p + q + 1$ is exactly as hard as computing the totient $\varphi(n) = (p - 1)(q - 1) = pq - p - q + 1$. This is tantamount to solving the RSA problem, which is widely believed to be difficult (in the same way that factoring in general is widely believed to be difficult), and this belief is the foundation for the assumption that RSA is secure.

  • $\begingroup$ Thanks for the response. I am only a high school student so forgive my ignorance. However, isn't the fact that this formula is able to give the exact divisor sigma and is completely dependent on $x$ interesting or useful at all? Observe the effect in Desmos: desmos.com/calculator/flxctujecz (look at the actual integer values not the peaks) $\endgroup$ – tyobrien Nov 18 '15 at 22:38
  • $\begingroup$ Actually look at this graph instead. desmos.com/calculator/y8s4jneqb0. Again look at the integer values not the peaks. $\endgroup$ – tyobrien Nov 24 '15 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.