blob: d5cf03d7e43ce3ebc6d4eb918259822db4a5a691 [file] [edit]
def minFacAux (n : Nat) : Nat → Nat
| k =>
if h : n < k * k then n
else
if h' : k ∣ n then k
else
have : k ≤ n := by have := Nat.le_mul_self k; omega
minFacAux n (k + 2)
termination_by k => n + 2 - k
def Nat.minFac (n : Nat) : Nat :=
if 2 ∣ n then 2 else minFacAux n 3
def Nat.log (b n : Nat) : Nat :=
if b ≤ 1 then 0 else (go b n).2 where
go : Nat → Nat → Nat × Nat
| _, 0 => (n, 0)
| b, fuel + 1 =>
if n < b then
(n, 0)
else
let (q, e) := go (b * b) fuel
if q < b then (q, 2 * e) else (q / b, 2 * e + 1)
theorem test : ¬∃ k, k ≤ Nat.log 2 15 ∧ 0 < k ∧ 15 = Nat.minFac 15 ^ k := by
apply of_decide_eq_true
conv => lhs; cbv