1
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Wadim Zudilin
    Commented Jul 10, 2011 at 11:32
  • 2
    $\begingroup$ This is a relation, undoubtedly, but it's he "recurrence" part that's missing. $\endgroup$
    – Gjergji Zaimi
    Commented Jul 10, 2011 at 12:23
  • 4
    $\begingroup$ What's with the minus sign inside the cosine? $\endgroup$
    – Gerald Edgar
    Commented Jul 10, 2011 at 13:18
  • 2
    $\begingroup$ I saw "Schramm" and thought "Oded Schramm" (maybe that's silly, given the topic?), but this is Wolfgang Schramm: emis.ams.org/journals/INTEGERS/papers/i50/i50.pdf $\endgroup$
    – Michael Hardy
    Commented Jul 10, 2011 at 20:05
  • 2
    $\begingroup$ 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? $\endgroup$
    – Todd Trimble
    Commented Jul 11, 2011 at 14:03

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .