data.nat.digits
⟷
Mathlib.Data.Nat.Digits
The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -3,7 +3,7 @@ Copyright (c) 2020 Scott Morrison. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Scott Morrison, Shing Tak Lam, Mario Carneiro
-/
-import Data.Int.Modeq
+import Data.Int.ModEq
import Data.Nat.Bits
import Data.Nat.Log
import Data.List.Indexes
@@ -223,7 +223,7 @@ theorem ofDigits_eq_sum_map_with_index_aux (b : ℕ) (l : List ℕ) :
by simp [this]
congr
ext
- simp [pow_succ]
+ simp [pow_succ']
ring
#align nat.of_digits_eq_sum_map_with_index_aux Nat.ofDigits_eq_sum_map_with_index_aux
-/
@@ -262,7 +262,7 @@ theorem ofDigits_append {b : ℕ} {l1 l2 : List ℕ} :
by
induction' l1 with hd tl IH
· simp [of_digits]
- · rw [of_digits, List.cons_append, of_digits, IH, List.length_cons, pow_succ']
+ · rw [of_digits, List.cons_append, of_digits, IH, List.length_cons, pow_succ]
ring
#align nat.of_digits_append Nat.ofDigits_append
-/
@@ -494,7 +494,7 @@ theorem ofDigits_lt_base_pow_length' {b : ℕ} {l : List ℕ} (hl : ∀ x ∈ l,
by
induction' l with hd tl IH
· simp [of_digits]
- · rw [of_digits, List.length_cons, pow_succ]
+ · rw [of_digits, List.length_cons, pow_succ']
have : (of_digits (b + 2) tl + 1) * (b + 2) ≤ (b + 2) ^ tl.length * (b + 2) :=
mul_le_mul (IH fun x hx => hl _ (List.mem_cons_of_mem _ hx)) (by rfl) (by decide)
(Nat.zero_le _)
@@ -768,7 +768,7 @@ theorem nine_dvd_iff (n : ℕ) : 9 ∣ n ↔ 9 ∣ (digits 10 n).Sum :=
theorem dvd_iff_dvd_ofDigits (b b' : ℕ) (c : ℤ) (h : (b : ℤ) ∣ (b' : ℤ) - c) (n : ℕ) :
b ∣ n ↔ (b : ℤ) ∣ ofDigits c (digits b' n) :=
by
- rw [← Int.coe_nat_dvd]
+ rw [← Int.natCast_dvd_natCast]
exact
dvd_iff_dvd_of_dvd_sub (zmodeq_of_digits_digits b b' c (Int.modEq_iff_dvd.2 h).symm _).symm.Dvd
#align nat.dvd_iff_dvd_of_digits Nat.dvd_iff_dvd_ofDigits
@@ -791,7 +791,7 @@ theorem eleven_dvd_of_palindrome (p : (digits 10 n).Palindrome) (h : Even (digit
replace h : Even dig.length := by rwa [List.length_map]
refine' eleven_dvd_iff.2 ⟨0, (_ : dig.alternating_sum = 0)⟩
have := dig.alternating_sum_reverse
- rw [(p.map _).reverse_eq, pow_succ, h.neg_one_pow, mul_one, neg_one_zsmul] at this
+ rw [(p.map _).reverse_eq, pow_succ', h.neg_one_pow, mul_one, neg_one_zsmul] at this
exact eq_zero_of_neg_eq this.symm
#align nat.eleven_dvd_of_palindrome Nat.eleven_dvd_of_palindrome
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -311,7 +311,7 @@ theorem digits_ofDigits (b : ℕ) (h : 1 < b) (L : List ℕ) (w₁ : ∀ l ∈ L
· rw [ih]
· intro l m; apply w₁; exact List.mem_cons_of_mem _ m
· intro h
- · rw [List.getLast_cons h] at w₂
+ · rw [List.getLast_cons h] at w₂
convert w₂
· exact w₁ d (List.mem_cons_self _ _)
· by_cases h' : L = []
@@ -392,9 +392,9 @@ theorem digits_eq_cons_digits_div {b n : ℕ} (h : 1 < b) (w : n ≠ 0) :
by
rcases b with (_ | _ | b)
· rw [digits_zero_succ' w, Nat.mod_zero, Nat.div_zero, Nat.digits_zero_zero]
- · norm_num at h
+ · norm_num at h
rcases n with (_ | n)
- · norm_num at w
+ · norm_num at w
simp
#align nat.digits_eq_cons_digits_div Nat.digits_eq_cons_digits_div
-/
@@ -469,9 +469,9 @@ theorem digits_lt_base' {b m : ℕ} : ∀ {d}, d ∈ digits (b + 2) m → d < b
apply Nat.strong_induction_on m
intro n IH d hd
cases' n with n
- · rw [digits_zero] at hd ; cases hd
+ · rw [digits_zero] at hd; cases hd
-- base b+2 expansion of 0 has no digits
- rw [digits_add_two_add_one] at hd
+ rw [digits_add_two_add_one] at hd
cases hd
· rw [hd]; exact n.succ.mod_lt (by linarith)
· exact IH _ (Nat.div_lt_self (Nat.succ_pos _) (by linarith)) hd
@@ -735,7 +735,7 @@ theorem modEq_eleven_digits_sum (n : ℕ) :
n ≡ ((digits 10 n).map fun n : ℕ => (n : ℤ)).alternatingSum [ZMOD 11] :=
by
have t := zmodeq_of_digits_digits 11 10 (-1 : ℤ) (by unfold Int.ModEq <;> norm_num) n
- rwa [of_digits_neg_one] at t
+ rwa [of_digits_neg_one] at t
#align nat.modeq_eleven_digits_sum Nat.modEq_eleven_digits_sum
-/
@@ -779,7 +779,7 @@ theorem eleven_dvd_iff :
11 ∣ n ↔ (11 : ℤ) ∣ ((digits 10 n).map fun n : ℕ => (n : ℤ)).alternatingSum :=
by
have t := dvd_iff_dvd_of_digits 11 10 (-1 : ℤ) (by norm_num) n
- rw [of_digits_neg_one] at t
+ rw [of_digits_neg_one] at t
exact t
#align nat.eleven_dvd_iff Nat.eleven_dvd_iff
-/
@@ -791,7 +791,7 @@ theorem eleven_dvd_of_palindrome (p : (digits 10 n).Palindrome) (h : Even (digit
replace h : Even dig.length := by rwa [List.length_map]
refine' eleven_dvd_iff.2 ⟨0, (_ : dig.alternating_sum = 0)⟩
have := dig.alternating_sum_reverse
- rw [(p.map _).reverse_eq, pow_succ, h.neg_one_pow, mul_one, neg_one_zsmul] at this
+ rw [(p.map _).reverse_eq, pow_succ, h.neg_one_pow, mul_one, neg_one_zsmul] at this
exact eq_zero_of_neg_eq this.symm
#align nat.eleven_dvd_of_palindrome Nat.eleven_dvd_of_palindrome
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -274,7 +274,7 @@ theorem coe_ofDigits (α : Type _) [Semiring α] (b : ℕ) (L : List ℕ) :
by
induction' L with d L ih
· simp [of_digits]
- · dsimp [of_digits]; push_cast ; rw [ih]
+ · dsimp [of_digits]; push_cast; rw [ih]
#align nat.coe_of_digits Nat.coe_ofDigits
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,13 +3,13 @@ Copyright (c) 2020 Scott Morrison. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Scott Morrison, Shing Tak Lam, Mario Carneiro
-/
-import Mathbin.Data.Int.Modeq
-import Mathbin.Data.Nat.Bits
-import Mathbin.Data.Nat.Log
-import Mathbin.Data.List.Indexes
-import Mathbin.Data.List.Palindrome
-import Mathbin.Algebra.Parity
-import Mathbin.Tactic.IntervalCases
+import Data.Int.Modeq
+import Data.Nat.Bits
+import Data.Nat.Log
+import Data.List.Indexes
+import Data.List.Palindrome
+import Algebra.Parity
+import Tactic.IntervalCases
import Mathbin.Tactic.Linarith.Default
#align_import data.nat.digits from "leanprover-community/mathlib"@"832f7b9162039c28b9361289c8681f155cae758f"
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,11 +2,6 @@
Copyright (c) 2020 Scott Morrison. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Scott Morrison, Shing Tak Lam, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.nat.digits
-! leanprover-community/mathlib commit 832f7b9162039c28b9361289c8681f155cae758f
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Data.Int.Modeq
import Mathbin.Data.Nat.Bits
@@ -17,6 +12,8 @@ import Mathbin.Algebra.Parity
import Mathbin.Tactic.IntervalCases
import Mathbin.Tactic.Linarith.Default
+#align_import data.nat.digits from "leanprover-community/mathlib"@"832f7b9162039c28b9361289c8681f155cae758f"
+
/-!
# Digits of a natural number
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -205,6 +205,7 @@ def ofDigits {α : Type _} [Semiring α] (b : α) : List ℕ → α
#align nat.of_digits Nat.ofDigits
-/
+#print Nat.ofDigits_eq_foldr /-
theorem ofDigits_eq_foldr {α : Type _} [Semiring α] (b : α) (L : List ℕ) :
ofDigits b L = L.foldr (fun x y => x + b * y) 0 :=
by
@@ -212,6 +213,7 @@ theorem ofDigits_eq_foldr {α : Type _} [Semiring α] (b : α) (L : List ℕ) :
· rfl
· dsimp [of_digits]; rw [ih]
#align nat.of_digits_eq_foldr Nat.ofDigits_eq_foldr
+-/
#print Nat.ofDigits_eq_sum_map_with_index_aux /-
theorem ofDigits_eq_sum_map_with_index_aux (b : ℕ) (l : List ℕ) :
@@ -250,10 +252,12 @@ theorem ofDigits_singleton {b n : ℕ} : ofDigits b [n] = n := by simp [of_digit
-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.ofDigits_one_cons /-
@[simp]
theorem ofDigits_one_cons {α : Type _} [Semiring α] (h : ℕ) (L : List ℕ) :
ofDigits (1 : α) (h::L) = h + ofDigits 1 L := by simp [of_digits]
#align nat.of_digits_one_cons Nat.ofDigits_one_cons
+-/
#print Nat.ofDigits_append /-
theorem ofDigits_append {b : ℕ} {l1 l2 : List ℕ} :
@@ -277,6 +281,7 @@ theorem coe_ofDigits (α : Type _) [Semiring α] (b : ℕ) (L : List ℕ) :
#align nat.coe_of_digits Nat.coe_ofDigits
-/
+#print Nat.coe_int_ofDigits /-
@[norm_cast]
theorem coe_int_ofDigits (b : ℕ) (L : List ℕ) : ((ofDigits b L : ℕ) : ℤ) = ofDigits (b : ℤ) L :=
by
@@ -284,6 +289,7 @@ theorem coe_int_ofDigits (b : ℕ) (L : List ℕ) : ((ofDigits b L : ℕ) : ℤ)
· rfl
· dsimp [of_digits]; push_cast
#align nat.coe_int_of_digits Nat.coe_int_ofDigits
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
@@ -613,6 +619,7 @@ theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1
/-! ### Modular Arithmetic -/
+#print Nat.dvd_ofDigits_sub_ofDigits /-
-- This is really a theorem about polynomials.
theorem dvd_ofDigits_sub_ofDigits {α : Type _} [CommRing α] {a b k : α} (h : k ∣ a - b)
(L : List ℕ) : k ∣ ofDigits a L - ofDigits b L :=
@@ -622,6 +629,7 @@ theorem dvd_ofDigits_sub_ofDigits {α : Type _} [CommRing α] {a b k : α} (h :
· simp only [of_digits, add_sub_add_left_eq_sub]
exact dvd_mul_sub_mul h ih
#align nat.dvd_of_digits_sub_of_digits Nat.dvd_ofDigits_sub_ofDigits
+-/
#print Nat.ofDigits_modEq' /-
theorem ofDigits_modEq' (b b' : ℕ) (k : ℕ) (h : b ≡ b' [MOD k]) (L : List ℕ) :
@@ -648,6 +656,7 @@ theorem ofDigits_mod (b k : ℕ) (L : List ℕ) : ofDigits b L % k = ofDigits (b
#align nat.of_digits_mod Nat.ofDigits_mod
-/
+#print Nat.ofDigits_zmodeq' /-
theorem ofDigits_zmodeq' (b b' : ℤ) (k : ℕ) (h : b ≡ b' [ZMOD k]) (L : List ℕ) :
ofDigits b L ≡ ofDigits b' L [ZMOD k] :=
by
@@ -658,14 +667,19 @@ theorem ofDigits_zmodeq' (b b' : ℤ) (k : ℕ) (h : b ≡ b' [ZMOD k]) (L : Lis
conv_lhs => rw [Int.add_emod, Int.mul_emod, h, ih]
conv_rhs => rw [Int.add_emod, Int.mul_emod]
#align nat.of_digits_zmodeq' Nat.ofDigits_zmodeq'
+-/
+#print Nat.ofDigits_zmodeq /-
theorem ofDigits_zmodeq (b : ℤ) (k : ℕ) (L : List ℕ) : ofDigits b L ≡ ofDigits (b % k) L [ZMOD k] :=
ofDigits_zmodeq' b (b % k) k (b.mod_modEq ↑k).symm L
#align nat.of_digits_zmodeq Nat.ofDigits_zmodeq
+-/
+#print Nat.ofDigits_zmod /-
theorem ofDigits_zmod (b : ℤ) (k : ℕ) (L : List ℕ) : ofDigits b L % k = ofDigits (b % k) L % k :=
ofDigits_zmodeq b k L
#align nat.of_digits_zmod Nat.ofDigits_zmod
+-/
#print Nat.modEq_digits_sum /-
theorem modEq_digits_sum (b b' : ℕ) (h : b' % b = 1) (n : ℕ) : n ≡ (digits b' n).Sum [MOD b] :=
@@ -692,6 +706,7 @@ theorem modEq_nine_digits_sum (n : ℕ) : n ≡ (digits 10 n).Sum [MOD 9] :=
#align nat.modeq_nine_digits_sum Nat.modEq_nine_digits_sum
-/
+#print Nat.zmodeq_ofDigits_digits /-
theorem zmodeq_ofDigits_digits (b b' : ℕ) (c : ℤ) (h : b' ≡ c [ZMOD b]) (n : ℕ) :
n ≡ ofDigits c (digits b' n) [ZMOD b] :=
by
@@ -702,9 +717,11 @@ theorem zmodeq_ofDigits_digits (b b' : ℕ) (c : ℤ) (h : b' ≡ c [ZMOD b]) (n
rw [coe_int_of_digits]
apply of_digits_zmodeq' _ _ _ h
#align nat.zmodeq_of_digits_digits Nat.zmodeq_ofDigits_digits
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.ofDigits_neg_one /-
theorem ofDigits_neg_one :
∀ L : List ℕ, ofDigits (-1 : ℤ) L = (L.map fun n : ℕ => (n : ℤ)).alternatingSum
| [] => rfl
@@ -714,6 +731,7 @@ theorem ofDigits_neg_one :
simp only [of_digits, List.alternatingSum, List.map_cons, of_digits_neg_one t]
ring
#align nat.of_digits_neg_one Nat.ofDigits_neg_one
+-/
#print Nat.modEq_eleven_digits_sum /-
theorem modEq_eleven_digits_sum (n : ℕ) :
@@ -749,6 +767,7 @@ theorem nine_dvd_iff (n : ℕ) : 9 ∣ n ↔ 9 ∣ (digits 10 n).Sum :=
#align nat.nine_dvd_iff Nat.nine_dvd_iff
-/
+#print Nat.dvd_iff_dvd_ofDigits /-
theorem dvd_iff_dvd_ofDigits (b b' : ℕ) (c : ℤ) (h : (b : ℤ) ∣ (b' : ℤ) - c) (n : ℕ) :
b ∣ n ↔ (b : ℤ) ∣ ofDigits c (digits b' n) :=
by
@@ -756,7 +775,9 @@ theorem dvd_iff_dvd_ofDigits (b b' : ℕ) (c : ℤ) (h : (b : ℤ) ∣ (b' : ℤ
exact
dvd_iff_dvd_of_dvd_sub (zmodeq_of_digits_digits b b' c (Int.modEq_iff_dvd.2 h).symm _).symm.Dvd
#align nat.dvd_iff_dvd_of_digits Nat.dvd_iff_dvd_ofDigits
+-/
+#print Nat.eleven_dvd_iff /-
theorem eleven_dvd_iff :
11 ∣ n ↔ (11 : ℤ) ∣ ((digits 10 n).map fun n : ℕ => (n : ℤ)).alternatingSum :=
by
@@ -764,6 +785,7 @@ theorem eleven_dvd_iff :
rw [of_digits_neg_one] at t
exact t
#align nat.eleven_dvd_iff Nat.eleven_dvd_iff
+-/
#print Nat.eleven_dvd_of_palindrome /-
theorem eleven_dvd_of_palindrome (p : (digits 10 n).Palindrome) (h : Even (digits 10 n).length) :
mathlib commit https://github.com/leanprover-community/mathlib/commit/31c24aa72e7b3e5ed97a8412470e904f82b81004
@@ -808,6 +808,7 @@ theorem digits_one (b n) (n0 : 0 < n) (nb : n < b) : Nat.digits b n = [n] ∧ 1
open Tactic
+-- PLEASE REPORT THIS TO MATHPORT DEVS, THIS SHOULD NOT HAPPEN.
-- failed to format: unknown constant 'term.pseudo.antiquot'
/-- Helper function for the `norm_digits` tactic. -/ unsafe
def
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -308,7 +308,7 @@ theorem digits_ofDigits (b : ℕ) (h : 1 < b) (L : List ℕ) (w₁ : ∀ l ∈ L
· rw [ih]
· intro l m; apply w₁; exact List.mem_cons_of_mem _ m
· intro h
- · rw [List.getLast_cons h] at w₂
+ · rw [List.getLast_cons h] at w₂
convert w₂
· exact w₁ d (List.mem_cons_self _ _)
· by_cases h' : L = []
@@ -389,9 +389,9 @@ theorem digits_eq_cons_digits_div {b n : ℕ} (h : 1 < b) (w : n ≠ 0) :
by
rcases b with (_ | _ | b)
· rw [digits_zero_succ' w, Nat.mod_zero, Nat.div_zero, Nat.digits_zero_zero]
- · norm_num at h
+ · norm_num at h
rcases n with (_ | n)
- · norm_num at w
+ · norm_num at w
simp
#align nat.digits_eq_cons_digits_div Nat.digits_eq_cons_digits_div
-/
@@ -466,9 +466,9 @@ theorem digits_lt_base' {b m : ℕ} : ∀ {d}, d ∈ digits (b + 2) m → d < b
apply Nat.strong_induction_on m
intro n IH d hd
cases' n with n
- · rw [digits_zero] at hd; cases hd
+ · rw [digits_zero] at hd ; cases hd
-- base b+2 expansion of 0 has no digits
- rw [digits_add_two_add_one] at hd
+ rw [digits_add_two_add_one] at hd
cases hd
· rw [hd]; exact n.succ.mod_lt (by linarith)
· exact IH _ (Nat.div_lt_self (Nat.succ_pos _) (by linarith)) hd
@@ -720,7 +720,7 @@ theorem modEq_eleven_digits_sum (n : ℕ) :
n ≡ ((digits 10 n).map fun n : ℕ => (n : ℤ)).alternatingSum [ZMOD 11] :=
by
have t := zmodeq_of_digits_digits 11 10 (-1 : ℤ) (by unfold Int.ModEq <;> norm_num) n
- rwa [of_digits_neg_one] at t
+ rwa [of_digits_neg_one] at t
#align nat.modeq_eleven_digits_sum Nat.modEq_eleven_digits_sum
-/
@@ -761,7 +761,7 @@ theorem eleven_dvd_iff :
11 ∣ n ↔ (11 : ℤ) ∣ ((digits 10 n).map fun n : ℕ => (n : ℤ)).alternatingSum :=
by
have t := dvd_iff_dvd_of_digits 11 10 (-1 : ℤ) (by norm_num) n
- rw [of_digits_neg_one] at t
+ rw [of_digits_neg_one] at t
exact t
#align nat.eleven_dvd_iff Nat.eleven_dvd_iff
@@ -772,7 +772,7 @@ theorem eleven_dvd_of_palindrome (p : (digits 10 n).Palindrome) (h : Even (digit
replace h : Even dig.length := by rwa [List.length_map]
refine' eleven_dvd_iff.2 ⟨0, (_ : dig.alternating_sum = 0)⟩
have := dig.alternating_sum_reverse
- rw [(p.map _).reverse_eq, pow_succ, h.neg_one_pow, mul_one, neg_one_zsmul] at this
+ rw [(p.map _).reverse_eq, pow_succ, h.neg_one_pow, mul_one, neg_one_zsmul] at this
exact eq_zero_of_neg_eq this.symm
#align nat.eleven_dvd_of_palindrome Nat.eleven_dvd_of_palindrome
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -205,12 +205,6 @@ def ofDigits {α : Type _} [Semiring α] (b : α) : List ℕ → α
#align nat.of_digits Nat.ofDigits
-/
-/- warning: nat.of_digits_eq_foldr -> Nat.ofDigits_eq_foldr is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : Semiring.{u1} α] (b : α) (L : List.{0} Nat), Eq.{succ u1} α (Nat.ofDigits.{u1} α _inst_1 b L) (List.foldr.{0, u1} Nat α (fun (x : Nat) (y : α) => HAdd.hAdd.{u1, u1, u1} α α α (instHAdd.{u1} α (Distrib.toHasAdd.{u1} α (NonUnitalNonAssocSemiring.toDistrib.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))) ((fun (a : Type) (b : Type.{u1}) [self : HasLiftT.{1, succ u1} a b] => self.0) Nat α (HasLiftT.mk.{1, succ u1} Nat α (CoeTCₓ.coe.{1, succ u1} Nat α (Nat.castCoe.{u1} α (AddMonoidWithOne.toNatCast.{u1} α (AddCommMonoidWithOne.toAddMonoidWithOne.{u1} α (NonAssocSemiring.toAddCommMonoidWithOne.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))))) x) (HMul.hMul.{u1, u1, u1} α α α (instHMul.{u1} α (Distrib.toHasMul.{u1} α (NonUnitalNonAssocSemiring.toDistrib.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))) b y)) (OfNat.ofNat.{u1} α 0 (OfNat.mk.{u1} α 0 (Zero.zero.{u1} α (MulZeroClass.toHasZero.{u1} α (NonUnitalNonAssocSemiring.toMulZeroClass.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))))) L)
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : Semiring.{u1} α] (b : α) (L : List.{0} Nat), Eq.{succ u1} α (Nat.ofDigits.{u1} α _inst_1 b L) (List.foldr.{0, u1} Nat α (fun (x : Nat) (y : α) => HAdd.hAdd.{u1, u1, u1} α α α (instHAdd.{u1} α (Distrib.toAdd.{u1} α (NonUnitalNonAssocSemiring.toDistrib.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))) (Nat.cast.{u1} α (Semiring.toNatCast.{u1} α _inst_1) x) (HMul.hMul.{u1, u1, u1} α α α (instHMul.{u1} α (NonUnitalNonAssocSemiring.toMul.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1)))) b y)) (OfNat.ofNat.{u1} α 0 (Zero.toOfNat0.{u1} α (MonoidWithZero.toZero.{u1} α (Semiring.toMonoidWithZero.{u1} α _inst_1)))) L)
-Case conversion may be inaccurate. Consider using '#align nat.of_digits_eq_foldr Nat.ofDigits_eq_foldrₓ'. -/
theorem ofDigits_eq_foldr {α : Type _} [Semiring α] (b : α) (L : List ℕ) :
ofDigits b L = L.foldr (fun x y => x + b * y) 0 :=
by
@@ -255,12 +249,6 @@ theorem ofDigits_singleton {b n : ℕ} : ofDigits b [n] = n := by simp [of_digit
#align nat.of_digits_singleton Nat.ofDigits_singleton
-/
-/- warning: nat.of_digits_one_cons -> Nat.ofDigits_one_cons is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : Semiring.{u1} α] (h : Nat) (L : List.{0} Nat), Eq.{succ u1} α (Nat.ofDigits.{u1} α _inst_1 (OfNat.ofNat.{u1} α 1 (OfNat.mk.{u1} α 1 (One.one.{u1} α (AddMonoidWithOne.toOne.{u1} α (AddCommMonoidWithOne.toAddMonoidWithOne.{u1} α (NonAssocSemiring.toAddCommMonoidWithOne.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))))) (List.cons.{0} Nat h L)) (HAdd.hAdd.{u1, u1, u1} α α α (instHAdd.{u1} α (Distrib.toHasAdd.{u1} α (NonUnitalNonAssocSemiring.toDistrib.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))) ((fun (a : Type) (b : Type.{u1}) [self : HasLiftT.{1, succ u1} a b] => self.0) Nat α (HasLiftT.mk.{1, succ u1} Nat α (CoeTCₓ.coe.{1, succ u1} Nat α (Nat.castCoe.{u1} α (AddMonoidWithOne.toNatCast.{u1} α (AddCommMonoidWithOne.toAddMonoidWithOne.{u1} α (NonAssocSemiring.toAddCommMonoidWithOne.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))))) h) (Nat.ofDigits.{u1} α _inst_1 (OfNat.ofNat.{u1} α 1 (OfNat.mk.{u1} α 1 (One.one.{u1} α (AddMonoidWithOne.toOne.{u1} α (AddCommMonoidWithOne.toAddMonoidWithOne.{u1} α (NonAssocSemiring.toAddCommMonoidWithOne.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))))) L))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : Semiring.{u1} α] (h : Nat) (L : List.{0} Nat), Eq.{succ u1} α (Nat.ofDigits.{u1} α _inst_1 (OfNat.ofNat.{u1} α 1 (One.toOfNat1.{u1} α (Semiring.toOne.{u1} α _inst_1))) (List.cons.{0} Nat h L)) (HAdd.hAdd.{u1, u1, u1} α α α (instHAdd.{u1} α (Distrib.toAdd.{u1} α (NonUnitalNonAssocSemiring.toDistrib.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))) (Nat.cast.{u1} α (Semiring.toNatCast.{u1} α _inst_1) h) (Nat.ofDigits.{u1} α _inst_1 (OfNat.ofNat.{u1} α 1 (One.toOfNat1.{u1} α (Semiring.toOne.{u1} α _inst_1))) L))
-Case conversion may be inaccurate. Consider using '#align nat.of_digits_one_cons Nat.ofDigits_one_consₓ'. -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
@[simp]
theorem ofDigits_one_cons {α : Type _} [Semiring α] (h : ℕ) (L : List ℕ) :
@@ -289,12 +277,6 @@ theorem coe_ofDigits (α : Type _) [Semiring α] (b : ℕ) (L : List ℕ) :
#align nat.coe_of_digits Nat.coe_ofDigits
-/
-/- warning: nat.coe_int_of_digits -> Nat.coe_int_ofDigits is a dubious translation:
-lean 3 declaration is
- forall (b : Nat) (L : List.{0} Nat), Eq.{1} Int ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) (Nat.ofDigits.{0} Nat Nat.semiring b L)) (Nat.ofDigits.{0} Int Int.semiring ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) L)
-but is expected to have type
- forall (b : Nat) (L : List.{0} Nat), Eq.{1} Int (Nat.cast.{0} Int instNatCastInt (Nat.ofDigits.{0} Nat Nat.semiring b L)) (Nat.ofDigits.{0} Int Int.instSemiringInt (Nat.cast.{0} Int instNatCastInt b) L)
-Case conversion may be inaccurate. Consider using '#align nat.coe_int_of_digits Nat.coe_int_ofDigitsₓ'. -/
@[norm_cast]
theorem coe_int_ofDigits (b : ℕ) (L : List ℕ) : ((ofDigits b L : ℕ) : ℤ) = ofDigits (b : ℤ) L :=
by
@@ -631,12 +613,6 @@ theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1
/-! ### Modular Arithmetic -/
-/- warning: nat.dvd_of_digits_sub_of_digits -> Nat.dvd_ofDigits_sub_ofDigits is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : CommRing.{u1} α] {a : α} {b : α} {k : α}, (Dvd.Dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (SubNegMonoid.toHasSub.{u1} α (AddGroup.toSubNegMonoid.{u1} α (AddGroupWithOne.toAddGroup.{u1} α (AddCommGroupWithOne.toAddGroupWithOne.{u1} α (Ring.toAddCommGroupWithOne.{u1} α (CommRing.toRing.{u1} α _inst_1))))))) a b)) -> (forall (L : List.{0} Nat), Dvd.Dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (SubNegMonoid.toHasSub.{u1} α (AddGroup.toSubNegMonoid.{u1} α (AddGroupWithOne.toAddGroup.{u1} α (AddCommGroupWithOne.toAddGroupWithOne.{u1} α (Ring.toAddCommGroupWithOne.{u1} α (CommRing.toRing.{u1} α _inst_1))))))) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) a L) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) b L)))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : CommRing.{u1} α] {a : α} {b : α} {k : α}, (Dvd.dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalCommSemiring.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalCommSemiring.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (Ring.toSub.{u1} α (CommRing.toRing.{u1} α _inst_1))) a b)) -> (forall (L : List.{0} Nat), Dvd.dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalCommSemiring.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalCommSemiring.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (Ring.toSub.{u1} α (CommRing.toRing.{u1} α _inst_1))) (Nat.ofDigits.{u1} α (CommSemiring.toSemiring.{u1} α (CommRing.toCommSemiring.{u1} α _inst_1)) a L) (Nat.ofDigits.{u1} α (CommSemiring.toSemiring.{u1} α (CommRing.toCommSemiring.{u1} α _inst_1)) b L)))
-Case conversion may be inaccurate. Consider using '#align nat.dvd_of_digits_sub_of_digits Nat.dvd_ofDigits_sub_ofDigitsₓ'. -/
-- This is really a theorem about polynomials.
theorem dvd_ofDigits_sub_ofDigits {α : Type _} [CommRing α] {a b k : α} (h : k ∣ a - b)
(L : List ℕ) : k ∣ ofDigits a L - ofDigits b L :=
@@ -672,12 +648,6 @@ theorem ofDigits_mod (b k : ℕ) (L : List ℕ) : ofDigits b L % k = ofDigits (b
#align nat.of_digits_mod Nat.ofDigits_mod
-/
-/- warning: nat.of_digits_zmodeq' -> Nat.ofDigits_zmodeq' is a dubious translation:
-lean 3 declaration is
- forall (b : Int) (b' : Int) (k : Nat), (Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k) b b') -> (forall (L : List.{0} Nat), Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k) (Nat.ofDigits.{0} Int Int.semiring b L) (Nat.ofDigits.{0} Int Int.semiring b' L))
-but is expected to have type
- forall (b : Int) (b' : Int) (k : Nat), (Int.ModEq (Nat.cast.{0} Int instNatCastInt k) b b') -> (forall (L : List.{0} Nat), Int.ModEq (Nat.cast.{0} Int instNatCastInt k) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.ofDigits.{0} Int Int.instSemiringInt b' L))
-Case conversion may be inaccurate. Consider using '#align nat.of_digits_zmodeq' Nat.ofDigits_zmodeq'ₓ'. -/
theorem ofDigits_zmodeq' (b b' : ℤ) (k : ℕ) (h : b ≡ b' [ZMOD k]) (L : List ℕ) :
ofDigits b L ≡ ofDigits b' L [ZMOD k] :=
by
@@ -689,22 +659,10 @@ theorem ofDigits_zmodeq' (b b' : ℤ) (k : ℕ) (h : b ≡ b' [ZMOD k]) (L : Lis
conv_rhs => rw [Int.add_emod, Int.mul_emod]
#align nat.of_digits_zmodeq' Nat.ofDigits_zmodeq'
-/- warning: nat.of_digits_zmodeq -> Nat.ofDigits_zmodeq is a dubious translation:
-lean 3 declaration is
- forall (b : Int) (k : Nat) (L : List.{0} Nat), Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k) (Nat.ofDigits.{0} Int Int.semiring b L) (Nat.ofDigits.{0} Int Int.semiring (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) b ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k)) L)
-but is expected to have type
- forall (b : Int) (k : Nat) (L : List.{0} Nat), Int.ModEq (Nat.cast.{0} Int instNatCastInt k) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.ofDigits.{0} Int Int.instSemiringInt (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) b (Nat.cast.{0} Int instNatCastInt k)) L)
-Case conversion may be inaccurate. Consider using '#align nat.of_digits_zmodeq Nat.ofDigits_zmodeqₓ'. -/
theorem ofDigits_zmodeq (b : ℤ) (k : ℕ) (L : List ℕ) : ofDigits b L ≡ ofDigits (b % k) L [ZMOD k] :=
ofDigits_zmodeq' b (b % k) k (b.mod_modEq ↑k).symm L
#align nat.of_digits_zmodeq Nat.ofDigits_zmodeq
-/- warning: nat.of_digits_zmod -> Nat.ofDigits_zmod is a dubious translation:
-lean 3 declaration is
- forall (b : Int) (k : Nat) (L : List.{0} Nat), Eq.{1} Int (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) (Nat.ofDigits.{0} Int Int.semiring b L) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k)) (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) (Nat.ofDigits.{0} Int Int.semiring (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) b ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k)) L) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k))
-but is expected to have type
- forall (b : Int) (k : Nat) (L : List.{0} Nat), Eq.{1} Int (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.cast.{0} Int instNatCastInt k)) (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) (Nat.ofDigits.{0} Int Int.instSemiringInt (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) b (Nat.cast.{0} Int instNatCastInt k)) L) (Nat.cast.{0} Int instNatCastInt k))
-Case conversion may be inaccurate. Consider using '#align nat.of_digits_zmod Nat.ofDigits_zmodₓ'. -/
theorem ofDigits_zmod (b : ℤ) (k : ℕ) (L : List ℕ) : ofDigits b L % k = ofDigits (b % k) L % k :=
ofDigits_zmodeq b k L
#align nat.of_digits_zmod Nat.ofDigits_zmod
@@ -734,12 +692,6 @@ theorem modEq_nine_digits_sum (n : ℕ) : n ≡ (digits 10 n).Sum [MOD 9] :=
#align nat.modeq_nine_digits_sum Nat.modEq_nine_digits_sum
-/
-/- warning: nat.zmodeq_of_digits_digits -> Nat.zmodeq_ofDigits_digits is a dubious translation:
-lean 3 declaration is
- forall (b : Nat) (b' : Nat) (c : Int), (Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b') c) -> (forall (n : Nat), Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (Nat.ofDigits.{0} Int Int.semiring c (Nat.digits b' n)))
-but is expected to have type
- forall (b : Nat) (b' : Nat) (c : Int), (Int.ModEq (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt b') c) -> (forall (n : Nat), Int.ModEq (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt n) (Nat.ofDigits.{0} Int Int.instSemiringInt c (Nat.digits b' n)))
-Case conversion may be inaccurate. Consider using '#align nat.zmodeq_of_digits_digits Nat.zmodeq_ofDigits_digitsₓ'. -/
theorem zmodeq_ofDigits_digits (b b' : ℕ) (c : ℤ) (h : b' ≡ c [ZMOD b]) (n : ℕ) :
n ≡ ofDigits c (digits b' n) [ZMOD b] :=
by
@@ -751,12 +703,6 @@ theorem zmodeq_ofDigits_digits (b b' : ℕ) (c : ℤ) (h : b' ≡ c [ZMOD b]) (n
apply of_digits_zmodeq' _ _ _ h
#align nat.zmodeq_of_digits_digits Nat.zmodeq_ofDigits_digits
-/- warning: nat.of_digits_neg_one -> Nat.ofDigits_neg_one is a dubious translation:
-lean 3 declaration is
- forall (L : List.{0} Nat), Eq.{1} Int (Nat.ofDigits.{0} Int Int.semiring (Neg.neg.{0} Int Int.hasNeg (OfNat.ofNat.{0} Int 1 (OfNat.mk.{0} Int 1 (One.one.{0} Int Int.hasOne)))) L) (List.alternatingSum.{0} Int Int.hasZero Int.hasAdd Int.hasNeg (List.map.{0, 0} Nat Int (fun (n : Nat) => (fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) L))
-but is expected to have type
- forall (L : List.{0} Nat), Eq.{1} Int (Nat.ofDigits.{0} Int Int.instSemiringInt (Neg.neg.{0} Int Int.instNegInt (OfNat.ofNat.{0} Int 1 (instOfNatInt 1))) L) (List.alternatingSum.{0} Int (CommMonoidWithZero.toZero.{0} Int (CancelCommMonoidWithZero.toCommMonoidWithZero.{0} Int (IsDomain.toCancelCommMonoidWithZero.{0} Int Int.instCommSemiringInt (LinearOrderedRing.isDomain.{0} Int (LinearOrderedCommRing.toLinearOrderedRing.{0} Int Int.linearOrderedCommRing))))) Int.instAddInt Int.instNegInt (List.map.{0, 0} Nat Int (fun (n : Nat) => Nat.cast.{0} Int instNatCastInt n) L))
-Case conversion may be inaccurate. Consider using '#align nat.of_digits_neg_one Nat.ofDigits_neg_oneₓ'. -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
theorem ofDigits_neg_one :
@@ -803,12 +749,6 @@ theorem nine_dvd_iff (n : ℕ) : 9 ∣ n ↔ 9 ∣ (digits 10 n).Sum :=
#align nat.nine_dvd_iff Nat.nine_dvd_iff
-/
-/- warning: nat.dvd_iff_dvd_of_digits -> Nat.dvd_iff_dvd_ofDigits is a dubious translation:
-lean 3 declaration is
- forall (b : Nat) (b' : Nat) (c : Int), (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b') c)) -> (forall (n : Nat), Iff (Dvd.Dvd.{0} Nat Nat.hasDvd b n) (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) (Nat.ofDigits.{0} Int Int.semiring c (Nat.digits b' n))))
-but is expected to have type
- forall (b : Nat) (b' : Nat) (c : Int), (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt b) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int instNatCastInt b') c)) -> (forall (n : Nat), Iff (Dvd.dvd.{0} Nat Nat.instDvdNat b n) (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt b) (Nat.ofDigits.{0} Int Int.instSemiringInt c (Nat.digits b' n))))
-Case conversion may be inaccurate. Consider using '#align nat.dvd_iff_dvd_of_digits Nat.dvd_iff_dvd_ofDigitsₓ'. -/
theorem dvd_iff_dvd_ofDigits (b b' : ℕ) (c : ℤ) (h : (b : ℤ) ∣ (b' : ℤ) - c) (n : ℕ) :
b ∣ n ↔ (b : ℤ) ∣ ofDigits c (digits b' n) :=
by
@@ -817,12 +757,6 @@ theorem dvd_iff_dvd_ofDigits (b b' : ℕ) (c : ℤ) (h : (b : ℤ) ∣ (b' : ℤ
dvd_iff_dvd_of_dvd_sub (zmodeq_of_digits_digits b b' c (Int.modEq_iff_dvd.2 h).symm _).symm.Dvd
#align nat.dvd_iff_dvd_of_digits Nat.dvd_iff_dvd_ofDigits
-/- warning: nat.eleven_dvd_iff -> Nat.eleven_dvd_iff is a dubious translation:
-lean 3 declaration is
- forall {n : Nat}, Iff (Dvd.Dvd.{0} Nat Nat.hasDvd (OfNat.ofNat.{0} Nat 11 (OfNat.mk.{0} Nat 11 (bit1.{0} Nat Nat.hasOne Nat.hasAdd (bit1.{0} Nat Nat.hasOne Nat.hasAdd (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) n) (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) (OfNat.ofNat.{0} Int 11 (OfNat.mk.{0} Int 11 (bit1.{0} Int Int.hasOne Int.hasAdd (bit1.{0} Int Int.hasOne Int.hasAdd (bit0.{0} Int Int.hasAdd (One.one.{0} Int Int.hasOne)))))) (List.alternatingSum.{0} Int Int.hasZero Int.hasAdd Int.hasNeg (List.map.{0, 0} Nat Int (fun (n : Nat) => (fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (Nat.digits (OfNat.ofNat.{0} Nat 10 (OfNat.mk.{0} Nat 10 (bit0.{0} Nat Nat.hasAdd (bit1.{0} Nat Nat.hasOne Nat.hasAdd (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) n))))
-but is expected to have type
- forall {n : Nat}, Iff (Dvd.dvd.{0} Nat Nat.instDvdNat (OfNat.ofNat.{0} Nat 11 (instOfNatNat 11)) n) (Dvd.dvd.{0} Int Int.instDvdInt (OfNat.ofNat.{0} Int 11 (instOfNatInt 11)) (List.alternatingSum.{0} Int (CommMonoidWithZero.toZero.{0} Int (CancelCommMonoidWithZero.toCommMonoidWithZero.{0} Int (IsDomain.toCancelCommMonoidWithZero.{0} Int Int.instCommSemiringInt (LinearOrderedRing.isDomain.{0} Int (LinearOrderedCommRing.toLinearOrderedRing.{0} Int Int.linearOrderedCommRing))))) Int.instAddInt Int.instNegInt (List.map.{0, 0} Nat Int (fun (n : Nat) => Nat.cast.{0} Int instNatCastInt n) (Nat.digits (OfNat.ofNat.{0} Nat 10 (instOfNatNat 10)) n))))
-Case conversion may be inaccurate. Consider using '#align nat.eleven_dvd_iff Nat.eleven_dvd_iffₓ'. -/
theorem eleven_dvd_iff :
11 ∣ n ↔ (11 : ℤ) ∣ ((digits 10 n).map fun n : ℕ => (n : ℤ)).alternatingSum :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -149,10 +149,8 @@ theorem digits_one_succ (n : ℕ) : digits 1 (n + 1) = 1::digits 1 n :=
#print Nat.digits_add_two_add_one /-
@[simp]
theorem digits_add_two_add_one (b n : ℕ) :
- digits (b + 2) (n + 1) = ((n + 1) % (b + 2))::digits (b + 2) ((n + 1) / (b + 2)) :=
- by
- rw [digits, digits_aux_def]
- exact succ_pos n
+ digits (b + 2) (n + 1) = ((n + 1) % (b + 2))::digits (b + 2) ((n + 1) / (b + 2)) := by
+ rw [digits, digits_aux_def]; exact succ_pos n
#align nat.digits_add_two_add_one Nat.digits_add_two_add_one
-/
@@ -218,8 +216,7 @@ theorem ofDigits_eq_foldr {α : Type _} [Semiring α] (b : α) (L : List ℕ) :
by
induction' L with d L ih
· rfl
- · dsimp [of_digits]
- rw [ih]
+ · dsimp [of_digits]; rw [ih]
#align nat.of_digits_eq_foldr Nat.ofDigits_eq_foldr
#print Nat.ofDigits_eq_sum_map_with_index_aux /-
@@ -288,9 +285,7 @@ theorem coe_ofDigits (α : Type _) [Semiring α] (b : ℕ) (L : List ℕ) :
by
induction' L with d L ih
· simp [of_digits]
- · dsimp [of_digits]
- push_cast
- rw [ih]
+ · dsimp [of_digits]; push_cast ; rw [ih]
#align nat.coe_of_digits Nat.coe_ofDigits
-/
@@ -305,8 +300,7 @@ theorem coe_int_ofDigits (b : ℕ) (L : List ℕ) : ((ofDigits b L : ℕ) : ℤ)
by
induction' L with d L ih
· rfl
- · dsimp [of_digits]
- push_cast
+ · dsimp [of_digits]; push_cast
#align nat.coe_int_of_digits Nat.coe_int_ofDigits
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
@@ -325,15 +319,12 @@ theorem digits_ofDigits (b : ℕ) (h : 1 < b) (L : List ℕ) (w₁ : ∀ l ∈ L
(w₂ : ∀ h : L ≠ [], L.getLast h ≠ 0) : digits b (ofDigits b L) = L :=
by
induction' L with d L ih
- · dsimp [of_digits]
- simp
+ · dsimp [of_digits]; simp
· dsimp [of_digits]
replace w₂ := w₂ (by simp)
rw [digits_add b h]
· rw [ih]
- · intro l m
- apply w₁
- exact List.mem_cons_of_mem _ m
+ · intro l m; apply w₁; exact List.mem_cons_of_mem _ m
· intro h
· rw [List.getLast_cons h] at w₂
convert w₂
@@ -363,12 +354,10 @@ theorem ofDigits_digits (b n : ℕ) : ofDigits b (digits b n) = n :=
· induction' n with n ih
· rfl
· simp only [ih, add_comm 1, of_digits_one_cons, Nat.cast_id, digits_one_succ]
- · apply Nat.strong_induction_on n _
- clear n
+ · apply Nat.strong_induction_on n _; clear n
intro n h
cases n
- · rw [digits_zero]
- rfl
+ · rw [digits_zero]; rfl
· simp only [Nat.succ_eq_add_one, digits_add_two_add_one]
dsimp [of_digits]
rw [h _ (Nat.div_lt_self' n b)]
@@ -474,8 +463,7 @@ theorem getLast_digit_ne_zero (b : ℕ) {m : ℕ} (hm : m ≠ 0) :
· cases m
· cases hm rfl
· simp
- · cases m
- · cases hm rfl
+ · cases m; · cases hm rfl
simpa only [digits_one, List.getLast_replicate_succ m 1] using one_ne_zero
revert hm
apply Nat.strong_induction_on m
@@ -496,13 +484,11 @@ theorem digits_lt_base' {b m : ℕ} : ∀ {d}, d ∈ digits (b + 2) m → d < b
apply Nat.strong_induction_on m
intro n IH d hd
cases' n with n
- · rw [digits_zero] at hd
- cases hd
+ · rw [digits_zero] at hd; cases hd
-- base b+2 expansion of 0 has no digits
rw [digits_add_two_add_one] at hd
cases hd
- · rw [hd]
- exact n.succ.mod_lt (by linarith)
+ · rw [hd]; exact n.succ.mod_lt (by linarith)
· exact IH _ (Nat.div_lt_self (Nat.succ_pos _) (by linarith)) hd
#align nat.digits_lt_base' Nat.digits_lt_base'
-/
@@ -595,8 +581,7 @@ theorem pow_length_le_mul_ofDigits {b : ℕ} {l : List ℕ} (hl : l ≠ []) (hl2
apply Nat.mul_le_mul_left
refine' le_trans _ (Nat.le_add_left _ _)
have : 0 < l.last hl := by rwa [pos_iff_ne_zero]
- convert Nat.mul_le_mul_left _ this
- rw [mul_one]
+ convert Nat.mul_le_mul_left _ this; rw [mul_one]
#align nat.pow_length_le_mul_of_digits Nat.pow_length_le_mul_ofDigits
-/
@@ -657,8 +642,7 @@ theorem dvd_ofDigits_sub_ofDigits {α : Type _} [CommRing α] {a b k : α} (h :
(L : List ℕ) : k ∣ ofDigits a L - ofDigits b L :=
by
induction' L with d L ih
- · change k ∣ 0 - 0
- simp
+ · change k ∣ 0 - 0; simp
· simp only [of_digits, add_sub_add_left_eq_sub]
exact dvd_mul_sub_mul h ih
#align nat.dvd_of_digits_sub_of_digits Nat.dvd_ofDigits_sub_ofDigits
mathlib commit https://github.com/leanprover-community/mathlib/commit/08e1d8d4d989df3a6df86f385e9053ec8a372cc1
@@ -650,7 +650,7 @@ theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1
lean 3 declaration is
forall {α : Type.{u1}} [_inst_1 : CommRing.{u1} α] {a : α} {b : α} {k : α}, (Dvd.Dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (SubNegMonoid.toHasSub.{u1} α (AddGroup.toSubNegMonoid.{u1} α (AddGroupWithOne.toAddGroup.{u1} α (AddCommGroupWithOne.toAddGroupWithOne.{u1} α (Ring.toAddCommGroupWithOne.{u1} α (CommRing.toRing.{u1} α _inst_1))))))) a b)) -> (forall (L : List.{0} Nat), Dvd.Dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (SubNegMonoid.toHasSub.{u1} α (AddGroup.toSubNegMonoid.{u1} α (AddGroupWithOne.toAddGroup.{u1} α (AddCommGroupWithOne.toAddGroupWithOne.{u1} α (Ring.toAddCommGroupWithOne.{u1} α (CommRing.toRing.{u1} α _inst_1))))))) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) a L) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) b L)))
but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : CommRing.{u1} α] {a : α} {b : α} {k : α}, (Dvd.dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (Ring.toSub.{u1} α (CommRing.toRing.{u1} α _inst_1))) a b)) -> (forall (L : List.{0} Nat), Dvd.dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (Ring.toSub.{u1} α (CommRing.toRing.{u1} α _inst_1))) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) a L) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) b L)))
+ forall {α : Type.{u1}} [_inst_1 : CommRing.{u1} α] {a : α} {b : α} {k : α}, (Dvd.dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalCommSemiring.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalCommSemiring.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (Ring.toSub.{u1} α (CommRing.toRing.{u1} α _inst_1))) a b)) -> (forall (L : List.{0} Nat), Dvd.dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalCommSemiring.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalCommSemiring.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (Ring.toSub.{u1} α (CommRing.toRing.{u1} α _inst_1))) (Nat.ofDigits.{u1} α (CommSemiring.toSemiring.{u1} α (CommRing.toCommSemiring.{u1} α _inst_1)) a L) (Nat.ofDigits.{u1} α (CommSemiring.toSemiring.{u1} α (CommRing.toCommSemiring.{u1} α _inst_1)) b L)))
Case conversion may be inaccurate. Consider using '#align nat.dvd_of_digits_sub_of_digits Nat.dvd_ofDigits_sub_ofDigitsₓ'. -/
-- This is really a theorem about polynomials.
theorem dvd_ofDigits_sub_ofDigits {α : Type _} [CommRing α] {a b k : α} (h : k ∣ a - b)
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce86f4e05e9a9b8da5e316b22c76ce76440c56a1
@@ -648,7 +648,7 @@ theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1
/- warning: nat.dvd_of_digits_sub_of_digits -> Nat.dvd_ofDigits_sub_ofDigits is a dubious translation:
lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : CommRing.{u1} α] {a : α} {b : α} {k : α}, (Dvd.Dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (SubNegMonoid.toHasSub.{u1} α (AddGroup.toSubNegMonoid.{u1} α (AddGroupWithOne.toAddGroup.{u1} α (NonAssocRing.toAddGroupWithOne.{u1} α (Ring.toNonAssocRing.{u1} α (CommRing.toRing.{u1} α _inst_1))))))) a b)) -> (forall (L : List.{0} Nat), Dvd.Dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (SubNegMonoid.toHasSub.{u1} α (AddGroup.toSubNegMonoid.{u1} α (AddGroupWithOne.toAddGroup.{u1} α (NonAssocRing.toAddGroupWithOne.{u1} α (Ring.toNonAssocRing.{u1} α (CommRing.toRing.{u1} α _inst_1))))))) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) a L) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) b L)))
+ forall {α : Type.{u1}} [_inst_1 : CommRing.{u1} α] {a : α} {b : α} {k : α}, (Dvd.Dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (SubNegMonoid.toHasSub.{u1} α (AddGroup.toSubNegMonoid.{u1} α (AddGroupWithOne.toAddGroup.{u1} α (AddCommGroupWithOne.toAddGroupWithOne.{u1} α (Ring.toAddCommGroupWithOne.{u1} α (CommRing.toRing.{u1} α _inst_1))))))) a b)) -> (forall (L : List.{0} Nat), Dvd.Dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (SubNegMonoid.toHasSub.{u1} α (AddGroup.toSubNegMonoid.{u1} α (AddGroupWithOne.toAddGroup.{u1} α (AddCommGroupWithOne.toAddGroupWithOne.{u1} α (Ring.toAddCommGroupWithOne.{u1} α (CommRing.toRing.{u1} α _inst_1))))))) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) a L) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) b L)))
but is expected to have type
forall {α : Type.{u1}} [_inst_1 : CommRing.{u1} α] {a : α} {b : α} {k : α}, (Dvd.dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (Ring.toSub.{u1} α (CommRing.toRing.{u1} α _inst_1))) a b)) -> (forall (L : List.{0} Nat), Dvd.dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (Ring.toSub.{u1} α (CommRing.toRing.{u1} α _inst_1))) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) a L) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) b L)))
Case conversion may be inaccurate. Consider using '#align nat.dvd_of_digits_sub_of_digits Nat.dvd_ofDigits_sub_ofDigitsₓ'. -/
mathlib commit https://github.com/leanprover-community/mathlib/commit/da3fc4a33ff6bc75f077f691dc94c217b8d41559
@@ -298,7 +298,7 @@ theorem coe_ofDigits (α : Type _) [Semiring α] (b : ℕ) (L : List ℕ) :
lean 3 declaration is
forall (b : Nat) (L : List.{0} Nat), Eq.{1} Int ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) (Nat.ofDigits.{0} Nat Nat.semiring b L)) (Nat.ofDigits.{0} Int Int.semiring ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) L)
but is expected to have type
- forall (b : Nat) (L : List.{0} Nat), Eq.{1} Int (Nat.cast.{0} Int Int.instNatCastInt (Nat.ofDigits.{0} Nat Nat.semiring b L)) (Nat.ofDigits.{0} Int Int.instSemiringInt (Nat.cast.{0} Int Int.instNatCastInt b) L)
+ forall (b : Nat) (L : List.{0} Nat), Eq.{1} Int (Nat.cast.{0} Int instNatCastInt (Nat.ofDigits.{0} Nat Nat.semiring b L)) (Nat.ofDigits.{0} Int Int.instSemiringInt (Nat.cast.{0} Int instNatCastInt b) L)
Case conversion may be inaccurate. Consider using '#align nat.coe_int_of_digits Nat.coe_int_ofDigitsₓ'. -/
@[norm_cast]
theorem coe_int_ofDigits (b : ℕ) (L : List ℕ) : ((ofDigits b L : ℕ) : ℤ) = ofDigits (b : ℤ) L :=
@@ -692,7 +692,7 @@ theorem ofDigits_mod (b k : ℕ) (L : List ℕ) : ofDigits b L % k = ofDigits (b
lean 3 declaration is
forall (b : Int) (b' : Int) (k : Nat), (Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k) b b') -> (forall (L : List.{0} Nat), Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k) (Nat.ofDigits.{0} Int Int.semiring b L) (Nat.ofDigits.{0} Int Int.semiring b' L))
but is expected to have type
- forall (b : Int) (b' : Int) (k : Nat), (Int.ModEq (Nat.cast.{0} Int Int.instNatCastInt k) b b') -> (forall (L : List.{0} Nat), Int.ModEq (Nat.cast.{0} Int Int.instNatCastInt k) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.ofDigits.{0} Int Int.instSemiringInt b' L))
+ forall (b : Int) (b' : Int) (k : Nat), (Int.ModEq (Nat.cast.{0} Int instNatCastInt k) b b') -> (forall (L : List.{0} Nat), Int.ModEq (Nat.cast.{0} Int instNatCastInt k) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.ofDigits.{0} Int Int.instSemiringInt b' L))
Case conversion may be inaccurate. Consider using '#align nat.of_digits_zmodeq' Nat.ofDigits_zmodeq'ₓ'. -/
theorem ofDigits_zmodeq' (b b' : ℤ) (k : ℕ) (h : b ≡ b' [ZMOD k]) (L : List ℕ) :
ofDigits b L ≡ ofDigits b' L [ZMOD k] :=
@@ -709,7 +709,7 @@ theorem ofDigits_zmodeq' (b b' : ℤ) (k : ℕ) (h : b ≡ b' [ZMOD k]) (L : Lis
lean 3 declaration is
forall (b : Int) (k : Nat) (L : List.{0} Nat), Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k) (Nat.ofDigits.{0} Int Int.semiring b L) (Nat.ofDigits.{0} Int Int.semiring (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) b ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k)) L)
but is expected to have type
- forall (b : Int) (k : Nat) (L : List.{0} Nat), Int.ModEq (Nat.cast.{0} Int Int.instNatCastInt k) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.ofDigits.{0} Int Int.instSemiringInt (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) b (Nat.cast.{0} Int Int.instNatCastInt k)) L)
+ forall (b : Int) (k : Nat) (L : List.{0} Nat), Int.ModEq (Nat.cast.{0} Int instNatCastInt k) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.ofDigits.{0} Int Int.instSemiringInt (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) b (Nat.cast.{0} Int instNatCastInt k)) L)
Case conversion may be inaccurate. Consider using '#align nat.of_digits_zmodeq Nat.ofDigits_zmodeqₓ'. -/
theorem ofDigits_zmodeq (b : ℤ) (k : ℕ) (L : List ℕ) : ofDigits b L ≡ ofDigits (b % k) L [ZMOD k] :=
ofDigits_zmodeq' b (b % k) k (b.mod_modEq ↑k).symm L
@@ -719,7 +719,7 @@ theorem ofDigits_zmodeq (b : ℤ) (k : ℕ) (L : List ℕ) : ofDigits b L ≡ of
lean 3 declaration is
forall (b : Int) (k : Nat) (L : List.{0} Nat), Eq.{1} Int (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) (Nat.ofDigits.{0} Int Int.semiring b L) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k)) (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) (Nat.ofDigits.{0} Int Int.semiring (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) b ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k)) L) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k))
but is expected to have type
- forall (b : Int) (k : Nat) (L : List.{0} Nat), Eq.{1} Int (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.cast.{0} Int Int.instNatCastInt k)) (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) (Nat.ofDigits.{0} Int Int.instSemiringInt (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) b (Nat.cast.{0} Int Int.instNatCastInt k)) L) (Nat.cast.{0} Int Int.instNatCastInt k))
+ forall (b : Int) (k : Nat) (L : List.{0} Nat), Eq.{1} Int (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.cast.{0} Int instNatCastInt k)) (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) (Nat.ofDigits.{0} Int Int.instSemiringInt (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) b (Nat.cast.{0} Int instNatCastInt k)) L) (Nat.cast.{0} Int instNatCastInt k))
Case conversion may be inaccurate. Consider using '#align nat.of_digits_zmod Nat.ofDigits_zmodₓ'. -/
theorem ofDigits_zmod (b : ℤ) (k : ℕ) (L : List ℕ) : ofDigits b L % k = ofDigits (b % k) L % k :=
ofDigits_zmodeq b k L
@@ -754,7 +754,7 @@ theorem modEq_nine_digits_sum (n : ℕ) : n ≡ (digits 10 n).Sum [MOD 9] :=
lean 3 declaration is
forall (b : Nat) (b' : Nat) (c : Int), (Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b') c) -> (forall (n : Nat), Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (Nat.ofDigits.{0} Int Int.semiring c (Nat.digits b' n)))
but is expected to have type
- forall (b : Nat) (b' : Nat) (c : Int), (Int.ModEq (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.cast.{0} Int Int.instNatCastInt b') c) -> (forall (n : Nat), Int.ModEq (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.cast.{0} Int Int.instNatCastInt n) (Nat.ofDigits.{0} Int Int.instSemiringInt c (Nat.digits b' n)))
+ forall (b : Nat) (b' : Nat) (c : Int), (Int.ModEq (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt b') c) -> (forall (n : Nat), Int.ModEq (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt n) (Nat.ofDigits.{0} Int Int.instSemiringInt c (Nat.digits b' n)))
Case conversion may be inaccurate. Consider using '#align nat.zmodeq_of_digits_digits Nat.zmodeq_ofDigits_digitsₓ'. -/
theorem zmodeq_ofDigits_digits (b b' : ℕ) (c : ℤ) (h : b' ≡ c [ZMOD b]) (n : ℕ) :
n ≡ ofDigits c (digits b' n) [ZMOD b] :=
@@ -771,7 +771,7 @@ theorem zmodeq_ofDigits_digits (b b' : ℕ) (c : ℤ) (h : b' ≡ c [ZMOD b]) (n
lean 3 declaration is
forall (L : List.{0} Nat), Eq.{1} Int (Nat.ofDigits.{0} Int Int.semiring (Neg.neg.{0} Int Int.hasNeg (OfNat.ofNat.{0} Int 1 (OfNat.mk.{0} Int 1 (One.one.{0} Int Int.hasOne)))) L) (List.alternatingSum.{0} Int Int.hasZero Int.hasAdd Int.hasNeg (List.map.{0, 0} Nat Int (fun (n : Nat) => (fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) L))
but is expected to have type
- forall (L : List.{0} Nat), Eq.{1} Int (Nat.ofDigits.{0} Int Int.instSemiringInt (Neg.neg.{0} Int Int.instNegInt (OfNat.ofNat.{0} Int 1 (instOfNatInt 1))) L) (List.alternatingSum.{0} Int (CommMonoidWithZero.toZero.{0} Int (CancelCommMonoidWithZero.toCommMonoidWithZero.{0} Int (IsDomain.toCancelCommMonoidWithZero.{0} Int Int.instCommSemiringInt (LinearOrderedRing.isDomain.{0} Int (LinearOrderedCommRing.toLinearOrderedRing.{0} Int Int.linearOrderedCommRing))))) Int.instAddInt Int.instNegInt (List.map.{0, 0} Nat Int (fun (n : Nat) => Nat.cast.{0} Int Int.instNatCastInt n) L))
+ forall (L : List.{0} Nat), Eq.{1} Int (Nat.ofDigits.{0} Int Int.instSemiringInt (Neg.neg.{0} Int Int.instNegInt (OfNat.ofNat.{0} Int 1 (instOfNatInt 1))) L) (List.alternatingSum.{0} Int (CommMonoidWithZero.toZero.{0} Int (CancelCommMonoidWithZero.toCommMonoidWithZero.{0} Int (IsDomain.toCancelCommMonoidWithZero.{0} Int Int.instCommSemiringInt (LinearOrderedRing.isDomain.{0} Int (LinearOrderedCommRing.toLinearOrderedRing.{0} Int Int.linearOrderedCommRing))))) Int.instAddInt Int.instNegInt (List.map.{0, 0} Nat Int (fun (n : Nat) => Nat.cast.{0} Int instNatCastInt n) L))
Case conversion may be inaccurate. Consider using '#align nat.of_digits_neg_one Nat.ofDigits_neg_oneₓ'. -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
@@ -823,7 +823,7 @@ theorem nine_dvd_iff (n : ℕ) : 9 ∣ n ↔ 9 ∣ (digits 10 n).Sum :=
lean 3 declaration is
forall (b : Nat) (b' : Nat) (c : Int), (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b') c)) -> (forall (n : Nat), Iff (Dvd.Dvd.{0} Nat Nat.hasDvd b n) (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) (Nat.ofDigits.{0} Int Int.semiring c (Nat.digits b' n))))
but is expected to have type
- forall (b : Nat) (b' : Nat) (c : Int), (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int Int.instNatCastInt b) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int Int.instNatCastInt b') c)) -> (forall (n : Nat), Iff (Dvd.dvd.{0} Nat Nat.instDvdNat b n) (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.ofDigits.{0} Int Int.instSemiringInt c (Nat.digits b' n))))
+ forall (b : Nat) (b' : Nat) (c : Int), (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt b) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int instNatCastInt b') c)) -> (forall (n : Nat), Iff (Dvd.dvd.{0} Nat Nat.instDvdNat b n) (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt b) (Nat.ofDigits.{0} Int Int.instSemiringInt c (Nat.digits b' n))))
Case conversion may be inaccurate. Consider using '#align nat.dvd_iff_dvd_of_digits Nat.dvd_iff_dvd_ofDigitsₓ'. -/
theorem dvd_iff_dvd_ofDigits (b b' : ℕ) (c : ℤ) (h : (b : ℤ) ∣ (b' : ℤ) - c) (n : ℕ) :
b ∣ n ↔ (b : ℤ) ∣ ofDigits c (digits b' n) :=
@@ -837,7 +837,7 @@ theorem dvd_iff_dvd_ofDigits (b b' : ℕ) (c : ℤ) (h : (b : ℤ) ∣ (b' : ℤ
lean 3 declaration is
forall {n : Nat}, Iff (Dvd.Dvd.{0} Nat Nat.hasDvd (OfNat.ofNat.{0} Nat 11 (OfNat.mk.{0} Nat 11 (bit1.{0} Nat Nat.hasOne Nat.hasAdd (bit1.{0} Nat Nat.hasOne Nat.hasAdd (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) n) (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) (OfNat.ofNat.{0} Int 11 (OfNat.mk.{0} Int 11 (bit1.{0} Int Int.hasOne Int.hasAdd (bit1.{0} Int Int.hasOne Int.hasAdd (bit0.{0} Int Int.hasAdd (One.one.{0} Int Int.hasOne)))))) (List.alternatingSum.{0} Int Int.hasZero Int.hasAdd Int.hasNeg (List.map.{0, 0} Nat Int (fun (n : Nat) => (fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (Nat.digits (OfNat.ofNat.{0} Nat 10 (OfNat.mk.{0} Nat 10 (bit0.{0} Nat Nat.hasAdd (bit1.{0} Nat Nat.hasOne Nat.hasAdd (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) n))))
but is expected to have type
- forall {n : Nat}, Iff (Dvd.dvd.{0} Nat Nat.instDvdNat (OfNat.ofNat.{0} Nat 11 (instOfNatNat 11)) n) (Dvd.dvd.{0} Int Int.instDvdInt (OfNat.ofNat.{0} Int 11 (instOfNatInt 11)) (List.alternatingSum.{0} Int (CommMonoidWithZero.toZero.{0} Int (CancelCommMonoidWithZero.toCommMonoidWithZero.{0} Int (IsDomain.toCancelCommMonoidWithZero.{0} Int Int.instCommSemiringInt (LinearOrderedRing.isDomain.{0} Int (LinearOrderedCommRing.toLinearOrderedRing.{0} Int Int.linearOrderedCommRing))))) Int.instAddInt Int.instNegInt (List.map.{0, 0} Nat Int (fun (n : Nat) => Nat.cast.{0} Int Int.instNatCastInt n) (Nat.digits (OfNat.ofNat.{0} Nat 10 (instOfNatNat 10)) n))))
+ forall {n : Nat}, Iff (Dvd.dvd.{0} Nat Nat.instDvdNat (OfNat.ofNat.{0} Nat 11 (instOfNatNat 11)) n) (Dvd.dvd.{0} Int Int.instDvdInt (OfNat.ofNat.{0} Int 11 (instOfNatInt 11)) (List.alternatingSum.{0} Int (CommMonoidWithZero.toZero.{0} Int (CancelCommMonoidWithZero.toCommMonoidWithZero.{0} Int (IsDomain.toCancelCommMonoidWithZero.{0} Int Int.instCommSemiringInt (LinearOrderedRing.isDomain.{0} Int (LinearOrderedCommRing.toLinearOrderedRing.{0} Int Int.linearOrderedCommRing))))) Int.instAddInt Int.instNegInt (List.map.{0, 0} Nat Int (fun (n : Nat) => Nat.cast.{0} Int instNatCastInt n) (Nat.digits (OfNat.ofNat.{0} Nat 10 (instOfNatNat 10)) n))))
Case conversion may be inaccurate. Consider using '#align nat.eleven_dvd_iff Nat.eleven_dvd_iffₓ'. -/
theorem eleven_dvd_iff :
11 ∣ n ↔ (11 : ℤ) ∣ ((digits 10 n).map fun n : ℕ => (n : ℤ)).alternatingSum :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/21e3562c5e12d846c7def5eff8cdbc520d7d4936
@@ -663,8 +663,8 @@ theorem dvd_ofDigits_sub_ofDigits {α : Type _} [CommRing α] {a b k : α} (h :
exact dvd_mul_sub_mul h ih
#align nat.dvd_of_digits_sub_of_digits Nat.dvd_ofDigits_sub_ofDigits
-#print Nat.ofDigits_modeq' /-
-theorem ofDigits_modeq' (b b' : ℕ) (k : ℕ) (h : b ≡ b' [MOD k]) (L : List ℕ) :
+#print Nat.ofDigits_modEq' /-
+theorem ofDigits_modEq' (b b' : ℕ) (k : ℕ) (h : b ≡ b' [MOD k]) (L : List ℕ) :
ofDigits b L ≡ ofDigits b' L [MOD k] :=
by
induction' L with d L ih
@@ -673,12 +673,12 @@ theorem ofDigits_modeq' (b b' : ℕ) (k : ℕ) (h : b ≡ b' [MOD k]) (L : List
dsimp [Nat.ModEq] at *
conv_lhs => rw [Nat.add_mod, Nat.mul_mod, h, ih]
conv_rhs => rw [Nat.add_mod, Nat.mul_mod]
-#align nat.of_digits_modeq' Nat.ofDigits_modeq'
+#align nat.of_digits_modeq' Nat.ofDigits_modEq'
-/
#print Nat.ofDigits_modEq /-
theorem ofDigits_modEq (b k : ℕ) (L : List ℕ) : ofDigits b L ≡ ofDigits (b % k) L [MOD k] :=
- ofDigits_modeq' b (b % k) k (b.mod_modEq k).symm L
+ ofDigits_modEq' b (b % k) k (b.mod_modEq k).symm L
#align nat.of_digits_modeq Nat.ofDigits_modEq
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/62e8311c791f02c47451bf14aa2501048e7c2f33
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Scott Morrison, Shing Tak Lam, Mario Carneiro
! This file was ported from Lean 3 source module data.nat.digits
-! leanprover-community/mathlib commit 2609ad04e2b77aceb2200e273daf11cc65856fda
+! leanprover-community/mathlib commit 832f7b9162039c28b9361289c8681f155cae758f
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -20,6 +20,9 @@ import Mathbin.Tactic.Linarith.Default
/-!
# Digits of a natural number
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
This provides a basic API for extracting the digits of a natural number in a given base,
and reconstructing numbers from their digits.
mathlib commit https://github.com/leanprover-community/mathlib/commit/4c586d291f189eecb9d00581aeb3dd998ac34442
@@ -35,18 +35,23 @@ namespace Nat
variable {n : ℕ}
+#print Nat.digitsAux0 /-
/-- (Impl.) An auxiliary definition for `digits`, to help get the desired definitional unfolding. -/
def digitsAux0 : ℕ → List ℕ
| 0 => []
| n + 1 => [n + 1]
#align nat.digits_aux_0 Nat.digitsAux0
+-/
+#print Nat.digitsAux1 /-
/-- (Impl.) An auxiliary definition for `digits`, to help get the desired definitional unfolding. -/
def digitsAux1 (n : ℕ) : List ℕ :=
List.replicate n 1
#align nat.digits_aux_1 Nat.digitsAux1
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.digitsAux /-
/-- (Impl.) An auxiliary definition for `digits`, to help get the desired definitional unfolding. -/
def digitsAux (b : ℕ) (h : 2 ≤ b) : ℕ → List ℕ
| 0 => []
@@ -54,12 +59,16 @@ def digitsAux (b : ℕ) (h : 2 ≤ b) : ℕ → List ℕ
have : (n + 1) / b < n + 1 := Nat.div_lt_self (Nat.succ_pos _) h
((n + 1) % b)::digits_aux ((n + 1) / b)
#align nat.digits_aux Nat.digitsAux
+-/
+#print Nat.digitsAux_zero /-
@[simp]
theorem digitsAux_zero (b : ℕ) (h : 2 ≤ b) : digitsAux b h 0 = [] := by rw [digits_aux]
#align nat.digits_aux_zero Nat.digitsAux_zero
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.digitsAux_def /-
theorem digitsAux_def (b : ℕ) (h : 2 ≤ b) (n : ℕ) (w : 0 < n) :
digitsAux b h n = (n % b)::digitsAux b h (n / b) :=
by
@@ -67,7 +76,9 @@ theorem digitsAux_def (b : ℕ) (h : 2 ≤ b) (n : ℕ) (w : 0 < n) :
· cases w
· rw [digits_aux]
#align nat.digits_aux_def Nat.digitsAux_def
+-/
+#print Nat.digits /-
/-- `digits b n` gives the digits, in little-endian order,
of a natural number `n` in a specified base `b`.
@@ -86,39 +97,53 @@ def digits : ℕ → ℕ → List ℕ
| 1 => digitsAux1
| b + 2 => digitsAux (b + 2) (by norm_num)
#align nat.digits Nat.digits
+-/
+#print Nat.digits_zero /-
@[simp]
theorem digits_zero (b : ℕ) : digits b 0 = [] := by
rcases b with (_ | ⟨_ | ⟨_⟩⟩) <;> simp [digits, digits_aux_0, digits_aux_1]
#align nat.digits_zero Nat.digits_zero
+-/
+#print Nat.digits_zero_zero /-
@[simp]
theorem digits_zero_zero : digits 0 0 = [] :=
rfl
#align nat.digits_zero_zero Nat.digits_zero_zero
+-/
+#print Nat.digits_zero_succ /-
@[simp]
theorem digits_zero_succ (n : ℕ) : digits 0 n.succ = [n + 1] :=
rfl
#align nat.digits_zero_succ Nat.digits_zero_succ
+-/
+#print Nat.digits_zero_succ' /-
theorem digits_zero_succ' : ∀ {n : ℕ}, n ≠ 0 → digits 0 n = [n]
| 0, h => (h rfl).elim
| n + 1, _ => rfl
#align nat.digits_zero_succ' Nat.digits_zero_succ'
+-/
+#print Nat.digits_one /-
@[simp]
theorem digits_one (n : ℕ) : digits 1 n = List.replicate n 1 :=
rfl
#align nat.digits_one Nat.digits_one
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.digits_one_succ /-
@[simp]
theorem digits_one_succ (n : ℕ) : digits 1 (n + 1) = 1::digits 1 n :=
rfl
#align nat.digits_one_succ Nat.digits_one_succ
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.digits_add_two_add_one /-
@[simp]
theorem digits_add_two_add_one (b n : ℕ) :
digits (b + 2) (n + 1) = ((n + 1) % (b + 2))::digits (b + 2) ((n + 1) / (b + 2)) :=
@@ -126,15 +151,19 @@ theorem digits_add_two_add_one (b n : ℕ) :
rw [digits, digits_aux_def]
exact succ_pos n
#align nat.digits_add_two_add_one Nat.digits_add_two_add_one
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.digits_def' /-
theorem digits_def' :
∀ {b : ℕ} (h : 1 < b) {n : ℕ} (w : 0 < n), digits b n = (n % b)::digits b (n / b)
| 0, h => absurd h (by decide)
| 1, h => absurd h (by decide)
| b + 2, h => digitsAux_def _ _
#align nat.digits_def' Nat.digits_def'
+-/
+#print Nat.digits_of_lt /-
@[simp]
theorem digits_of_lt (b x : ℕ) (hx : x ≠ 0) (hxb : x < b) : digits b x = [x] :=
by
@@ -142,8 +171,10 @@ theorem digits_of_lt (b x : ℕ) (hx : x ≠ 0) (hxb : x < b) : digits b x = [x]
rcases exists_eq_add_of_le' ((Nat.le_add_left 1 x).trans_lt hxb) with ⟨b, rfl⟩
rw [digits_add_two_add_one, div_eq_of_lt hxb, digits_zero, mod_eq_of_lt hxb]
#align nat.digits_of_lt Nat.digits_of_lt
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.digits_add /-
theorem digits_add (b : ℕ) (h : 1 < b) (x y : ℕ) (hxb : x < b) (hxy : x ≠ 0 ∨ y ≠ 0) :
digits b (x + b * y) = x::digits b y :=
by
@@ -157,8 +188,10 @@ theorem digits_add (b : ℕ) (h : 1 < b) (x y : ℕ) (hxb : x < b) (hxy : x ≠
· simp [add_mul_div_left, div_eq_of_lt hxb]
· apply Nat.succ_pos
#align nat.digits_add Nat.digits_add
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.ofDigits /-
-- If we had a function converting a list into a polynomial,
-- and appropriate lemmas about that function,
-- we could rewrite this in terms of that.
@@ -169,7 +202,14 @@ def ofDigits {α : Type _} [Semiring α] (b : α) : List ℕ → α
| [] => 0
| h::t => h + b * of_digits t
#align nat.of_digits Nat.ofDigits
+-/
+/- warning: nat.of_digits_eq_foldr -> Nat.ofDigits_eq_foldr is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : Semiring.{u1} α] (b : α) (L : List.{0} Nat), Eq.{succ u1} α (Nat.ofDigits.{u1} α _inst_1 b L) (List.foldr.{0, u1} Nat α (fun (x : Nat) (y : α) => HAdd.hAdd.{u1, u1, u1} α α α (instHAdd.{u1} α (Distrib.toHasAdd.{u1} α (NonUnitalNonAssocSemiring.toDistrib.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))) ((fun (a : Type) (b : Type.{u1}) [self : HasLiftT.{1, succ u1} a b] => self.0) Nat α (HasLiftT.mk.{1, succ u1} Nat α (CoeTCₓ.coe.{1, succ u1} Nat α (Nat.castCoe.{u1} α (AddMonoidWithOne.toNatCast.{u1} α (AddCommMonoidWithOne.toAddMonoidWithOne.{u1} α (NonAssocSemiring.toAddCommMonoidWithOne.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))))) x) (HMul.hMul.{u1, u1, u1} α α α (instHMul.{u1} α (Distrib.toHasMul.{u1} α (NonUnitalNonAssocSemiring.toDistrib.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))) b y)) (OfNat.ofNat.{u1} α 0 (OfNat.mk.{u1} α 0 (Zero.zero.{u1} α (MulZeroClass.toHasZero.{u1} α (NonUnitalNonAssocSemiring.toMulZeroClass.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))))) L)
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : Semiring.{u1} α] (b : α) (L : List.{0} Nat), Eq.{succ u1} α (Nat.ofDigits.{u1} α _inst_1 b L) (List.foldr.{0, u1} Nat α (fun (x : Nat) (y : α) => HAdd.hAdd.{u1, u1, u1} α α α (instHAdd.{u1} α (Distrib.toAdd.{u1} α (NonUnitalNonAssocSemiring.toDistrib.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))) (Nat.cast.{u1} α (Semiring.toNatCast.{u1} α _inst_1) x) (HMul.hMul.{u1, u1, u1} α α α (instHMul.{u1} α (NonUnitalNonAssocSemiring.toMul.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1)))) b y)) (OfNat.ofNat.{u1} α 0 (Zero.toOfNat0.{u1} α (MonoidWithZero.toZero.{u1} α (Semiring.toMonoidWithZero.{u1} α _inst_1)))) L)
+Case conversion may be inaccurate. Consider using '#align nat.of_digits_eq_foldr Nat.ofDigits_eq_foldrₓ'. -/
theorem ofDigits_eq_foldr {α : Type _} [Semiring α] (b : α) (L : List ℕ) :
ofDigits b L = L.foldr (fun x y => x + b * y) 0 :=
by
@@ -179,7 +219,8 @@ theorem ofDigits_eq_foldr {α : Type _} [Semiring α] (b : α) (L : List ℕ) :
rw [ih]
#align nat.of_digits_eq_foldr Nat.ofDigits_eq_foldr
-theorem of_digits_eq_sum_map_with_index_aux (b : ℕ) (l : List ℕ) :
+#print Nat.ofDigits_eq_sum_map_with_index_aux /-
+theorem ofDigits_eq_sum_map_with_index_aux (b : ℕ) (l : List ℕ) :
((List.range l.length).zipWith ((fun i a : ℕ => a * b ^ i) ∘ succ) l).Sum =
b * ((List.range l.length).zipWith (fun i a => a * b ^ i) l).Sum :=
by
@@ -191,8 +232,10 @@ theorem of_digits_eq_sum_map_with_index_aux (b : ℕ) (l : List ℕ) :
ext
simp [pow_succ]
ring
-#align nat.of_digits_eq_sum_map_with_index_aux Nat.of_digits_eq_sum_map_with_index_aux
+#align nat.of_digits_eq_sum_map_with_index_aux Nat.ofDigits_eq_sum_map_with_index_aux
+-/
+#print Nat.ofDigits_eq_sum_mapIdx /-
theorem ofDigits_eq_sum_mapIdx (b : ℕ) (L : List ℕ) :
ofDigits b L = (L.mapIdx fun i a => a * b ^ i).Sum :=
by
@@ -204,17 +247,27 @@ theorem ofDigits_eq_sum_mapIdx (b : ℕ) (L : List ℕ) :
simpa [List.range_succ_eq_map, List.zipWith_map_left, of_digits_eq_sum_map_with_index_aux] using
Or.inl hl
#align nat.of_digits_eq_sum_map_with_index Nat.ofDigits_eq_sum_mapIdx
+-/
+#print Nat.ofDigits_singleton /-
@[simp]
theorem ofDigits_singleton {b n : ℕ} : ofDigits b [n] = n := by simp [of_digits]
#align nat.of_digits_singleton Nat.ofDigits_singleton
+-/
+/- warning: nat.of_digits_one_cons -> Nat.ofDigits_one_cons is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : Semiring.{u1} α] (h : Nat) (L : List.{0} Nat), Eq.{succ u1} α (Nat.ofDigits.{u1} α _inst_1 (OfNat.ofNat.{u1} α 1 (OfNat.mk.{u1} α 1 (One.one.{u1} α (AddMonoidWithOne.toOne.{u1} α (AddCommMonoidWithOne.toAddMonoidWithOne.{u1} α (NonAssocSemiring.toAddCommMonoidWithOne.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))))) (List.cons.{0} Nat h L)) (HAdd.hAdd.{u1, u1, u1} α α α (instHAdd.{u1} α (Distrib.toHasAdd.{u1} α (NonUnitalNonAssocSemiring.toDistrib.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))) ((fun (a : Type) (b : Type.{u1}) [self : HasLiftT.{1, succ u1} a b] => self.0) Nat α (HasLiftT.mk.{1, succ u1} Nat α (CoeTCₓ.coe.{1, succ u1} Nat α (Nat.castCoe.{u1} α (AddMonoidWithOne.toNatCast.{u1} α (AddCommMonoidWithOne.toAddMonoidWithOne.{u1} α (NonAssocSemiring.toAddCommMonoidWithOne.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))))) h) (Nat.ofDigits.{u1} α _inst_1 (OfNat.ofNat.{u1} α 1 (OfNat.mk.{u1} α 1 (One.one.{u1} α (AddMonoidWithOne.toOne.{u1} α (AddCommMonoidWithOne.toAddMonoidWithOne.{u1} α (NonAssocSemiring.toAddCommMonoidWithOne.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))))) L))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : Semiring.{u1} α] (h : Nat) (L : List.{0} Nat), Eq.{succ u1} α (Nat.ofDigits.{u1} α _inst_1 (OfNat.ofNat.{u1} α 1 (One.toOfNat1.{u1} α (Semiring.toOne.{u1} α _inst_1))) (List.cons.{0} Nat h L)) (HAdd.hAdd.{u1, u1, u1} α α α (instHAdd.{u1} α (Distrib.toAdd.{u1} α (NonUnitalNonAssocSemiring.toDistrib.{u1} α (NonAssocSemiring.toNonUnitalNonAssocSemiring.{u1} α (Semiring.toNonAssocSemiring.{u1} α _inst_1))))) (Nat.cast.{u1} α (Semiring.toNatCast.{u1} α _inst_1) h) (Nat.ofDigits.{u1} α _inst_1 (OfNat.ofNat.{u1} α 1 (One.toOfNat1.{u1} α (Semiring.toOne.{u1} α _inst_1))) L))
+Case conversion may be inaccurate. Consider using '#align nat.of_digits_one_cons Nat.ofDigits_one_consₓ'. -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
@[simp]
theorem ofDigits_one_cons {α : Type _} [Semiring α] (h : ℕ) (L : List ℕ) :
ofDigits (1 : α) (h::L) = h + ofDigits 1 L := by simp [of_digits]
#align nat.of_digits_one_cons Nat.ofDigits_one_cons
+#print Nat.ofDigits_append /-
theorem ofDigits_append {b : ℕ} {l1 l2 : List ℕ} :
ofDigits b (l1 ++ l2) = ofDigits b l1 + b ^ l1.length * ofDigits b l2 :=
by
@@ -223,7 +276,9 @@ theorem ofDigits_append {b : ℕ} {l1 l2 : List ℕ} :
· rw [of_digits, List.cons_append, of_digits, IH, List.length_cons, pow_succ']
ring
#align nat.of_digits_append Nat.ofDigits_append
+-/
+#print Nat.coe_ofDigits /-
@[norm_cast]
theorem coe_ofDigits (α : Type _) [Semiring α] (b : ℕ) (L : List ℕ) :
((ofDigits b L : ℕ) : α) = ofDigits (b : α) L :=
@@ -234,7 +289,14 @@ theorem coe_ofDigits (α : Type _) [Semiring α] (b : ℕ) (L : List ℕ) :
push_cast
rw [ih]
#align nat.coe_of_digits Nat.coe_ofDigits
+-/
+/- warning: nat.coe_int_of_digits -> Nat.coe_int_ofDigits is a dubious translation:
+lean 3 declaration is
+ forall (b : Nat) (L : List.{0} Nat), Eq.{1} Int ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) (Nat.ofDigits.{0} Nat Nat.semiring b L)) (Nat.ofDigits.{0} Int Int.semiring ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) L)
+but is expected to have type
+ forall (b : Nat) (L : List.{0} Nat), Eq.{1} Int (Nat.cast.{0} Int Int.instNatCastInt (Nat.ofDigits.{0} Nat Nat.semiring b L)) (Nat.ofDigits.{0} Int Int.instSemiringInt (Nat.cast.{0} Int Int.instNatCastInt b) L)
+Case conversion may be inaccurate. Consider using '#align nat.coe_int_of_digits Nat.coe_int_ofDigitsₓ'. -/
@[norm_cast]
theorem coe_int_ofDigits (b : ℕ) (L : List ℕ) : ((ofDigits b L : ℕ) : ℤ) = ofDigits (b : ℤ) L :=
by
@@ -246,13 +308,16 @@ theorem coe_int_ofDigits (b : ℕ) (L : List ℕ) : ((ofDigits b L : ℕ) : ℤ)
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.digits_zero_of_eq_zero /-
theorem digits_zero_of_eq_zero {b : ℕ} (h : b ≠ 0) :
∀ {L : List ℕ} (h0 : ofDigits b L = 0), ∀ l ∈ L, l = 0
| a::L, h0, l, Or.inl rfl => Nat.eq_zero_of_add_eq_zero_right h0
| a::L, h0, l, Or.inr hL =>
digits_zero_of_eq_zero (mul_right_injective₀ h (Nat.eq_zero_of_add_eq_zero_left h0)) _ hL
#align nat.digits_zero_of_eq_zero Nat.digits_zero_of_eq_zero
+-/
+#print Nat.digits_ofDigits /-
theorem digits_ofDigits (b : ℕ) (h : 1 < b) (L : List ℕ) (w₁ : ∀ l ∈ L, l < b)
(w₂ : ∀ h : L ≠ [], L.getLast h ≠ 0) : digits b (ofDigits b L) = L :=
by
@@ -280,7 +345,9 @@ theorem digits_ofDigits (b : ℕ) (h : 1 < b) (L : List ℕ) (w₁ : ∀ l ∈ L
rw [List.getLast_cons h']
exact List.getLast_mem h'
#align nat.digits_of_digits Nat.digits_ofDigits
+-/
+#print Nat.ofDigits_digits /-
theorem ofDigits_digits (b n : ℕ) : ofDigits b (digits b n) = n :=
by
cases' b with b
@@ -304,13 +371,16 @@ theorem ofDigits_digits (b n : ℕ) : ofDigits b (digits b n) = n :=
rw [h _ (Nat.div_lt_self' n b)]
rw [Nat.mod_add_div]
#align nat.of_digits_digits Nat.ofDigits_digits
+-/
+#print Nat.ofDigits_one /-
theorem ofDigits_one (L : List ℕ) : ofDigits 1 L = L.Sum :=
by
induction' L with d L ih
· rfl
· simp [of_digits, List.sum_cons, ih]
#align nat.of_digits_one Nat.ofDigits_one
+-/
/-!
### Properties
@@ -319,6 +389,7 @@ This section contains various lemmas of properties relating to `digits` and `of_
-/
+#print Nat.digits_eq_nil_iff_eq_zero /-
theorem digits_eq_nil_iff_eq_zero {b n : ℕ} : digits b n = [] ↔ n = 0 :=
by
constructor
@@ -329,12 +400,16 @@ theorem digits_eq_nil_iff_eq_zero {b n : ℕ} : digits b n = [] ↔ n = 0 :=
· rintro rfl
simp
#align nat.digits_eq_nil_iff_eq_zero Nat.digits_eq_nil_iff_eq_zero
+-/
+#print Nat.digits_ne_nil_iff_ne_zero /-
theorem digits_ne_nil_iff_ne_zero {b n : ℕ} : digits b n ≠ [] ↔ n ≠ 0 :=
not_congr digits_eq_nil_iff_eq_zero
#align nat.digits_ne_nil_iff_ne_zero Nat.digits_ne_nil_iff_ne_zero
+-/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.digits_eq_cons_digits_div /-
theorem digits_eq_cons_digits_div {b n : ℕ} (h : 1 < b) (w : n ≠ 0) :
digits b n = (n % b)::digits b (n / b) :=
by
@@ -345,7 +420,9 @@ theorem digits_eq_cons_digits_div {b n : ℕ} (h : 1 < b) (w : n ≠ 0) :
· norm_num at w
simp
#align nat.digits_eq_cons_digits_div Nat.digits_eq_cons_digits_div
+-/
+#print Nat.digits_getLast /-
theorem digits_getLast {b : ℕ} (m : ℕ) (h : 1 < b) (p q) :
(digits b m).getLast p = (digits b (m / b)).getLast q :=
by
@@ -354,16 +431,22 @@ theorem digits_getLast {b : ℕ} (m : ℕ) (h : 1 < b) (p q) :
simp only [digits_eq_cons_digits_div h hm]
rw [List.getLast_cons]
#align nat.digits_last Nat.digits_getLast
+-/
+#print Nat.digits.injective /-
theorem digits.injective (b : ℕ) : Function.Injective b.digits :=
Function.LeftInverse.injective (ofDigits_digits b)
#align nat.digits.injective Nat.digits.injective
+-/
+#print Nat.digits_inj_iff /-
@[simp]
theorem digits_inj_iff {b n m : ℕ} : b.digits n = b.digits m ↔ n = m :=
(digits.injective b).eq_iff
#align nat.digits_inj_iff Nat.digits_inj_iff
+-/
+#print Nat.digits_len /-
theorem digits_len (b n : ℕ) (hb : 1 < b) (hn : n ≠ 0) : (b.digits n).length = b.log n + 1 :=
by
induction' n using Nat.strong_induction_on with n IH
@@ -378,7 +461,9 @@ theorem digits_len (b n : ℕ) (hb : 1 < b) (hn : n ≠ 0) : (b.digits n).length
contrapose! h
exact div_eq_of_lt h
#align nat.digits_len Nat.digits_len
+-/
+#print Nat.getLast_digit_ne_zero /-
theorem getLast_digit_ne_zero (b : ℕ) {m : ℕ} (hm : m ≠ 0) :
(digits b m).getLast (digits_ne_nil_iff_ne_zero.mpr hm) ≠ 0 :=
by
@@ -399,7 +484,9 @@ theorem getLast_digit_ne_zero (b : ℕ) {m : ℕ} (hm : m ≠ 0) :
· rw [← pos_iff_ne_zero]
exact Nat.div_pos (le_of_not_lt hnb) (by decide)
#align nat.last_digit_ne_zero Nat.getLast_digit_ne_zero
+-/
+#print Nat.digits_lt_base' /-
/-- The digits in the base b+2 expansion of n are all less than b+2 -/
theorem digits_lt_base' {b m : ℕ} : ∀ {d}, d ∈ digits (b + 2) m → d < b + 2 :=
by
@@ -415,14 +502,18 @@ theorem digits_lt_base' {b m : ℕ} : ∀ {d}, d ∈ digits (b + 2) m → d < b
exact n.succ.mod_lt (by linarith)
· exact IH _ (Nat.div_lt_self (Nat.succ_pos _) (by linarith)) hd
#align nat.digits_lt_base' Nat.digits_lt_base'
+-/
+#print Nat.digits_lt_base /-
/-- The digits in the base b expansion of n are all less than b, if b ≥ 2 -/
theorem digits_lt_base {b m d : ℕ} (hb : 1 < b) (hd : d ∈ digits b m) : d < b :=
by
rcases b with (_ | _ | b) <;> try linarith
exact digits_lt_base' hd
#align nat.digits_lt_base Nat.digits_lt_base
+-/
+#print Nat.ofDigits_lt_base_pow_length' /-
/-- an n-digit number in base b + 2 is less than (b + 2)^n -/
theorem ofDigits_lt_base_pow_length' {b : ℕ} {l : List ℕ} (hl : ∀ x ∈ l, x < b + 2) :
ofDigits (b + 2) l < (b + 2) ^ l.length :=
@@ -437,7 +528,9 @@ theorem ofDigits_lt_base_pow_length' {b : ℕ} {l : List ℕ} (hl : ∀ x ∈ l,
norm_cast
exact hl hd (List.mem_cons_self _ _)
#align nat.of_digits_lt_base_pow_length' Nat.ofDigits_lt_base_pow_length'
+-/
+#print Nat.ofDigits_lt_base_pow_length /-
/-- an n-digit number in base b is less than b^n if b > 1 -/
theorem ofDigits_lt_base_pow_length {b : ℕ} {l : List ℕ} (hb : 1 < b) (hl : ∀ x ∈ l, x < b) :
ofDigits b l < b ^ l.length :=
@@ -445,26 +538,34 @@ theorem ofDigits_lt_base_pow_length {b : ℕ} {l : List ℕ} (hb : 1 < b) (hl :
rcases b with (_ | _ | b) <;> try linarith
exact of_digits_lt_base_pow_length' hl
#align nat.of_digits_lt_base_pow_length Nat.ofDigits_lt_base_pow_length
+-/
+#print Nat.lt_base_pow_length_digits' /-
/-- Any number m is less than (b+2)^(number of digits in the base b + 2 representation of m) -/
theorem lt_base_pow_length_digits' {b m : ℕ} : m < (b + 2) ^ (digits (b + 2) m).length :=
by
convert of_digits_lt_base_pow_length' fun _ => digits_lt_base'
rw [of_digits_digits (b + 2) m]
#align nat.lt_base_pow_length_digits' Nat.lt_base_pow_length_digits'
+-/
+#print Nat.lt_base_pow_length_digits /-
/-- Any number m is less than b^(number of digits in the base b representation of m) -/
theorem lt_base_pow_length_digits {b m : ℕ} (hb : 1 < b) : m < b ^ (digits b m).length :=
by
rcases b with (_ | _ | b) <;> try linarith
exact lt_base_pow_length_digits'
#align nat.lt_base_pow_length_digits Nat.lt_base_pow_length_digits
+-/
+#print Nat.ofDigits_digits_append_digits /-
theorem ofDigits_digits_append_digits {b m n : ℕ} :
ofDigits b (digits b n ++ digits b m) = n + b ^ (digits b n).length * m := by
rw [of_digits_append, of_digits_digits, of_digits_digits]
#align nat.of_digits_digits_append_digits Nat.ofDigits_digits_append_digits
+-/
+#print Nat.digits_len_le_digits_len_succ /-
theorem digits_len_le_digits_len_succ (b n : ℕ) : (digits b n).length ≤ (digits b (n + 1)).length :=
by
rcases Decidable.eq_or_ne n 0 with (rfl | hn)
@@ -473,11 +574,15 @@ theorem digits_len_le_digits_len_succ (b n : ℕ) : (digits b n).length ≤ (dig
· interval_cases <;> simp [digits_zero_succ', hn]
simpa [digits_len, hb, hn] using log_mono_right (le_succ _)
#align nat.digits_len_le_digits_len_succ Nat.digits_len_le_digits_len_succ
+-/
+#print Nat.le_digits_len_le /-
theorem le_digits_len_le (b n m : ℕ) (h : n ≤ m) : (digits b n).length ≤ (digits b m).length :=
monotone_nat_of_le_succ (digits_len_le_digits_len_succ b) h
#align nat.le_digits_len_le Nat.le_digits_len_le
+-/
+#print Nat.pow_length_le_mul_ofDigits /-
theorem pow_length_le_mul_ofDigits {b : ℕ} {l : List ℕ} (hl : l ≠ []) (hl2 : l.getLast hl ≠ 0) :
(b + 2) ^ l.length ≤ (b + 2) * ofDigits (b + 2) l :=
by
@@ -490,7 +595,9 @@ theorem pow_length_le_mul_ofDigits {b : ℕ} {l : List ℕ} (hl : l ≠ []) (hl2
convert Nat.mul_le_mul_left _ this
rw [mul_one]
#align nat.pow_length_le_mul_of_digits Nat.pow_length_le_mul_ofDigits
+-/
+#print Nat.base_pow_length_digits_le' /-
/-- Any non-zero natural number `m` is greater than
(b+2)^((number of digits in the base (b+2) representation of m) - 1)
-/
@@ -501,7 +608,9 @@ theorem base_pow_length_digits_le' (b m : ℕ) (hm : m ≠ 0) :
convert pow_length_le_mul_of_digits this (last_digit_ne_zero _ hm)
rwa [of_digits_digits]
#align nat.base_pow_length_digits_le' Nat.base_pow_length_digits_le'
+-/
+#print Nat.base_pow_length_digits_le /-
/-- Any non-zero natural number `m` is greater than
b^((number of digits in the base b representation of m) - 1)
-/
@@ -511,10 +620,12 @@ theorem base_pow_length_digits_le (b m : ℕ) (hb : 1 < b) :
rcases b with (_ | _ | b) <;> try linarith
exact base_pow_length_digits_le' b m
#align nat.base_pow_length_digits_le Nat.base_pow_length_digits_le
+-/
/-! ### Binary -/
+#print Nat.digits_two_eq_bits /-
theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1 0 :=
by
induction' n using Nat.binaryRecFromOne with b n h ih
@@ -527,10 +638,17 @@ theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1
· simpa [pos_iff_ne_zero, bit_eq_zero_iff]
· simpa [Nat.bit, Nat.bit1_val n, add_comm, digits_add 2 one_lt_two 1 n]
#align nat.digits_two_eq_bits Nat.digits_two_eq_bits
+-/
/-! ### Modular Arithmetic -/
+/- warning: nat.dvd_of_digits_sub_of_digits -> Nat.dvd_ofDigits_sub_ofDigits is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : CommRing.{u1} α] {a : α} {b : α} {k : α}, (Dvd.Dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (SubNegMonoid.toHasSub.{u1} α (AddGroup.toSubNegMonoid.{u1} α (AddGroupWithOne.toAddGroup.{u1} α (NonAssocRing.toAddGroupWithOne.{u1} α (Ring.toNonAssocRing.{u1} α (CommRing.toRing.{u1} α _inst_1))))))) a b)) -> (forall (L : List.{0} Nat), Dvd.Dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (SubNegMonoid.toHasSub.{u1} α (AddGroup.toSubNegMonoid.{u1} α (AddGroupWithOne.toAddGroup.{u1} α (NonAssocRing.toAddGroupWithOne.{u1} α (Ring.toNonAssocRing.{u1} α (CommRing.toRing.{u1} α _inst_1))))))) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) a L) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) b L)))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : CommRing.{u1} α] {a : α} {b : α} {k : α}, (Dvd.dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (Ring.toSub.{u1} α (CommRing.toRing.{u1} α _inst_1))) a b)) -> (forall (L : List.{0} Nat), Dvd.dvd.{u1} α (semigroupDvd.{u1} α (SemigroupWithZero.toSemigroup.{u1} α (NonUnitalSemiring.toSemigroupWithZero.{u1} α (NonUnitalRing.toNonUnitalSemiring.{u1} α (NonUnitalCommRing.toNonUnitalRing.{u1} α (CommRing.toNonUnitalCommRing.{u1} α _inst_1)))))) k (HSub.hSub.{u1, u1, u1} α α α (instHSub.{u1} α (Ring.toSub.{u1} α (CommRing.toRing.{u1} α _inst_1))) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) a L) (Nat.ofDigits.{u1} α (Ring.toSemiring.{u1} α (CommRing.toRing.{u1} α _inst_1)) b L)))
+Case conversion may be inaccurate. Consider using '#align nat.dvd_of_digits_sub_of_digits Nat.dvd_ofDigits_sub_ofDigitsₓ'. -/
-- This is really a theorem about polynomials.
theorem dvd_ofDigits_sub_ofDigits {α : Type _} [CommRing α] {a b k : α} (h : k ∣ a - b)
(L : List ℕ) : k ∣ ofDigits a L - ofDigits b L :=
@@ -542,6 +660,7 @@ theorem dvd_ofDigits_sub_ofDigits {α : Type _} [CommRing α] {a b k : α} (h :
exact dvd_mul_sub_mul h ih
#align nat.dvd_of_digits_sub_of_digits Nat.dvd_ofDigits_sub_ofDigits
+#print Nat.ofDigits_modeq' /-
theorem ofDigits_modeq' (b b' : ℕ) (k : ℕ) (h : b ≡ b' [MOD k]) (L : List ℕ) :
ofDigits b L ≡ ofDigits b' L [MOD k] :=
by
@@ -552,15 +671,26 @@ theorem ofDigits_modeq' (b b' : ℕ) (k : ℕ) (h : b ≡ b' [MOD k]) (L : List
conv_lhs => rw [Nat.add_mod, Nat.mul_mod, h, ih]
conv_rhs => rw [Nat.add_mod, Nat.mul_mod]
#align nat.of_digits_modeq' Nat.ofDigits_modeq'
+-/
+#print Nat.ofDigits_modEq /-
theorem ofDigits_modEq (b k : ℕ) (L : List ℕ) : ofDigits b L ≡ ofDigits (b % k) L [MOD k] :=
ofDigits_modeq' b (b % k) k (b.mod_modEq k).symm L
#align nat.of_digits_modeq Nat.ofDigits_modEq
+-/
+#print Nat.ofDigits_mod /-
theorem ofDigits_mod (b k : ℕ) (L : List ℕ) : ofDigits b L % k = ofDigits (b % k) L % k :=
ofDigits_modEq b k L
#align nat.of_digits_mod Nat.ofDigits_mod
+-/
+/- warning: nat.of_digits_zmodeq' -> Nat.ofDigits_zmodeq' is a dubious translation:
+lean 3 declaration is
+ forall (b : Int) (b' : Int) (k : Nat), (Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k) b b') -> (forall (L : List.{0} Nat), Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k) (Nat.ofDigits.{0} Int Int.semiring b L) (Nat.ofDigits.{0} Int Int.semiring b' L))
+but is expected to have type
+ forall (b : Int) (b' : Int) (k : Nat), (Int.ModEq (Nat.cast.{0} Int Int.instNatCastInt k) b b') -> (forall (L : List.{0} Nat), Int.ModEq (Nat.cast.{0} Int Int.instNatCastInt k) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.ofDigits.{0} Int Int.instSemiringInt b' L))
+Case conversion may be inaccurate. Consider using '#align nat.of_digits_zmodeq' Nat.ofDigits_zmodeq'ₓ'. -/
theorem ofDigits_zmodeq' (b b' : ℤ) (k : ℕ) (h : b ≡ b' [ZMOD k]) (L : List ℕ) :
ofDigits b L ≡ ofDigits b' L [ZMOD k] :=
by
@@ -572,14 +702,27 @@ theorem ofDigits_zmodeq' (b b' : ℤ) (k : ℕ) (h : b ≡ b' [ZMOD k]) (L : Lis
conv_rhs => rw [Int.add_emod, Int.mul_emod]
#align nat.of_digits_zmodeq' Nat.ofDigits_zmodeq'
+/- warning: nat.of_digits_zmodeq -> Nat.ofDigits_zmodeq is a dubious translation:
+lean 3 declaration is
+ forall (b : Int) (k : Nat) (L : List.{0} Nat), Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k) (Nat.ofDigits.{0} Int Int.semiring b L) (Nat.ofDigits.{0} Int Int.semiring (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) b ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k)) L)
+but is expected to have type
+ forall (b : Int) (k : Nat) (L : List.{0} Nat), Int.ModEq (Nat.cast.{0} Int Int.instNatCastInt k) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.ofDigits.{0} Int Int.instSemiringInt (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) b (Nat.cast.{0} Int Int.instNatCastInt k)) L)
+Case conversion may be inaccurate. Consider using '#align nat.of_digits_zmodeq Nat.ofDigits_zmodeqₓ'. -/
theorem ofDigits_zmodeq (b : ℤ) (k : ℕ) (L : List ℕ) : ofDigits b L ≡ ofDigits (b % k) L [ZMOD k] :=
ofDigits_zmodeq' b (b % k) k (b.mod_modEq ↑k).symm L
#align nat.of_digits_zmodeq Nat.ofDigits_zmodeq
+/- warning: nat.of_digits_zmod -> Nat.ofDigits_zmod is a dubious translation:
+lean 3 declaration is
+ forall (b : Int) (k : Nat) (L : List.{0} Nat), Eq.{1} Int (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) (Nat.ofDigits.{0} Int Int.semiring b L) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k)) (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) (Nat.ofDigits.{0} Int Int.semiring (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.hasMod) b ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k)) L) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) k))
+but is expected to have type
+ forall (b : Int) (k : Nat) (L : List.{0} Nat), Eq.{1} Int (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) (Nat.ofDigits.{0} Int Int.instSemiringInt b L) (Nat.cast.{0} Int Int.instNatCastInt k)) (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) (Nat.ofDigits.{0} Int Int.instSemiringInt (HMod.hMod.{0, 0, 0} Int Int Int (instHMod.{0} Int Int.instModInt_1) b (Nat.cast.{0} Int Int.instNatCastInt k)) L) (Nat.cast.{0} Int Int.instNatCastInt k))
+Case conversion may be inaccurate. Consider using '#align nat.of_digits_zmod Nat.ofDigits_zmodₓ'. -/
theorem ofDigits_zmod (b : ℤ) (k : ℕ) (L : List ℕ) : ofDigits b L % k = ofDigits (b % k) L % k :=
ofDigits_zmodeq b k L
#align nat.of_digits_zmod Nat.ofDigits_zmod
+#print Nat.modEq_digits_sum /-
theorem modEq_digits_sum (b b' : ℕ) (h : b' % b = 1) (n : ℕ) : n ≡ (digits b' n).Sum [MOD b] :=
by
rw [← of_digits_one]
@@ -590,15 +733,26 @@ theorem modEq_digits_sum (b b' : ℕ) (h : b' % b = 1) (n : ℕ) : n ≡ (digits
convert of_digits_modeq _ _ _
exact h.symm
#align nat.modeq_digits_sum Nat.modEq_digits_sum
+-/
+#print Nat.modEq_three_digits_sum /-
theorem modEq_three_digits_sum (n : ℕ) : n ≡ (digits 10 n).Sum [MOD 3] :=
modEq_digits_sum 3 10 (by norm_num) n
#align nat.modeq_three_digits_sum Nat.modEq_three_digits_sum
+-/
+#print Nat.modEq_nine_digits_sum /-
theorem modEq_nine_digits_sum (n : ℕ) : n ≡ (digits 10 n).Sum [MOD 9] :=
modEq_digits_sum 9 10 (by norm_num) n
#align nat.modeq_nine_digits_sum Nat.modEq_nine_digits_sum
+-/
+/- warning: nat.zmodeq_of_digits_digits -> Nat.zmodeq_ofDigits_digits is a dubious translation:
+lean 3 declaration is
+ forall (b : Nat) (b' : Nat) (c : Int), (Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b') c) -> (forall (n : Nat), Int.ModEq ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (Nat.ofDigits.{0} Int Int.semiring c (Nat.digits b' n)))
+but is expected to have type
+ forall (b : Nat) (b' : Nat) (c : Int), (Int.ModEq (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.cast.{0} Int Int.instNatCastInt b') c) -> (forall (n : Nat), Int.ModEq (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.cast.{0} Int Int.instNatCastInt n) (Nat.ofDigits.{0} Int Int.instSemiringInt c (Nat.digits b' n)))
+Case conversion may be inaccurate. Consider using '#align nat.zmodeq_of_digits_digits Nat.zmodeq_ofDigits_digitsₓ'. -/
theorem zmodeq_ofDigits_digits (b b' : ℕ) (c : ℤ) (h : b' ≡ c [ZMOD b]) (n : ℕ) :
n ≡ ofDigits c (digits b' n) [ZMOD b] :=
by
@@ -610,6 +764,12 @@ theorem zmodeq_ofDigits_digits (b b' : ℕ) (c : ℤ) (h : b' ≡ c [ZMOD b]) (n
apply of_digits_zmodeq' _ _ _ h
#align nat.zmodeq_of_digits_digits Nat.zmodeq_ofDigits_digits
+/- warning: nat.of_digits_neg_one -> Nat.ofDigits_neg_one is a dubious translation:
+lean 3 declaration is
+ forall (L : List.{0} Nat), Eq.{1} Int (Nat.ofDigits.{0} Int Int.semiring (Neg.neg.{0} Int Int.hasNeg (OfNat.ofNat.{0} Int 1 (OfNat.mk.{0} Int 1 (One.one.{0} Int Int.hasOne)))) L) (List.alternatingSum.{0} Int Int.hasZero Int.hasAdd Int.hasNeg (List.map.{0, 0} Nat Int (fun (n : Nat) => (fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) L))
+but is expected to have type
+ forall (L : List.{0} Nat), Eq.{1} Int (Nat.ofDigits.{0} Int Int.instSemiringInt (Neg.neg.{0} Int Int.instNegInt (OfNat.ofNat.{0} Int 1 (instOfNatInt 1))) L) (List.alternatingSum.{0} Int (CommMonoidWithZero.toZero.{0} Int (CancelCommMonoidWithZero.toCommMonoidWithZero.{0} Int (IsDomain.toCancelCommMonoidWithZero.{0} Int Int.instCommSemiringInt (LinearOrderedRing.isDomain.{0} Int (LinearOrderedCommRing.toLinearOrderedRing.{0} Int Int.linearOrderedCommRing))))) Int.instAddInt Int.instNegInt (List.map.{0, 0} Nat Int (fun (n : Nat) => Nat.cast.{0} Int Int.instNatCastInt n) L))
+Case conversion may be inaccurate. Consider using '#align nat.of_digits_neg_one Nat.ofDigits_neg_oneₓ'. -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
theorem ofDigits_neg_one :
@@ -622,32 +782,46 @@ theorem ofDigits_neg_one :
ring
#align nat.of_digits_neg_one Nat.ofDigits_neg_one
+#print Nat.modEq_eleven_digits_sum /-
theorem modEq_eleven_digits_sum (n : ℕ) :
n ≡ ((digits 10 n).map fun n : ℕ => (n : ℤ)).alternatingSum [ZMOD 11] :=
by
have t := zmodeq_of_digits_digits 11 10 (-1 : ℤ) (by unfold Int.ModEq <;> norm_num) n
rwa [of_digits_neg_one] at t
#align nat.modeq_eleven_digits_sum Nat.modEq_eleven_digits_sum
+-/
/-! ## Divisibility -/
+#print Nat.dvd_iff_dvd_digits_sum /-
theorem dvd_iff_dvd_digits_sum (b b' : ℕ) (h : b' % b = 1) (n : ℕ) :
b ∣ n ↔ b ∣ (digits b' n).Sum := by
rw [← of_digits_one]
conv_lhs => rw [← of_digits_digits b' n]
rw [Nat.dvd_iff_mod_eq_zero, Nat.dvd_iff_mod_eq_zero, of_digits_mod, h]
#align nat.dvd_iff_dvd_digits_sum Nat.dvd_iff_dvd_digits_sum
+-/
+#print Nat.three_dvd_iff /-
/-- **Divisibility by 3 Rule** -/
theorem three_dvd_iff (n : ℕ) : 3 ∣ n ↔ 3 ∣ (digits 10 n).Sum :=
dvd_iff_dvd_digits_sum 3 10 (by norm_num) n
#align nat.three_dvd_iff Nat.three_dvd_iff
+-/
+#print Nat.nine_dvd_iff /-
theorem nine_dvd_iff (n : ℕ) : 9 ∣ n ↔ 9 ∣ (digits 10 n).Sum :=
dvd_iff_dvd_digits_sum 9 10 (by norm_num) n
#align nat.nine_dvd_iff Nat.nine_dvd_iff
+-/
+/- warning: nat.dvd_iff_dvd_of_digits -> Nat.dvd_iff_dvd_ofDigits is a dubious translation:
+lean 3 declaration is
+ forall (b : Nat) (b' : Nat) (c : Int), (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b') c)) -> (forall (n : Nat), Iff (Dvd.Dvd.{0} Nat Nat.hasDvd b n) (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) (Nat.ofDigits.{0} Int Int.semiring c (Nat.digits b' n))))
+but is expected to have type
+ forall (b : Nat) (b' : Nat) (c : Int), (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int Int.instNatCastInt b) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int Int.instNatCastInt b') c)) -> (forall (n : Nat), Iff (Dvd.dvd.{0} Nat Nat.instDvdNat b n) (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.ofDigits.{0} Int Int.instSemiringInt c (Nat.digits b' n))))
+Case conversion may be inaccurate. Consider using '#align nat.dvd_iff_dvd_of_digits Nat.dvd_iff_dvd_ofDigitsₓ'. -/
theorem dvd_iff_dvd_ofDigits (b b' : ℕ) (c : ℤ) (h : (b : ℤ) ∣ (b' : ℤ) - c) (n : ℕ) :
b ∣ n ↔ (b : ℤ) ∣ ofDigits c (digits b' n) :=
by
@@ -656,6 +830,12 @@ theorem dvd_iff_dvd_ofDigits (b b' : ℕ) (c : ℤ) (h : (b : ℤ) ∣ (b' : ℤ
dvd_iff_dvd_of_dvd_sub (zmodeq_of_digits_digits b b' c (Int.modEq_iff_dvd.2 h).symm _).symm.Dvd
#align nat.dvd_iff_dvd_of_digits Nat.dvd_iff_dvd_ofDigits
+/- warning: nat.eleven_dvd_iff -> Nat.eleven_dvd_iff is a dubious translation:
+lean 3 declaration is
+ forall {n : Nat}, Iff (Dvd.Dvd.{0} Nat Nat.hasDvd (OfNat.ofNat.{0} Nat 11 (OfNat.mk.{0} Nat 11 (bit1.{0} Nat Nat.hasOne Nat.hasAdd (bit1.{0} Nat Nat.hasOne Nat.hasAdd (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) n) (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) (OfNat.ofNat.{0} Int 11 (OfNat.mk.{0} Int 11 (bit1.{0} Int Int.hasOne Int.hasAdd (bit1.{0} Int Int.hasOne Int.hasAdd (bit0.{0} Int Int.hasAdd (One.one.{0} Int Int.hasOne)))))) (List.alternatingSum.{0} Int Int.hasZero Int.hasAdd Int.hasNeg (List.map.{0, 0} Nat Int (fun (n : Nat) => (fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (Nat.digits (OfNat.ofNat.{0} Nat 10 (OfNat.mk.{0} Nat 10 (bit0.{0} Nat Nat.hasAdd (bit1.{0} Nat Nat.hasOne Nat.hasAdd (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))))) n))))
+but is expected to have type
+ forall {n : Nat}, Iff (Dvd.dvd.{0} Nat Nat.instDvdNat (OfNat.ofNat.{0} Nat 11 (instOfNatNat 11)) n) (Dvd.dvd.{0} Int Int.instDvdInt (OfNat.ofNat.{0} Int 11 (instOfNatInt 11)) (List.alternatingSum.{0} Int (CommMonoidWithZero.toZero.{0} Int (CancelCommMonoidWithZero.toCommMonoidWithZero.{0} Int (IsDomain.toCancelCommMonoidWithZero.{0} Int Int.instCommSemiringInt (LinearOrderedRing.isDomain.{0} Int (LinearOrderedCommRing.toLinearOrderedRing.{0} Int Int.linearOrderedCommRing))))) Int.instAddInt Int.instNegInt (List.map.{0, 0} Nat Int (fun (n : Nat) => Nat.cast.{0} Int Int.instNatCastInt n) (Nat.digits (OfNat.ofNat.{0} Nat 10 (instOfNatNat 10)) n))))
+Case conversion may be inaccurate. Consider using '#align nat.eleven_dvd_iff Nat.eleven_dvd_iffₓ'. -/
theorem eleven_dvd_iff :
11 ∣ n ↔ (11 : ℤ) ∣ ((digits 10 n).map fun n : ℕ => (n : ℤ)).alternatingSum :=
by
@@ -664,6 +844,7 @@ theorem eleven_dvd_iff :
exact t
#align nat.eleven_dvd_iff Nat.eleven_dvd_iff
+#print Nat.eleven_dvd_of_palindrome /-
theorem eleven_dvd_of_palindrome (p : (digits 10 n).Palindrome) (h : Even (digits 10 n).length) :
11 ∣ n := by
let dig := (digits 10 n).map (coe : ℕ → ℤ)
@@ -673,6 +854,7 @@ theorem eleven_dvd_of_palindrome (p : (digits 10 n).Palindrome) (h : Even (digit
rw [(p.map _).reverse_eq, pow_succ, h.neg_one_pow, mul_one, neg_one_zsmul] at this
exact eq_zero_of_neg_eq this.symm
#align nat.eleven_dvd_of_palindrome Nat.eleven_dvd_of_palindrome
+-/
/-! ### `norm_digits` tactic -/
@@ -680,6 +862,7 @@ theorem eleven_dvd_of_palindrome (p : (digits 10 n).Palindrome) (h : Even (digit
namespace NormDigits
/- ./././Mathport/Syntax/Translate/Expr.lean:177:8: unsupported: ambiguous notation -/
+#print Nat.NormDigits.digits_succ /-
theorem digits_succ (b n m r l) (e : r + b * m = n) (hr : r < b)
(h : Nat.digits b m = l ∧ 1 < b ∧ 0 < m) : (Nat.digits b n = r::l) ∧ 1 < b ∧ 0 < n :=
by
@@ -690,7 +873,9 @@ theorem digits_succ (b n m r l) (e : r + b * m = n) (hr : r < b)
obtain ⟨rfl, rfl⟩ := (Nat.div_mod_unique b0).2 ⟨e, hr⟩
subst h; exact Nat.digits_def' b2 n0
#align nat.norm_digits.digits_succ Nat.NormDigits.digits_succ
+-/
+#print Nat.NormDigits.digits_one /-
theorem digits_one (b n) (n0 : 0 < n) (nb : n < b) : Nat.digits b n = [n] ∧ 1 < b ∧ 0 < n :=
by
have b2 : 1 < b := by linarith
@@ -698,6 +883,7 @@ theorem digits_one (b n) (n0 : 0 < n) (nb : n < b) : Nat.digits b n = [n] ∧ 1
rw [Nat.digits_def' b2 n0, Nat.mod_eq_of_lt nb,
(Nat.div_eq_zero_iff ((zero_le n).trans_lt nb)).2 nb, Nat.digits_zero]
#align nat.norm_digits.digits_one Nat.NormDigits.digits_one
+-/
open Tactic
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
@@ -244,8 +244,8 @@ theorem digits_ofDigits (b : ℕ) (h : 1 < b) (L : List ℕ) (w₁ : ∀ l ∈ L
apply w₁
exact List.mem_cons_of_mem _ m
· intro h
- · rw [List.getLast_cons h] at w₂
- convert w₂
+ rw [List.getLast_cons h] at w₂
+ convert w₂
· exact w₁ d (List.mem_cons_self _ _)
· by_cases h' : L = []
· rcases h' with rfl
@@ -366,8 +366,8 @@ theorem getLast_digit_ne_zero (b : ℕ) {m : ℕ} (hm : m ≠ 0) :
· simpa only [digits_of_lt (b + 2) n hn hnb]
· rw [digits_getLast n (le_add_left 2 b)]
refine' IH _ (Nat.div_lt_self hn.bot_lt (one_lt_succ_succ b)) _
- · rw [← pos_iff_ne_zero]
- exact Nat.div_pos (le_of_not_lt hnb) (zero_lt_succ (succ b))
+ rw [← pos_iff_ne_zero]
+ exact Nat.div_pos (le_of_not_lt hnb) (zero_lt_succ (succ b))
#align nat.last_digit_ne_zero Nat.getLast_digit_ne_zero
/-- The digits in the base b+2 expansion of n are all less than b+2 -/
deprecated
attributeWhy these changes?
@@ -752,8 +752,7 @@ lemma toDigitsCore_lens_eq_aux (b f : Nat) :
specialize ih (n / b) (Nat.digitChar (n % b) :: l1) (Nat.digitChar (n % b) :: l2)
simp only [List.length, congrArg (fun l ↦ l + 1) hlen] at ih
exact ih trivial
--- deprecated 2024-02-19
-@[deprecated] alias to_digits_core_lens_eq_aux:= toDigitsCore_lens_eq_aux
+@[deprecated] alias to_digits_core_lens_eq_aux:= toDigitsCore_lens_eq_aux -- 2024-02-19
lemma toDigitsCore_lens_eq (b f : Nat) : ∀ (n : Nat) (c : Char) (tl : List Char),
(Nat.toDigitsCore b f n (c :: tl)).length = (Nat.toDigitsCore b f n tl).length + 1 := by
@@ -770,8 +769,7 @@ lemma toDigitsCore_lens_eq (b f : Nat) : ∀ (n : Nat) (c : Char) (tl : List Cha
have lens_eq : (x :: (c :: tl)).length = (c :: x :: tl).length := by simp
apply toDigitsCore_lens_eq_aux
exact lens_eq
--- deprecated 2024-02-19
-@[deprecated] alias to_digits_core_lens_eq:= toDigitsCore_lens_eq
+@[deprecated] alias to_digits_core_lens_eq:= toDigitsCore_lens_eq -- 2024-02-19
lemma nat_repr_len_aux (n b e : Nat) (h_b_pos : 0 < b) : n < b ^ e.succ → n / b < b ^ e := by
simp only [Nat.pow_succ]
@@ -802,8 +800,7 @@ lemma toDigitsCore_length (b : Nat) (h : 2 <= b) (f n e : Nat)
have _ : b ^ 1 = b := by simp only [Nat.pow_succ, pow_zero, Nat.one_mul]
have _ : n < b := ‹b ^ 1 = b› ▸ hlt
simp [(@Nat.div_eq_of_lt n b ‹n < b› : n / b = 0)]
--- deprecated 2024-02-19
-@[deprecated] alias to_digits_core_length := toDigitsCore_length
+@[deprecated] alias to_digits_core_length := toDigitsCore_length -- 2024-02-19
/-- The core implementation of `Nat.repr` returns a String with length less than or equal to the
number of digits in the decimal number (represented by `e`). For example, the decimal string
Rat
has a long history in (and before) mathlib and as such its development is full of cruft. Now that NNRat
is a thing, there is a need for the theory of Rat
to be mimickable to yield the theory of NNRat
, which is not currently the case.
Broadly, this PR aims at mirroring the Rat
and NNRat
declarations. It achieves this by:
Rat.num
and Rat.den
, and less on the structure representation of Rat
Rat.Nonneg
(which was replaced in Std by a new development of the order on Rat
)Rat
lemmas with dubious names. This creates quite a lot of conflicts with Std lemmas, whose names are themselves dubious. I am priming the relevant new mathlib names and leaving TODOs to fix the Std names.Rat
porting notesReduce the diff of #11203
@@ -598,7 +598,7 @@ theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1
cases b
· rw [digits_def' one_lt_two]
· simpa [Nat.bit, Nat.bit0_val n]
- · simpa [pos_iff_ne_zero, bit_eq_zero_iff]
+ · simpa [pos_iff_ne_zero, Nat.bit0_eq_zero]
· simpa [Nat.bit, Nat.bit1_val n, add_comm, digits_add 2 one_lt_two 1 n, Nat.add_mul_div_left]
#align nat.digits_two_eq_bits Nat.digits_two_eq_bits
@@ -33,9 +33,6 @@ A basic `norm_digits` tactic for proving goals of the form `Nat.digits a b = l`
are numerals is not yet ported.
-/
-set_option autoImplicit true
-
-
namespace Nat
variable {n : ℕ}
@@ -467,7 +464,7 @@ theorem ofDigits_monotone {p q : ℕ} (L : List ℕ) (h : p ≤ q) : ofDigits p
· simp only [ofDigits, cast_id, add_le_add_iff_left]
exact Nat.mul_le_mul h hi
-theorem sum_le_ofDigits (L : List ℕ) (h : 1 ≤ p) : L.sum ≤ ofDigits p L :=
+theorem sum_le_ofDigits {p : ℕ} (L : List ℕ) (h : 1 ≤ p) : L.sum ≤ ofDigits p L :=
(ofDigits_one L).symm ▸ ofDigits_monotone L h
theorem digit_sum_le (p n : ℕ) : List.sum (digits p n) ≤ n := by
@@ -513,7 +510,7 @@ theorem base_pow_length_digits_le (b m : ℕ) (hb : 1 < b) :
/-- Interpreting as a base `p` number and dividing by `p` is the same as interpreting the tail.
-/
-lemma ofDigits_div_eq_ofDigits_tail (hpos : 0 < p) (digits : List ℕ)
+lemma ofDigits_div_eq_ofDigits_tail {p : ℕ} (hpos : 0 < p) (digits : List ℕ)
(w₁ : ∀ l ∈ digits, l < p) : ofDigits p digits / p = ofDigits p digits.tail := by
induction' digits with hd tl
· simp [ofDigits]
@@ -524,7 +521,7 @@ lemma ofDigits_div_eq_ofDigits_tail (hpos : 0 < p) (digits : List ℕ)
/-- Interpreting as a base `p` number and dividing by `p^i` is the same as dropping `i`.
-/
lemma ofDigits_div_pow_eq_ofDigits_drop
- (i : ℕ) (hpos : 0 < p) (digits : List ℕ) (w₁ : ∀ l ∈ digits, l < p) :
+ {p : ℕ} (i : ℕ) (hpos : 0 < p) (digits : List ℕ) (w₁ : ∀ l ∈ digits, l < p) :
ofDigits p digits / p ^ i = ofDigits p (digits.drop i) := by
induction' i with i hi
· simp
@@ -534,7 +531,7 @@ lemma ofDigits_div_pow_eq_ofDigits_drop
/-- Dividing `n` by `p^i` is like truncating the first `i` digits of `n` in base `p`.
-/
-lemma self_div_pow_eq_ofDigits_drop (i n : ℕ) (h : 2 ≤ p):
+lemma self_div_pow_eq_ofDigits_drop {p : ℕ} (i n : ℕ) (h : 2 ≤ p):
n / p ^ i = ofDigits p ((p.digits n).drop i) := by
convert ofDigits_div_pow_eq_ofDigits_drop i (zero_lt_of_lt h) (p.digits n)
(fun l hl ↦ digits_lt_base h hl)
@@ -542,7 +539,7 @@ lemma self_div_pow_eq_ofDigits_drop (i n : ℕ) (h : 2 ≤ p):
open BigOperators Finset
-theorem sub_one_mul_sum_div_pow_eq_sub_sum_digits
+theorem sub_one_mul_sum_div_pow_eq_sub_sum_digits {p : ℕ}
(L : List ℕ) {h_nonempty} (h_ne_zero : L.getLast h_nonempty ≠ 0) (h_lt : ∀ l ∈ L, l < p) :
(p - 1) * ∑ i in range L.length, (ofDigits p L) / p ^ i.succ = (ofDigits p L) - L.sum := by
obtain h | rfl | h : 1 < p ∨ 1 = p ∨ p < 1 := trichotomous 1 p
@@ -576,7 +573,7 @@ theorem sub_one_mul_sum_div_pow_eq_sub_sum_digits
· rfl
· simp [ofDigits]
-theorem sub_one_mul_sum_log_div_pow_eq_sub_sum_digits (n : ℕ) :
+theorem sub_one_mul_sum_log_div_pow_eq_sub_sum_digits {p : ℕ} (n : ℕ) :
(p - 1) * ∑ i in range (log p n).succ, n / p ^ i.succ = n - (p.digits n).sum := by
obtain h | rfl | h : 1 < p ∨ 1 = p ∨ p < 1 := trichotomous 1 p
· rcases eq_or_ne n 0 with rfl | hn
coe_nat
to natCast
(#11637)
Reduce the diff of #11499
All in the Int
namespace:
ofNat_eq_cast
→ ofNat_eq_natCast
cast_eq_cast_iff_Nat
→ natCast_inj
natCast_eq_ofNat
→ ofNat_eq_natCast
coe_nat_sub
→ natCast_sub
coe_nat_nonneg
→ natCast_nonneg
sign_coe_add_one
→ sign_natCast_add_one
nat_succ_eq_int_succ
→ natCast_succ
succ_neg_nat_succ
→ succ_neg_natCast_succ
coe_pred_of_pos
→ natCast_pred_of_pos
coe_nat_div
→ natCast_div
coe_nat_ediv
→ natCast_ediv
sign_coe_nat_of_nonzero
→ sign_natCast_of_ne_zero
toNat_coe_nat
→ toNat_natCast
toNat_coe_nat_add_one
→ toNat_natCast_add_one
coe_nat_dvd
→ natCast_dvd_natCast
coe_nat_dvd_left
→ natCast_dvd
coe_nat_dvd_right
→ dvd_natCast
le_coe_nat_sub
→ le_natCast_sub
succ_coe_nat_pos
→ succ_natCast_pos
coe_nat_modEq_iff
→ natCast_modEq_iff
coe_natAbs
→ natCast_natAbs
coe_nat_eq_zero
→ natCast_eq_zero
coe_nat_ne_zero
→ natCast_ne_zero
coe_nat_ne_zero_iff_pos
→ natCast_ne_zero_iff_pos
abs_coe_nat
→ abs_natCast
coe_nat_nonpos_iff
→ natCast_nonpos_iff
Also rename Nat.coe_nat_dvd
to Nat.cast_dvd_cast
@@ -718,7 +718,7 @@ theorem nine_dvd_iff (n : ℕ) : 9 ∣ n ↔ 9 ∣ (digits 10 n).sum :=
theorem dvd_iff_dvd_ofDigits (b b' : ℕ) (c : ℤ) (h : (b : ℤ) ∣ (b' : ℤ) - c) (n : ℕ) :
b ∣ n ↔ (b : ℤ) ∣ ofDigits c (digits b' n) := by
- rw [← Int.coe_nat_dvd]
+ rw [← Int.natCast_dvd_natCast]
exact
dvd_iff_dvd_of_dvd_sub (zmodeq_ofDigits_digits b b' c (Int.modEq_iff_dvd.2 h).symm _).symm.dvd
#align nat.dvd_iff_dvd_of_digits Nat.dvd_iff_dvd_ofDigits
Algebra.BigOperators.List
(#11729)
This is algebra and should be foldered as such.
@@ -4,11 +4,11 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Scott Morrison, Shing Tak Lam, Mario Carneiro
-/
import Mathlib.Algebra.BigOperators.Intervals
+import Mathlib.Algebra.BigOperators.List.Lemmas
import Mathlib.Algebra.Parity
import Mathlib.Data.Int.ModEq
import Mathlib.Data.Nat.Bits
import Mathlib.Data.Nat.Log
-import Mathlib.Data.List.BigOperators.Lemmas
import Mathlib.Data.List.Indexes
import Mathlib.Data.List.Palindrome
import Mathlib.Tactic.IntervalCases
We change the following field in the definition of an additive commutative monoid:
nsmul_succ : ∀ (n : ℕ) (x : G),
- AddMonoid.nsmul (n + 1) x = x + AddMonoid.nsmul n x
+ AddMonoid.nsmul (n + 1) x = AddMonoid.nsmul n x + x
where the latter is more natural
We adjust the definitions of ^
in monoids, groups, etc.
Originally there was a warning comment about why this natural order was preferred
use
x * npowRec n x
and notnpowRec n x * x
in the definition to make sure that definitional unfolding ofnpowRec
is blocked, to avoid deep recursion issues.
but it seems to no longer apply.
Remarks on the PR :
pow_succ
and pow_succ'
have switched their meanings.Ideal.IsPrime.mul_mem_pow
which is defined in [Mathlib/RingTheory/DedekindDomain/Ideal.lean]. Changing the order of operation forced me to add the symmetric lemma Ideal.IsPrime.mem_pow_mul
.@@ -736,7 +736,7 @@ theorem eleven_dvd_of_palindrome (p : (digits 10 n).Palindrome) (h : Even (digit
replace h : Even dig.length := by rwa [List.length_map]
refine' eleven_dvd_iff.2 ⟨0, (_ : dig.alternatingSum = 0)⟩
have := dig.alternatingSum_reverse
- rw [(p.map _).reverse_eq, _root_.pow_succ, h.neg_one_pow, mul_one, neg_one_zsmul] at this
+ rw [(p.map _).reverse_eq, _root_.pow_succ', h.neg_one_pow, mul_one, neg_one_zsmul] at this
exact eq_zero_of_neg_eq this.symm
#align nat.eleven_dvd_of_palindrome Nat.eleven_dvd_of_palindrome
After the (d)simp
and rw
tactics - hints to find further occurrences welcome.
Co-authored-by: @sven-manthe
@@ -270,7 +270,7 @@ theorem ofDigits_digits (b n : ℕ) : ofDigits b (digits b n) = n := by
· cases' b with b
· induction' n with n ih
· rfl
- · rw[show succ zero = 1 by rfl] at ih ⊢
+ · rw [show succ zero = 1 by rfl] at ih ⊢
simp only [ih, add_comm 1, ofDigits_one_cons, Nat.cast_id, digits_one_succ]
· apply Nat.strongInductionOn n _
clear n
@@ -407,7 +407,6 @@ theorem ofDigits_lt_base_pow_length' {b : ℕ} {l : List ℕ} (hl : ∀ x ∈ l,
mul_le_mul (IH fun x hx => hl _ (List.mem_cons_of_mem _ hx)) (by rfl) (by simp only [zero_le])
(Nat.zero_le _)
suffices ↑hd < b + 2 by linarith
- norm_cast
exact hl hd (List.mem_cons_self _ _)
#align nat.of_digits_lt_base_pow_length' Nat.ofDigits_lt_base_pow_length'
This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0
branch as we update to intermediate nightlies.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>
@@ -803,7 +803,7 @@ lemma toDigitsCore_length (b : Nat) (h : 2 <= b) (f n e : Nat)
exact Nat.succ_le_succ ih
else
obtain rfl : e = 0 := Nat.eq_zero_of_not_pos h_pred_pos
- have _ : b ^ 1 = b := by simp only [pow_succ, pow_zero, Nat.one_mul]
+ have _ : b ^ 1 = b := by simp only [Nat.pow_succ, pow_zero, Nat.one_mul]
have _ : n < b := ‹b ^ 1 = b› ▸ hlt
simp [(@Nat.div_eq_of_lt n b ‹n < b› : n / b = 0)]
-- deprecated 2024-02-19
I ran tryAtEachStep on all files under Mathlib
to find all locations where omega
succeeds. For each that was a linarith
without an only
, I tried replacing it with omega
, and I verified that elaboration time got smaller. (In almost all cases, there was a noticeable speedup.) I also replaced some slow aesop
s along the way.
@@ -830,7 +830,7 @@ namespace NormDigits
theorem digits_succ (b n m r l) (e : r + b * m = n) (hr : r < b)
(h : Nat.digits b m = l ∧ 1 < b ∧ 0 < m) : (Nat.digits b n = r :: l) ∧ 1 < b ∧ 0 < n := by
rcases h with ⟨h, b2, m0⟩
- have b0 : 0 < b := by linarith
+ have b0 : 0 < b := by omega
have n0 : 0 < n := by linarith [mul_pos b0 m0]
refine' ⟨_, b2, n0⟩
obtain ⟨rfl, rfl⟩ := (Nat.div_mod_unique b0).2 ⟨e, hr⟩
There's no need to have this result so early.
No changes to the moved code.
@@ -25,8 +25,12 @@ and reconstructing numbers from their digits.
We also prove some divisibility tests based on digits, in particular completing
Theorem #85 from https://www.cs.ru.nl/~freek/100/.
-A basic `norm_digits` tactic is also provided for proving goals of the form
-`Nat.digits a b = l` where `a` and `b` are numerals.
+Also included is a bound on the length of `Nat.toDigits` from core.
+
+## TODO
+
+A basic `norm_digits` tactic for proving goals of the form `Nat.digits a b = l` where `a` and `b`
+are numerals is not yet ported.
-/
set_option autoImplicit true
@@ -737,6 +741,87 @@ theorem eleven_dvd_of_palindrome (p : (digits 10 n).Palindrome) (h : Even (digit
exact eq_zero_of_neg_eq this.symm
#align nat.eleven_dvd_of_palindrome Nat.eleven_dvd_of_palindrome
+/-! ### `Nat.toDigits` length -/
+
+lemma toDigitsCore_lens_eq_aux (b f : Nat) :
+ ∀ (n : Nat) (l1 l2 : List Char), l1.length = l2.length →
+ (Nat.toDigitsCore b f n l1).length = (Nat.toDigitsCore b f n l2).length := by
+ induction f with (simp only [Nat.toDigitsCore, List.length]; intro n l1 l2 hlen)
+ | zero => assumption
+ | succ f ih =>
+ if hx : n / b = 0 then
+ simp only [hx, if_true, List.length, congrArg (fun l ↦ l + 1) hlen]
+ else
+ simp only [hx, if_false]
+ specialize ih (n / b) (Nat.digitChar (n % b) :: l1) (Nat.digitChar (n % b) :: l2)
+ simp only [List.length, congrArg (fun l ↦ l + 1) hlen] at ih
+ exact ih trivial
+-- deprecated 2024-02-19
+@[deprecated] alias to_digits_core_lens_eq_aux:= toDigitsCore_lens_eq_aux
+
+lemma toDigitsCore_lens_eq (b f : Nat) : ∀ (n : Nat) (c : Char) (tl : List Char),
+ (Nat.toDigitsCore b f n (c :: tl)).length = (Nat.toDigitsCore b f n tl).length + 1 := by
+ induction f with (intro n c tl; simp only [Nat.toDigitsCore, List.length])
+ | succ f ih =>
+ if hnb : (n / b) = 0 then
+ simp only [hnb, if_true, List.length]
+ else
+ generalize hx: Nat.digitChar (n % b) = x
+ simp only [hx, hnb, if_false] at ih
+ simp only [hnb, if_false]
+ specialize ih (n / b) c (x :: tl)
+ rw [← ih]
+ have lens_eq : (x :: (c :: tl)).length = (c :: x :: tl).length := by simp
+ apply toDigitsCore_lens_eq_aux
+ exact lens_eq
+-- deprecated 2024-02-19
+@[deprecated] alias to_digits_core_lens_eq:= toDigitsCore_lens_eq
+
+lemma nat_repr_len_aux (n b e : Nat) (h_b_pos : 0 < b) : n < b ^ e.succ → n / b < b ^ e := by
+ simp only [Nat.pow_succ]
+ exact (@Nat.div_lt_iff_lt_mul b n (b ^ e) h_b_pos).mpr
+
+/-- The String representation produced by toDigitsCore has the proper length relative to
+the number of digits in `n < e` for some base `b`. Since this works with any base greater
+than one, it can be used for binary, decimal, and hex. -/
+lemma toDigitsCore_length (b : Nat) (h : 2 <= b) (f n e : Nat)
+ (hlt : n < b ^ e) (h_e_pos: 0 < e) : (Nat.toDigitsCore b f n []).length <= e := by
+ induction f generalizing n e hlt h_e_pos with
+ simp only [Nat.toDigitsCore, List.length, Nat.zero_le]
+ | succ f ih =>
+ cases e with
+ | zero => exact False.elim (Nat.lt_irrefl 0 h_e_pos)
+ | succ e =>
+ if h_pred_pos : 0 < e then
+ have _ : 0 < b := Nat.lt_trans (by decide) h
+ specialize ih (n / b) e (nat_repr_len_aux n b e ‹0 < b› hlt) h_pred_pos
+ if hdiv_ten : n / b = 0 then
+ simp only [hdiv_ten]; exact Nat.le.step h_pred_pos
+ else
+ simp only [hdiv_ten,
+ toDigitsCore_lens_eq b f (n / b) (Nat.digitChar <| n % b), if_false]
+ exact Nat.succ_le_succ ih
+ else
+ obtain rfl : e = 0 := Nat.eq_zero_of_not_pos h_pred_pos
+ have _ : b ^ 1 = b := by simp only [pow_succ, pow_zero, Nat.one_mul]
+ have _ : n < b := ‹b ^ 1 = b› ▸ hlt
+ simp [(@Nat.div_eq_of_lt n b ‹n < b› : n / b = 0)]
+-- deprecated 2024-02-19
+@[deprecated] alias to_digits_core_length := toDigitsCore_length
+
+/-- The core implementation of `Nat.repr` returns a String with length less than or equal to the
+number of digits in the decimal number (represented by `e`). For example, the decimal string
+representation of any number less than 1000 (10 ^ 3) has a length less than or equal to 3. -/
+lemma repr_length (n e : Nat) : 0 < e → n < 10 ^ e → (Nat.repr n).length <= e := by
+ cases n with
+ (intro e0 he; simp only [Nat.repr, Nat.toDigits, String.length, List.asString])
+ | zero => assumption
+ | succ n =>
+ if hterm : n.succ / 10 = 0 then
+ simp only [hterm, Nat.toDigitsCore]; assumption
+ else
+ exact toDigitsCore_length 10 (by decide) (Nat.succ n + 1) (Nat.succ n) e he e0
+
/-! ### `norm_digits` tactic -/
@@ -729,7 +729,7 @@ theorem eleven_dvd_iff :
theorem eleven_dvd_of_palindrome (p : (digits 10 n).Palindrome) (h : Even (digits 10 n).length) :
11 ∣ n := by
- let dig := (digits 10 n).map (Coe.coe : ℕ → ℤ)
+ let dig := (digits 10 n).map fun n : ℕ => (n : ℤ)
replace h : Even dig.length := by rwa [List.length_map]
refine' eleven_dvd_iff.2 ⟨0, (_ : dig.alternatingSum = 0)⟩
have := dig.alternatingSum_reverse
@@ -110,7 +110,7 @@ theorem digits_one (n : ℕ) : digits 1 n = List.replicate n 1 :=
rfl
#align nat.digits_one Nat.digits_one
--- @[simp] -- Porting note: dsimp can prove this
+-- @[simp] -- Porting note (#10685): dsimp can prove this
theorem digits_one_succ (n : ℕ) : digits 1 (n + 1) = 1 :: digits 1 n :=
rfl
#align nat.digits_one_succ Nat.digits_one_succ
@@ -90,7 +90,7 @@ theorem digits_zero (b : ℕ) : digits b 0 = [] := by
rcases b with (_ | ⟨_ | ⟨_⟩⟩) <;> simp [digits, digitsAux0, digitsAux1]
#align nat.digits_zero Nat.digits_zero
--- @[simp] -- Porting note: simp can prove this
+-- @[simp] -- Porting note (#10618): simp can prove this
theorem digits_zero_zero : digits 0 0 = [] :=
rfl
#align nat.digits_zero_zero Nat.digits_zero_zero
@@ -76,8 +76,8 @@ In any base, we have `ofDigits b L = L.foldr (fun x y ↦ x + b * y) 0`.
* For `b = 1`, we define `digits 1 n = List.replicate n 1`.
* For `b = 0`, we define `digits 0 n = [n]`, except `digits 0 0 = []`.
-Note this differs from the existing `Nat.to_digits` in core, which is used for printing numerals.
-In particular, `Nat.to_digits b 0 = [0]`, while `digits b 0 = []`.
+Note this differs from the existing `Nat.toDigits` in core, which is used for printing numerals.
+In particular, `Nat.toDigits b 0 = ['0']`, while `digits b 0 = []`.
-/
def digits : ℕ → ℕ → List ℕ
| 0 => digitsAux0
Data.Real.CauSeq
to Algebra.Order.CauSeq.Basic
Data.Real.CauSeqCompletion
to Algebra.Order.CauSeq.Completion
CauSeq
from Data.Complex.Exponential
to a new file Algebra.Order.CauSeq.BigOperators
Module
from Algebra.BigOperators.Intervals
to a new file Algebra.BigOperators.Module
abv_sum_le_sum_abv
as it's a duplicate of IsAbsoluteValue.abv_sum
@@ -3,15 +3,14 @@ Copyright (c) 2020 Scott Morrison. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Scott Morrison, Shing Tak Lam, Mario Carneiro
-/
+import Mathlib.Algebra.BigOperators.Intervals
+import Mathlib.Algebra.Parity
import Mathlib.Data.Int.ModEq
import Mathlib.Data.Nat.Bits
import Mathlib.Data.Nat.Log
import Mathlib.Data.List.BigOperators.Lemmas
import Mathlib.Data.List.Indexes
import Mathlib.Data.List.Palindrome
-import Mathlib.Algebra.CharZero.Lemmas
-import Mathlib.Algebra.Parity
-import Mathlib.Algebra.BigOperators.Intervals
import Mathlib.Tactic.IntervalCases
import Mathlib.Tactic.Linarith
@@ -136,13 +136,13 @@ theorem digits_def' :
@[simp]
theorem digits_of_lt (b x : ℕ) (hx : x ≠ 0) (hxb : x < b) : digits b x = [x] := by
rcases exists_eq_succ_of_ne_zero hx with ⟨x, rfl⟩
- rcases exists_eq_add_of_le' ((Nat.le_add_left 1 x).trans_lt hxb) with ⟨b, rfl⟩
+ rcases Nat.exists_eq_add_of_le' ((Nat.le_add_left 1 x).trans_lt hxb) with ⟨b, rfl⟩
rw [digits_add_two_add_one, div_eq_of_lt hxb, digits_zero, mod_eq_of_lt hxb]
#align nat.digits_of_lt Nat.digits_of_lt
theorem digits_add (b : ℕ) (h : 1 < b) (x y : ℕ) (hxb : x < b) (hxy : x ≠ 0 ∨ y ≠ 0) :
digits b (x + b * y) = x :: digits b y := by
- rcases exists_eq_add_of_le' h with ⟨b, rfl : _ = _ + 2⟩
+ rcases Nat.exists_eq_add_of_le' h with ⟨b, rfl : _ = _ + 2⟩
cases y
· simp [hxb, hxy.resolve_right (absurd rfl)]
dsimp [digits]
@@ -9,6 +9,7 @@ import Mathlib.Data.Nat.Log
import Mathlib.Data.List.BigOperators.Lemmas
import Mathlib.Data.List.Indexes
import Mathlib.Data.List.Palindrome
+import Mathlib.Algebra.CharZero.Lemmas
import Mathlib.Algebra.Parity
import Mathlib.Algebra.BigOperators.Intervals
import Mathlib.Tactic.IntervalCases
@@ -559,7 +559,7 @@ theorem sub_one_mul_sum_div_pow_eq_sub_sum_digits
← Nat.one_add] at ih
have := sum_singleton (fun x ↦ ofDigits p <| tl.drop x) tl.length
rw [← Ico_succ_singleton, List.drop_length, ofDigits] at this
- have h₁ : 1 ≤ tl.length := List.length_pos.mpr h'
+ have h₁ : 1 ≤ tl.length := List.length_pos.mpr h'
rw [← sum_range_add_sum_Ico _ <| h₁, ← add_zero (∑ x in Ico _ _, ofDigits p (tl.drop x)),
← this, sum_Ico_consecutive _ h₁ <| le_succ tl.length, ← sum_Ico_add _ 0 tl.length 1,
Ico_zero_eq_range, mul_add, mul_add, ih, range_one, sum_singleton, List.drop, ofDigits,
@@ -526,7 +526,7 @@ lemma ofDigits_div_pow_eq_ofDigits_drop
induction' i with i hi
· simp
· rw [Nat.pow_succ, ← Nat.div_div_eq_div_mul, hi, ofDigits_div_eq_ofDigits_tail hpos
- (List.drop i digits) <| fun x hx ↦ w₁ x <| List.mem_of_mem_drop hx, ← List.drop_one,
+ (List.drop i digits) fun x hx ↦ w₁ x <| List.mem_of_mem_drop hx, ← List.drop_one,
List.drop_drop, add_comm]
/-- Dividing `n` by `p^i` is like truncating the first `i` digits of `n` in base `p`.
cases'
(#9171)
I literally went through and regex'd some uses of cases'
, replacing them with rcases
; this is meant to be a low effort PR as I hope that tools can do this in the future.
rcases
is an easier replacement than cases
, though with better tools we could in future do a second pass converting simple rcases
added here (and existing ones) to cases
.
@@ -448,7 +448,7 @@ theorem digits_len_le_digits_len_succ (b n : ℕ) :
(digits b n).length ≤ (digits b (n + 1)).length := by
rcases Decidable.eq_or_ne n 0 with (rfl | hn)
· simp
- cases' le_or_lt b 1 with hb hb
+ rcases le_or_lt b 1 with hb | hb
· interval_cases b <;> simp_arith [digits_zero_succ', hn]
simpa [digits_len, hb, hn] using log_mono_right (le_succ _)
#align nat.digits_len_le_digits_len_succ Nat.digits_len_le_digits_len_succ
@@ -556,7 +556,7 @@ theorem sub_one_mul_sum_div_pow_eq_sub_sum_digits
have w₂' := fun (h : tl ≠ []) ↦ (List.getLast_cons h) ▸ h_ne_zero
have ih := ih (w₂' h') w₁'
simp only [self_div_pow_eq_ofDigits_drop _ _ h, digits_ofDigits p h tl w₁' w₂',
- ←Nat.one_add] at ih
+ ← Nat.one_add] at ih
have := sum_singleton (fun x ↦ ofDigits p <| tl.drop x) tl.length
rw [← Ico_succ_singleton, List.drop_length, ofDigits] at this
have h₁ : 1 ≤ tl.length := List.length_pos.mpr h'
I've also got a change to make this required, but I'd like to land this first.
@@ -438,7 +438,7 @@ theorem digits_append_digits {b m n : ℕ} (hb : 0 < b) :
rw [← ofDigits_digits_append_digits]
refine' (digits_ofDigits b hb _ (fun l hl => _) (fun h_append => _)).symm
· rcases (List.mem_append.mp hl) with (h | h) <;> exact digits_lt_base hb h
- · by_cases digits b m = []
+ · by_cases h : digits b m = []
· simp only [h, List.append_nil] at h_append ⊢
exact getLast_digit_ne_zero b <| digits_ne_nil_iff_ne_zero.mp h_append
· exact (List.getLast_append' _ _ h) ▸
This is the supremum of
along with some minor fixes from failures on nightly-testing as Mathlib master
is merged into it.
Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.
I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0
branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.
In particular this includes adjustments for the Lean PRs
We can get rid of all the
local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)
macros across Mathlib (and in any projects that want to write natural number powers of reals).
Changes the default behaviour of simp
to (config := {decide := false})
. This makes simp
(and consequentially norm_num
) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp
or norm_num
to decide
or rfl
, or adding (config := {decide := true})
.
This changed the behaviour of simp
so that simp [f]
will only unfold "fully applied" occurrences of f
. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true })
. We may in future add a syntax for this, e.g. simp [!f]
; please provide feedback! In the meantime, we have made the following changes:
(config := { unfoldPartialApp := true })
in some places, to recover the old behaviour@[eqns]
to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp
and Function.flip
.This change in Lean may require further changes down the line (e.g. adding the !f
syntax, and/or upstreaming the special treatment for Function.comp
and Function.flip
, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!
Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>
@@ -357,6 +357,7 @@ theorem getLast_digit_ne_zero (b : ℕ) {m : ℕ} (hm : m ≠ 0) :
· cases hm rfl
rename ℕ => m
simp only [digits_one, List.getLast_replicate_succ m 1]
+ exact Nat.one_ne_zero
revert hm
apply Nat.strongInductionOn m
intro n IH hn
@@ -569,7 +570,7 @@ theorem sub_one_mul_sum_div_pow_eq_sub_sum_digits
· simp [ofDigits_one]
· simp [lt_one_iff.mp h]
cases L
- · simp
+ · rfl
· simp [ofDigits]
theorem sub_one_mul_sum_log_div_pow_eq_sub_sum_digits (n : ℕ) :
@@ -592,7 +593,7 @@ theorem sub_one_mul_sum_log_div_pow_eq_sub_sum_digits (n : ℕ) :
theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1 0 := by
induction' n using Nat.binaryRecFromOne with b n h ih
· simp
- · simp
+ · rfl
rw [bits_append_bit _ _ fun hn => absurd hn h]
cases b
· rw [digits_def' one_lt_two]
@@ -689,7 +690,7 @@ theorem ofDigits_neg_one :
theorem modEq_eleven_digits_sum (n : ℕ) :
n ≡ ((digits 10 n).map fun n : ℕ => (n : ℤ)).alternatingSum [ZMOD 11] := by
- have t := zmodeq_ofDigits_digits 11 10 (-1 : ℤ) (by unfold Int.ModEq; norm_num) n
+ have t := zmodeq_ofDigits_digits 11 10 (-1 : ℤ) (by unfold Int.ModEq; rfl) n
rwa [ofDigits_neg_one] at t
#align nat.modeq_eleven_digits_sum Nat.modEq_eleven_digits_sum
@@ -463,7 +463,7 @@ theorem ofDigits_monotone {p q : ℕ} (L : List ℕ) (h : p ≤ q) : ofDigits p
· simp only [ofDigits, cast_id, add_le_add_iff_left]
exact Nat.mul_le_mul h hi
-theorem sum_le_ofDigits (L : List ℕ) (h: 1 ≤ p) : L.sum ≤ ofDigits p L :=
+theorem sum_le_ofDigits (L : List ℕ) (h : 1 ≤ p) : L.sum ≤ ofDigits p L :=
(ofDigits_one L).symm ▸ ofDigits_monotone L h
theorem digit_sum_le (p n : ℕ) : List.sum (digits p n) ≤ n := by
@@ -555,7 +555,7 @@ theorem sub_one_mul_sum_div_pow_eq_sub_sum_digits
have w₂' := fun (h : tl ≠ []) ↦ (List.getLast_cons h) ▸ h_ne_zero
have ih := ih (w₂' h') w₁'
simp only [self_div_pow_eq_ofDigits_drop _ _ h, digits_ofDigits p h tl w₁' w₂',
- succ_eq_one_add] at ih
+ ←Nat.one_add] at ih
have := sum_singleton (fun x ↦ ofDigits p <| tl.drop x) tl.length
rw [← Ico_succ_singleton, List.drop_length, ofDigits] at this
have h₁ : 1 ≤ tl.length := List.length_pos.mpr h'
@@ -514,7 +514,7 @@ lemma ofDigits_div_eq_ofDigits_tail (hpos : 0 < p) (digits : List ℕ)
induction' digits with hd tl
· simp [ofDigits]
· refine' Eq.trans (add_mul_div_left hd _ hpos) _
- rw [Nat.div_eq_zero <| w₁ _ <| List.mem_cons_self _ _, zero_add]
+ rw [Nat.div_eq_of_lt <| w₁ _ <| List.mem_cons_self _ _, zero_add]
rfl
/-- Interpreting as a base `p` number and dividing by `p^i` is the same as dropping `i`.
Some deleted lemmas have been upstreamed to Std.
Note that the statements of List.zipWith_map_left
(and _right
) have been changed, requiring slight changes here.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: sgouezel <sebastien.gouezel@univ-rennes1.fr>
@@ -172,10 +172,10 @@ theorem ofDigits_eq_foldr {α : Type*} [Semiring α] (b : α) (L : List ℕ) :
#align nat.of_digits_eq_foldr Nat.ofDigits_eq_foldr
theorem ofDigits_eq_sum_map_with_index_aux (b : ℕ) (l : List ℕ) :
- ((List.range l.length).zipWith ((fun i a : ℕ => a * b ^ i) ∘ succ) l).sum =
+ ((List.range l.length).zipWith ((fun i a : ℕ => a * b ^ (i + 1))) l).sum =
b * ((List.range l.length).zipWith (fun i a => a * b ^ i) l).sum := by
suffices
- (List.range l.length).zipWith ((fun i a : ℕ => a * b ^ i) ∘ succ) l =
+ (List.range l.length).zipWith (fun i a : ℕ => a * b ^ (i + 1)) l =
(List.range l.length).zipWith (fun i a => b * (a * b ^ i)) l
by simp [this]
congr; ext; simp [pow_succ]; ring
This seems more useful once the theory is set up. Previously
Nat.digits 10 (n + 1) = l
would simp to
(n + 1) % (8 + 2) :: Nat.digits (8 + 2) ((n + 1) / (8 + 2)) = l
now it simps to
(n + 1) % 10 :: Nat.digits 10 ((n + 1) / 10) = l
@@ -115,12 +115,16 @@ theorem digits_one_succ (n : ℕ) : digits 1 (n + 1) = 1 :: digits 1 n :=
rfl
#align nat.digits_one_succ Nat.digits_one_succ
-@[simp]
theorem digits_add_two_add_one (b n : ℕ) :
digits (b + 2) (n + 1) = ((n + 1) % (b + 2)) :: digits (b + 2) ((n + 1) / (b + 2)) := by
simp [digits, digitsAux_def]
#align nat.digits_add_two_add_one Nat.digits_add_two_add_one
+@[simp]
+lemma digits_of_two_le_of_pos {b : ℕ} (hb : 2 ≤ b) (hn : 0 < n) :
+ Nat.digits b n = n % b :: Nat.digits b (n / b) := by
+ rw [Nat.eq_add_of_sub_eq hb rfl, Nat.eq_add_of_sub_eq hn rfl, Nat.digits_add_two_add_one]
+
theorem digits_def' :
∀ {b : ℕ} (_ : 1 < b) {n : ℕ} (_ : 0 < n), digits b n = (n % b) :: digits b (n / b)
| 0, h => absurd h (by decide)
@@ -594,7 +598,7 @@ theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1
· rw [digits_def' one_lt_two]
· simpa [Nat.bit, Nat.bit0_val n]
· simpa [pos_iff_ne_zero, bit_eq_zero_iff]
- · simpa [Nat.bit, Nat.bit1_val n, add_comm, digits_add 2 one_lt_two 1 n]
+ · simpa [Nat.bit, Nat.bit1_val n, add_comm, digits_add 2 one_lt_two 1 n, Nat.add_mul_div_left]
#align nat.digits_two_eq_bits Nat.digits_two_eq_bits
/-! ### Modular Arithmetic -/
Also fix implicitness of arguments to Finset.sum_singleton
.
@@ -552,7 +552,7 @@ theorem sub_one_mul_sum_div_pow_eq_sub_sum_digits
have ih := ih (w₂' h') w₁'
simp only [self_div_pow_eq_ofDigits_drop _ _ h, digits_ofDigits p h tl w₁' w₂',
succ_eq_one_add] at ih
- have := @sum_singleton _ _ tl.length (fun x => ofDigits p <| tl.drop x) _
+ have := sum_singleton (fun x ↦ ofDigits p <| tl.drop x) tl.length
rw [← Ico_succ_singleton, List.drop_length, ofDigits] at this
have h₁ : 1 ≤ tl.length := List.length_pos.mpr h'
rw [← sum_range_add_sum_Ico _ <| h₁, ← add_zero (∑ x in Ico _ _, ofDigits p (tl.drop x)),
@@ -569,7 +569,7 @@ theorem sub_one_mul_sum_div_pow_eq_sub_sum_digits
· simp [ofDigits]
theorem sub_one_mul_sum_log_div_pow_eq_sub_sum_digits (n : ℕ) :
- (p - 1) * ∑ i in range (log p n).succ, n / p ^ i.succ = n - (p.digits n).sum := by
+ (p - 1) * ∑ i in range (log p n).succ, n / p ^ i.succ = n - (p.digits n).sum := by
obtain h | rfl | h : 1 < p ∨ 1 = p ∨ p < 1 := trichotomous 1 p
· rcases eq_or_ne n 0 with rfl | hn
· simp
Similar to Nat.ofDigits_digits_append_digits
, but with a digits
on the RHS instead of an ofDigits
on the LHS.
@@ -426,6 +426,19 @@ theorem ofDigits_digits_append_digits {b m n : ℕ} :
rw [ofDigits_append, ofDigits_digits, ofDigits_digits]
#align nat.of_digits_digits_append_digits Nat.ofDigits_digits_append_digits
+theorem digits_append_digits {b m n : ℕ} (hb : 0 < b) :
+ digits b n ++ digits b m = digits b (n + b ^ (digits b n).length * m) := by
+ rcases eq_or_lt_of_le (Nat.succ_le_of_lt hb) with (rfl | hb)
+ · simp [List.replicate_add]
+ rw [← ofDigits_digits_append_digits]
+ refine' (digits_ofDigits b hb _ (fun l hl => _) (fun h_append => _)).symm
+ · rcases (List.mem_append.mp hl) with (h | h) <;> exact digits_lt_base hb h
+ · by_cases digits b m = []
+ · simp only [h, List.append_nil] at h_append ⊢
+ exact getLast_digit_ne_zero b <| digits_ne_nil_iff_ne_zero.mp h_append
+ · exact (List.getLast_append' _ _ h) ▸
+ (getLast_digit_ne_zero _ <| digits_ne_nil_iff_ne_zero.mp h)
+
theorem digits_len_le_digits_len_succ (b n : ℕ) :
(digits b n).length ≤ (digits b (n + 1)).length := by
rcases Decidable.eq_or_ne n 0 with (rfl | hn)
Autoimplicits are highly controversial and also defeat the performance-improving work in #6474.
The intent of this PR is to make autoImplicit
opt-in on a per-file basis, by disabling it in the lakefile and enabling it again with set_option autoImplicit true
in the few files that rely on it.
That also keeps this PR small, as opposed to attempting to "fix" files to not need it any more.
I claim that many of the uses of autoImplicit
in these files are accidental; situations such as:
variables
are in scope, but pasting the lemma in the wrong sectionHaving set_option autoImplicit false
as the default prevents these types of mistake being made in the 90% of files where autoImplicit
s are not used at all, and causes them to be caught by CI during review.
I think there were various points during the port where we encouraged porters to delete the universes u v
lines; I think having autoparams for universe variables only would cover a lot of the cases we actually use them, while avoiding any real shortcomings.
A Zulip poll (after combining overlapping votes accordingly) was in favor of this change with 5:5:18
as the no:dontcare:yes
vote ratio.
While this PR was being reviewed, a handful of files gained some more likely-accidental autoImplicits. In these places, set_option autoImplicit true
has been placed locally within a section, rather than at the top of the file.
@@ -29,6 +29,8 @@ A basic `norm_digits` tactic is also provided for proving goals of the form
`Nat.digits a b = l` where `a` and `b` are numerals.
-/
+set_option autoImplicit true
+
namespace Nat
@@ -10,6 +10,7 @@ import Mathlib.Data.List.BigOperators.Lemmas
import Mathlib.Data.List.Indexes
import Mathlib.Data.List.Palindrome
import Mathlib.Algebra.Parity
+import Mathlib.Algebra.BigOperators.Intervals
import Mathlib.Tactic.IntervalCases
import Mathlib.Tactic.Linarith
@@ -516,6 +517,56 @@ lemma self_div_pow_eq_ofDigits_drop (i n : ℕ) (h : 2 ≤ p):
(fun l hl ↦ digits_lt_base h hl)
exact (ofDigits_digits p n).symm
+open BigOperators Finset
+
+theorem sub_one_mul_sum_div_pow_eq_sub_sum_digits
+ (L : List ℕ) {h_nonempty} (h_ne_zero : L.getLast h_nonempty ≠ 0) (h_lt : ∀ l ∈ L, l < p) :
+ (p - 1) * ∑ i in range L.length, (ofDigits p L) / p ^ i.succ = (ofDigits p L) - L.sum := by
+ obtain h | rfl | h : 1 < p ∨ 1 = p ∨ p < 1 := trichotomous 1 p
+ · induction' L with hd tl ih
+ · simp [ofDigits]
+ · simp only [List.length_cons, List.sum_cons, self_div_pow_eq_ofDigits_drop _ _ h,
+ digits_ofDigits p h (hd :: tl) h_lt (fun _ => h_ne_zero)]
+ simp only [ofDigits]
+ rw [sum_range_succ, Nat.cast_id]
+ simp only [List.drop, List.drop_length]
+ obtain rfl | h' := em <| tl = []
+ · simp [ofDigits]
+ · have w₁' := fun l hl ↦ h_lt l <| List.mem_cons_of_mem hd hl
+ have w₂' := fun (h : tl ≠ []) ↦ (List.getLast_cons h) ▸ h_ne_zero
+ have ih := ih (w₂' h') w₁'
+ simp only [self_div_pow_eq_ofDigits_drop _ _ h, digits_ofDigits p h tl w₁' w₂',
+ succ_eq_one_add] at ih
+ have := @sum_singleton _ _ tl.length (fun x => ofDigits p <| tl.drop x) _
+ rw [← Ico_succ_singleton, List.drop_length, ofDigits] at this
+ have h₁ : 1 ≤ tl.length := List.length_pos.mpr h'
+ rw [← sum_range_add_sum_Ico _ <| h₁, ← add_zero (∑ x in Ico _ _, ofDigits p (tl.drop x)),
+ ← this, sum_Ico_consecutive _ h₁ <| le_succ tl.length, ← sum_Ico_add _ 0 tl.length 1,
+ Ico_zero_eq_range, mul_add, mul_add, ih, range_one, sum_singleton, List.drop, ofDigits,
+ mul_zero, add_zero, ← Nat.add_sub_assoc <| sum_le_ofDigits _ <| Nat.le_of_lt h]
+ nth_rw 2 [← one_mul <| ofDigits p tl]
+ rw [← add_mul, one_eq_succ_zero, Nat.sub_add_cancel <| zero_lt_of_lt h,
+ Nat.add_sub_add_left]
+ · simp [ofDigits_one]
+ · simp [lt_one_iff.mp h]
+ cases L
+ · simp
+ · simp [ofDigits]
+
+theorem sub_one_mul_sum_log_div_pow_eq_sub_sum_digits (n : ℕ) :
+ (p - 1) * ∑ i in range (log p n).succ, n / p ^ i.succ = n - (p.digits n).sum := by
+ obtain h | rfl | h : 1 < p ∨ 1 = p ∨ p < 1 := trichotomous 1 p
+ · rcases eq_or_ne n 0 with rfl | hn
+ · simp
+ · convert sub_one_mul_sum_div_pow_eq_sub_sum_digits (p.digits n) (getLast_digit_ne_zero p hn) <|
+ (fun l a ↦ digits_lt_base h a)
+ · refine' (digits_len p n h hn).symm
+ all_goals exact (ofDigits_digits p n).symm
+ · simp
+ · simp [lt_one_iff.mp h]
+ cases n
+ all_goals simp
+
/-! ### Binary -/
@@ -443,6 +443,9 @@ theorem ofDigits_monotone {p q : ℕ} (L : List ℕ) (h : p ≤ q) : ofDigits p
· simp only [ofDigits, cast_id, add_le_add_iff_left]
exact Nat.mul_le_mul h hi
+theorem sum_le_ofDigits (L : List ℕ) (h: 1 ≤ p) : L.sum ≤ ofDigits p L :=
+ (ofDigits_one L).symm ▸ ofDigits_monotone L h
+
theorem digit_sum_le (p n : ℕ) : List.sum (digits p n) ≤ n := by
induction' n with n
· exact digits_zero _ ▸ Nat.le_refl (List.sum [])
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -151,12 +151,12 @@ theorem digits_add (b : ℕ) (h : 1 < b) (x y : ℕ) (hxb : x < b) (hxy : x ≠
/-- `ofDigits b L` takes a list `L` of natural numbers, and interprets them
as a number in semiring, as the little-endian digits in base `b`.
-/
-def ofDigits {α : Type _} [Semiring α] (b : α) : List ℕ → α
+def ofDigits {α : Type*} [Semiring α] (b : α) : List ℕ → α
| [] => 0
| h :: t => h + b * ofDigits b t
#align nat.of_digits Nat.ofDigits
-theorem ofDigits_eq_foldr {α : Type _} [Semiring α] (b : α) (L : List ℕ) :
+theorem ofDigits_eq_foldr {α : Type*} [Semiring α] (b : α) (L : List ℕ) :
ofDigits b L = List.foldr (fun x y => ↑x + b * y) 0 L := by
induction' L with d L ih
· rfl
@@ -189,7 +189,7 @@ theorem ofDigits_singleton {b n : ℕ} : ofDigits b [n] = n := by simp [ofDigits
#align nat.of_digits_singleton Nat.ofDigits_singleton
@[simp]
-theorem ofDigits_one_cons {α : Type _} [Semiring α] (h : ℕ) (L : List ℕ) :
+theorem ofDigits_one_cons {α : Type*} [Semiring α] (h : ℕ) (L : List ℕ) :
ofDigits (1 : α) (h :: L) = h + ofDigits 1 L := by simp [ofDigits]
#align nat.of_digits_one_cons Nat.ofDigits_one_cons
@@ -202,7 +202,7 @@ theorem ofDigits_append {b : ℕ} {l1 l2 : List ℕ} :
#align nat.of_digits_append Nat.ofDigits_append
@[norm_cast]
-theorem coe_ofDigits (α : Type _) [Semiring α] (b : ℕ) (L : List ℕ) :
+theorem coe_ofDigits (α : Type*) [Semiring α] (b : ℕ) (L : List ℕ) :
((ofDigits b L : ℕ) : α) = ofDigits (b : α) L := by
induction' L with d L ih
· simp [ofDigits]
@@ -532,7 +532,7 @@ theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1
-- This is really a theorem about polynomials.
-theorem dvd_ofDigits_sub_ofDigits {α : Type _} [CommRing α] {a b k : α} (h : k ∣ a - b)
+theorem dvd_ofDigits_sub_ofDigits {α : Type*} [CommRing α] {a b k : α} (h : k ∣ a - b)
(L : List ℕ) : k ∣ ofDigits a L - ofDigits b L := by
induction' L with d L ih
· change k ∣ 0 - 0
@@ -484,6 +484,35 @@ theorem base_pow_length_digits_le (b m : ℕ) (hb : 1 < b) :
exact base_pow_length_digits_le' b m
#align nat.base_pow_length_digits_le Nat.base_pow_length_digits_le
+/-- Interpreting as a base `p` number and dividing by `p` is the same as interpreting the tail.
+-/
+lemma ofDigits_div_eq_ofDigits_tail (hpos : 0 < p) (digits : List ℕ)
+ (w₁ : ∀ l ∈ digits, l < p) : ofDigits p digits / p = ofDigits p digits.tail := by
+ induction' digits with hd tl
+ · simp [ofDigits]
+ · refine' Eq.trans (add_mul_div_left hd _ hpos) _
+ rw [Nat.div_eq_zero <| w₁ _ <| List.mem_cons_self _ _, zero_add]
+ rfl
+
+/-- Interpreting as a base `p` number and dividing by `p^i` is the same as dropping `i`.
+-/
+lemma ofDigits_div_pow_eq_ofDigits_drop
+ (i : ℕ) (hpos : 0 < p) (digits : List ℕ) (w₁ : ∀ l ∈ digits, l < p) :
+ ofDigits p digits / p ^ i = ofDigits p (digits.drop i) := by
+ induction' i with i hi
+ · simp
+ · rw [Nat.pow_succ, ← Nat.div_div_eq_div_mul, hi, ofDigits_div_eq_ofDigits_tail hpos
+ (List.drop i digits) <| fun x hx ↦ w₁ x <| List.mem_of_mem_drop hx, ← List.drop_one,
+ List.drop_drop, add_comm]
+
+/-- Dividing `n` by `p^i` is like truncating the first `i` digits of `n` in base `p`.
+-/
+lemma self_div_pow_eq_ofDigits_drop (i n : ℕ) (h : 2 ≤ p):
+ n / p ^ i = ofDigits p ((p.digits n).drop i) := by
+ convert ofDigits_div_pow_eq_ofDigits_drop i (zero_lt_of_lt h) (p.digits n)
+ (fun l hl ↦ digits_lt_base h hl)
+ exact (ofDigits_digits p n).symm
+
/-! ### Binary -/
@@ -2,11 +2,6 @@
Copyright (c) 2020 Scott Morrison. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Scott Morrison, Shing Tak Lam, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.nat.digits
-! leanprover-community/mathlib commit 369525b73f229ccd76a6ec0e0e0bf2be57599768
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Data.Int.ModEq
import Mathlib.Data.Nat.Bits
@@ -18,6 +13,8 @@ import Mathlib.Algebra.Parity
import Mathlib.Tactic.IntervalCases
import Mathlib.Tactic.Linarith
+#align_import data.nat.digits from "leanprover-community/mathlib"@"369525b73f229ccd76a6ec0e0e0bf2be57599768"
+
/-!
# Digits of a natural number
@@ -439,6 +439,22 @@ theorem le_digits_len_le (b n m : ℕ) (h : n ≤ m) : (digits b n).length ≤ (
monotone_nat_of_le_succ (digits_len_le_digits_len_succ b) h
#align nat.le_digits_len_le Nat.le_digits_len_le
+@[mono]
+theorem ofDigits_monotone {p q : ℕ} (L : List ℕ) (h : p ≤ q) : ofDigits p L ≤ ofDigits q L := by
+ induction' L with _ _ hi
+ · rfl
+ · simp only [ofDigits, cast_id, add_le_add_iff_left]
+ exact Nat.mul_le_mul h hi
+
+theorem digit_sum_le (p n : ℕ) : List.sum (digits p n) ≤ n := by
+ induction' n with n
+ · exact digits_zero _ ▸ Nat.le_refl (List.sum [])
+ · induction' p with p
+ · rw [digits_zero_succ, List.sum_cons, List.sum_nil, add_zero]
+ · nth_rw 2 [← ofDigits_digits p.succ n.succ]
+ rw [← ofDigits_one <| digits p.succ n.succ]
+ exact ofDigits_monotone (digits p.succ n.succ) <| Nat.succ_pos p
+
theorem pow_length_le_mul_ofDigits {b : ℕ} {l : List ℕ} (hl : l ≠ []) (hl2 : l.getLast hl ≠ 0) :
(b + 2) ^ l.length ≤ (b + 2) * ofDigits (b + 2) l := by
rw [← List.dropLast_append_getLast hl]
Co-authored-by: Komyyy <pol_tta@outlook.jp> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@anu.edu.au> Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>
@@ -352,10 +352,7 @@ theorem getLast_digit_ne_zero (b : ℕ) {m : ℕ} (hm : m ≠ 0) :
· cases m
· cases hm rfl
rename ℕ => m
- -- Porting note: Added `have`
- have : ∀ v, List.getLast (digits (succ zero) (succ v)) (by simp [digits, digitsAux1]) = 1 := by
- intros v; induction v <;> simp; assumption
- simp only [digits_one, List.getLast_replicate_succ m 1, this]
+ simp only [digits_one, List.getLast_replicate_succ m 1]
revert hm
apply Nat.strongInductionOn m
intro n IH hn
@@ -480,7 +477,7 @@ theorem base_pow_length_digits_le (b m : ℕ) (hb : 1 < b) :
theorem digits_two_eq_bits (n : ℕ) : digits 2 n = n.bits.map fun b => cond b 1 0 := by
induction' n using Nat.binaryRecFromOne with b n h ih
· simp
- · simp; trivial
+ · simp
rw [bits_append_bit _ _ fun hn => absurd hn h]
cases b
· rw [digits_def' one_lt_two]
This PR is the result of running
find . -type f -name "*.lean" -exec sed -i -E 's/^( +)\. /\1· /' {} \;
find . -type f -name "*.lean" -exec sed -i -E 'N;s/^( +·)\n +(.*)$/\1 \2/;P;D' {} \;
which firstly replaces .
focusing dots with ·
and secondly removes isolated instances of such dots, unifying them with the following line. A new rule is placed in the style linter to verify this.
@@ -310,7 +310,7 @@ theorem digits_eq_cons_digits_div {b n : ℕ} (h : 1 < b) (w : n ≠ 0) :
· norm_num at h
rcases n with (_ | n)
· norm_num at w
- . simp only [digits_add_two_add_one, ne_eq]
+ · simp only [digits_add_two_add_one, ne_eq]
#align nat.digits_eq_cons_digits_div Nat.digits_eq_cons_digits_div
theorem digits_getLast {b : ℕ} (m : ℕ) (h : 1 < b) (p q) :
@@ -381,8 +381,8 @@ theorem digits_lt_base' {b m : ℕ} : ∀ {d}, d ∈ digits (b + 2) m → d < b
-- Porting note: Previous code (single line) contained linarith.
-- . exact IH _ (Nat.div_lt_self (Nat.succ_pos _) (by linarith)) hd
· apply IH ((n + 1) / (b + 2))
- . apply Nat.div_lt_self <;> simp
- . assumption
+ · apply Nat.div_lt_self <;> simp
+ · assumption
#align nat.digits_lt_base' Nat.digits_lt_base'
/-- The digits in the base b expansion of n are all less than b, if b ≥ 2 -/
@@ -69,7 +69,7 @@ theorem digitsAux_def (b : ℕ) (h : 2 ≤ b) (n : ℕ) (w : 0 < n) :
/-- `digits b n` gives the digits, in little-endian order,
of a natural number `n` in a specified base `b`.
-In any base, we have `ofDigits b L = L.foldr (λ x y, x + b * y) 0`.
+In any base, we have `ofDigits b L = L.foldr (fun x y ↦ x + b * y) 0`.
* For any `2 ≤ b`, we have `l < b` for any `l ∈ digits b n`,
and the last digit is not zero.
This uniquely specifies the behaviour of `digits b`.
fix-comments.py
on all files.@@ -699,7 +699,7 @@ open Tactic
`a` and `b` are numerals.
```
-example : nat.digits 10 123 = [3,2,1] := by norm_num
+example : Nat.digits 10 123 = [3,2,1] := by norm_num
```
-/
@[norm_num]
by
s! (#3825)
This PR puts, with one exception, every single remaining by
that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh
. The exception is when the by
begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.
Essentially this is s/\n *by$/ by/g
, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated by
s".
@@ -429,8 +429,8 @@ theorem ofDigits_digits_append_digits {b m n : ℕ} :
rw [ofDigits_append, ofDigits_digits, ofDigits_digits]
#align nat.of_digits_digits_append_digits Nat.ofDigits_digits_append_digits
-theorem digits_len_le_digits_len_succ (b n : ℕ) : (digits b n).length ≤ (digits b (n + 1)).length :=
- by
+theorem digits_len_le_digits_len_succ (b n : ℕ) :
+ (digits b n).length ≤ (digits b (n + 1)).length := by
rcases Decidable.eq_or_ne n 0 with (rfl | hn)
· simp
cases' le_or_lt b 1 with hb hb
@@ -570,8 +570,7 @@ theorem ofDigits_neg_one :
∀ L : List ℕ, ofDigits (-1 : ℤ) L = (L.map fun n : ℕ => (n : ℤ)).alternatingSum
| [] => rfl
| [n] => by simp [ofDigits, List.alternatingSum]
- | a :: b :: t =>
- by
+ | a :: b :: t => by
simp only [ofDigits, List.alternatingSum, List.map_cons, ofDigits_neg_one t]
ring
#align nat.of_digits_neg_one Nat.ofDigits_neg_one
Enable the cancelDenoms
preprocessor in linarith
. Closes #2714.
Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: Patrick Massot <patrickmassot@free.fr> Co-authored-by: Floris van Doorn <fpvdoorn@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -633,10 +633,8 @@ namespace NormDigits
theorem digits_succ (b n m r l) (e : r + b * m = n) (hr : r < b)
(h : Nat.digits b m = l ∧ 1 < b ∧ 0 < m) : (Nat.digits b n = r :: l) ∧ 1 < b ∧ 0 < n := by
rcases h with ⟨h, b2, m0⟩
- -- Porting note: Below line was proved by `by linarith`
- have b0 : 0 < b := by simp_arith [lt_iff_le_and_ne.mp b2]
- -- Porting note: Below line was proved by `by linarith [mul_pos b0 m0]`
- have n0 : 0 < n := le_trans (lt_iff_add_one_le.mp (mul_pos b0 m0)) (e.subst (le_add_left _ r))
+ have b0 : 0 < b := by linarith
+ have n0 : 0 < n := by linarith [mul_pos b0 m0]
refine' ⟨_, b2, n0⟩
obtain ⟨rfl, rfl⟩ := (Nat.div_mod_unique b0).2 ⟨e, hr⟩
subst h; exact Nat.digits_def' b2 n0
congr!
and convert
(#2606)
congr!
, convert
, and convert_to
to control parts of the congruence algorithm, in particular transparency settings when applying congruence lemmas.congr!
now applies congruence lemmas with reducible transparency by default. This prevents it from unfolding definitions when applying congruence lemmas. It also now tries both the LHS-biased and RHS-biased simp congruence lemmas, with a configuration option to set which it should try first.HEq
congruence lemma generator that gives each hypothesis access to the proofs of previous hypotheses. This means that if you have an equality ⊢ ⟨a, x⟩ = ⟨b, y⟩
of sigma types, congr!
turns this into goals ⊢ a = b
and ⊢ a = b → HEq x y
(note that congr!
will also auto-introduce a = b
for you in the second goal). This congruence lemma generator applies to more cases than the simp congruence lemma generator does.congr!
(and hence convert
) are more careful about applying lemmas that don't force definitions to unfold. There were a number of cases in mathlib where the implementation of congr
was being abused to unfold definitions.set_option trace.congr! true
you can see what congr!
sees when it is deciding on congruence lemmas.convert_to
to do using 1
when there is no using
clause, to match its documentation.Note that congr!
is more capable than congr
at finding a way to equate left-hand sides and right-hand sides, so you will frequently need to limit its depth with a using
clause. However, there is also a new heuristic to prevent considering unlikely-to-be-provable type equalities (controlled by the typeEqs
option), which can help limit the depth automatically.
There is also a predefined configuration that you can invoke with, for example, convert (config := .unfoldSameFun) h
, that causes it to behave more like congr
, including using default transparency when unfolding.
@@ -450,7 +450,7 @@ theorem pow_length_le_mul_ofDigits {b : ℕ} {l : List ℕ} (hl : l ≠ []) (hl2
apply Nat.mul_le_mul_left
refine' le_trans _ (Nat.le_add_left _ _)
have : 0 < l.getLast hl := by rwa [pos_iff_ne_zero]
- convert Nat.mul_le_mul_left ((b + 2) ^ (l.length - 1)) this
+ convert Nat.mul_le_mul_left ((b + 2) ^ (l.length - 1)) this using 1
rw [Nat.mul_one]
#align nat.pow_length_le_mul_of_digits Nat.pow_length_le_mul_ofDigits
@@ -544,7 +544,8 @@ theorem modEq_digits_sum (b b' : ℕ) (h : b' % b = 1) (n : ℕ) : n ≡ (digits
congr
· skip
· rw [← ofDigits_digits b' n]
- convert ofDigits_modEq b' b (digits b' n) <;> exact h.symm
+ convert ofDigits_modEq b' b (digits b' n)
+ exact h.symm
#align nat.modeq_digits_sum Nat.modEq_digits_sum
theorem modEq_three_digits_sum (n : ℕ) : n ≡ (digits 10 n).sum [MOD 3] :=
@@ -502,7 +502,7 @@ theorem dvd_ofDigits_sub_ofDigits {α : Type _} [CommRing α] {a b k : α} (h :
exact dvd_mul_sub_mul h ih
#align nat.dvd_of_digits_sub_of_digits Nat.dvd_ofDigits_sub_ofDigits
-theorem ofDigits_modeq' (b b' : ℕ) (k : ℕ) (h : b ≡ b' [MOD k]) (L : List ℕ) :
+theorem ofDigits_modEq' (b b' : ℕ) (k : ℕ) (h : b ≡ b' [MOD k]) (L : List ℕ) :
ofDigits b L ≡ ofDigits b' L [MOD k] := by
induction' L with d L ih
· rfl
@@ -510,10 +510,10 @@ theorem ofDigits_modeq' (b b' : ℕ) (k : ℕ) (h : b ≡ b' [MOD k]) (L : List
dsimp [Nat.ModEq] at *
conv_lhs => rw [Nat.add_mod, Nat.mul_mod, h, ih]
conv_rhs => rw [Nat.add_mod, Nat.mul_mod]
-#align nat.of_digits_modeq' Nat.ofDigits_modeq'
+#align nat.of_digits_modeq' Nat.ofDigits_modEq'
theorem ofDigits_modEq (b k : ℕ) (L : List ℕ) : ofDigits b L ≡ ofDigits (b % k) L [MOD k] :=
- ofDigits_modeq' b (b % k) k (b.mod_modEq k).symm L
+ ofDigits_modEq' b (b % k) k (b.mod_modEq k).symm L
#align nat.of_digits_modeq Nat.ofDigits_modEq
theorem ofDigits_mod (b k : ℕ) (L : List ℕ) : ofDigits b L % k = ofDigits (b % k) L % k :=
The unported dependencies are