xlix. Wheat and Chessboard

Problem (legend of the inventor of chess). One grain of wheat on the first square, two on the second, four on the third, doubling each square. How much wheat is on the board?

Answer. $1+2+\cdots +2^{63}=2^{64}-1=18446744073709551615$ grains, exactly ULLONG_MAX. At about 50 mg per grain that is roughly $9\cdot 10^{11}$ tonnes, over a thousand years of today’s world wheat harvest (about $8\cdot 10^8$ tonnes a year).

Doubling fact	Value
square $k$	$2^{k-1}$ grains
first $k$ squares	$2^k-1$ (always one less than the next square)
second half of the board vs the first	$2^{32}$ times as much
$2^{10}=1024\approx 10^3$	so $2^{64}\approx 16\cdot 10^{18}$, quick estimate $1.6\cdot 10^{19}$ (true $1.84\cdot 10^{19}$)
lily pad doubling daily, lake full on day 48	half full on day 47
fold a 0.1 mm sheet 42 times	$0.1\text{mm}\cdot 2^{42}\approx 440000$ km, beyond the Moon
doubling time at growth rate $r$	$\ln 2/\ln (1+r)\approx 70/(100r)$ periods (rule of 70)

Overflow in practice

The board is the natural boundary of 64-bit integers, which is why the puzzle doubles as a checklist of integer pitfalls.

Expression	Problem	Fix
1 << 40	int shift, overflow	1LL << 40
1ULL << 64	shift by the full width is undefined	special-case $k=64$, or ~0ULL
1LL << 63	sign bit; before C++20 undefined	use ull, or LLONG_MIN
(ll)pow(10, 18)	double result may be $10^{18}-1$ after truncation	integer loop, or llround
a * b with $a,b\le 10^{18}$	overflows ll	__int128, or __builtin_mul_overflow
sum += x over $10^5$ values up to $10^{14}$	overflows at $9.2\cdot 10^{18}$	check the bound $n\cdot \max$ first, or saturate
a * b % m with $m\approx 10^{18}$	product overflows before %	(i128)a * b % m

ull grainsUpTo(int k) { return k >= 64 ? ~0ULL : (1ULL << k) - 1; }   // squares 1..k, k in [0, 64]
 
ll powSat(ll b, int e, ll cap) {                     // min(b^e, cap) for b >= 1, without overflow
    ll r = 1;
    while (e--) { if (r > cap / b) return cap; r *= b; }
    return r;
}
 
ll mulSat(ll a, ll b) {                              // a * b clamped to [LLONG_MIN, LLONG_MAX]
    ll r;
    if (!__builtin_mul_overflow(a, b, &r)) return r;
    return ((a < 0) ^ (b < 0)) ? LLONG_MIN : LLONG_MAX;
}

Proof: the geometric sum and the saturating helpers

Sum. Let $S={\sum }_{i=0}^{k-1}{2}^i$. Then $2S-S=2^k-1$ (every other term cancels), so $S=2^k-1$; for $k=64$ this is the largest unsigned long long. In particular square $k+1$ holds $2^k=S+1$: one grain more than all previous squares together. The second half holds $2^{64}-2^{32}$ against $2^{32}-1$ in the first, a ratio of $2^{32}$.

powSat. Invariant: $r=b^j\le$ cap after $j$ steps. Before multiplying, $r>\lfloor \text{cap}/b\rfloor$ iff $r\cdot b>\text{cap}$ (for integers $r,b\ge 1$), so the check detects exactly the steps where the product would exceed cap, without computing it. mulSat relies on __builtin_mul_overflow, which computes the exact product and reports whether it fits; on overflow the sign of the true product is the xor of the signs. Doubling time: $(1+r{)}^t=2⟺t=\ln 2/\ln (1+r)$, and $\ln (1+r)\approx r$ for small $r$, with $100\ln 2\approx 69.3$. Checked against __int128 for all $k\le 64$ and random bases and exponents.

Related notes

• C++ for Competitive Programming (integer types)
• Debugging and Stress Testing (overflow bugs)
• Tower of Hanoi (also $2^{64}-1$ moves for 64 discs)