Sum of a set of products

Algebra Level 4

Find the sum of the product of each pair of positive integers a a and b b such that a , b < 100 a, b < 100 and a b a \neq b .

If your solution can be expressed as m × 1 0 4 m \times 10^4 , submit your answer as m \lfloor m \rfloor .


Bonus: Generalize for a , b < n a,b < n .


The answer is 2417.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Guilherme Niedu
Oct 20, 2017

S = a = 1 n b = 1 n a b a = 1 , a = b n b = 1 , b = a n a b \large \displaystyle S = \sum_{a=1}^{n} \sum_{b=1}^{n} a \cdot b - \sum_{a=1, a=b}^{n} \sum_{b=1, b=a}^{n} a \cdot b

S = a = 1 n a b = 1 n b a = 1 n a 2 \large \displaystyle S = \sum_{a=1}^{n} a \sum_{b=1}^{n} b - \sum_{a=1}^{n} a^2

S = n ( n + 1 ) 2 n ( n + 1 ) 2 n ( n + 1 ) ( 2 n + 1 ) 6 \large \displaystyle S = \frac{n \cdot (n+1)}{2} \cdot \frac{n \cdot(n+1)}{2} - \frac{ n \cdot(n+1) \cdot (2n+1) }{6}

S = ( n 3 n ) ( 3 n + 2 ) 12 \color{#20A900} \boxed{ \large \displaystyle S = \frac{(n^3-n)(3n+2)}{12}}

For n = 99 n=99 :

S = 24174150 \color{#20A900} \boxed{ \large \displaystyle S = 24174150 }

Thus:

m = 2417.415 , m = 2417 \color{#3D99F6} \large \displaystyle m = 2417.415, \boxed{ \large \displaystyle \lfloor m \rfloor = 2417}

Akeel Howell
Oct 19, 2017

We have that a , b { Z + < n } a, b \in \{ \mathbb{Z^+} < n \} and a b a \neq b and we want to find the sum of the product of each pair of integers ( a , b ) (a,b) . In other words, we want to find \substack a , b { Z + < n } a b a b \large \displaystyle \sum_{\substack{a,b \space \in \space \{ \mathbb{Z^+} < \space n \} \\ a \neq b}}{a \cdot b} .

Define a set S S such that S i { Z + < n } S_i \in \{ \mathbb{Z^+} < n \} , where i i refers to the i th i^{\text{th}} element (the index) of S S .

The sum of the product of each pair is thus \substack a , b { Z + < n } a b a b = \substack a , b S a b a b = i j S i S j \displaystyle \sum_{\substack{a,b \space \in \space \{ \mathbb{Z^+} < \space n \} \\ a \neq b}}{a \cdot b} = \sum_{\substack{a,b \space \in \space S \\ a \neq b}}{a \cdot b} = \sum_{i \neq j}{S_i \cdot S_j} .

Note that the square of the sum of all the elements of S S (positive integers less than n n ) is j = 1 n 1 j 2 + i j S i S j \displaystyle \sum_{j = 1}^{n-1}{j^2} + \sum_{i \neq j}{S_i \cdot S_j} .

So i j S i S j = ( j = 1 n 1 j ) 2 j = 1 n 1 j 2 \displaystyle \sum_{i \neq j}{S_i \cdot S_j} = \left( \sum_{j = 1}^{n-1}{j} \right)^2 - \sum_{j = 1}^{n-1}{j^2} .

From here, we can reduce i j S i S j \displaystyle \sum_{i \neq j}{S_i \cdot S_j} to ( n ( n 1 ) 2 ) 2 n ( n 1 ) ( 2 n 1 ) 6 \left( \dfrac{n(n-1)}{2} \right) ^2 - \dfrac{n(n-1)(2n-1)}{6} .

Therefore i j S i S j = n ( n 1 ) ( 3 n ( n 1 ) 2 ( 2 n 1 ) ) 12 = ( n 2 ) ( n 1 ) n ( 3 n 1 ) 12 \displaystyle \sum_{i \neq j}{S_i \cdot S_j} = \dfrac{n(n-1)\left(3n(n-1)-2(2n-1)\right)}{12} = \dfrac{(n-2)(n-1)n(3n-1)}{12} (Final term as pointed out by @Mark Hennings ).

For n = 100 n = 100 this is 98 99 100 299 12 = 33 49 50 299 \dfrac{98 \cdot 99 \cdot 100 \cdot 299}{12} = 33 \cdot 49 \cdot 50 \cdot 299 and this value is m × 1 0 4 m \times 10^4 .

m m is thus 49 299 1650 1 0 4 = 14651 165 1000 \dfrac{49 \cdot 299 \cdot 1650}{10^4} = \dfrac{14651 \cdot 165}{1000} .

By direct computation, we see that m = 2417 . \lfloor m \rfloor = 2417._\square

The desired expression can be simplified to become 1 12 ( n 2 ) ( n 1 ) n ( 3 n 1 ) \tfrac{1}{12}(n-2)(n-1)n(3n-1)

Mark Hennings - 3 years, 7 months ago

Log in to reply

Nice simplification!

I didn't see those factors.

Akeel Howell - 3 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...