Find the value of the summation:

$$ val=\left( \sum_{i=1}^a \sum_{j=1}^b\sum_{k=1}^c....\sum_{x=1}^p GCD(i,j,k,..x) \right)$$


$2\leq$number of summation terms$\leq 500$, $1\leq a,b,c....p\leq 100000$

I applied brute force solution to solve it, but it takes too much time which is not acceptable

  • 1
    $\begingroup$ please show us what you have done.. $\endgroup$ – Apurv Jan 18 '14 at 17:36
  • $\begingroup$ i applied brute force it took lot of time $\endgroup$ – azdssdf Jan 18 '14 at 17:40
  • $\begingroup$ add that to the question.. $\endgroup$ – Apurv Jan 18 '14 at 17:41
  • $\begingroup$ A brute force that might take less time, and even lead to a closed form formula: Loop over all possible values of the gcd, try to figure out often that value appears in the sum. This approach can perhaps be refined a lot further. $\endgroup$ – Harald Hanche-Olsen Jan 18 '14 at 17:42
  • $\begingroup$ Or you could try to add one variable at a time, using that $\gcd(i,j,\ldots,x,y)=\gcd(\gcd(i,j‚\ldots,x),y)$. Possibly combine that with my previous suggestion. There seem to be lots of things one can try. $\endgroup$ – Harald Hanche-Olsen Jan 18 '14 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.