E2.29The Lazy Caterer's sequence

The Lazy Caterer's Sequence, \(f(n)\), describes the maximum number of pieces a circular pizza can be divided into with an increasing number of cuts, \(n\). Clearly \(f(0)=1\), \(f(1)=2\) and \(f(2)=4\)). For \(n=3\), \(f(3) = 7\) (the maximum number of pieces are formed if the cuts do not intersect at a common point). It can be shown that the general recursion formula,

applies. Although there is a closed form for this sequence, \(f(n) = \frac{1}{2}(n^2 + n + 2)\), we could also define a function to grow a list of consecutive values in the sequence:

>>> def f(seq):
...     seq.append(seq[-1] + n)
...
>>> seq = [1]     # f(0) = 1
>>> for n in range(1,16):
...     f(seq)
...
>>> print(seq)
[1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121]

The list seq is mutable and so grows in place each time the function f() is called. The n referred to within this function is the name found in global scope (the for loop counter).