A Huge Summation it is. #3

Number Theory Level 4

$\color{#3D99F6}{\displaystyle \sum_{n=1}^9 \left( {11 \times n} \right)^{11 \times n}}$

Find the last three digits of the above summation.

Join the Brilliant Classes and enjoy the excellence. Also checkout Foundation Assignment #2 for JEE.

The answer is 987.

2 solutions

Mas Mus
May 31, 2015

Let's write all items of the summation:

${11}^{11}=(10+1)^{11}=1000\times{C_1}+{11\choose{2}}\times{100}\times{1^{11}}+111\times{1}^{11}\\{22}^{22}=(20+2)^{22}=1000\times{C_2}+{22\choose{2}}\times{100}\times{2^{22}}+221\times{2}^{22}\\{33}^{33}=(30+3)^{33}=1000\times{C_3}+{33\choose{2}}\times{100}\times{3^{33}}+331\times{3}^{33}\\\vdots\\{99}^{99}=(90+9)^{99}=1000\times{C_9}+{99\choose{2}}\times{100}\times{9^{99}}+991\times{9}^{99}$

It's clear that $1000\times{C_1}, 1000\times{C_2}, 1000\times{C_3}, \ldots, 1000\times{C_9}$ are divisible by $1000$ , so we just need to find the reminder of all two last items $\pmod{1000}$ .

Now, we have

${11\choose{2}}\times{100}\times{1^{11}}+111\times{1}^{11}\equiv\left(500+111\right)\times{1^{11}}\equiv611\times{1^{11}}\pmod{1000}\\{22\choose{2}}\times{100}\times{2^{22}}+221\times{2}^{22}\equiv\left(100+221\right)\times{2^{22}}\equiv321\times{2^{22}}\pmod{1000}\\{33\choose{2}}\times{100}\times{3^{33}}+331\times{3}^{33}\equiv\left(800+331\right)\times{3^{33}}\equiv131\times{3^{33}}\pmod{1000}\\\vdots\\{99\choose{2}}\times{100}\times{9^{99}}+991\times{9}^{99}\equiv\left(100+991\right)\times{9^{99}}\equiv91\times{9^{99}}\pmod{1000}$

By using Euler's theorem, CRT, and the properties of modular arithmetic we will find that

${2}^{22}\equiv304\pmod{1000}~~~~~{3}^{33}\equiv523\pmod{1000}~~~~~{4}^{44}\equiv56\pmod{1000}\\{5}^{55}\equiv125\pmod{1000}~~~~~{6}^{66}\equiv456\pmod{1000}~~~~~{7}^{77}\equiv207\pmod{1000}\\{8}^{88}\equiv616\pmod{1000}~~~~~{9}^{99}\equiv889\pmod{1000}$

Then, we have left

$611\times{1}+321\times{304}+131\times{523}+41\times{56}+51\times{125}+161\times4{56}+\\371\times{207}+681\times{616}+91\times{889}\\\equiv611+584+513+296+375+416+797+496+899\\\equiv4987\equiv\boxed{987}\pmod{1000}$

This is a good solution

Rama Devi - 6 years ago

i did the same way

Shashank Rustagi - 5 years, 12 months ago

Brock Brown
May 26, 2015

Python 2.7:

1 2	`total = sum([(11n)(11n) for n in xrange(1,10)]) print "Answer:", str(total)[-3:]`

How to write this type of Computerised Solution? I mean how to write the code in this form? @Brock Brown

Anik Mandal - 6 years ago

Do you mean the part that's like this?

1	`sum([(11n)(11n) for n in xrange(1,10)])`

That's called a list comprehension .

Here's an example of a list comprehension that finds the sum of the squares of the first 10 natural numbers:

1	`print sum([n*n for n in xrange(10)])`

Which is just the shorter version of this:

total = 0
for n in xrange(10):
    total += n*n
print total

Does that answer your question, or were you asking something else?

Brock Brown - 6 years ago

I was able to write the code.But I could not Write it in that form(program format) I want to post a solution as a code..