Wheat on the Chessboard
The puzzle
An inventor asks a king for one grain of wheat on the first square of a chessboard, two on the second, four on the third, and so on, doubling to the sixty-fourth square.
How much wheat is that in total? Start by working out the total for the first ten squares.
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
The first ten squares hold 1 + 2 + 4 + ... + 512. Add them and compare with 1024.
Hint 2
A sum of powers of two is always one short of the next power.
Show the answer Hide the answer
2^64 - 1 grains, about 1.8 x 10^19 - roughly eight hundred years of the world's entire wheat harvest.
How to get there
The first ten squares hold 1 + 2 + 4 + ... + 512 = 1023, which is 1024 - 1 = 2^10 - 1. The pattern holds generally: the sum of the first n powers of two is 2^n - 1, because each new term equals the whole sum so far plus one.
So the full board holds 2^64 - 1 = 18,446,744,073,709,551,615 grains. A wheat grain weighs around 35 mg, which puts the debt at about 646 billion tonnes - some eight hundred times the world's annual wheat harvest of roughly 800 million tonnes.
The second half of the board is the shock: square 64 alone holds 2^63 grains, which is one more than the whole of the first 63 squares combined. Any doubling process has that property - the last step is always bigger than everything before it - which is why halfway through a doubling you are nowhere near halfway to the end.
The technique worth keeping
Recognise 1 + 2 + 4 + ... + 2^(n-1) = 2^n - 1 on sight. More usefully, remember that in any doubling the final term exceeds the sum of all the others, which is the right intuition for compound growth.