7
$\begingroup$

I stumbled upon a programming question which wanted me to calculate : $$G(n) = \sum _{i=1}^{n} \sum _{j=i+1}^{n} gcd(i, j).$$ now I wrote a code to solve this problem but it takes polynomial time to solve this .I asked this question here but I think I need more mathematical insight before solving this algorithmicly. So can someone tell me how should I solve this equation in sublinear time .I think this problem has to do something with dirichlet-convolution but I don't understand how .So please help me understand this.

this is anothe one

$$S(A,B) = \sum _{a=1}^{A} \sum _{b=1}^{B} {a*b } \ f(gcd(a,b))$$ Here, f(n)=n, if n is square free otherwise 0. Also f(1)=1. for this one also I was able to write

  _CACHE = {}
def G(a, b):
    a = a % DIVISOR
    b = b % DIVISOR
    key = (a, b) if a > b else (b, a)
    if key not in _CACHE:
        _CACHE[key] = (a * b * F(fractions.gcd(a, b))) % DIVISOR
    return _CACHE[key]

def S(A, B):
    s = 0
    for a in range(1, A+1):
        for b in range(1, B+1):
            s += G(a, b)
    return s

#there is also a code for checking square free number but I have not posted it ,
Here I just wanted to show the time comlexity of the real code which computes

here also as you can see I have polynomial time complexity .Maybe there is a mathematical way to reduce this where it is solvable in linear or sublinear time .Please help me out.

$\endgroup$
  • $\begingroup$ How many pairs $(i,j)$ with $1 \leqslant i < j \leqslant k$ and $\gcd(i,j) = d$ are there? (The case $d = 1$ is of special relevance.) $\endgroup$ – Daniel Fischer Apr 20 '16 at 19:56
  • $\begingroup$ I'm not asking for the first summation. I'm hinting at how this problem may be efficiently attacked. Admittedly, the hint is vague, but I don't want to spoil the challenge. $\endgroup$ – Daniel Fischer Apr 20 '16 at 20:31
  • $\begingroup$ @DanielFischer I think there are k**2-k(k+1)/2 pairs $\endgroup$ – sid Apr 20 '16 at 20:48
  • $\begingroup$ Nope, no such easy formula. For a fixed $d$, how many pairs …, the answer must of course depend on $d$ [and on $k$]. $\endgroup$ – Daniel Fischer Apr 20 '16 at 20:55
1
$\begingroup$

Classifying according to the value $d$ of $\gcd(p,q)$ we get

$$\sum_{p=1}^n\sum_{q=p+1}^n \gcd(p, q) = \sum_{d=1}^n d \sum_{q=2}^{\lfloor n/d\rfloor} \varphi(q) = -\frac{1}{2} n(n+1) + \sum_{d=1}^n d \sum_{q=1}^{\lfloor n/d\rfloor} \varphi(q).$$

This is

$$-\frac{1}{2} n(n+1) + \sum_{dq\le n} d\varphi(q) = -\frac{1}{2} n(n+1) + \sum_{q=1}^n \varphi(q) \sum_{d=1}^{\lfloor n/q\rfloor} d.$$

The final answer is therefore

$$-\frac{1}{2} n(n+1) + \frac{1}{2} \sum_{q=1}^n \varphi(q) \lfloor n/q\rfloor (\lfloor n/q\rfloor + 1) \\ = \frac{1}{2} \sum_{q=2}^n \varphi(q) \lfloor n/q\rfloor (\lfloor n/q\rfloor + 1).$$

Remark. No further comments will be made on this answer so as to keep some of the challenge.

$\endgroup$
  • $\begingroup$ I do not know much about number theory (but would like to know) an so I do not understand what some of the symbols are in your solution .Can you please tell me what should I read first to understand your solution or (hint) $\endgroup$ – sid Apr 20 '16 at 21:13
  • 1
    $\begingroup$ I suggest you consult Wikipedia on the Euler Totient and use that page as a starting point for additional readings. $\endgroup$ – Marko Riedel Apr 20 '16 at 21:19

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.