I am aware of the technique dubbed the "roots of unity filter" which calculates an expression of the form $\sum_{k|i}\dbinom{n}{i}$ in terms of the average of $(1+\omega^j)^n$ as $i$ and $j$ respectively taken the appropriate range. However, except in the case of very small $n$, I can't see how this is useful if one is interested in the actual value of the sum. For example, does this method lend any insight into the number theoretical properties of this number? (e.g. when is it prime, when is it a perfect power, etc.)
I suppose one approach would be to find the polynomial whose roots are the $(1+\omega^j)$'s. Can it be expressed in a suggestive form? I would also be curious if somebody with knowledge of discrete Fourier analysis could comment on any more advanced techniques to approach the problem.