import Mathlib /-! # Perfect Squares Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not. ## Constraints - 1 <= n <= 10^4 ## Provided examples - `n = 12` → `3` - `n = 13` → `2` - `n = 8` → `2` ## Synthesized negative examples - invalid input: `n = 0` ([structural] a predicate that admits 1 <= n <= 10^4. below the stated floor; zero squares are not admitted) - invalid input: `n = 10001` ([structural] a predicate that admits 1 <= n <= 10^4. one past the stated ceiling) - invalid input: `n = 100000` ([structural] a predicate that admits 1 <= n <= 10^4. an order of magnitude past the ceiling) - `n = 12` → `4` is wrong ([structural] minimality stated as achievability alone. 12 = 9+1+1+1, so 4 is achievable but not least) - `n = 13` → `4` is wrong ([structural] minimality stated as achievability alone. 4 is attainable (4+4+4+1) but not least) - `n = 8` → `5` is wrong ([structural] minimality stated as achievability alone. five squares 4+1+1+1+1 sum to 8 but not least) -/ namespace PPerfectSquares abbrev Input := Nat abbrev Output := Nat /-! ### Specification helpers -/ /-- `L` is a decomposition of `n` into positive perfect squares. -/ def IsSquareRepr (n : Nat) (L : List Nat) : Prop := (∀ x ∈ L, ∃ k : Nat, 0 < k ∧ x = k * k) ∧ L.sum = n /-! ### Validity predicate (V) -/ /-- Valid input: an integer `n` with `1 ≤ n ≤ 10^4`. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input ∧ input ≤ 10^4) /-! ### Ideal specification (P_spec) -/ /-- `result` is the least length of any decomposition of `input` into positive perfect squares: one decomposition has length `result` and none has fewer. -/ def leastSquareSumTermCount_spec (input : Input) (result : Output) : Prop := IsLeast {k | ∃ L : List Nat, IsSquareRepr input L ∧ L.length = k} result /-! ### Decidable specification (P_check) -/ /-- Positive square roots whose square is at most `n`. -/ def squareRootsUpTo (n : Nat) : List Nat := (List.range n.sqrt).map (· + 1) /-- All lists of length `k` whose entries are drawn from `xs`. -/ def listsOfLength : Nat → List Nat → List (List Nat) | 0, _ => [[]] | k + 1, xs => xs.flatMap fun x => (listsOfLength k xs).map fun L => x :: L /-- Decidable form of `IsSquareRepr`: positive perfect squares summing to `n`. -/ def isSquareReprB (n : Nat) (L : List Nat) : Bool := L.all (fun x => decide (0 < x) && decide (x.sqrt * x.sqrt = x)) && decide (L.sum = n) /-- Some decomposition of `n` into positive perfect squares has length exactly `k`. -/ def hasSquareReprOfLength (n k : Nat) : Bool := (listsOfLength k (squareRootsUpTo n)).any fun roots => isSquareReprB n (roots.map fun r => r * r) /-- Executable checker for `leastSquareSumTermCount_spec`, truncated at length four. -/ def leastSquareSumTermCount_check (input : Input) (result : Output) : Bool := decide (result ≤ 4) && (hasSquareReprOfLength input result && (List.range result).all fun k => !hasSquareReprOfLength input k) theorem four_bridge (n : Nat) : ∃ L, IsSquareRepr n L ∧ L.length ≤ 4 := by obtain ⟨a, b, c, d, hsum⟩ := Nat.sum_four_squares n let L := [a * a, b * b, c * c, d * d].filter (· != 0) refine ⟨L, ?_, ?_⟩ · constructor · intro x hx have hx' : (x = a * a ∨ x = b * b ∨ x = c * c ∨ x = d * d) ∧ x != 0 := by simpa [L] using hx rcases hx' with ⟨rfl | rfl | rfl | rfl, hx0⟩ all_goals refine ⟨_, ?_, rfl⟩ apply Nat.pos_of_ne_zero intro hz subst_vars simp at hx0 · by_cases ha : a = 0 <;> by_cases hb : b = 0 <;> by_cases hc : c = 0 <;> by_cases hd : d = 0 all_goals simpa [L, ha, hb, hc, hd, pow_two, Nat.add_assoc] using hsum · simpa [L] using (List.length_filter_le (fun x : Nat => x != 0) [a * a, b * b, c * c, d * d]) theorem root_of_bridges (repr : ∀ n k, hasSquareReprOfLength n k = true ↔ ∃ L, IsSquareRepr n L ∧ L.length = k) (four : ∀ n, ∃ L, IsSquareRepr n L ∧ L.length ≤ 4) (n k : Nat) : leastSquareSumTermCount_check n k ↔ leastSquareSumTermCount_spec n k := by simp only [leastSquareSumTermCount_check, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, List.mem_range, Bool.not_eq_true', Bool.eq_false_iff] unfold leastSquareSumTermCount_spec IsLeast lowerBounds simp only [Set.mem_setOf_eq] constructor · rintro ⟨hk, hw, hmin⟩ exact ⟨(repr n k).mp hw, fun j hj => by by_contra hn; exact hmin j (by omega) ((repr n j).mpr hj)⟩ · rintro ⟨hw, hmin⟩ obtain ⟨L, hL, hlen⟩ := four n exact ⟨le_trans (hmin ⟨L, hL, rfl⟩) hlen, (repr n k).mpr hw, fun j hj hwj => by have := hmin ((repr n j).mp hwj); omega⟩ theorem lists_mem (k : Nat) (xs L : List Nat) : L ∈ listsOfLength k xs ↔ L.length = k ∧ ∀ x ∈ L, x ∈ xs := by induction k generalizing L with | zero => simp +contextual [listsOfLength] | succ k ih => cases L with | nil => simp [listsOfLength] | cons a L => simp [listsOfLength, ih, and_assoc, and_left_comm, and_comm] theorem square_bool (n : Nat) (L : List Nat) : isSquareReprB n L = true ↔ IsSquareRepr n L := by simp only [isSquareReprB, Bool.and_eq_true, List.all_eq_true, decide_eq_true_eq, IsSquareRepr] have aux (x : Nat) : (0 < x ∧ x.sqrt * x.sqrt = x) ↔ ∃ k : Nat, 0 < k ∧ x = k * k := by constructor · rintro ⟨hp, he⟩ exact ⟨x.sqrt, Nat.sqrt_pos.mpr hp, he.symm⟩ · rintro ⟨k, hk, rfl⟩ simp [Nat.sqrt_eq, Nat.mul_pos hk hk] simp only [aux] theorem repr_bridge (n k : Nat) : hasSquareReprOfLength n k = true ↔ ∃ L, IsSquareRepr n L ∧ L.length = k := by simp only [hasSquareReprOfLength, List.any_eq_true] constructor · rintro ⟨roots, hr, hs⟩ exact ⟨roots.map (fun r => r * r), (square_bool n _).mp hs, by simpa using ((lists_mem k _ roots).mp hr).1⟩ · rintro ⟨L, hL, hlen⟩ have hsquare : ∀ x ∈ L, x.sqrt * x.sqrt = x := by intro x hx obtain ⟨r, hr, rfl⟩ := hL.1 x hx simp [Nat.sqrt_eq] have hmap : (L.map Nat.sqrt).map (fun r => r * r) = L := by rw [List.map_map] conv_rhs => rw [← List.map_id L] apply List.map_congr_left intro x hx exact hsquare x hx refine ⟨L.map Nat.sqrt, ?_, ?_⟩ · apply (lists_mem k _ _).mpr refine ⟨by simpa using hlen, ?_⟩ intro r hr obtain ⟨x, hx, rfl⟩ := List.mem_map.mp hr have hxpos : 0 < x := by obtain ⟨a, ha, rfl⟩ := hL.1 x hx exact Nat.mul_pos ha ha have hp : 0 < x.sqrt := Nat.sqrt_pos.mpr hxpos have hb : x.sqrt ≤ n.sqrt := Nat.sqrt_le_sqrt (by rw [← hL.2] exact List.le_sum_of_mem hx) simp only [squareRootsUpTo, List.mem_map, List.mem_range] exact ⟨x.sqrt - 1, by omega, by omega⟩ · rw [hmap] exact (square_bool n L).mpr hL /-- On valid input the checker accepts exactly the specified outputs. -/ theorem leastSquareSumTermCount_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : leastSquareSumTermCount_check input result ↔ leastSquareSumTermCount_spec input result := by exact root_of_bridges repr_bridge four_bridge input result /-! ### Implementation helpers -/ /-- Bottom-up table of least square counts: the entry for total `i` is the least number of positive perfect squares summing to `i`, most recent first. -/ def minSquaresTable (n : Nat) : List Nat := (List.range (n + 1)).foldl (fun acc i => if i = 0 then 0 :: acc else let best := (squareRootsUpTo i).foldl (fun b r => Nat.min b ((acc[r * r - 1]?).getD 0 + 1)) (i + 1) best :: acc) [] /-! ### Main algorithm (impl) -/ /-- Least number of perfect squares summing to `input`, by dynamic programming over totals with the minimum taken over the squares at most each total. -/ def leastSquareSumTermCountImpl (input : Input) : Output := ((minSquaresTable input).head?).getD 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem leastSquareSumTermCountImpl_correct (input : Input) (h : isValidInput input) : leastSquareSumTermCount_spec input (leastSquareSumTermCountImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 12 #guard isValidInput 13 #guard isValidInput 8 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 10001) #guard !(isValidInput 100000) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard leastSquareSumTermCount_check 12 3 #guard leastSquareSumTermCount_check 13 2 #guard leastSquareSumTermCount_check 8 2 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(leastSquareSumTermCount_check 12 4) #guard !(leastSquareSumTermCount_check 13 4) #guard !(leastSquareSumTermCount_check 8 5) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard leastSquareSumTermCountImpl 12 == 3 #guard leastSquareSumTermCountImpl 13 == 2 #guard leastSquareSumTermCountImpl 8 == 2 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard leastSquareSumTermCount_check 12 (leastSquareSumTermCountImpl 12) #guard leastSquareSumTermCount_check 13 (leastSquareSumTermCountImpl 13) #guard leastSquareSumTermCount_check 8 (leastSquareSumTermCountImpl 8) end PPerfectSquares