3
$\begingroup$

The problem is to find:

$$f(N)=\sum_{k=2}^N \gcd(K-1,N)\ where \gcd(N,K)=1 $$ For example:

$$N=50\\ f(N)=70$$ $$N=100\\ f(N)=260$$ $$N=524288 \\ f(N)=4718592$$

I am not very experienced with advanced math, however I understand coprime integers, Euler's Totient function and lemma.

Any tips on calculating this function using Euler's Totient function?

Edit: To clarify, The value of $gcd(k−1,N)$ should only be included in the sum for $f(N)$ when $gcd(k,N)=1$. Restricting the sum this way agrees with the example $f(N)$ values given.

$\endgroup$
2
$\begingroup$

So you want to find $f(N)=\sum\limits_{k=1}^{N-1} \gcd(k,N)$.

Sure, there is a faster way, and it goes as follows: instead of traversing all $k$ and counting the gcd's, let's traverse the possible values of gcd and find out how many times each of them occurs in the sum. Really, how many are such $k$ that $\gcd(k,N)=d$?

Well, first of all, $d$ must be a divisor of $N$. Also, $k$ must be a multiple of $d$; how many such multiples do not exceed $N$? Obviously, ${N\over d}$. But wait, some of these multiples may have greater common divisors with $N$, so we just need those where $N\over d$ and $k\over d$ are coprime. Well, this sounds mighty like the definition of the totient function. So in the end, our formula wraps up like this: $$f(N)=\sum_{\substack d|N\\d<N}d\cdot\varphi\left({N\over d}\right)$$

A cursory glance at OEIS A006579 could have helped you a lot. Then there is a related sequence OEIS A018804, with definition similar to yours, but with summation up to $N$, which makes it a lot more natural and nice (it is multiplicative, to begin with), but that's another story.

$\endgroup$
  • 1
    $\begingroup$ But I don't think this answer is precisely what the OP wants. The value of $\gcd(k-1,N)$ should only be included in the sum for $f(N)$ when $\gcd(k,N)=1$. Restricting the sum this way agrees with the example $f(N)$ values given by the OP. $\endgroup$ – nickgard May 4 '18 at 17:02
  • $\begingroup$ @nickgard I need exactly what you described Nick, the examples show just that. $\endgroup$ – Infinity May 4 '18 at 17:18

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.