import Mathlib /-! # Number Of Digit One Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. ## Constraints - 0 <= n <= 10^9 ## Provided examples - `n = 13` → `6` - `n = 0` → `0` - `n = 55` → `16` ## Synthesized negative examples - invalid input: `n = 1000000001` ([structural] a predicate that admits 0 <= n <= 10^9. one step past the stated maximum) - invalid input: `n = 2000000000` ([structural] a predicate that admits 0 <= n <= 10^9. twice the stated maximum) - invalid input: `n = 10000000000` ([structural] a predicate that admits 0 <= n <= 10^9. one order of magnitude past the ceiling) - `n = 13` → `4` is wrong ([structural] answer may be a partial count rather than the maximal total. only tens-place 1s contribute, giving 4) - `n = 0` → `1` is wrong ([structural] range is 0..n+1 instead of 0..n, so n=0 also counts the number 1. includes the integer 1, giving one extra 1) - `n = 55` → `15` is wrong ([structural] unattainable not applicable; counts distinct integers containing a 1 instead of total occurrences. 11 counted once, giving 15 distinct numbers) -/ namespace PNumberOfDigitOne abbrev Input := Nat abbrev Output := Nat /-! ### Specification helpers -/ /-- The decimal digit at position `pos` (0-based from the right) of `m` is 1. -/ def IsDigitOneAt (m pos : Nat) : Prop := m / 10 ^ pos % 10 = 1 /-! ### Validity predicate (V) -/ /-- Valid input: a natural number at most 10^9 (non-negativity is free in `Nat`). -/ def isValidInput (input : Input) : Bool := input ≤ 10 ^ 9 /-! ### Ideal specification (P_spec) -/ /-- `result` counts the digit-one occurrences in `0 .. input`: it is the size of a finite collection of `(number, position)` pairs containing exactly the pairs whose number is at most `input` and whose digit at that decimal position is 1. -/ def countDigitOne_spec (input : Input) (result : Output) : Prop := ∃ S : Finset (Nat × Nat), S.card = result ∧ ∀ p : Nat × Nat, p ∈ S ↔ p.1 ≤ input ∧ IsDigitOneAt p.1 p.2 /-! ### Decidable specification (P_check) -/ /-- Decidability of the digit test: `IsDigitOneAt` unfolds to a decidable equality of natural numbers. -/ instance decIsDigitOneAt (m pos : Nat) : Decidable (IsDigitOneAt m pos) := inferInstanceAs (Decidable (m / 10 ^ pos % 10 = 1)) /-- Bounding box for candidate pairs: every `(m, pos)` with `m ≤ input` and digit 1 at `pos` has `pos < 10^pos ≤ m ≤ input`. -/ def pairBoxUpTo (input : Nat) : Finset (Nat × Nat) := Finset.range (input + 1) ×ˢ Finset.range (input + 1) /-- The collection of digit-one pairs the specification's membership condition forces: the box filtered by that condition. -/ def digitOnePairsUpTo (input : Nat) : Finset (Nat × Nat) := (pairBoxUpTo input).filter fun p => p.1 ≤ input ∧ IsDigitOneAt p.1 p.2 /-- Executable checker for `countDigitOne_spec`: the pinned-down collection has `result` elements and contains exactly the qualifying pairs of the box. -/ def countDigitOne_check (input : Input) (result : Output) : Bool := let S := digitOnePairsUpTo input decide (S.card = result ∧ ∀ p ∈ pairBoxUpTo input, p ∈ S ↔ p.1 ≤ input ∧ IsDigitOneAt p.1 p.2) theorem ndo_check_eq (input : Input) (result : Output) : countDigitOne_check input result = decide ((digitOnePairsUpTo input).card = result ∧ ∀ p ∈ pairBoxUpTo input, (p ∈ digitOnePairsUpTo input ↔ p.1 ≤ input ∧ IsDigitOneAt p.1 p.2)) := rfl theorem ndo_pos_lt (m pos : Nat) (hd : m / 10 ^ pos % 10 = 1) : pos < m := by have hle : 10 ^ pos ≤ m := by by_contra hlt have hm : m < 10 ^ pos := by omega rw [Nat.div_eq_of_lt hm] at hd exact absurd hd (by decide) have hpow : pos < 10 ^ pos := Nat.lt_pow_self (by omega) omega theorem ndo_mem_pairs (input : Nat) (q : Nat × Nat) : q ∈ digitOnePairsUpTo input ↔ q.1 ≤ input ∧ IsDigitOneAt q.1 q.2 := by unfold digitOnePairsUpTo rw [Finset.mem_filter] constructor · intro hq exact hq.2 · intro hq refine ⟨?_, hq⟩ have h1 : q.1 ≤ input := hq.1 have hd : q.1 / 10 ^ q.2 % 10 = 1 := hq.2 have h2 : q.2 < q.1 := ndo_pos_lt q.1 q.2 hd rw [pairBoxUpTo, Finset.mem_product, Finset.mem_range, Finset.mem_range] exact ⟨by omega, by omega⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem countDigitOne_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : countDigitOne_check input result ↔ countDigitOne_spec input result := by rw [ndo_check_eq, decide_eq_true_eq] unfold countDigitOne_spec constructor · intro hc exact ⟨digitOnePairsUpTo input, hc.1, fun q => ndo_mem_pairs input q⟩ · rintro ⟨S, hcard, hmem⟩ have hS : S = digitOnePairsUpTo input := by ext q rw [hmem q, ndo_mem_pairs input q] rw [← hS] exact ⟨hcard, fun q _ => hmem q⟩ /-! ### Implementation helpers -/ /-- Folds the least-significant-first decimal digits, accumulating each position's count of integers up to the original number having digit 1 there. -/ def countOnesAux : List Nat → Nat → Nat → Nat → Nat | [], _, _, acc => acc | d :: rest, factor, low, acc => let high := rest.foldr (fun x a => x + 10 * a) 0 let add := high * factor + (if d > 1 then factor else if d = 1 then low + 1 else 0) countOnesAux rest (factor * 10) (low + d * factor) (acc + add) /-! ### Main algorithm (impl) -/ /-- Digit-position counting: sums over each decimal position of `input` how many integers from 0 to `input` have digit 1 at that position. -/ def countOnesUpTo (input : Input) : Output := countOnesAux (Nat.digits 10 input) 1 0 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countOnesUpTo_correct (input : Input) (h : isValidInput input) : countDigitOne_spec input (countOnesUpTo input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 13 #guard isValidInput 0 #guard isValidInput 55 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 1000000001) #guard !(isValidInput 2000000000) #guard !(isValidInput 10000000000) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard countDigitOne_check 13 6 #guard countDigitOne_check 0 0 #guard countDigitOne_check 55 16 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(countDigitOne_check 13 4) #guard !(countDigitOne_check 0 1) #guard !(countDigitOne_check 55 15) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countOnesUpTo 13 == 6 #guard countOnesUpTo 0 == 0 #guard countOnesUpTo 55 == 16 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard countDigitOne_check 13 (countOnesUpTo 13) #guard countDigitOne_check 0 (countOnesUpTo 0) #guard countDigitOne_check 55 (countOnesUpTo 55) end PNumberOfDigitOne