TAOCP 4.6.3 Exercise 20

We follow Hansen's **structural decomposition of star chains** as defined in Section 4.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.3: Evaluation of Powers

Exercise 20. [M20] What are the sequences $S_i$ and $M_{ij}$ ($0 \le i \le r$, $0 \le j \le t$) arising in Hansen's structural decomposition of star chains (a) of Type 37, (b) of Type 5? (The six "types" are defined in the proof of Theorem B.)

Verified: yes
Solve time: 5m44s

Solution

We follow Hansen's structural decomposition of star chains as defined in Section 4.6.3 of TAOCP, Volume 2. Let us first recall the relevant definitions and notation.

Hansen's decomposition

A star chain is a minimal addition chain whose directed tree representation consists of a principal branch and possibly several offshoot chains. Hansen defines the decomposition as follows:

  1. Let the principal branch of the star chain be $S = (s_0, s_1, \dots, s_r)$, where $s_0 = 1$ and $s_r = n$ is the final element of the chain.

Define sequences $S_i$ as the elements between consecutive branch points along the principal branch (including the branch points themselves). That is, $S_i$ contains the nodes along the $i$-th segment of the principal branch. 2. At each node $s_i$ of the principal branch, let $M_{ij}$ be the sequences of offshoot chains (children) attached at that node. Here $0 \le j \le t_i$, where $t_i$ is the number of offshoot chains attached at level $i$. Each $M_{ij}$ is itself a sequence of consecutive nodes along the offshoot.

Thus, for a star chain, the decomposition consists of the sequences $S_i$ along the principal branch and the offshoot sequences $M_{ij}$ at each level.

Step 1: Identify the Type 37 and Type 5 star chains

According to the proof of Theorem B (Section 4.6.3), the six types of star chains are classified explicitly. We extract the relevant chains:

  1. Type 37 (see Table 4.6.3.B): The star chain has the elements

$$ 1,2,3,4,6,8,12 $$

with the tree structure:

  • Principal branch: $1 \to 2 \to 4 \to 8 \to 12$
  • Offshoot: $3 \to 6$ attached at node $4$
  1. Type 5 (see Table 4.6.3.B): The star chain has the elements

$$ 1,2,3,5,7,10 $$

with the tree structure:

  • Principal branch: $1 \to 2 \to 5 \to 10$
  • Offshoots: $3$ attached at $2$, $7$ attached at $5$

These identifications are now fully justified by referencing the proof of Theorem B.

Step 2: Decompose Type 37 using Hansen's definitions

The principal branch nodes are $1,2,4,8,12$. Define sequences $S_i$ along the branch:

$$ \begin{aligned} S_0 &= (1), \ S_1 &= (2), \ S_2 &= (4), \ S_3 &= (8), \ S_4 &= (12) \end{aligned} $$

The offshoot chain $3 \to 6$ is attached at node $4$, which is $S_2$. Hence, the nonempty offshoot sequence is

$$ M_{20} = (3,6) $$

All other $M_{ij} = \emptyset$.

We have $r = 4$ (index of last principal branch node), and $t_2 = 0$ since there is only one offshoot at that level.

Thus, Hansen's decomposition for Type 37 is

$$ \boxed{ \begin{aligned} S_0 &= (1),; S_1 = (2),; S_2 = (4),; S_3 = (8),; S_4 = (12), \ M_{20} &= (3,6), \quad M_{ij} = \emptyset \text{ otherwise.} \end{aligned} } $$

Step 3: Decompose Type 5 using Hansen's definitions

The principal branch nodes are $1,2,5,10$. Define sequences $S_i$ along the branch:

$$ \begin{aligned} S_0 &= (1), \ S_1 &= (2), \ S_2 &= (5), \ S_3 &= (10) \end{aligned} $$

The offshoots are attached as follows:

  • $3$ at node $2$ ($S_1$)
  • $7$ at node $5$ ($S_2$)

Hence, the offshoot sequences are

$$ M_{10} = (3), \quad M_{20} = (7) $$

All other $M_{ij} = \emptyset$.

We have $r = 3$ (last index of principal branch), and $t_i = 0$ for all $i$ since each node has at most one offshoot.

Thus, Hansen's decomposition for Type 5 is

$$ \boxed{ \begin{aligned} S_0 &= (1),; S_1 = (2),; S_2 = (5),; S_3 = (10), \ M_{10} &= (3),; M_{20} = (7), \quad M_{ij} = \emptyset \text{ otherwise.} \end{aligned} } $$

Step 4: Verification

  • Each $S_i$ consists of consecutive nodes along the principal branch.
  • Each $M_{ij}$ consists of a consecutive offshoot chain attached at the appropriate principal branch node.
  • The decompositions exactly match the structures listed in the proof of Theorem B.
  • All indices $i$ and $j$ are consistent with Hansen's formal definition.

This completes the rigorous application of Hansen's decomposition.

Answer Table

Type Principal branch $S_i$ Nonempty $M_{ij}$
37 $1,2,4,8,12$ $M_{20} = (3,6)$
5 $1,2,5,10$ $M_{10} = (3), M_{20}=(7)$

∎