

Title: sum of lcm's Post by dormant on Jan 29^{th}, 2010, 1:24am I have to find: summation (lcm(i,n)) for i=1 to n,n<=10^6 I was thinking of summation i/gcd(i,n) But i can't any efficient way to find this. need help. :) P.S>I have wrote this question in pure maths section also. Apology, :) 

Title: Re: sum of lcm's Post by towr on Jan 29^{th}, 2010, 2:13am on 01/29/10 at 01:24:31, dormant wrote:
Quote:
After all gcd(i,n)*lcm(i,n)=i*n You can use the Euclidean algorithm (http://en.wikipedia.org/wiki/Euclidean_algorithm) to calculate the gcd fairly easily. I'll think about it some more whether there is a better way. [e]See also A051193 (http://www.research.att.com/~njas/sequences/A051193)[/e] 

Title: Re: sum of lcm's Post by towr on Jan 29^{th}, 2010, 5:01am If you can find a prime decomposition of n, you can use the fact that sum_of_lcm(n) = n * (a(n)+1)/2 where we have that a(k*l) = a(k)*a(l), and for primes p: a(p) = p*(p1)+1 And since n <= 10^{6}, it's not too difficult to find the prime factorization (just try all numbers under 1000, or do it even a bit smarter). 

Title: Re: sum of lcm's Post by dormant on Jan 29^{th}, 2010, 9:13am Quote:
how we arrive at this formula? Any special name for this a(k) function? 

Title: Re: sum of lcm's Post by dormant on Jan 29^{th}, 2010, 9:42am Towr, Thanx for the link to Encyclopedia, I never thought of searching it there. But, I think a(n) is sum {d*phi(d)} for dn. So ,taking only prime factorization can cause trouble. 

Title: Re: sum of lcm's Post by towr on Jan 29^{th}, 2010, 3:16pm On the page describing the sequence a(n) = sum_{{dn}} {d*phi(d)}, A057660 (http://www.research.att.com/~njas/sequences/A057660), there is some further useful information. Such as the a(k*l) = a(k)*a(l) I mentioned. But as it turns out that's not entirely correct, it only hold if gcd(k,l)=1. Which means we can use the prime factorization, but we need to be careful if a prime factor occurs more than once; namely, that page also says a(p^{e}) = (p^{2e+1}+1)/(p+1) So, we can use the following algorithm: javascript Code:


Title: Re: sum of lcm's Post by holtz on May 26^{th}, 2012, 12:44am Hello, I want to find lcm(m,n)+lcm(m+1,n)+...+lcm(n,n) where m<=n. How can it be done? Can it be done similarly to the method described above? Thanks 

Title: Re: sum of lcm's Post by towr on May 26^{th}, 2012, 1:22am Yes, just take the sum from 1n and subtract the sum of 1m1, this leaves the sum from mn 

Title: Re: sum of lcm's Post by holtz on May 26^{th}, 2012, 2:34am I think it wouldn't work, because: sum of 1..m1 is (m1)*(a(m1)+1)/2 = lcm(1,m1)+lcm(2,m1)+...+lcm(m1,m1) but what we need to find is lcm(1, n)+lcm(2,n)+...+lcm(m1,n) in order to subtract from sum 1..n and get the result. So, how can we calculate lcm(1, n)+lcm(2,n)+...+lcm(m1,n), that is the question. 

Title: Re: sum of lcm's Post by towr on May 26^{th}, 2012, 4:05am Ah, you're right.. There might still be some way to adapt the algorithm, but I'll have to think on it a bit more.. 

Title: Re: sum of lcm's Post by akasina9 on Nov 16^{th}, 2012, 12:12am For the sum lcm(m,n)+lcm(m+1,n)+...+lcm(n,n), you can proceed in the same way as calculating the sum lcm(1,n)+lcm(2,n)+...+lcm(n,n), but hold the value of the sum when you hit i=m in a temporary location and subtract it from the final achieved sum. :) 

Title: Re: sum of lcm's Post by towr on Nov 16^{th}, 2012, 8:37am That's not terribly helpful unless you can calculate both in a fast way. 

Title: Re: sum of lcm's Post by akasina9 on Nov 17^{th}, 2012, 12:50am on 11/16/12 at 08:37:23, towr wrote:
We need to compute just one value, namely lcm(1,n)+lcm(2,n)+...+lcm(n,n). We just store the intermediate value. So what are the 2 sums you are referring to? Did I miss something? 

Title: Re: sum of lcm's Post by towr on Nov 17^{th}, 2012, 2:54am Well, just that in that case it's faster to just skip the first m terms. There's no reason to compute them, just to subtract them again later. Unless there's a shortcut to compute the sums. 

Title: Re: sum of lcm's Post by birbal on Dec 13^{th}, 2012, 10:15am on 01/29/10 at 05:01:40, towr wrote:
Does sum_of_lcm(n) means summition lcm(i,n) ? How is a(p) defined for nonprimes ? 

Title: Re: sum of lcm's Post by towr on Dec 13^{th}, 2012, 11:23am on 12/13/12 at 10:15:40, birbal wrote:
Quote:
So just primedecompose n. (But bear in mind reply #5) 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 