The game of chess was invented in India by a man named Sissa ibn Dahir. The king, Shihram, was so pleased with the game
that he offered Sissa any reward that he wanted. Sissa said that he would take this reward: the king should put one grain of wheat
on the first square of a chessboard, two grains of wheat on the second square, four grains on the third square, eight grains on the
fourth square, and so on, doubling the number of grains of wheat with each square.
How many grains of wheat would be on the chessboard at the finish?
Solution to the Problem:
The simple, brute-force solution is to just manually double and add each step of the series:
Total = 1 + 2 + 4 + ... + 9,223,372,036,854,775,808 = 18,446,744,073,709,551,615
It can also be solved more easily using the formula for the sum of a geometric series:
Sum = 2
64 - 1 = 18,446,744,073,709,551,615.
Back to the story of the invention of chess. The king thought that Sissa was not asking for very much. "That's a tiny reward;
I would have given him much more." He ordered his slaves to bring out the chessboard and they started putting on the wheat.
Everything went well for a while, but the king was surprised to see that by the time they got halfway through the chessboard the
32nd square required more than four billion grains of wheat, or about 100,000 kilos of wheat. Now Sissa didn't seem so stupid anymore.
Even so, King Shihram was willing to pay up.
But as the slaves began on the second half of the chessboard, King Shihram gradually realized that he couldn't pay that much wheat - in
fact, to finish the chessboard you would need as much wheat as six times the weight of all the living things on Earth.