# Exercises, worked solutions, and mathematical connections These exercises move from computation to proof and then to the nine-star experiment. The [tutorial](01-moessner-tutorial.md) supplies the conventions; the [proof guide](02-proof-guide.md) supplies the block recurrence. Questions marked **extension** go beyond simply executing the existing algorithm. The solutions are included immediately after each question so that the document works as a self-contained study guide. For independent practice, solve the question before reading its solution. ## 1. Positions are not values **Question.** Apply one pass of period 3 to \[ [9,2,7,5,6,1,4]. \] Record the removed positions, retained values, and inclusive prefix sums. Explain why deleting values divisible by three would be a different computation. **Solution.** Positions 3 and 6 contain 7 and 1, so those entries are removed. The survivors are \[ [9,2,5,6,4], \] and their prefix sums are \[ [9,11,16,22,26]. \] The retained values 9 and 6 happen to be divisible by three. The sieve condition concerns their positions, not their numerical values. Deleting values divisible by three would instead keep \([2,7,5,1,4]\), producing a different row. ## 2. Produce the first five cubes **Question.** Start with the integers 1 through 15. Execute periods 3 and 2, showing the intermediate row after the first prefix sum. **Solution.** Period 3 removes 3, 6, 9, 12, and 15. The survivors are \[ [1,2,4,5,7,8,10,11,13,14]. \] Their prefix sums are \[ [1,3,7,12,19,27,37,48,61,75]. \] Period 2 keeps the entries in positions 1, 3, 5, 7, and 9: \[ [1,7,19,37,61]. \] Their prefix sums are \([1,8,27,64,125]\), the first five cubes. The fact that this finite computation succeeds verifies the example. The universal theorem requires the invariant proved in the proof guide. ## 3. Read the last retained row as differences **Question.** The fourth-power example ends by summing \([1,15,65,175]\). Predict the fifth retained value before the last prefix sum, and derive a formula for its \(n\)th retained value. **Solution.** Once the theorem is established, the last retained value must be the difference between consecutive outputs: \[ a_n=n^4-(n-1)^4. \] Expansion gives \[ a_n=4n^3-6n^2+4n-1. \] At \(n=5\), this is \(625-256=369\). The first five retained values are therefore \([1,15,65,175,369]\). This is a consequence of the theorem. Using the desired powers to invent a retained row and then summing it would not prove that the earlier positional-deletion stages produce that row. ## 4. How much finite input is really required? **Question.** Find both the clean complete-block input length and the minimum input length for the first seven fifth powers. Give the intermediate lengths under both choices. **Solution.** The complete-block choice is \(Nd=7\cdot5=35\). The lengths through periods 5, 4, 3, and 2 are \[ 35\to28\to21\to14\to7. \] The minimum is \(d(N-1)+1=5\cdot6+1=31\). Its lengths are \[ 31\to25\to19\to13\to7. \] For example, period 5 deletes \(\lfloor31/5\rfloor=6\) entries, leaving 25. Each later pass also removes six entries. The shorter prefix still contains the last source entry needed for the seventh output. A prefix of length 30 produces only six final values. The general proof of this minimum uses the inverse survivor-position map in the tutorial. ## 5. Convert between zero-based and one-based indexing **Question.** For period 4, where does zero-based survivor index \(k=7\) come from? Derive the source-index formula rather than enumerating a long row. **Solution.** There are three survivors per input block. Divide \(k=7\) by 3: \[ 7=2\cdot3+1. \] The survivor lies in block 2, column 1, both counted from zero. Its zero-based source index is \(2\cdot4+1=9\), the tenth input entry. In general, \[ \operatorname{source}_r(k) =\left\lfloor\frac{k}{r-1}\right\rfloor r+(k\bmod(r-1)) =k+\left\lfloor\frac{k}{r-1}\right\rfloor. \] The eighth survivor of the positive integers at period 4 is consequently 10. No extra \(+1\) belongs inside the zero-based map; the conversion to a printed term number happens at the end. ## 6. Diagnose an incorrect block reset **Question.** A program resets its running sum to zero after every input block. Show that it fails to generate cubes, even if the deletion periods are correct. **Solution.** After deleting every third entry from 1 through 12, the retained blocks are \([1,2]\), \([4,5]\), \([7,8]\), and \([10,11]\). Incorrectly resetting within each block produces \[ [1,3,4,9,7,15,10,21]. \] Deleting every second position of this row keeps \([1,4,7,10]\). Even with a correct global prefix sum at the last pass, the output is \([1,5,12,22]\), not cubes. The proper invariant includes contributions from **all preceding blocks**, which is why the second sum in the definition of `row` is essential. ## 7. What repeated prefix sums do without deletion **Question.** Let \(A_0(n)=1\) for \(n\geq1\), and let \[ A_{p+1}(n)=\sum_{j=1}^{n}A_p(j). \] Prove that \[ A_p(n)=\binom{n+p-1}{p}. \] Explain why repeatedly scanning the positive integers, without deletion, does not generate the desired powers. **Solution.** For \(p=0\), the formula is \(\binom{n-1}{0}=1\). Suppose it holds at \(p\). Pascal's identity implies \[ \binom{j+p-1}{p} =\binom{j+p}{p+1}-\binom{j+p-1}{p+1}. \] Summing over \(j=1,\ldots,n\) telescopes. The lower boundary \(\binom{p}{p+1}\) is zero, leaving \(\binom{n+p}{p+1}\), the required next formula. Thus the first scans of ones give \[ n,\qquad \frac{n(n+1)}2,\qquad \frac{n(n+1)(n+2)}6,\ldots \] Starting from the positive integers already includes one scan of ones. Adding \(d-1\) ordinary scans produces \(\binom{n+d-1}{d}\), not \(n^d\). For example, at \(n=2,d=3\), it gives 4 rather than 8. The deletion pattern changes the computation in an essential way. The binomial coefficients count weakly ordered choices, whereas \(n^d\) counts all independent ordered choices of length \(d\). This explains why both families arise naturally from addition, while remaining different families. ## 8. Finite differences recognize the degree **Question.** Define the forward difference by \[ \Delta f(n)=f(n+1)-f(n). \] Compute the difference table for \(n^3\) at \(n=0,\ldots,5\). Then prove that the \(d\)th difference of \(n^d\) is the constant \(d!\), and the next difference is zero. **Solution.** The finite rows are: | Difference order | Values | | --- | --- | | 0 | 0, 1, 8, 27, 64, 125 | | 1 | 1, 7, 19, 37, 61 | | 2 | 6, 12, 18, 24 | | 3 | 6, 6, 6 | | 4 | 0, 0 | | 5 | 0 | For a polynomial with leading term \(a n^p\), where \(p\geq1\), the binomial expansion of \((n+1)^p-n^p\) has leading term \(p n^{p-1}\). Differences of the lower-degree terms have degree at most \(p-2\). Hence \(\Delta\) reduces the degree by one and multiplies the leading coefficient by the old degree. Starting from leading coefficient 1 and degree \(d\), applying \(\Delta\) exactly \(d\) times gives the constant \(d!\). The next difference of a constant is zero. For \(d=0\), the same statement begins with \(0!=1\) and a constant sequence. The first-difference row of cubes is the last retained row of the cube sieve. Repeated differences are a useful independent check of the completed output. A finite difference table alone is not a proof that an arbitrarily long operational sieve has the asserted output. ## 9. Express a power using binomial sequences **Question — extension.** Prove \[ n^3=\binom n1+6\binom n2+6\binom n3 \] for every nonnegative integer \(n\). What does this say about the relation between powers and the sequences generated by ordinary prefix sums? **Solution.** Expanding the right side gives \[ n+3n(n-1)+n(n-1)(n-2)=n^3. \] The equality also holds at \(n=0,1,2\), with binomial coefficients above their range interpreted as zero. The coefficients \(1,6,6\) appear in the first entries of the first, second, and third difference rows at zero. This is an instance of the finite-difference expansion in the binomial basis. The two families are connected by explicit linear combinations and index shifts. They are not the same sequence produced by the same operator. This distinction helps explain why ordinary scans give binomial coefficients while deletion-plus-scan can give powers. ## 10. Count functions by their complete output tables **Question.** Enumerate all total functions from a two-element set to a three-element set. Give each one a rank, and explain the general recurrence for a domain of size \(d\) and codomain of size \(n\). **Solution.** Label the domain positions 0 and 1, and the possible outputs 0, 1, and 2. A function is completely specified by the ordered table \((f(0),f(1))\). The nine tables are \[ (0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2). \] The rank of \((a,b)\) is \(3a+b\), from 0 through 8. Its inverse recovers \(a=\lfloor r/3\rfloor\), \(b=r\bmod3\). More generally, a length-\(d\) output table is a base-\(n\) digit vector. There is exactly one function from an empty domain: the empty table. Extending the domain by one point chooses one output and a function on the remaining points. Therefore the counts satisfy \[ F(n,0)=1,\qquad F(n,d+1)=nF(n,d), \] and equal \(n^d\). This includes the combinatorial convention \(0^0=1\): there is one empty function even when the codomain is empty. A nonempty domain and empty codomain admit no total function. [FunctionSpace.hs](https://github.com/archgpt-agent/fengshui-2076/blob/main/haskell/src/Moessner/Dependent/FunctionSpace.hs) represents these canonical tables as `FiniteFunction b a`, and its enumeration has type `Vec (Pow a b) (FiniteFunction b a)`. Wrapping a deterministic result in `Identity` does not itself enumerate alternatives; the table construction makes the finite choices. Counting tables counts extensional total functions, not distinct program texts or nonterminating Haskell expressions. ## 11. Construct an actual bijection in the square case **Question — extension.** The nested-sum form at depth two is \[ \sum_{i=0}^{x}(2i+1)=(x+1)^2. \] Construct a bijection between its paths \((i,t)\), where \(0\leq i\leq x\) and \(0\leq t\leq2i\), and ordered pairs \((a,b)\) with \(0\leq a,b\leq x\). Prove that the map is invertible. **Solution.** Partition the square grid by the value \(i=\max(a,b)\). The band with maximum \(i\) contains the row \((i,0),\ldots,(i,i)\) and the column \((0,i),\ldots,(i-1,i)\): exactly \(2i+1\) points. Define \[ (i,t)\longmapsto \begin{cases} (i,t),&0\leq t\leq i,\\ (t-i-1,i),&i+1\leq t\leq2i. \end{cases} \] In the first branch the first coordinate is maximal; in the second branch the second coordinate is strictly larger than the first. The images are disjoint and both have maximum \(i\). The inverse sends \[ (a,b)\longmapsto \begin{cases} (a,b),&a\geq b,\\ (b,b+1+a),&a