import Mathlib /-! # Powerful Integers Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal to bound. An integer is powerful if it can be represented as x^i + y^j for some integers i >= 0 and j >= 0. You may return the answer in any order. In your answer, each value should occur at most once. ## Constraints - 1 <= x, y <= 100 - 0 <= bound <= 10^6 ## Provided examples - `x = 2, y = 3, bound = 10` → `[2, 3, 4, 5, 7, 9, 10]` - `x = 3, y = 5, bound = 15` → `[2, 4, 6, 8, 10, 14]` - `x = 1, y = 1, bound = 1` → `[]` ## Synthesized negative examples - invalid input: `x = 0, y = 1, bound = 0` ([structural] a predicate that admits 1 <= x, y <= 100. one below the stated minimum for x) - invalid input: `x = 1, y = 1, bound = 1000001` ([structural] a predicate that admits 0 <= bound <= 10^6. one above the stated maximum for bound) - invalid input: `x = 1, y = 0, bound = 0` ([structural] a predicate that admits 1 <= x, y <= 100. one below the stated minimum for y) - `x = 2, y = 3, bound = 10` → `[2, 3, 4, 5, 7, 9]` is wrong ([structural] bound treated as strict less-than, so equality is excluded. All powerful integers below 10 are present.) - `x = 3, y = 5, bound = 15` → `[]` is wrong ([structural] no requirement that the answer contain any powerful integer. empty list vacuously satisfies any element-wise condition) - `x = 1, y = 1, bound = 1` → `[0, 1]` is wrong ([structural] powerful constraint dropped; nonnegative ints up to bound are listed. 0 and 1 are not powerful) -/ namespace PPowerfulIntegers abbrev Input := (Nat) × (Nat) × (Nat) abbrev Output := List Nat /-! ### Specification helpers -/ /-- `n` is powerful for bases `x` and `y` when `n = x ^ i + y ^ j` for some natural exponents. -/ def IsPowerful (x y n : Nat) : Prop := ∃ i j : Nat, x ^ i + y ^ j = n /-! ### Validity predicate (V) -/ /-- Valid input: `x` and `y` lie between 1 and 100 and `bound` is at most 10^6. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1 && input.1 ≤ 100 && 1 ≤ input.2.1 && input.2.1 ≤ 100 && input.2.2 ≤ 10^6 /-! ### Ideal specification (P_spec) -/ /-- `result` has no duplicates and contains exactly the powerful integers not exceeding `bound`. -/ def powerfulIntegers_spec (input : Input) (result : Output) : Prop := result.Nodup ∧ ∀ n : Nat, n ∈ result ↔ IsPowerful input.1 input.2.1 n ∧ n ≤ input.2.2 /-! ### Decidable specification (P_check) -/ /-- Decides `IsPowerful x y n`. Exponent witnesses for `x ^ i + y ^ j = n` can always be chosen below `n + 2`: for `x ≥ 2` we have `i + 1 ≤ 2 ^ i ≤ x ^ i ≤ n`, and for `x ∈ {0, 1}` every value of `x ^ i` is already attained at `i ∈ {0, 1}`. The bounded existentials are decided by Lean's own instances (`Nat.decidableExistsLT`). -/ instance decIsPowerful (x y n : Nat) : Decidable (IsPowerful x y n) := decidable_of_iff (∃ i < n + 2, ∃ j < n + 2, x ^ i + y ^ j = n) (by constructor · rintro ⟨i, -, j, -, h⟩ exact ⟨i, j, h⟩ · rintro ⟨i, j, h⟩ have h2i : ∀ k : Nat, k + 1 ≤ 2 ^ k := by intro k induction k with | zero => decide | succ k ih => rw [Nat.pow_succ] omega have key : ∀ a i : Nat, a ^ i ≤ n → ∃ i' < n + 2, a ^ i' = a ^ i := by intro a i hai rcases Nat.lt_or_ge a 2 with ha | ha · rcases Nat.eq_zero_or_pos a with ha0 | ha0 · subst ha0 rcases Nat.eq_zero_or_pos i with hi0 | hi0 · exact ⟨0, by omega, by simp [hi0]⟩ · exact ⟨1, by omega, by rw [pow_one, zero_pow (Nat.ne_of_gt hi0)]⟩ · interval_cases a exact ⟨0, by omega, by simp⟩ · have h2 : 2 ^ i ≤ a ^ i := Nat.pow_le_pow_left ha i have hle : i + 1 ≤ n := le_trans (le_trans (h2i i) h2) hai exact ⟨i, by omega, rfl⟩ obtain ⟨i', hi', hie⟩ := key x i (by rw [← h]; exact Nat.le_add_right _ _) obtain ⟨j', hj', hje⟩ := key y j (by rw [← h]; exact Nat.le_add_left _ _) exact ⟨i', hi', j', hj', by rw [hie, hje]; exact h⟩) /-- Decides the unfolded specification `result.Nodup ∧ ∀ n, n ∈ result ↔ IsPowerful x y n ∧ n ≤ b`. The unbounded quantifier over `n` splits into a quantifier over the elements of `result` (decided by `List.decidableBAll`) and a quantifier over `n < b + 1` (decided by `Nat.decidableBallLT`), because the right-hand side of the equivalence entails `n ≤ b`. -/ instance decPowerfulIntegersSpec (x y b : Nat) (result : List Nat) : Decidable (result.Nodup ∧ ∀ n : Nat, n ∈ result ↔ IsPowerful x y n ∧ n ≤ b) := decidable_of_iff (result.Nodup ∧ (∀ n ∈ result, IsPowerful x y n ∧ n ≤ b) ∧ (∀ n < b + 1, IsPowerful x y n → n ∈ result)) (by constructor · rintro ⟨hnodup, hfwd, hbwd⟩ exact ⟨hnodup, fun n => ⟨fun hn => hfwd n hn, fun h => hbwd n (Nat.lt_succ_iff.mpr h.2) h.1⟩⟩ · rintro ⟨hnodup, hall⟩ exact ⟨hnodup, fun n hn => (hall n).mp hn, fun n hn hpow => (hall n).mpr ⟨hpow, Nat.lt_succ_iff.mp hn⟩⟩) /-- Executable checker obtained mechanically from the specification. -/ def powerfulIntegers_check (input : Input) (result : Output) : Bool := @decide (powerfulIntegers_spec input result) (by unfold powerfulIntegers_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem powerfulIntegers_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : powerfulIntegers_check input result ↔ powerfulIntegers_spec input result := by simp [powerfulIntegers_check] /-! ### Implementation helpers -/ /-- Inserts `a` into a sorted duplicate-free list, keeping it sorted and dropping a repeat. -/ def insertDedup (a : Nat) : List Nat → List Nat | [] => [a] | b :: bs => if a = b then b :: bs else if a < b then a :: b :: bs else b :: insertDedup a bs /-- Sorts a list of naturals ascending, removing duplicates. -/ def sortDedup : List Nat → List Nat | [] => [] | b :: bs => insertDedup b (sortDedup bs) /-- Largest `e` with `a ^ e ≤ bound`, or `0` when `a ≤ 1` or `bound < a`. -/ def maxExponent (a bound : Nat) : Nat := if h : 1 < a ∧ a ≤ bound then 1 + maxExponent a (bound / a) else 0 termination_by bound decreasing_by simp_wf obtain ⟨ha, hb⟩ := h exact Nat.div_lt_self (by omega) ha /-- The distinct powers `a ^ e` not exceeding `limit`; empty when `limit = 0`, and `[1]` when `a = 1`. -/ def powersOfBase (a limit : Nat) : List Nat := if limit = 0 then [] else (List.range (maxExponent a limit + 1)).map (a ^ ·) /-- Every sum `p + q ≤ bound` with `p` a power of `x` and `q` a power of `y`, sorted without duplicates. -/ def powerfulSums (x y bound : Nat) : List Nat := sortDedup ((powersOfBase x bound).flatMap fun p => (powersOfBase y (bound - p)).map (p + ·)) /-! ### Main algorithm (impl) -/ /-- Enumerates powerful integers by listing the powers of each base up to the bound, summing every pair, and deduplicating by insertion sort. -/ def enumeratePowerfulIntegers (input : Input) : Output := powerfulSums input.1 input.2.1 input.2.2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem enumeratePowerfulIntegers_correct (input : Input) (h : isValidInput input) : powerfulIntegers_spec input (enumeratePowerfulIntegers input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (2, 3, 10) #guard isValidInput (3, 5, 15) #guard isValidInput (1, 1, 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (0, 1, 0)) #guard !(isValidInput (1, 1, 1000001)) #guard !(isValidInput (1, 0, 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard powerfulIntegers_check (2, 3, 10) [2, 3, 4, 5, 7, 9, 10] #guard powerfulIntegers_check (3, 5, 15) [2, 4, 6, 8, 10, 14] #guard powerfulIntegers_check (1, 1, 1) [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(powerfulIntegers_check (2, 3, 10) [2, 3, 4, 5, 7, 9]) #guard !(powerfulIntegers_check (3, 5, 15) []) #guard !(powerfulIntegers_check (1, 1, 1) [0, 1]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard enumeratePowerfulIntegers (2, 3, 10) == [2, 3, 4, 5, 7, 9, 10] #guard enumeratePowerfulIntegers (3, 5, 15) == [2, 4, 6, 8, 10, 14] #guard enumeratePowerfulIntegers (1, 1, 1) == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard powerfulIntegers_check (2, 3, 10) (enumeratePowerfulIntegers (2, 3, 10)) #guard powerfulIntegers_check (3, 5, 15) (enumeratePowerfulIntegers (3, 5, 15)) #guard powerfulIntegers_check (1, 1, 1) (enumeratePowerfulIntegers (1, 1, 1)) end PPowerfulIntegers