By Kevin Carde
Answer: MBASIC PROGRAMMING
Here are Python implementations of all of the generator functions:
import itertools
def gen0(arg):
# Fibonacci when arg=2
x = range(arg)
for i in itertools.cycle(x):
yield x[i]
x[i] = sum(x)
def gen1(arg):
# binomials n choose arg
x = not arg
while x: yield x
for i in gen1(arg-1):
x += i
yield x
def gen2(arg):
# argth powers
x = not arg
while x: yield x
j = [x]*arg
for i in itertools.izip(*(gen2(i) for i in range(arg))):
x += sum(n*m for n,m in zip(i,j))
yield x
j = i[::-1]
def gen3(arg):
# product of first arg powers
for i in gen2(arg):
x = x*i if i else 1
yield x
def gen4(arg):
# Catalan when arg=1
x = [arg]
while True:
yield x[-1]
x.append(sum(n*m for n,m in zip(x,x[::-1])))
def gen5(arg):
# arithmetic with difference arg-1
x = [-1,arg]
for i in itertools.cycle(range(len(x))):
yield abs(x[i])
x[i] -= 2*sum(x)
def generator6(arg):
# geometric with ratio arg
x=[1,arg]
for i in itertools.cycle(range(arg)):
if not i:
yield x[i]
x[bool(i)]=bool(i)*x[bool(i)]+x[not(i)]
These are, in fact, all very well-known sequences, but the algorithm for generating them is not always as well-known. Here is a description of what each generator function is doing:
gen0: This one is fairly straightforward. It is simply the recurrence x_{n+arg} = x_n + x_{n+1} + ... + x_{n+arg-1}, with initial values x_i=i for i=0,...,arg-1. Hence when arg=2, this is simply the Fibonacci numbers.
gen1: This one generates binomial coefficients using the idea behind the "hockey stick" formula. It yields the sequence n choose arg for n=arg, arg+1, arg+2, etc. To get from n choose arg to (n+1) choose arg, the algorithm simply adds n choose arg-1.
gen2: The most fun! This produces perfect argth powers, using the identity (n+1)^k - n^k = (n+1)^{k-1} + (n+1)^{k-2}*n + ... + n^{k-1}. The giant zip produces the 0 through (k-1)th powers; it stores the previous one, reversed, in order to dot it with the next one. The result is precisely (n+1)^k - n^k according to the above identity, so we add that to our current power to get the next one.
gen3: This one is possibly the most straightforward. It begins at 1, then multiplies by successive elements of gen2(arg). Since gen2(arg) yields the perfect argth powers, this generator function yields the products of the first argth powers. In particular, if arg=1, this generates the factorials.
gen4: This yields the Catalan numbers if arg=1, using the recurrence x_{n+1} = x_0*x_n + x_1*x_{n-1} + ... + x_n*x_0. arg just affects the initial value.
gen5: This yields the arithmetic sequence starting at 1 with difference arg-1, but it does so in not the most obvious way. Notice that by definition, a sequence is arithmetic if it satisfies the recurrence x_{n+1} - x_n = x_n - x_{n-1}. Rearranging, this is x_{n+1} = 2*x_n - x_{n-1}. If we fiddle with signs so that every other term is taken to be negative, this recurrence has the form x_{n+1} = -2*x_n - x_{n-1} = x_{n-1} - 2*(x_n+x_{n-1}). Hence we generate x_{n+1} from x_{n-1} by subtracting twice the sum of the elements we're storing in our list.
gen6: This yields the geometric sequence starting at 1 with ratio arg. The list x stores the next two values of the geometric sequence, and then we proceed in cycles of length arg. Every arg steps, when i=0, we will find ourselves with a list x of the form [arg^{k-1}, arg^k]. We yield arg^{k-1}, then copy arg^k over into the first position. Then, for the remaining steps in the cycle, we add copies of arg^k to the second position. Doing this arg-1 times results in a list of the form [arg^k, arg^{k+1}], and we are now ready to yield arg^k, the next element of the sequence.
The expressions on the bottom of the page are generating functions for various sequences generated by these generator functions. Using the assignment of letters to generators given in the puzzle, the two lines at the bottom spell out MBASIC PROGRAMMING.