TAOCP 5.4.2 Exercise 21

Exercise 21. [11] [11] What should appear on level 7 in (26)?

Verified: yes
Solve time: 1m23s

Solution

In the six-tape case we have $T=6$ and hence $P=T-1=5$. The perfect distributions in (26) satisfy the $5$th-order Fibonacci propagation rule: each new level is obtained by summing the preceding five levels componentwise, as encoded by the backward construction of the table.

Let level $n$ be the vector

$$ (A_n, B_n, C_n, D_n, E_n). $$

Then the structure of (26) implies that level $n+1$ is formed by

$$ A_{n+1}=A_n+A_{n-1}+A_{n-2}+A_{n-3}+A_{n-4}, $$

and similarly for each coordinate, since each tape’s population evolves according to the same $5$th-order Fibonacci recurrence induced by the reversed merging pattern.

Using the last five fully determined levels,

$$ \begin{aligned} \text{level }2 &= (2,2,2,2,1),\ \text{level }3 &= (4,4,4,3,2),\ \text{level }4 &= (8,8,7,6,4),\ \text{level }5 &= (16,15,14,12,8),\ \text{level }6 &= (31,30,28,24,16), \end{aligned} $$

level $7$ is obtained by coordinatewise addition of these five vectors.

For the first coordinate,

$$ A_7 = 31+16+8+4+2 = 61. $$

For the second coordinate,

$$ B_7 = 30+15+8+4+2 = 59. $$

For the third coordinate,

$$ C_7 = 28+14+7+4+2 = 55. $$

For the fourth coordinate,

$$ D_7 = 24+12+6+3+2 = 47. $$

For the fifth coordinate,

$$ E_7 = 16+8+4+2+1 = 31. $$

Thus level $7$ in (26) is

$$ (61, 59, 55, 47, 31), $$

which is the next perfect $5$th-order Fibonacci distribution in the polyphase pattern.

$$ \boxed{(61,\ 59,\ 55,\ 47,\ 31)} $$