sum(floor(k/a)*floor(k/b),k=1..a*b-1)
in [Math]
|
From: Robert Israel on 11 Aug 2010 13:55 "M.A.Fajjal" <h2maf(a)yahoo.com> writes: > > Raymond Manzoni <raymman(a)free.fr> writes: > > > > > M.A.Fajjal a écrit : > > > > Evaluate > > > > > > > > sum(floor(k/a)*floor(k/b),k=1..a*b-1) > > > > > > > > where gcd(a,b)=1 > > > > > > > > > I'll conjecture that this is : > > > > > > (a + b + 4 a b + 1) (a - 1) (b - 1) / 12 > > > > > > > > > Hoping it helped a little, > > > Raymond > > > > I'm assuming a and b are positive integers. Let n = > > a*b. > > For i in {0,...,a-1} and j in {0,...,b-1}, let K(i,j) > > be the > > unique integer k in {0,...,ab-1} such that k == i mod > > a and > > k == j mod b. Note that floor(K(i,j)/a) = > > (K(i,j)-i)/a > > and floor(K(i,j)/a) = (K(i,j)-j)/b. So your sum is > > sum_{i=0}^{a-1} sum_{j=0}^{b-1} (K(i,j) - i)(K(i,j) - > > j)/(ab) > > = sum_{i=0}^{a-1} sum_{j=0}^{b-1} (K(i,j)^2 - i > > K(i,j) - j K(i,j) + ij)/(ab) > > > > sum_{i=0}^{a-1} sum_{j=0}^{b-1} K(i,j)^2 = > > sum_{k=0}^{ab-1} k^2 > > = a b (a b - 1) (2 a b - 1)/6 > > > > sum_{i=0}^{a-1} sum_{j=0}^{b-1} i K(i,j) > > = sum_{i=0}^{a-1} sum_{m=0}^{b-1} i (m a + i) > > = a b (a - 1) (3 a b + a - 2) / 12 > > > > similarly > > sum_{i=0}^{a-1} sum_{j=0}^{b-1} j K(i,j) > > = a b (b - 1) (3 a b + b - 2) / 12 > > > > sum_{i=0}^{a-1} sum_{j=0}^{b-1} i j = a b (a-1) (b - > > 1)/4 > > > > After some simplification (with Maple's help), the > > result is > > as Raymond conjectured. > > -- > > Robert Israel > > israel(a)math.MyUniversitysInitials.ca > > Department of Mathematics > > http://www.math.ubc.ca/~israel > > University of British Columbia Vancouver, > > BC, Canada > > Thanks > > what about gcd(a,b)=/= 1 where a,b are positive intergers Suppose gcd(a,b) = g. Thus a = s*g, b=t*g where gcd(s,t) = 1. Let K(i,j) be the unique integer k in {0,...,s*t-1} with k == i mod s and k == j mod t. Each integer k in {0,...,a*b-1} can be written uniquely as k = m*s*t*g + g*K(i,j) + r with m in {0,...,g-1}, i in {0,...,s-1}, j in {0,...,t-1}, r in {0,...,g-1}, and k == r + g*i mod a so floor(k/a) = (k - r - g*i)/a = m*t + (K(i,j) - i)/s. Similarly floor(k/b) = m*s + (K(i,j) - j)/t. So your sum is sum_{m=0}^{g-1} sum_{r=0}^{g-1} sum_{i=0}^{t-1} sum_{j=0}^{s-1}(m t + (K(i,j)-i)/s) (m s + (K(i,j) - j)/t) = t^2 s^2 g sum_{m=0}^{g-1} m^2 + 2 g sum_{m=0}^{g-1} m sum_{i=0}^{t-1} sum_{j=0}^{s-1} K(i,j) - g s sum_{m=0}^{g-1} m sum_{i=0}^{t-1} i - g t sum_{m=0}^{g-1} m sum_{j=0}^{s-1} j + g^2/(s t) sum_{i=0}^{t-1} sum_{j=0}^{s-1} (K(i,j) - i) (K(i,j) - j) and the result I get is ((a + b + 4 a b + 1) (a - 1) (b-1) + g^2 - 1)/12 -- Robert Israel israel(a)math.MyUniversitysInitials.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada
From: Rob Johnson on 13 Aug 2010 12:10 In article <964632355.93227.1281535013783.JavaMail.root(a)gallium.mathforum.org>, "M.A.Fajjal" <h2maf(a)yahoo.com> wrote: >Robert Israel <israel(a)math.MyUniversitysInitials.ca> wrote: >> Raymond Manzoni <raymman(a)free.fr> writes: >> >> > M.A.Fajjal a ̩crit : >> > > Evaluate >> > > >> > > sum(floor(k/a)*floor(k/b),k=1..a*b-1) >> > > >> > > where gcd(a,b)=1 >> > >> > >> > I'll conjecture that this is : >> > >> > (a + b + 4 a b + 1) (a - 1) (b - 1) / 12 >> > >> > >> > Hoping it helped a little, >> > Raymond >> >> I'm assuming a and b are positive integers. Let n = >> a*b. >> For i in {0,...,a-1} and j in {0,...,b-1}, let K(i,j) >> be the >> unique integer k in {0,...,ab-1} such that k == i mod >> a and >> k == j mod b. Note that floor(K(i,j)/a) = >> (K(i,j)-i)/a >> and floor(K(i,j)/a) = (K(i,j)-j)/b. So your sum is >> sum_{i=0}^{a-1} sum_{j=0}^{b-1} (K(i,j) - i)(K(i,j) - >> j)/(ab) >> = sum_{i=0}^{a-1} sum_{j=0}^{b-1} (K(i,j)^2 - i >> K(i,j) - j K(i,j) + ij)/(ab) >> >> sum_{i=0}^{a-1} sum_{j=0}^{b-1} K(i,j)^2 = >> sum_{k=0}^{ab-1} k^2 >> = a b (a b - 1) (2 a b - 1)/6 >> >> sum_{i=0}^{a-1} sum_{j=0}^{b-1} i K(i,j) >> = sum_{i=0}^{a-1} sum_{m=0}^{b-1} i (m a + i) >> = a b (a - 1) (3 a b + a - 2) / 12 >> >> similarly >> sum_{i=0}^{a-1} sum_{j=0}^{b-1} j K(i,j) >> = a b (b - 1) (3 a b + b - 2) / 12 >> >> sum_{i=0}^{a-1} sum_{j=0}^{b-1} i j = a b (a-1) (b - >> 1)/4 >> >> After some simplification (with Maple's help), the >> result is >> as Raymond conjectured. > >Thanks > >what about gcd(a,b)=/= 1 where a,b are positive intergers This problem seemed very familiar, and after I worked out the derivation below, I found the following thread from 2003: <http://groups.google.com/group/sci.math/browse_frm/thread/f0c7bb2c772cdd91/> which looks a bit more complicated, but arrives at the same formula. Robert Israel has already posted a proof of this formula, and although it is short and to the point, it is a bit dense. I am posting this in hopes that someone might find it a bit more accessible, if quite a bit longer. In the following derivation, we will use the two summations n-1 --- > k = n(n-1)/2 [1] --- k=0 and n-1 --- > k^2 = (2n-1)n(n-1)/6 [2] --- k=0 Let [x] be floor(x) and {x} be x - [x], the fractional part of x. To me, it is easier to work with {x} than [x], so let us rewrite ab-1 --- > [k/a][k/b] --- k=0 ab-1 --- = > (k/a-{k/a})(k/b-{k/b}) --- k=0 ab-1 --- = > k^2/a/b - k/b {k/a} - k/a {k/b} + {k/a}){k/b} --- k=0 = A - B - C + D [3] Using [2], we get directly that ab-1 --- A = > k^2/a/b --- k=0 = (2ab-1)(ab-1)/6 [4] To get B and C, we need to write each integer from 0 to ab-1 as k+ja, where j ranges from 0 to b-1 and k ranges from 0 to a-1. Then {(k+ja)/a} = k/a. Thus, using both [1] and [2], we get ab-1 --- B = > k/b {k/a} --- k=0 ab-1 1 --- = - > k {k/a} b --- k=0 b-1 a-1 1 --- --- = - > > (k + ja) k/a b --- --- j=0 k=0 b-1 1 --- = - > (2a-1)(a-1)/6 + j a(a-1)/2 b --- j=0 = (2a-1)(a-1)/6 + (b-1)/2 a(a-1)/2 = (3ab + a - 2) (a-1)/12 [5] Swapping a and b, we get ab-1 --- C = > k/a {k/b} --- k=0 = (3ab + b - 2) (b-1)/12 [6] Computing D is a bit trickier. Let g = gcd(a,b). For each residue class i mod a, all residue classes mod a are represented by i+jg, where j ranges from 0 to a/g-1, and all the residue classes mod b are represented by i+kg, where k ranges from 0 to b/g-1. Each pair of residue classes mod a and mod b occur g times between 0 and ab-1. Thus, we get ab-1 --- D = > {k/a}{k/b} --- k=0 g-1 a/g-1 b/g-1 --- --- --- i+jg i+kg = g > > > ---- ---- --- --- --- a b i=0 j=0 k=0 g-1 a/g-1 --- --- i+jg b/g i + b/g(b/g-1)/2 g = g > > ---- ---------------------- --- --- a b i=0 j=0 g-1 --- a/g i + a/g(a/g-1)/2 g b/g i + b/g(b/g-1)/2 g = g > ---------------------- ---------------------- --- a b i=0 g-1 --- = g > (1/g i + (a/g-1)/2) (1/g i + (b/g-1)/2) --- i=0 = g ( 1/g^2 (2g-1)g(g-1)/6 + 1/g (b/g-1)/2 g(g-1)/2 + 1/g (a/g-1)/2 g(g-1)/2 + g (a/g-1)/2 (b/g-1)/2) = (2g-1)(g-1)/6 + (b-g)/2 (g-1)/2 + (a-g)/2 (g-1)/2 + (a-g)/2 (b-g)/2 = (a-1)(b-1)/4 + (g^2-1)/12 [7] Putting this all together, we get ab-1 --- > [k/a][k/b] --- k=0 = A - B - C + D = (2ab-1)(ab-1)/6 - (3ab + a - 2) (a-1)/12 - (3ab + b - 2) (b-1)/12 + (a-1)(b-1)/4 + (g^2-1)/12 = ((4ab + a + b + 1) (a-1) (b-1) + (g^2-1))/12 [8] which is the same as given by Robert Israel. To me, it seems quite interesting that the result of [8] is always an integer. At first glance, I would not expect it to be. Rob Johnson <rob(a)trash.whim.org> take out the trash before replying to view any ASCII art, display article in a monospaced font
From: Rob Johnson on 13 Aug 2010 17:42
In article <964632355.93227.1281535013783.JavaMail.root(a)gallium.mathforum.org>, "M.A.Fajjal" <h2maf(a)yahoo.com> wrote: >Robert Israel <israel(a)math.MyUniversitysInitials.ca> wrote: >> Raymond Manzoni <raymman(a)free.fr> writes: >> >> > M.A.Fajjal a ̩crit : >> > > Evaluate >> > > >> > > sum(floor(k/a)*floor(k/b),k=1..a*b-1) >> > > >> > > where gcd(a,b)=1 >> > >> > >> > I'll conjecture that this is : >> > >> > (a + b + 4 a b + 1) (a - 1) (b - 1) / 12 >> > >> > >> > Hoping it helped a little, >> > Raymond >> >> I'm assuming a and b are positive integers. Let n = >> a*b. >> For i in {0,...,a-1} and j in {0,...,b-1}, let K(i,j) >> be the >> unique integer k in {0,...,ab-1} such that k == i mod >> a and >> k == j mod b. Note that floor(K(i,j)/a) = >> (K(i,j)-i)/a >> and floor(K(i,j)/a) = (K(i,j)-j)/b. So your sum is >> sum_{i=0}^{a-1} sum_{j=0}^{b-1} (K(i,j) - i)(K(i,j) - >> j)/(ab) >> = sum_{i=0}^{a-1} sum_{j=0}^{b-1} (K(i,j)^2 - i >> K(i,j) - j K(i,j) + ij)/(ab) >> >> sum_{i=0}^{a-1} sum_{j=0}^{b-1} K(i,j)^2 = >> sum_{k=0}^{ab-1} k^2 >> = a b (a b - 1) (2 a b - 1)/6 >> >> sum_{i=0}^{a-1} sum_{j=0}^{b-1} i K(i,j) >> = sum_{i=0}^{a-1} sum_{m=0}^{b-1} i (m a + i) >> = a b (a - 1) (3 a b + a - 2) / 12 >> >> similarly >> sum_{i=0}^{a-1} sum_{j=0}^{b-1} j K(i,j) >> = a b (b - 1) (3 a b + b - 2) / 12 >> >> sum_{i=0}^{a-1} sum_{j=0}^{b-1} i j = a b (a-1) (b - >> 1)/4 >> >> After some simplification (with Maple's help), the >> result is >> as Raymond conjectured. > >Thanks > >what about gcd(a,b)=/= 1 where a,b are positive intergers This corrects a typo in my preious post (i mod a -> i mod g). This problem seemed very familiar, and after I worked out the derivation below, I found the following thread from 2003: <http://groups.google.com/group/sci.math/browse_frm/thread/f0c7bb2c772cdd91/> which looks a bit more complicated, but arrives at the same formula. Robert Israel has already posted a proof of this formula, and although it is short and to the point, it is a bit dense. I am posting this in hopes that someone might find it a bit more accessible, if quite a bit longer. In the following derivation, we will use the two summations n-1 --- > k = n(n-1)/2 [1] --- k=0 and n-1 --- > k^2 = (2n-1)n(n-1)/6 [2] --- k=0 Let [x] be floor(x) and {x} be x - [x], the fractional part of x. To me, it is easier to work with {x} than [x], so let us rewrite ab-1 --- > [k/a][k/b] --- k=0 ab-1 --- = > (k/a-{k/a})(k/b-{k/b}) --- k=0 ab-1 --- = > k^2/a/b - k/b {k/a} - k/a {k/b} + {k/a}){k/b} --- k=0 = A - B - C + D [3] Using [2], we get directly that ab-1 --- A = > k^2/a/b --- k=0 = (2ab-1)(ab-1)/6 [4] To get B and C, we need to write each integer from 0 to ab-1 as k+ja, where j ranges from 0 to b-1 and k ranges from 0 to a-1. Then {(k+ja)/a} = k/a. Thus, using both [1] and [2], we get ab-1 --- B = > k/b {k/a} --- k=0 ab-1 1 --- = - > k {k/a} b --- k=0 b-1 a-1 1 --- --- = - > > (k + ja) k/a b --- --- j=0 k=0 b-1 1 --- = - > (2a-1)(a-1)/6 + j a(a-1)/2 b --- j=0 = (2a-1)(a-1)/6 + (b-1)/2 a(a-1)/2 = (3ab + a - 2) (a-1)/12 [5] Swapping a and b, we get ab-1 --- C = > k/a {k/b} --- k=0 = (3ab + b - 2) (b-1)/12 [6] Computing D is a bit trickier. Let g = gcd(a,b). For each residue class i mod g, all residue classes mod a are represented by i+jg, where j ranges from 0 to a/g-1, and all the residue classes mod b are represented by i+kg, where k ranges from 0 to b/g-1. Each pair of residue classes mod a and mod b occur g times between 0 and ab-1. Thus, we get ab-1 --- D = > {k/a}{k/b} --- k=0 g-1 a/g-1 b/g-1 --- --- --- i+jg i+kg = g > > > ---- ---- --- --- --- a b i=0 j=0 k=0 g-1 a/g-1 --- --- i+jg b/g i + b/g(b/g-1)/2 g = g > > ---- ---------------------- --- --- a b i=0 j=0 g-1 --- a/g i + a/g(a/g-1)/2 g b/g i + b/g(b/g-1)/2 g = g > ---------------------- ---------------------- --- a b i=0 g-1 --- = g > (1/g i + (a/g-1)/2) (1/g i + (b/g-1)/2) --- i=0 = g ( 1/g^2 (2g-1)g(g-1)/6 + 1/g (b/g-1)/2 g(g-1)/2 + 1/g (a/g-1)/2 g(g-1)/2 + g (a/g-1)/2 (b/g-1)/2) = (2g-1)(g-1)/6 + (b-g)/2 (g-1)/2 + (a-g)/2 (g-1)/2 + (a-g)/2 (b-g)/2 = (a-1)(b-1)/4 + (g^2-1)/12 [7] Putting this all together, we get ab-1 --- > [k/a][k/b] --- k=0 = A - B - C + D = (2ab-1)(ab-1)/6 - (3ab + a - 2) (a-1)/12 - (3ab + b - 2) (b-1)/12 + (a-1)(b-1)/4 + (g^2-1)/12 = ((4ab + a + b + 1) (a-1) (b-1) + (g^2-1))/12 [8] which is the same as given by Robert Israel. To me, it seems quite interesting that the result of [8] is always an integer. At first glance, I would not expect it to be. Rob Johnson <rob(a)trash.whim.org> take out the trash before replying to view any ASCII art, display article in a monospaced font |