# Thread: Set of Very Challenging Problems ):

1. ## Set of Very Challenging Problems ):

1) 2^9876543
a) determine last 3 digits
b) determine first 3 digits

2) find sum of numbers from 1000 to 10000 with distinct digits

3) NO COMPUTER SOFTWARE. how many 0s at the end of 1000!..1001!....all the way to 1005!

2. Hello, CalcBeginner!

Edit: Okay, you want the number-of-zeros for each factorial.

3) Find the number of 0's at the end of: .$\displaystyle (1000!)(1001!)(1002!)(1003!)(1004!)(1005!)$

Every factor-of-5 (together with a factor-of-2) contributes a zero to the end of the number.

How many factors-of-5 are in 1000-factorial?

Every 5th number has a factor-of-5: .$\displaystyle \left[\frac{1000}{5}\right] \:=\:200$ fives.

But every 25th number has $\displaystyle 5^2$, each of which contributes another 5: .$\displaystyle \left[\frac{1000}{25}\right] \:=\:40$ more fives.

And every 125th number has $\displaystyle 5^3$, each of which contributes yet another 5: .$\displaystyle \left[\frac{1000}{125}\right] \:=\:8$ more fives.

And every 625th number has $\displaystyle 5^4$, each of which contributes yet another 5: .$\displaystyle \left[\frac{1000}{625}\right] \:=\:1$ more five.

Therefore, 1000! contains $\displaystyle 200 + 40 + 8 + 1 \:=\:249$ factors-of-5,
. . . . . . . . and ends in 249 zeros.

How factors-of-5 are in 1001-factorial?
. . Using the same prodecure, we find the same number: 249 final zeros.

The same holds true for 1002-factorial, 1003-factorial and 1004-factorial.
. . Each has 249 final zeros.

We find that 1005! contains: .$\displaystyle \left[\frac{1005}{5}\right] + \left[\frac{1005}{25}\right] + \left[\frac{1005}{125}\right] + \left[\frac{1005}{625}\right] \;=\;250$ final zeros

So we have these answers: . $\displaystyle \begin{array}{ccc}\text{Number} & \text{Final zeros} \\ \hline 1000! & 249 \\ 1001! & 249 \\ 1002! & 249 \\ 1003! & 249 \\ 1004! & 249 \\ 1005! & 250 \end{array}$

3. No, sorry
it actually means find the number of 0s at the end of 1000!
then 10001!
then 10002! all the way to 1005! separately ):

4. Originally Posted by CalcBeginner
No, sorry
it actually means find the number of 0s at the end of 1000!
then 10001! then 10002! all the way to 1005! separately ):
$\displaystyle 1000!$ ends in $\displaystyle \left\lfloor {\frac{{1000}} {5}} \right\rfloor + \left\lfloor {\frac{{1000}} {{25}}} \right\rfloor + \left\lfloor {\frac{{1000}} {{125}}} \right\rfloor + \left\lfloor {\frac{{1000}} {{625}}} \right\rfloor$ zeros.
That is the floor function.

5. Originally Posted by CalcBeginner
2) find sum of numbers from 1000 to 10000 with distinct digits
Hi CalcBeginner,

I can address problem 2. Am I to understand that you're not allowed to use computer software for this one either? Because writing a brute force program should be pretty trivial, you just need a doesHaveDistinctDigits() function, and a simple for() loop.

But for a more paper-and-pencil approach, consider that we are looking at simple permutations, except that the first digit has to be treated in a special manner because it cannot be zero.

Before we begin, I'll tell you that the following is a complete solution, so if you want to solve it more on your own (which might increase your opportunity to learn), then you should try to anticipate my next steps, and possibly try stopping part-way through to see if you can complete the rest of the steps on your own.

So, consider 9 cases, which will basically reduce to just one case since they're so similar.

case: first digit is 1:

Numbers of the form 1XYZ, where X, Y, and Z can be any distinct integers from 0 to 9 inclusive other than 1.

It should be evident (I won't offer a proof) that for the permutations of {X, Y, Z}, each digit will appear the same number of times in each position.

So we have 3! ways to arrange them, and each one will appear in each slot 3!/3 times.

So for a particular {X, Y, Z}, we'll have (3!)(1)(10^3) + (3!/3)[(10^2)(X+Y+Z) + (10^1)(X+Y+Z) + (10^0)(X+Y+Z)] = 6000 + (222)(X+Y+Z).

Then we need to work out how many ways to get {X, Y, Z}. There are C(9, 3) ways, where C(n, k) is binomial coefficient "n choose k." Consider that if we fix X, there are C(8, 2) ways to pick {Y, Z}. That means that each digit appears in exactly C(8, 2) of the C(9, 3) combinations. So we have

$\displaystyle \sum_{i=1}^{C(9, 3)}\big(6000+(222)(X_i+Y_i+Z_i)\big)$

$\displaystyle = (6000)\binom{9}{3}+(222)\bigg(\sum_{i=1}^{C(9, 3)}X_i+\sum_{i=1}^{C(9, 3)}Y_i+\sum_{i=1}^{C(9, 3)}Z_i\bigg)$

$\displaystyle = (6000)\binom{9}{3}+(222)\binom{8}{2}(0+2+3+4+5+6+7 +8+9)$

$\displaystyle = (\color{red}1\color{black})(6000)\binom{9}{3}+(222 )\binom{8}{2}(T(9)-\color{red}1\color{black})$

where $\displaystyle T(n) = \frac{n(n+1)}{2}$ is the nth triangle number, and marked in red are those things specific to choosing the digit 1 in the thousands digit place for this case.

Then simply do cases 2-9 and sum them. It looks like this, in case you had any doubt

$\displaystyle \sum_{i=1}^9\bigg( (i)(6000)\binom{9}{3}+(222)\binom{8}{2}(T(9)-i) \bigg)$

I have confirmed this works using a brute force algorithm.

6. Originally Posted by CalcBeginner
1) 2^9876543
a) determine last 3 digits
This is asking for $\displaystyle 2^{9876543} \bmod{1000}$.

I'd calculate this by noticing $\displaystyle 9876543 = 3\cdot 227\cdot 14503$.

7. For question 1 (a) ,

we have $\displaystyle x = 2^{9876543} \equiv 0 \bmod{8}$

Also consider (by property of Euler-Phi function )

$\displaystyle 2^{100} \equiv 1 \bmod{125}$

therefore,

$\displaystyle x = 2^{9876500 + 43 }= 2^{9876500}\cdot 2^{43}$

$\displaystyle \equiv 2^{43} \equiv 2\cdot (2^7)^6 \equiv 2(3^6) \equiv 2(3)(243) \bmod{125}$

$\displaystyle \equiv 6(-7) \equiv -42 \equiv 83 \bmod{125}$

We obtain $\displaystyle x \equiv 0\bmod{8} , x \equiv 83 \bmod{125}$

so $\displaystyle x \equiv 208 \bmod{1000}$ , the answer is$\displaystyle 208$.

Can we use calculator to sovle the b part of question one ?

I obtain $\displaystyle 9400169755.....$
EDITED : it is wrong answer , so embarrassed ...

8. Originally Posted by CalcBeginner
1) 2^9876543
b) determine first 3 digits
Suppose a number $\displaystyle n$ is written in scientific form. That is, $\displaystyle n = d.a \times 10^b$, where $\displaystyle d$ is a single digit.
This means that $\displaystyle \log_{10} n = b + \log_{10} d.a$. From here it follows that $\displaystyle \log_{10}d.a = \{\log_{10}n\}$, where $\displaystyle \{x\} = x - \lfloor x \rfloor$. We want the first digits, which can be obtained from $\displaystyle d.a$. Therefore, we want to compute $\displaystyle 10^{\{\log_{10}n\}} = d.a$. Now all what's left is to let $\displaystyle n=2^{9876543}$ and remember that $\displaystyle \log a^b = b\log a$.

The answer is get is $\displaystyle 4.971244503647...$.