@[reducible, inline]

abbrev Nat.avg (a : Nat) (b : Nat) : Nat

Average of two natural numbers rounded toward zero.

Equations

• a.avg b = (a + b) / 2

theorem Nat.avg_comm (a : Nat) (b : Nat) : a.avg b = b.avg a

theorem Nat.avg_le_left {b : Nat} {a : Nat} (h : b ≤ a) : a.avg b ≤ a

theorem Nat.avg_le_right {a : Nat} {b : Nat} (h : a ≤ b) : a.avg b ≤ b

theorem Nat.avg_lt_left {b : Nat} {a : Nat} (h : b < a) : a.avg b < a

theorem Nat.avg_lt_right {a : Nat} {b : Nat} (h : a < b) : a.avg b < b

theorem Nat.le_avg_left {a : Nat} {b : Nat} (h : a ≤ b) : a ≤ a.avg b

theorem Nat.le_avg_right {b : Nat} {a : Nat} (h : b ≤ a) : b ≤ a.avg b

theorem Nat.le_add_one_of_avg_eq_left {a : Nat} {b : Nat} (h : a.avg b = a) : b ≤ a + 1

theorem Nat.le_add_one_of_avg_eq_right {a : Nat} {b : Nat} (h : a.avg b = b) : a ≤ b + 1

@[irreducible]

def Nat.bisect {start : Nat} {stop : Nat} {p : Nat → Bool} (h : start < stop) (hstart : p start = true) (hstop : p stop = false) : Nat

Given natural numbers a < b such that p a = true and p b = false, bisect finds a natural number a ≤ c < b such that p c = true and p (c+1) = false.

Equations

• One or more equations did not get rendered due to their size.

@[irreducible]

theorem Nat.bisect_lt_stop {start : Nat} {stop : Nat} {p : Nat → Bool} (h : start < stop) (hstart : p start = true) (hstop : p stop = false) : Nat.bisect h hstart hstop < stop

@[irreducible]

theorem Nat.start_le_bisect {start : Nat} {stop : Nat} {p : Nat → Bool} (h : start < stop) (hstart : p start = true) (hstop : p stop = false) : start ≤ Nat.bisect h hstart hstop

@[irreducible]

theorem Nat.bisect_true {start : Nat} {stop : Nat} {p : Nat → Bool} (h : start < stop) (hstart : p start = true) (hstop : p stop = false) : p (Nat.bisect h hstart hstop) = true

@[irreducible]

theorem Nat.bisect_add_one_false {start : Nat} {stop : Nat} {p : Nat → Bool} (h : start < stop) (hstart : p start = true) (hstop : p stop = false) : p (Nat.bisect h hstart hstop + 1) = false