# Moessner's sieve, from addition to powers **Learning goal:** perform the sieve exactly, see why its output is surprising, and understand the indexing well enough to reproduce it with a finite list. Moessner's theorem says that a sequence of positional deletions and running additions produces the powers \[ 1^d,2^d,3^d,\ldots \] for any positive integer degree \(d\). The arithmetic used by the sieve is addition. Exponentiation describes the result; it is not an operation hidden in the sieve. The classical procedure and a separate machine formalization are documented in the [Cornell Nuprl account](https://nuprl-web.cs.cornell.edu/documents/Moessner/). The tables below are independently calculated finite examples. ## 1. Two operations, three conventions Start with the positive integers. For each period \(r=d,d-1,\ldots,2\), carry out these operations in this order: 1. Delete the entries at **current positions** \(r,2r,3r,\ldots\), counting from one. 2. Compact the surviving entries into a list and replace them by their inclusive prefix sums. An inclusive prefix sum includes the entry where it stops. Applied to \([2,5,7]\), it gives \([2,7,14]\). There is no initial zero in the result. The deletion period counts positions, not divisibility of the values. After the first pass, a value of 12 might be in position 4; deleting every third position does not delete it merely because 12 is divisible by 3. Counting restarts at position 1 for each new pass. The running total does **not** restart at a block boundary. Blocks organize the table; a pass has one running total across all its survivors. A new pass starts its own running total at zero. For degree one, the period list is empty. The untouched positive integers already are the first powers. ## 2. Squares: keep the odd positions, then accumulate To produce four squares, start with eight integers and delete every second position. Each row of the following table is one input block of length two. The right-hand column is the cumulative sum across all blocks so far. | Current positions | Input block | Deleted position and value | Surviving values | Inclusive prefix sums | | --- | --- | --- | --- | --- | | 1–2 | 1, 2 | position 2: 2 | 1 | 1 | | 3–4 | 3, 4 | position 4: 4 | 3 | 4 | | 5–6 | 5, 6 | position 6: 6 | 5 | 9 | | 7–8 | 7, 8 | position 8: 8 | 7 | 16 | The output is \([1,4,9,16]\). Here the answer has a familiar explanation: the \(n\)th surviving value is \(2n-1\), and \[ \sum_{j=1}^{n}(2j-1)=n^2. \] One elementary verification is to subtract successive squares: \[ n^2-(n-1)^2=2n-1. \] Adding these identities telescopes to the result. This explains the square case completely. The higher-degree cases need a more general invariant, developed in the [proof guide](02-proof-guide.md). ## 3. Cubes: the second deletion acts on the newly summed row For four cubes, use the integers 1 through 12. The periods are 3 and then 2. ### Pass 1: delete every third position | Current positions | Input block | Deleted position and value | Surviving values | Inclusive prefix sums | | --- | --- | --- | --- | --- | | 1–3 | 1, 2, 3 | position 3: 3 | 1, 2 | 1, 3 | | 4–6 | 4, 5, 6 | position 6: 6 | 4, 5 | 7, 12 | | 7–9 | 7, 8, 9 | position 9: 9 | 7, 8 | 19, 27 | | 10–12 | 10, 11, 12 | position 12: 12 | 10, 11 | 37, 48 | The new row is \[ [1,3,7,12,19,27,37,48]. \] For example, the 12 in this row is \(1+2+4+5\). The deleted 3 and 6 contributed nothing. ### Pass 2: delete every second position of that row | Current positions | Input block | Deleted position and value | Surviving values | Inclusive prefix sums | | --- | --- | --- | --- | --- | | 1–2 | 1, 3 | position 2: 3 | 1 | 1 | | 3–4 | 7, 12 | position 4: 12 | 7 | 8 | | 5–6 | 19, 27 | position 6: 27 | 19 | 27 | | 7–8 | 37, 48 | position 8: 48 | 37 | 64 | The output is \[ [1,8,27,64]=[1^3,2^3,3^3,4^3]. \] Notice that a numerical value of 27 occurs in both the input and the output of this pass, with different roles. In the input it is at position 6 and is deleted. In the output it is the sum \(1+7+19\). A visualization must track positions and computation stages, not just match equal printed values. There is also a direct check of the final retained row. Before its \(n\)th retained entry, the first pass has kept the two numbers \(3j+1,3j+2\) from each complete block \(j=0,\ldots,n-2\), followed by \(3n-2\). Their sum is \[ \begin{aligned} \sum_{j=0}^{n-2}(6j+3)+(3n-2) &=3(n-1)^2+3n-2\\ &=3n^2-3n+1\\ &=n^3-(n-1)^3. \end{aligned} \] Thus the last prefix sum telescopes to \(n^3\). For \(n=1\), the sum over complete blocks is empty and the same formula gives 1. ## 4. Fourth powers: three passes, with every intermediate value visible For four fourth powers, start with the integers 1 through 16. The periods are 4, 3, and 2. ### Pass 1: period 4 | Current positions | Input block | Deleted position and value | Surviving values | Inclusive prefix sums | | --- | --- | --- | --- | --- | | 1–4 | 1, 2, 3, 4 | position 4: 4 | 1, 2, 3 | 1, 3, 6 | | 5–8 | 5, 6, 7, 8 | position 8: 8 | 5, 6, 7 | 11, 17, 24 | | 9–12 | 9, 10, 11, 12 | position 12: 12 | 9, 10, 11 | 33, 43, 54 | | 13–16 | 13, 14, 15, 16 | position 16: 16 | 13, 14, 15 | 67, 81, 96 | ### Pass 2: period 3 The input to this pass is precisely the right-hand column of the previous table, read in order. Its length is twelve. | Current positions | Input block | Deleted position and value | Surviving values | Inclusive prefix sums | | --- | --- | --- | --- | --- | | 1–3 | 1, 3, 6 | position 3: 6 | 1, 3 | 1, 4 | | 4–6 | 11, 17, 24 | position 6: 24 | 11, 17 | 15, 32 | | 7–9 | 33, 43, 54 | position 9: 54 | 33, 43 | 65, 108 | | 10–12 | 67, 81, 96 | position 12: 96 | 67, 81 | 175, 256 | ### Pass 3: period 2 | Current positions | Input block | Deleted position and value | Surviving values | Inclusive prefix sums | | --- | --- | --- | --- | --- | | 1–2 | 1, 4 | position 2: 4 | 1 | 1 | | 3–4 | 15, 32 | position 4: 32 | 15 | 16 | | 5–6 | 65, 108 | position 6: 108 | 65 | 81 | | 7–8 | 175, 256 | position 8: 256 | 175 | 256 | The output is \[ [1,16,81,256]=[1^4,2^4,3^4,4^4]. \] The last retained values \([1,15,65,175]\) are the consecutive differences of these fourth powers, with the initial value at \(n=0\) given by \(0^4=0\). Recognizing the differences checks this table, but a proof for every degree must also explain why all the earlier passes produce the right differences. That is the role of the block invariant. ## 5. Finite input: a clean guarantee Suppose we want the first \(N\geq1\) outputs of degree \(d\geq1\). Starting with exactly \[ 1,2,\ldots,Nd \] is sufficient. More precisely, at the pass with period \(r\), the input has length \(Nr\). It consists of \(N\) complete blocks of length \(r\). Deleting the last position of each block leaves exactly \(N(r-1)\) entries. Prefix summation preserves this new length. The lengths therefore follow \[ Nd\longrightarrow N(d-1)\longrightarrow\cdots\longrightarrow 2N\longrightarrow N. \] This is a proof about lengths, independent of the theorem about values. The values agree with the infinite-stream calculation because deletion and prefix summation are causal: a retained output at a given position depends only on a finite prefix of its input. No later input changes any earlier running total. The [JavaScript engine](https://github.com/archgpt-agent/fengshui-2076/blob/main/website/public/engine.mjs) uses this complete-block choice. It makes every intermediate table easy to inspect. The [Haskell implementation](https://github.com/archgpt-agent/fengshui-2076/blob/main/haskell/src/Moessner.hs) uses an infinite list and asks for a finite output prefix. A short display preview of an intermediate Haskell stage is not itself sufficient input for later stages; the original lazy stream remains the computation. ### A sharper result: the shortest initial prefix The exact minimum length for producing \(N\) final values is \[ \boxed{d(N-1)+1.} \] To prove this, first consider one pass of period \(r\). Its \(M\)th survivor comes from one-based input position \[ \sigma_r(M)=M+\left\lfloor\frac{M-1}{r-1}\right\rfloor. \] There are \(r-1\) survivors per full block. Before the \(M\)th survivor, exactly \(\lfloor(M-1)/(r-1)\rfloor\) discarded positions have been crossed. The prefix sum ending at this survivor needs all survivors through it and no subsequent input. Thus \(\sigma_r(M)\) is both sufficient and necessary. Work backwards from the last pass. For period 2, the first \(N\) outputs need \(2(N-1)+1\) input entries. If a period-\(r\) pass must supply \((r-1)(N-1)+1\) entries to the rest of the computation, its required input length is \[ \begin{aligned} \sigma_r\big((r-1)(N-1)+1\big) &=(r-1)(N-1)+1+(N-1)\\ &=r(N-1)+1. \end{aligned} \] Induction up to \(r=d\) proves the formula. One fewer initial entry cannot supply the last necessary survivor, so it yields only \(N-1\) final entries. The clean complete-block prefix \(Nd\) therefore contains \(d-1\) extra tail entries. Those extra entries make complete display blocks; they do not change the requested outputs. | Degree | Desired outputs | Clean complete-block length | Minimal initial length | | --- | --- | --- | --- | | 1 | 4 | 4 | 4 | | 2 | 4 | 8 | 7 | | 3 | 4 | 12 | 10 | | 4 | 4 | 16 | 13 | | 9 | 4 | 36 | 28 | ## 6. Indexing without ambiguity These notes use \(n=1,2,\ldots\) for the argument in \(n^d\). Programs usually use a zero-based output index \(k\), with \(n=k+1\). For period \(r\), zero-based survivor index \(k\) maps to zero-based input index \[ \left\lfloor\frac{k}{r-1}\right\rfloor r+(k\bmod(r-1)). \] Writing \(k=a(r-1)+b\), where \(0\leq b