MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Using Schramm's result (2008): $$\varphi(n)=\sum_{k=1}^n{\gcd(k,n)\cos\left(\frac{-2\pi k}{n}\right)} $$ Let the partial sum of this series be represented by:

$$\varphi(m,n)=\sum_{k=1}^m{\gcd(k,n)\cos\left(\frac{-2\pi k}{n}\right)}\qquad1\leq m\leq n$$

I came across this relationship:

$$\varphi(n)=\varphi(n,n)=\frac{n}{2}+n\left(\frac{n}{2}-\lfloor{\frac{n}{2}}\rfloor\right)+2\varphi\left( \lfloor\frac{n-1}{2}\rfloor,n\right)$$

Has anyone seen a recurrence like this before, or something similar? I wonder if this can be solved for $\varphi(n)$ without involving a gcd...

Edit: Oops this is not a recurrence, still, maybe there are more relations that can be combined with this?

By numerical evaluation of quite a few values of the totient and cumulative sums, I found that $\varphi(n)$ can be computed from partial summing of the series plus a function of $n$, but there seems to be 2 different patterns, depending on whether $n$ is an even or odd integer.

$$\varphi(n)=\varphi(n,n)=\frac{n}{2}+2\varphi\left(\frac{n}{2}-1, n\right)= \frac{n}{2}+2\sum_{k=1}^{\frac{n}{2}-1}\gcd(n,k) \cos\left(\frac{2\pi k}{n}\right)\qquad n \text{ even }$$ $$\varphi(n)=\varphi(n,n)=n+2\varphi\left(\frac{n-1}{2}, n\right)= n+2\sum_{k=1}^{\frac{n-1}{2}}\gcd(n,k) \cos\left(\frac{2\pi k}{n}\right)\qquad n \text{ odd }$$

I then combined these two relations into the one above using the floor function to cover both conditions.

share|cite|improve this question
Can you give a single example when the relation of type $f(n,n)=\sum_{i<n}c_if(i,n)+g(n)$ could determine $f(n,n)$? There is no control of $f(i,n)$ for $i\ne n$, but even if it were, you would require at least one more recursion plus initial conditions. – Wadim Zudilin Jul 10 '11 at 11:32
This is a relation, undoubtedly, but it's he "recurrence" part that's missing. – Gjergji Zaimi Jul 10 '11 at 12:23
What's with the minus sign inside the cosine? – Gerald Edgar Jul 10 '11 at 13:18
I saw "Schramm" and thought "Oded Schramm" (maybe that's silly, given the topic?), but this is Wolfgang Schramm: – Michael Hardy Jul 10 '11 at 20:05
I'm having some trouble believing this is originally due to W. Schramm. It looks awfully similar to a formula like $\phi(n) = \sum_{d|n} (n/d)\mu(d)$, where $\mu(d)$ is recast as the sum of primitive $d^{th}$ roots of unity. Am I making a mistake? – Todd Trimble Jul 11 '11 at 14:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.