Posts

Showing posts from September, 2013

Giant Numbers and Modulo Arithmetic

Q: What is the last digit of the giant number $$7^{2000}$$.

Kindle Fire HDX 7", HDX Display, Wi-Fi, 16 GB - Includes Special Offers

A: At first blush this is an impossible task. The above number is impossible to compute. However, using some simple rules from modulo arithmetic, it is possible to answer this.

Let us first try to solve this the long way and run some experiments with 7.
$$7^{2} = 49 \text{ last digit is 9}\\ 7^{3} \equiv 49 \times 7 \equiv \text{ last digit is 3 as } 9\times7 \equiv \text{ last digit is 3}\\$$
Continuing in the same fashion
$$7^{4} \equiv 3 \times 7 \equiv \text{ last digit is 1 as } 3 \times 7 = 21$$
Now $$7 ^ {5}$$ would have its last digit as 7, because 21's last digit is 1 and when multiplied by 7 yields 7. But this is the same as $$7^{1}$$. This resets the entire process. We can conclude that as we multiply into higher powers of 7, the last digits cycles (of length 4) as $${7,9,3,1,...}$$. This implies, $$7^{2000}\… The Five Numbers Game Q: You are in a game where numbers from 1 to 5 are drawn in a random order (without repetition). You win the game if you do not get 3 numbers in successive order (not necessarily consecutive) that are increasing. What is the probability that you will win this game? Catalan Numbers with Applications A: Problems of this particular nature are trivially solved by using/remembering that the number of permutations that avoid an increasing triplet of 3 numbers are simply the Catalan number for n=5. Catalan number for a given \(n$$ is
$$C_n = \frac{1}{n+1}\binom{2n}{n}$$
Plugging in $$n = 5$$ into this yields
$$C_5 = \frac{1}{6}\frac{10!}{5!5!} = 42$$
The total number of ways that 5 numbers can be drawn is $$5! = 120$$. The probability that you will win the game is $$1 - \frac{42}{120} = 65\%$$.

If you are looking to buy some books in probability here are some of the best books to learn the art of Probability

Fifty Challenging Problems in Probability with Solutions …

The Best Books for Linear Algebra

The following are some good books to own in the area of Linear Algebra.

Linear Algebra (2nd Edition)
This is the gold standard for linear algebra at an undergraduate level. This book has been around for quite sometime a great book to own.

Linear Algebra: A Modern Introduction
Good book if you want to learn more on the subject of linear algebra however typos in the text could be a problem.

Linear Algebra (Dover Books on Mathematics)
An excellent book to own if you are looking to get into, or want to understand linear algebra. Please keep in mind that you need to have some basic mathematical background before you can use this book.

Linear Algebra Done Right (Undergraduate Texts in Mathematics)
A great book that exposes the method of proof as it used in Linear Algebra. This book is not for the beginner though. You do need some prior knowledge of the basics at least. It would be a good add-on to an existing course you are doing in Linear Algebra.

Linear Algebra, 4th Edition
This is good book …

Estimating Unseen Bugs in Software

Q: Two engineers independently do quality assurance testing a large swath of code and discover $$e_1$$ and $$e_2$$ number of bugs of which $$e_c$$ are common to both. The probability that each of them would find a bug given a large swath of code is $$p_1$$ and $$p_2$$ respectively. What is your best estimate of the number of unseen bugs in the code?

Toshiba Satellite C55D-A5240NR 15.6-Inch Laptop (Satin Black in Trax Horizon)

A: This puzzle is inspired from W Feller's book on introduction to probability. The total number of unique bugs identified are $$e_1 + e_2 - e_c$$. Let $$B_0$$ represent the total number of bugs in the software application. We could make the following statements
$$e_1 = p_1 \times B_0 \\ e_2 = p_2 \times B_0 \\ e_c = p_1 p_2 \times B_0 = \frac{e_1 e_2}{B_0}$$
The unseen bugs are simply
$$\text{Unseen Bugs} = B_0 - (e_1 + e_2 - e_c)$$
Combining the above two equations yields

\text{Unseen Bugs} = \frac{e_1 e_2}{e_c} - (e_1 + e_2 - e…

Blending Expert Estimates

Q: You have a diamond but are not sure whether its a real or a fake one. You show the diamond to two experts who independently estimate the probability that it is real at $$p_1$$ and $$p_2$$. What is your estimate of what the true probability is?

Canon EOS Rebel T3 12.2 MP CMOS Digital SLR Camera with EF-S 18-55mm f/3.5-5.6 IS II Zoom Lens & EF 75-300mm f/4-5.6 III Telephoto Zoom Lens + 10pc Bundle 16GB Deluxe Accessory Kit

A: Surprisingly, there is no clear answer or strategy on how to approach and blend such subjective estimates together. Most people run into similar situations all the time wherein they get estimates from different sources on a fixed decision they need to make.

A naive way to approach this would be to average the two estimates. This would yield $$\frac{p_1 + p_2}{2}$$ in the present case. But this doesn't address all the cases. For example if $$p_1 = p_2 = 0.6$$, i.e. the experts agree independently the overall estimate has to be greate…