def lt_succ_isqrt

bend-collections-laws-math@1.0.0.0 · proofs/math/natural/sqrtn.bend:148

import Base
import bend-collections-laws-math@1.0.0.0/proofs/lib/lemmas/proofs/nat_algebra.bend as A
import bend-collections-laws-math@1.0.0.0/src/math/natural.bend as M
import bend-collections-laws-math@1.0.0.0/src/math/pow2.bend as P2

148# n < (isqrt(n) + 1)^2   (Mathlib Nat.lt_succ_sqrt')
149def lt_succ_isqrt(+n: Nat) -> {Nat.is_lt(n, Nat.pow(1n+M.isqrt(n), 2n)) == True{} : Bool}:
150  +g = P2.pow2t(1n+Nat.div(M.bit_length(n), 2n))
151  %Equal.sym(Nat, Nat.pow(1n+M.isqrt(n), 2n), Nat.mul(1n+M.isqrt(n), 1n+M.isqrt(n)), Equal.cong(Nat, Nat, z => Nat.mul(1n+M.isqrt(n), z), Nat.mul(1n+M.isqrt(n), 1n), 1n+M.isqrt(n), A.mul_one(1n+M.isqrt(n)))) : {Nat.is_lt(n, _) == True{} : Bool}
152  iter_lt(g, n, g, M.sqrt_next(n, g), Nat.is_lt(M.sqrt_next(n, g), g), {==}, {==}, g0_bound(n))