Author 
Topic: sum of lcm's (Read 8743 times) 

newb
Newbie
Posts: 38


sum of lcm's
« on: Jan 29^{th}, 2010, 1:24am » 
Quote Modify

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,


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: sum of lcm's
« Reply #1 on: Jan 29^{th}, 2010, 2:13am » 
Quote Modify

on Jan 29^{th}, 2010, 1:24am, dormant wrote:P.S>I have wrote this question in pure maths section also. Apology, 
 I've removed the thread in the maths section. Quote:I was thinking of summation i/gcd(i,n) 
 You would want summation n*i/gcd(i,n) After all gcd(i,n)*lcm(i,n)=i*n You can use the 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[/e]

« Last Edit: Jan 29^{th}, 2010, 4:16am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: sum of lcm's
« Reply #2 on: Jan 29^{th}, 2010, 5:01am » 
Quote Modify

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).

« Last Edit: Jan 29^{th}, 2010, 5:02am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



newb
Newbie
Posts: 38


Re: sum of lcm's
« Reply #3 on: Jan 29^{th}, 2010, 9:13am » 
Quote Modify

Quote: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 
 how we arrive at this formula? Any special name for this a(k) function?


IP Logged 



newb
Newbie
Posts: 38


Re: sum of lcm's
« Reply #4 on: Jan 29^{th}, 2010, 9:42am » 
Quote Modify

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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: sum of lcm's
« Reply #5 on: Jan 29^{th}, 2010, 3:16pm » 
Quote Modify

On the page describing the sequence a(n) = sum_{{dn}} {d*phi(d)}, 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:<script> prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997] function a(n) { res=1; for(i=0; i < prime.length && 1 < n && prime[i] < n; i++) { x = prime[i]; while(n % prime[i]==0) { x *= prime[i]*prime[i]; n /= prime[i]; } res *= (x+1)/(prime[i]+1); } if(n > 1) res*=(n*(n1)+1); return res; } function sum_of_lcm(n) { return n*(a(n)+1)/2; } for(n=1; n <= 20; n++) document.write(n + ": " + sum_of_lcm(n) + "<br>"); document.close(); </script> 


« Last Edit: Jan 29^{th}, 2010, 3:21pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



holtz
Newbie
Posts: 2


Re: sum of lcm's
« Reply #6 on: May 26^{th}, 2012, 12:44am » 
Quote Modify

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


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: sum of lcm's
« Reply #7 on: May 26^{th}, 2012, 1:22am » 
Quote Modify

Yes, just take the sum from 1n and subtract the sum of 1m1, this leaves the sum from mn


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



holtz
Newbie
Posts: 2


Re: sum of lcm's
« Reply #8 on: May 26^{th}, 2012, 2:34am » 
Quote Modify

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.

« Last Edit: May 26^{th}, 2012, 2:35am by holtz » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: sum of lcm's
« Reply #9 on: May 26^{th}, 2012, 4:05am » 
Quote Modify

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..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



akasina9
Newbie
x = 0x2B  ~ 0x2B. x is the question
Gender:
Posts: 9


Re: sum of lcm's
« Reply #10 on: Nov 16^{th}, 2012, 12:12am » 
Quote Modify

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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: sum of lcm's
« Reply #11 on: Nov 16^{th}, 2012, 8:37am » 
Quote Modify

That's not terribly helpful unless you can calculate both in a fast way.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



akasina9
Newbie
x = 0x2B  ~ 0x2B. x is the question
Gender:
Posts: 9


Re: sum of lcm's
« Reply #12 on: Nov 17^{th}, 2012, 12:50am » 
Quote Modify

on Nov 16^{th}, 2012, 8:37am, towr wrote:That's not terribly helpful unless you can calculate both in a fast way. 
 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?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: sum of lcm's
« Reply #13 on: Nov 17^{th}, 2012, 2:54am » 
Quote Modify

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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



birbal
Full Member
Gender:
Posts: 250


Re: sum of lcm's
« Reply #14 on: Dec 13^{th}, 2012, 10:15am » 
Quote Modify

on Jan 29^{th}, 2010, 5:01am, towr wrote: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). 
 Does sum_of_lcm(n) means summition lcm(i,n) ? How is a(p) defined for nonprimes ?


IP Logged 
The only thing we have to fear is fear itself!



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: sum of lcm's
« Reply #15 on: Dec 13^{th}, 2012, 11:23am » 
Quote Modify

on Dec 13^{th}, 2012, 10:15am, birbal wrote:Does sum_of_lcm(n) means summition lcm(i,n) ? 
 sum_of_lcm(n) means whatever was asked in the opening post that resembles it most closely Quote:How is a(p) defined for nonprimes ? 
 Exactly as it says in the quoted text: a(k*l) = a(k)*a(l) So just primedecompose n. (But bear in mind reply #5)

« Last Edit: Dec 13^{th}, 2012, 11:24am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



