Power of 3 in 1000!

There are $\lfloor \frac {1000}{3} \rfloor = 333$ multiple of $3$ in the $1000$ factors of $1000!$ . Every multiple of $3$ have at least $1$ factor of $3^1$ , so $1000!$ is divisible by $3^{333}$ . Moreover, there are $\lfloor \frac {1000}{3^2} \rfloor = 111$ multiple of $3^2$ in the $1000$ factor of $1000!$ . Every multiple of $3^2$ has $3 \times 3$ as factor and note that multiple of $3^2$ is also multiple of $3^1$ so we have already counted the first $3$ in the previous counting, thus this time we are only counting the second $3$ , and this provide extra factor, $3^{111}$ , so now we know that $1000!$ is divisible by $3^{333} \cdot 3^ {111} = 3 ^ {444}$ . Apply the same argument on counting the number of multiple of $3^3, 3^4, 3^5, 3^6$ in $1000$ factor of $1000!$ lead to $a = \lfloor \frac {1000}{3} \rfloor + \lfloor \frac {1000}{3^2} \rfloor + \lfloor \frac {1000}{3^3} \rfloor + \lfloor \frac {1000}{3^4} \rfloor + \lfloor \frac {1000}{3^5} \rfloor + \lfloor \frac {1000}{3^6} \rfloor \\ = 333 + 111 + 37 + 12 + 4 + 1 \\ = 498 \\$ .

Generalization : The argument above can be generalized to the problem of determining the highest power $n^a$ that divides $k!$ . $a = \displaystyle \sum_{i=1}^{\infty} \lfloor \frac {k}{n^i} \rfloor$

As 3^a is divided by the product of so many numbers, 1000!, the highest power of 3 that can be divided by 1000! depends on the number of factors 3 in the product of numbers from 1 to 1000.

The quantity of numbers from 1 to 1000 which can be divided by 3 at least once can be found from the smallest integer < \frac {1000}{3} , as this would show how many numbers have 3 as a factor. The result is 333.

Then, we can find the quantity of numbers with 3^2, 9, as a factor, using the same method, with a result of 111. For numbers with the factor 9, after the factor 3 has been taken care of in the earlier step, the factor 9 would become the factor 3, and so they are divided again, and are thus taken into account. So far, a can definitely be at least 444.

This continues on for factors 3^3, 27, 3^4, 81, 3^5, 243 and 3^6, 729. As 729 is the highest value of 3^x lower than 1000, it is the last power to be considered. After counting the quantity of numbers with factors 3^1, 3^2, 3^3, 3^4, 3^5 and 3^6, the highest power a of 3^a divisible by 1000! is determined to be 333+111+37+12+4+1=498.

First, we calculate the number of multiplier which is divisible by 3^6- denoted k (for the reason that 3^7 > 1000), because k.(3^6) \leq 1000, and k is an positive integer, so k=1 We continue equivalently with respect to 3^5, 3^4, 3^3, 3^2, 3^1. But in each case, we have to omit the multiplier which is divisible by 3. For example, for 3^5, we have 4 value of k (1, 23, 4), but one of those is divisible by 3, that means we may be double-counting. In the end we have the result of the product : 3^(6 1) 3^(5 3) 3^(4 8) 3^(3 25) 3^(2 74) 3^(1 222) P (P represented for the remain product which is indivisible by 3) =3^498*P Therefore we get the value of a is 498 P/s: I come from non-english-speaking country, so there definitely some mistakes about expession and grammar

For any integer $d>0$ , let $1000 = q \cdot d + r$ , where $q$ and $r$ are integers and $0 \leq r \leq d-1$ is the remainder of 600 upon division by $d$ . Then there are $q$ numbers less than or equal to 1000 that are multiples of $d$ .

We will calculate the number of times that 3 divides $1000!$ and this will give us the highest power of 3. There are 333 multiples of 3, 111 multiples of 9, 37 multiples of 27, 12 multiples of 81, 4 multiples of 243, 1 multiple of 729, and 0 multiples of 2187. The multiples of 3 will contribute 1 factor of 3 each. The multiples of 9 will contribute 2 factors of 3, but we have already counted 1 factor from the multiple of 3, so they will contribute 1 additional factor of 3. Similarly, the multiples of 27, 81, 243, and 729 will contribute 1 additional factor of 3.

Therefore the highest power of 3 that divides $1000!$ is $333 + 111 + 37 + 12 + 4 + 1 = 498$ .

Note: Using the floor function, the above answer is

$\left \lfloor \frac {1000} {3} \right \rfloor + \left \lfloor \frac {1000} {9} \right \rfloor + \left \lfloor \frac {1000} {27} \right \rfloor + \left \lfloor \frac {1000} {81} \right \rfloor + \left \lfloor \frac {1000} {243} \right \rfloor + \left \lfloor \frac {1000} {729} \right \rfloor = 498.$

1000/3=333+1000/9=111+ 1000/27=37+1000/81=12+1000/243=4+1000/729=1 =498

$a = \sum_{i=1}^{6}\lfloor \frac{k}{n^i} \rfloor=\boxed {498}$ where $k=1000$ and $n=3$

We have to use the Greatest Integer Function of the floor function to find out how much of each power of $3$ can go into $1000$ :

$\left\lfloor \frac { 1000 }{ 3 } \right\rfloor +\left\lfloor \frac { 1000 }{ { 3 }^{ 2 } } \right\rfloor +\left\lfloor \frac { 1000 }{ { 3 }^{ 3 } } \right\rfloor +\left\lfloor \frac { 1000 }{ { 3 }^{ 4 } } \right\rfloor +\left\lfloor \frac { 1000 }{ { 3 }^{ 5 } } \right\rfloor +\left\lfloor \frac { 1000 }{ { 3 }^{ 6 } } \right\rfloor$ which is $\boxed{498}$

[1000/3]+[1000/9]+[1000/27]+[1000/81]+[1000/243]+[1000/729]=333+111+37+12+4+1=498