import Mathlib /-! # Super Ugly Number A super ugly number is a positive integer whose prime factors are in the array primes. Given an integer n and an array of integers primes, return the nth super ugly number. The nth super ugly number is guaranteed to fit in a 32-bit signed integer. ## Constraints - 1 <= n <= 10^5 - 1 <= primes.length <= 100 - 2 <= primes[i] <= 1000 - primes[i] is guaranteed to be a prime number. - All the values of primes are unique and sorted in ascending order. ## Provided examples - `n = 1, primes = [2, 3, 5]` → `1` - `n = 2, primes = [2, 7]` → `2` - `n = 5, primes = [2, 7, 11]` → `8` ## Synthesized negative examples - invalid input: `n = 0, primes = [2]` ([structural] a predicate that admits 1 <= n <= 10^5. zero below the stated minimum for n) - invalid input: `n = 1, primes = []` ([structural] a predicate that admits 1 <= primes.length <= 100. empty primes array where at least one is required) - invalid input: `n = 1, primes = [4]` ([structural] a predicate that admits primes[i] is guaranteed to be a prime number.. composite number where a prime is guaranteed) - `n = 1, primes = [2, 3, 5]` → `2` is wrong ([structural] n and n+1 indexing swapped; returns the second super ugly number for n=1.. returns n+1th instead of nth.) - `n = 2, primes = [2, 7]` → `1` is wrong ([structural] soundness clause omitted: any lower bound is accepted. 1 is below the true answer and no output equals it) - `n = 5, primes = [2, 7, 11]` → `7` is wrong ([structural] returns the (n-1)th super ugly number instead of the nth. 7 is the fourth super ugly number for primes [2,7,11]) -/ namespace PSuperUglyNumber abbrev Input := (Nat) × (List Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- `m` is super ugly for `primes`: nonzero with every prime divisor in `primes`. -/ def IsSuperUgly (m : Nat) (primes : List Nat) : Prop := m ∈ Nat.factoredNumbers primes.toFinset /-! ### Validity predicate (V) -/ /-- Valid input: `1 ≤ n ≤ 10^5` and `primes` a sorted list of 1 to 100 distinct primes, each in `[2, 1000]`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1 && input.1 ≤ 10 ^ 5 && 1 ≤ input.2.length && input.2.length ≤ 100 && input.2.all (fun p => 2 ≤ p && p ≤ 1000 && Nat.Prime p) && decide input.2.Nodup && decide (input.2.Pairwise (· < ·)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the `n`-th super ugly number for `primes`: super ugly itself, with a finite set of `n − 1` predecessors containing exactly the super ugly numbers below it. -/ def nthSuperUglyNumber_spec (input : Input) (result : Output) : Prop := IsSuperUgly result input.2 ∧ ∃ S : Finset Nat, S.card + 1 = input.1 ∧ ∀ m : Nat, m ∈ S ↔ (IsSuperUgly m input.2 ∧ m < result) /-! ### Decidable specification (P_check) -/ /-- The super ugly numbers for `primes` strictly below `bound`. -/ def superUglyBelow (bound : Nat) (primes : List Nat) : Finset Nat := (Finset.range bound).filter (fun m => m ∈ Nat.factoredNumbers primes.toFinset) /-- Executable checker for `nthSuperUglyNumber_spec`: `result` is super ugly and the set of super ugly numbers below it, which the spec's biconditional forces to be exactly `superUglyBelow result primes`, has cardinality `n − 1`. -/ def nthSuperUglyNumber_check (input : Input) (result : Output) : Bool := decide (result ∈ Nat.factoredNumbers input.2.toFinset) && decide ((superUglyBelow result input.2).card + 1 = input.1) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem nthSuperUglyNumber_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : nthSuperUglyNumber_check input result ↔ nthSuperUglyNumber_spec input result := by simp only [nthSuperUglyNumber_check, Bool.and_eq_true, decide_eq_true_eq, nthSuperUglyNumber_spec] constructor · rintro ⟨hr, hc⟩ refine ⟨hr, superUglyBelow result input.2, hc, ?_⟩ intro m simp [superUglyBelow, IsSuperUgly, and_comm] · rintro ⟨hr, S, hc, hS⟩ refine ⟨hr, ?_⟩ have heq : S = superUglyBelow result input.2 := by ext m simpa [superUglyBelow, IsSuperUgly, and_comm] using hS m simpa [← heq] using hc /-! ### Implementation helpers -/ /-- Increment every pointer whose candidate product with its prime equals the newly appended value. -/ def advancePointers (uglys : Array Nat) (primes : Array Nat) (pointers : Array Nat) (next : Nat) : Array Nat := (List.range primes.size).foldl (fun acc i => if uglys[acc[i]!]! * primes[i]! = next then acc.set! i (acc[i]! + 1) else acc) pointers /-- Extend `uglys` by repeatedly appending the minimum candidate and advancing the matching pointers until it holds `n` entries. -/ def generateSuperUgly (n : Nat) (primes : Array Nat) (uglys : Array Nat) (pointers : Array Nat) : Array Nat := if primes.size = 0 then uglys else if h : n ≤ uglys.size then uglys else let next := (List.range primes.size).foldl (fun best i => Nat.min best (uglys[pointers[i]!]! * primes[i]!)) (uglys[pointers[0]!]! * primes[0]!) generateSuperUgly n primes (uglys.push next) (advancePointers uglys primes pointers next) termination_by n - uglys.size decreasing_by have h' : uglys.size < n := Nat.lt_of_not_ge h simp only [Array.size_push] omega /-! ### Main algorithm (impl) -/ /-- The `n`-th super ugly number by k-pointer dynamic programming over the generated sequence. -/ def findNthSuperUglyNumber (input : Input) : Output := let primes := input.2.toArray let uglys := generateSuperUgly input.1 primes #[1] (Array.replicate primes.size 0) uglys[input.1 - 1]! /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findNthSuperUglyNumber_correct (input : Input) (h : isValidInput input) : nthSuperUglyNumber_spec input (findNthSuperUglyNumber input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (1, [2, 3, 5]) #guard isValidInput (2, [2, 7]) #guard isValidInput (5, [2, 7, 11]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (0, [2])) #guard !(isValidInput (1, [])) #guard !(isValidInput (1, [4])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard nthSuperUglyNumber_check (1, [2, 3, 5]) 1 #guard nthSuperUglyNumber_check (2, [2, 7]) 2 #guard nthSuperUglyNumber_check (5, [2, 7, 11]) 8 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(nthSuperUglyNumber_check (1, [2, 3, 5]) 2) #guard !(nthSuperUglyNumber_check (2, [2, 7]) 1) #guard !(nthSuperUglyNumber_check (5, [2, 7, 11]) 7) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findNthSuperUglyNumber (1, [2, 3, 5]) == 1 #guard findNthSuperUglyNumber (2, [2, 7]) == 2 #guard findNthSuperUglyNumber (5, [2, 7, 11]) == 8 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard nthSuperUglyNumber_check (1, [2, 3, 5]) (findNthSuperUglyNumber (1, [2, 3, 5])) #guard nthSuperUglyNumber_check (2, [2, 7]) (findNthSuperUglyNumber (2, [2, 7])) #guard nthSuperUglyNumber_check (5, [2, 7, 11]) (findNthSuperUglyNumber (5, [2, 7, 11])) end PSuperUglyNumber