Find the sum of the product of each pair of positive integers a and b such that a , b < 1 0 0 and a = b .
If your solution can be expressed as m × 1 0 4 , submit your answer as ⌊ m ⌋ .
Bonus: Generalize for a , b < n .
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.
We have that a , b ∈ { Z + < n } and a = b and we want to find the sum of the product of each pair of integers ( a , b ) . In other words, we want to find \substack a , b ∈ { Z + < n } a = b ∑ a ⋅ b .
Define a set S such that S i ∈ { Z + < n } , where i refers to the i th element (the index) of 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 .
Note that the square of the sum of all the elements of S (positive integers less than n ) is j = 1 ∑ n − 1 j 2 + i = j ∑ S i ⋅ S j .
So i = j ∑ S i ⋅ S j = ( j = 1 ∑ n − 1 j ) 2 − j = 1 ∑ n − 1 j 2 .
From here, we can reduce i = j ∑ S i ⋅ S j to ( 2 n ( n − 1 ) ) 2 − 6 n ( n − 1 ) ( 2 n − 1 ) .
Therefore i = j ∑ S i ⋅ S j = 1 2 n ( n − 1 ) ( 3 n ( n − 1 ) − 2 ( 2 n − 1 ) ) = 1 2 ( n − 2 ) ( n − 1 ) n ( 3 n − 1 ) (Final term as pointed out by @Mark Hennings ).
For n = 1 0 0 this is 1 2 9 8 ⋅ 9 9 ⋅ 1 0 0 ⋅ 2 9 9 = 3 3 ⋅ 4 9 ⋅ 5 0 ⋅ 2 9 9 and this value is m × 1 0 4 .
m is thus 1 0 4 4 9 ⋅ 2 9 9 ⋅ 1 6 5 0 = 1 0 0 0 1 4 6 5 1 ⋅ 1 6 5 .
By direct computation, we see that ⌊ m ⌋ = 2 4 1 7 . □
The desired expression can be simplified to become 1 2 1 ( n − 2 ) ( n − 1 ) n ( 3 n − 1 )
Log in to reply
Problem Loading...
Note Loading...
Set Loading...
S = a = 1 ∑ n b = 1 ∑ n a ⋅ b − a = 1 , a = b ∑ n b = 1 , b = a ∑ n a ⋅ b
S = a = 1 ∑ n a b = 1 ∑ n b − a = 1 ∑ n a 2
S = 2 n ⋅ ( n + 1 ) ⋅ 2 n ⋅ ( n + 1 ) − 6 n ⋅ ( n + 1 ) ⋅ ( 2 n + 1 )
S = 1 2 ( n 3 − n ) ( 3 n + 2 )
For n = 9 9 :
S = 2 4 1 7 4 1 5 0
Thus:
m = 2 4 1 7 . 4 1 5 , ⌊ m ⌋ = 2 4 1 7