Let again be the total. Reject unless is divisible by three, and put . Define to mean that the first occurrences can be assigned to three groups so that the first two groups have sums and . Their third sum is already determined by the processed list prefix sum minus , so it need not be stored as another coordinate.
Initialize true and all other states false. For each reachable state, assign the next occurrence to exactly one group:
threeEqualParts(A):
    S = sum of A
    if S mod 3 != 0: return false
    h = S/3
    D[0..h,0..h] = false
    D[0,0] = true
    for each indexed entry a in A:
        Next[0..h,0..h] = false
        for x from 0 to h:
            for y from 0 to h:
                if D[x,y]:
                    Next[x,y] = true
                    if x+a <= h: Next[x+a,y] = true
                    if y+a <= h: Next[x,y+a] = true
        D = Next
    return D[h,h]
The three transitions put the occurrence in the third, first or second group, respectively. Using a fresh layer prevents reusing it. Conversely, deleting the last occurrence from any valid list prefix assignment leaves exactly one predecessor state, so induction proves completeness as well as soundness. At the final state , the third sum is , giving precisely the required disjoint partition.
There are states per layer and a constant number of transitions per state. Thus the time is , and rolling layers use space for nonempty inputs. The source mentions an additional integer in this part, but it does not occur in the stated equal-partition condition; the required target is determined by . Empty groups are allowed by the stated subset formulation.
Maintain opposite signs at the endpoints, rather than assuming that the polynomial is monotone:
def floorRoot(X: Int): Int = {
  require(X > 0 && eval(0.0) <= 0.0 && eval(X.toDouble) > 0.0)
  var lo = 0
  var hi = X
  while (hi - lo > 1) {
    val mid = lo + (hi - lo) / 2
    if (eval(mid.toDouble) <= 0.0) lo = mid
    else hi = mid
  }
  lo
}
The loop invariant is and . Both branches preserve those signs, even when there are other roots of a polynomial or sign reversals elsewhere. When the interval width exceeds one, the midpoint is strictly between its endpoints, so the positive integer loop variant hi - lo strictly decreases. On exit hi == lo + 1, giving the required postcondition . Continuity establishes a root of a polynomial between those adjacent integers, possibly at the left endpoint.
The width is at most halved with rounding upwards, so there are at most midpoint evaluations, plus two endpoint evaluations in the precondition check. The midpoint expression avoids adding two large endpoints. The explicit positive upper-bound precondition supplies the interval order assumed in the question. For the literal computed-eval contract, the same proof holds provided evaluated midpoints are not NaN; identifying its bracket with the real polynomial additionally requires trustworthy evaluation signs.
First find a sign bracket by exponential search, then bisect that bracket without evaluating its endpoints again:
def floorRoot(): Int = {
  require(eval(0.0) < 0.0)
  var lo = 0
  var hi = 1
  while (eval(hi.toDouble) <= 0.0) {
    lo = hi
    require(hi <= Int.MaxValue / 2, "doubling bound exceeds Int range")
    hi *= 2
  }
  while (hi - lo > 1) {
    val mid = lo + (hi - lo) / 2
    if (eval(mid.toDouble) <= 0.0) lo = mid
    else hi = mid
  }
  lo
}
For the first while loop the loop invariant is , with hi a positive power of two, and either or . Every previously tested power of two has nonpositive value. Let be the least nonnegative integer for which . It exists by the positive leading coefficient. If the current upper endpoint is , a mathematical loop variant is while the guard holds; the next doubling decreases it by one. The first while loop's postcondition is . The second while loop has exactly the invariant, variant and adjacent-integer postcondition established in part c.
There are evaluations at powers of two. If , the final bracket has width and takes exactly midpoint evaluations. Including the initial sign check, the total is evaluations for , and two for . Thus evaluation cost is for the first positive dyadic bound ; it is not a claim about the first positive root of a polynomial when the polynomial is nonmonotone.
The mathematical argument uses unbounded integer endpoints and reliable signs. The guarded Int implementation requires the successful dyadic bound to fit in Int; otherwise it explicitly fails rather than wrapping to a negative bound. The coefficient assumptions alone cannot guarantee that a requested integer result fits a fixed-width type. Floating-point overflow or unreliable signs likewise need a wider or certified evaluator for a fully general implementation.
Use two finite integer lists , with the head of each list representing its stack top. Initially both are empty. A suitable abstract object interface is
trait DoubleStack {
  def pusha(x: Int): Unit
  def pushb(x: Int): Unit
  def popa: Int
  def popb: Int
  def isEmptya: Boolean
  def isEmptyb: Boolean
}
For the unbounded abstract data type, each push has no logical precondition. The postcondition of pusha(x) is and ; pushb(x) symmetrically gives and . The precondition of popa is , and its postcondition is return value , new state , and unchanged . The specification for popb exchanges . Each emptiness query leaves both lists unchanged and returns exactly whether its corresponding list is empty.
These frame conditions matter: an operation on one stack must preserve the other, not merely produce the right return value.
The implementation maintains the two boundaries from part b:
class ArrayDoubleStack(val MAX: Int) extends DoubleStack {
  require(MAX >= 0)
  private val data = new Array[Int](MAX)
  private var left = 0
  private var right = MAX

  def isEmptya: Boolean = left == 0
  def isEmptyb: Boolean = right == MAX

  def pusha(x: Int): Unit = {
    require(left < right, "double stack is full")
    data(left) = x
    left += 1
  }
  def pushb(x: Int): Unit = {
    require(left < right, "double stack is full")
    right -= 1
    data(right) = x
  }
  def popa: Int = {
    require(left > 0, "stack a is empty")
    left -= 1
    data(left)
  }
  def popb: Int = {
    require(right < MAX, "stack b is empty")
    val answer = data(right)
    right += 1
    answer
  }
}
Initialization gives empty abstract lists. Each push consumes one free position next to the appropriate top; each pop returns that top and releases its position. The guards preserve the ordering of the two boundaries and prevent invalid indexing. The abstraction function shows directly that the untouched stack is unchanged. Keeping data private prevents clients from violating the representation invariant; this strengthens encapsulation relative to a publicly exposed implementation field without changing the six required operations.
All six operations run in time, with a fixed array of MAX integers and constant extra state. Creating and zero-initializing the array takes time, outside those operation bounds. Capacity zero gives a valid always-empty bounded structure whose pushes fail their precondition.
A sentinel node supplies a permanent predecessor for the first real node. Inserting or deleting at the front then uses the same predecessor.next update as an interior operation. Its datum is not a multiset element: the chosen extreme integer is merely unused sentinel data.
A representation invariant requires a nonnull fixed header, a finite acyclic chain starting at bagHeader.next, and exclusion of the header from that chain. Each node identity occurs once, although different nodes may have equal data. Representation links are owned by the implementation, so outside mutation cannot alter them unexpectedly.
The abstraction function counts occurrences:
This yields nonnegative multiplicities and finite support. Initialization with a null successor gives the empty multiset. Excluding the sentinel is essential even when a real item equals its datum.
Throw an informative exception, such as NoSuchElementException, and leave the set unchanged. This makes a violated nonempty precondition visible at the point of misuse. Returning a distinguished integer would be ambiguous because every integer is a legitimate set member.
A different object interface could return an optional integer, representing failure explicitly, but that changes the declared return type. For the supplied integer-returning operation, a checked failure is useful and consistent with the stated precondition.
Instantiate the two type parameters and implement the function object interface:
val square: Fun[Int, Int] = new Fun[Int, Int] {
  override def apply(x: Int): Int = x * x
}
Parametric polymorphism occurs because the generic trait is specialized by choosing its argument and result types. Subtype polymorphism occurs because the anonymous implementing software class is used through a Fun[Int, Int] reference; calls to its apply operation use the object interface contract and dynamic dispatch. Multiplication itself is not the second polymorphism needed for this explanation.
For values whose mathematical squares fit in a signed 32-bit integer, the result is the ordinary square. Outside that range, the supplied integer return type cannot represent every mathematical square, and the multiplication follows Scala integer-overflow behavior. An implementation requiring exact mathematical results for all integer inputs would need a wider result type or an explicit overflow exception.
Override the operation and scale the result of exactly one superclass call:
class ScaledSumChannel(factor: Int) extends SumChannel {
  override def apply(n: Int): Int = factor * super.apply(n)
}
The superclass updates its previous-input state once and returns its ordinary sum; only that returned value is scaled. The inputs and superclass history are unchanged by the scaling. Reimplementing the state update is unnecessary and could accidentally diverge from the superclass contract. As in the supplied channel, arithmetic uses the declared fixed-width integer type.
The abstract data type invariant constrains a total count function on integer keys as follows:
The initial state has every count zero, and . These conditions make the abstract state a multiset supported on the allowed finite key range. Since the interface returns an Int, the implementations below use representable nonnegative multiplicities; equivalently add to the invariant, where . The corresponding add precondition below prevents overflow. An idealized unbounded-integer specification can omit that machine bound.
Use the empty reference as the base case:
def printInorder(root: Tree): Unit = {
  if (root != null) {
    printInorder(root.left)
    println(root.datum)
    printInorder(root.right)
  }
}
Induction on the tree proves the order: the first recursive call prints exactly the left subtree, then the procedure prints the root, then the final call prints exactly the right subtree. A finite acyclic tree supplies decreasing proper subtrees, so the recursion terminates. The traversal is valid for arbitrary integer labels; sorted output would additionally require a binary search tree invariant.
Use a widened interval width, so the arithmetic also handles endpoints near the limits of Int:
final class Uniform(l: Int, u: Int) extends FiniteDist[Int] {
  require(l <= u)
  private val width = u.toLong - l.toLong + 1L

  def getDom: List[Int] = {
    val builder = List.newBuilder[Int]
    var value = l.toLong
    while (value <= u.toLong) {
      builder += value.toInt
      value += 1L
    }
    builder.result()
  }

  def getProb(x: Int): Double =
    if (l <= x && x <= u) 1.0 / width.toDouble else 0.0
}
The support lists every integer in the inclusive interval once. Its cardinality is width, so assigning each atom mass gives total mass one. The loop counter is also widened, preventing an increment past Int.MaxValue from wrapping to a negative value. Returning the full support takes time and space proportional to its width and can be impractical for a very large interval; the mass query itself is constant-time. The full integer interval has width , which fits Long but not positive Int.
Use the AAPCS32 convention: r0 holds the input address, r1 the length, and r0 receives the result. The following Thumb instruction set assembly language uses only scratch processor registers, so no callee-saved registers need saving. Assume the array is valid, halfword-aligned, and has nonnegative length; for the mathematical sum assume it fits a signed 32-bit two's complement integer.
.syntax unified
.thumb
.thumb_func
sum16:
    movs r2, #0             @ accumulated sum
    cmp  r1, #0
    ble  .Ldone             @ empty array; also returns 0 if n < 0
.Lloop:
    movs r3, #0             @ Thumb signed load needs a register offset
    ldrsh r3, [r0, r3]      @ signed halfword at a; offset read before r3 changes
    adds r2, r2, r3         @ include this signed value
    adds r0, r0, #2         @ advance by one short, not one byte
    subs r1, r1, #1         @ one fewer element remains
    bne  .Lloop
.Ldone:
    movs r0, r2             @ result register
    bx   lr                 @ leaf routine: lr was not overwritten
After iterations, the loop invariant is that r2 contains the first elements' sum, r0 points to element , and r1 is . The sign extension in ldrsh supplies the correct signed addend. One iteration preserves this loop invariant, and the decreasing remaining length proves algorithm termination. For the seven-element calls, the sum lies between and , so it fits. For longer arrays that overflow, these instructions compute the sum modulo ; that is not a claim about defined signed C programming language overflow behavior. The operand forms are those of the paper's reference sheet.[ref]
Evaluate the recurrence relation successively, retaining only the preceding two values. Each of the updates uses three multiplications and one subtraction. Hence arithmetic operations and auxiliary storage suffice, excluding the stored input. Naively branching into two recursive calls would repeat work; the sequential computation is essential. This is an arithmetic-operation bound, not a bit-complexity bound for arbitrarily large exact integers.
Express that the order is a dense order:
In either real interval, lies strictly between any two distinct ordered elements and remains in the domain. In the integers, have no intervening integer, so this first-order sentence is false. The endpoints of a closed interval do not prevent a dense order.
Combine a minimum with an adjacent pair in a linear order:
In , choose . The minimum and the adjacent pair in a linear order both exist. In , the dense order property rules out such an adjacent pair. In , adjacent pairs exist, but no minimum exists: for any , the integer is smaller. Thus this first-order sentence has precisely the required three truth values. Neither the endpoints nor the numerical witnesses occur as constant symbols in the first-order sentence.
Figure 1.
A minimum and an adjacent pair distinguish the two-interval order from a closed interval and the integers
. Orange highlights the consecutive domain members and in the two-interval order. The dotted arrow crosses points absent from that domain. A closed real interval has intervening domain members; the integers have adjacent pairs but no minimum. Details.
Use the intended first-order structure of real arithmetic, with Int selecting the integers; is the parameter in . A suitable first-order formula is
The first condition requires a real square root of . The second excludes every representation as a rational number with a nonzero integer denominator. This uses only the listed function and constant symbols, the Int predicate and logical equality; in particular, is written and there is no extra division symbol. A square root exists exactly when , and either sign of a root is a rational number exactly when the other sign is a rational number, so the absence of a positivity condition on does not affect the claim about the principal square root. At the formula is false; for there is no real witness. The meanings of and as real arithmetic, not just the meaning of Int, are part of this interpretation.
Use r0 for the argument and result. With 32-bit integers and pointers, the three fields have byte offsets 0, 4 and 8. Assume an acyclic finite binary tree, no concurrent mutation, a valid aligned call stack, and no signed integer overflow in any evaluated sum. These are representation and arithmetic assumptions, rather than properties of arbitrary C programming language implementations.
.syntax unified
.cpu cortex-m0
.thumb
.global sum_rec
.thumb_func
sum_rec:
    cmp  r0, #0
    beq  .Lempty
    push {r4, r5, r6, lr}    @ 16-byte frame; r6 is alignment padding
    movs r4, r0              @ retain this invocation's node
    ldr  r5, [r4, #0]        @ running value begins with its label
    ldr  r0, [r4, #4]
    bl   sum_rec             @ r0 = left subtree sum
    adds r5, r5, r0
    ldr  r0, [r4, #8]
    bl   sum_rec             @ r0 = right subtree sum
    adds r0, r0, r5
    pop  {r4, r5, r6, pc}    @ restore caller state and return
.Lempty:
    movs r0, #0
    bx   lr
The node and partial sum are held in callee-saved registers r4,r5. Each recursive invocation saves its caller's values before replacing them, so a child returns with the parent's values intact. Saving lr preserves the return address across the two bl instructions. Caller-saved registers may be overwritten by a child; no parent value is left live only in them. Pushing four words maintains eight-byte stack alignment at recursive calls.[ref]
Correctness follows by structural induction. An empty subtree returns zero. For a nonempty subtree, assume both recursive calls return their respective label sums. The final addition then combines the node's label with exactly those two sums, so r0 returns the sum of all labels. The instruction forms and field offsets fit the short load and arithmetic encodings.[ref]
The initial vector decomposes especially simply in the eigenbasis:
because . Applying multiplies the two eigenvectors by and . Part (b) then yields
Reading the second coordinate gives the Lucas closed form
At this is 2 and at it is 1. Each summand obeys the same recurrence relation, which independently verifies the formula and explains why the irrational parts cancel to give an integer.
On the universe , interpret the first-order signature by
This assigns both constants, a total binary function, a unary relation and a binary relation, so it specifies a complete first-order structure. If and both hold, then , and hence , proving the consequent. If either premise fails, the implication is true. Thus the universally quantified implication holds for every pair of integers, nonvacuously for every pair of nonnegative integers. Distinct constant symbols need not denote distinct objects unless a separate axiom requires it.