Hi, does anybody of you know of the Wheat chessboard legend? If not, it goes something like this:
Shihram, ruler of India, was quite a abusive ruler. To show him the wrongness of his ways without risking his own live, Sissa developed a game in which the king was the most important figure, but was not able to do anything without his pawns. You may have already guessed that, but this game was chess. Playing chess with Sissa, Shihram became a more calm ruler. To reward Sissa for this, Shihram granted him a wish. And Sissa wished to have wheat grains put onto a chessboard, one grain on the first field, two on the second, four on the third and so on. Shihram started laughing and granted his wish, still being annoyed because he thought Sissa was wishing for so little. Two days later, he asked his underlings if Sissa had gotten his reward, but was told that his underlings were still calculating. Two more days later, he was told that the reward was not yet calculated, but already much more then all wheat in his whole kingdom.
So how much was it exactly?
A chessboard has 64 fields so we would have:
$$w = \sum_{i=0}^{63} 2^i$$
We notice if we wrote this in binary, this would be:
$$w = 0111111111111111111111111111111111111111111111111111111111111111$$
which we also can write as:
$$w = 1000000000000000000000000000000000000000000000000000000000000000 - 1$$
or again in decimal:
$$w = 2^{64} - 1$$
so how do we calculate this without a calculator?
Lets assume we know: $1024 = 2^{10}$ so we get $w = 2^4 \cdot 1024^6$.
Now the question is, how much is $1024^6$?
Spliting it into $(1000 + 24)^6$ and using Pascal's triangle
$$ \begin{array}{c|ccccccccccccc} 0& & & & & & & 1 & & & & & & \ 1& & & & & & 1 & & 1 & & & & & \ 2& & & & & 1 & & 2 & & 1 & & & & \ 3& & & & 1 & & 3 & & 3 & & 1 & & & \ 4& & & 1 & & 4 & & 6 & & 4 & & 1 & & \ 5& & 1 & & 5 & & 10& &10 & & 5 & & 1 & \ 6& 1 & & 6 & &15 & &20 & &15 & & 6 & & 1 \end{array} $$
leads us to this:
$$ \begin{align} (1000 + 24)^6 &= 1 &\cdot 24^0 &\cdot 1000^6 \ &+ 6 &\cdot 24^1 &\cdot 1000^5 \ &+ 15 &\cdot 24^2 &\cdot 1000^4\ &+ 20 &\cdot 24^3 &\cdot 1000^3\ &+ 15 &\cdot 24^4 &\cdot 1000^2\ &+ 6 &\cdot 24^5 &\cdot 1000^1\ &+ 1 &\cdot 24^6 &\cdot 1000^0 \end{align} $$
which means we only need to calculate the powers of 24, the higher the power of 24 the less effect it will have on the final result so we can even ignore higher orders of 24 if we are not interested in calculating the value exactly. Suddenly, 64 multiplications become 6 multiplications for the powers of 24, 6 additions and one final multiplications with 16.
Actually calculating them will give us $\approx 18.447 \cdot 10^{18}$ wheat grains. No wonder they could not find enough of it ^^
So how did Shihram solve this without refusing to grant Sissa his wish?
Shihram became very angry when he understood that Sissa had tricked him into granting an unfulfillable wish. But his underling had an idea how to still grant Sissa his wish. Sissa should come to him and count his reward one grant at a time!