AFTD Auto-Formalizing Theoretical Domains

greedy_distinct_diff_seq_surjective

theoremverifiedoriginal

Conjecture: for any distinct positive integers a₁, a₂, the greedy sequence with distinct consecutive differences started at a₁, a₂ takes every positive integer as a value (it is a permutation of the positive integers).

Statement

theorem greedy_distinct_diff_seq_surjective (a₁ a₂ : ℕ) (h₁ : 0 < a₁) (h₂ : 0 < a₂)
    (h : a₁ ≠ a₂) : ∀ v, 0 < v → ∃ n, greedy_distinct_diff_seq a₁ a₂ n = v
Related work
List entry OP-203, a question proposed here from arXiv:2610.15860 (A note on the Slater–Vélez permutation), which works with the start a₁ = 1, a₂ = 2, for which Slater and Vélez (1977) proved the sequence is a permutation; the paper does not ask about other starts.
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • greedy_distinct_diff_seqThe greedy sequence with distinct consecutive differences started at a₁, a₂ (term 0 is a₁, term 1 is a₂; each later term is the least…
  • greedy_distinct_diff_nextGiven the terms so far (most recent first), the next greedy term: the least positive integer not used yet whose absolute difference with…
  • greedy_distinct_diff_historyThe first n + 2 terms of the greedy sequence started at a₁, a₂, most recent first.
Used by 1

The proof, explained

We prove by contradiction that the greedy sequence with distinct consecutive differences is surjective. If a positive integer v were never attained, then whenever the sequence exceeds v, the distance to v must belong to the set of past differences D(k). Consequently, once all sequence values stay above v, no new maximum difference can ever be created, bounding the elements of D(k) by a constant. But D(k) contains k distinct differences, which cannot fit into a bounded set for large k, giving a contradiction.

  1. History is the reverse range mapped by sequence

    By induction on n.

    lines 13–23

      induction n with
      | zero => rfl
      | succ n ih =>
        rw [greedy_distinct_diff_history]
        rw [show (n+1)+2 = (n+2)+1 from by ring]
        rw [List.range_succ, List.reverse_append, List.reverse_singleton]
        simp only [List.map_cons, List.singleton_append]
        have hnext : greedy_distinct_diff_next (greedy_distinct_diff_history a₁ a₂ n)
            = greedy_distinct_diff_seq a₁ a₂ (n+2) := by
          simp [greedy_distinct_diff_seq, greedy_distinct_diff_history]
        rw [hnext, ih]
  2. Membership in history corresponds to index at most n+1

    Unfolding the map and range.

    lines 28–36

      rw [greedy_distinct_diff_seq_surjective_hist_eq, List.mem_map]
      constructor
      · rintro ⟨a, ha, rfl⟩
        rw [List.mem_reverse, List.mem_range] at ha
        exact ⟨a, by omega, rfl⟩
      · rintro ⟨i, hi, rfl⟩
        refine ⟨i, ?_, rfl⟩
        rw [List.mem_reverse, List.mem_range]
        omega
  3. History head is the latest element

    Splitting the head element from the range.

    lines 42–45

      rw [greedy_distinct_diff_seq_surjective_hist_eq]
      rw [show n+2 = (n+1)+1 from rfl, List.range_succ, List.reverse_append,
          List.reverse_singleton]
      simp
  4. Difference list recursive cons structure

    By definition of difference list and history.

    lines 51–64

      unfold greedy_distinct_diff_seq_surjective_difflist greedy_distinct_diff_seq_surjective_gd
      have hnext : greedy_distinct_diff_next (greedy_distinct_diff_history a₁ a₂ n)
          = greedy_distinct_diff_seq a₁ a₂ (n+2) := by
        simp [greedy_distinct_diff_seq, greedy_distinct_diff_history]
      have hh : greedy_distinct_diff_history a₁ a₂ (n+1)
          = greedy_distinct_diff_seq a₁ a₂ (n+2) ::
            greedy_distinct_diff_history a₁ a₂ n := by
        rw [show greedy_distinct_diff_history a₁ a₂ (n+1)
            = greedy_distinct_diff_next (greedy_distinct_diff_history a₁ a₂ n) ::
              greedy_distinct_diff_history a₁ a₂ n from rfl, hnext]
      rw [hh, List.tail_cons]
      rw [greedy_distinct_diff_seq_surjective_hist_head_eq a₁ a₂ n]
      rw [List.zip_cons_cons, List.tail_cons]
      simp only [List.map_cons]
  5. Base case of difference list

    By definition for n=0.

    lines 69–70

      unfold greedy_distinct_diff_seq_surjective_difflist greedy_distinct_diff_seq_surjective_gd
      rfl
  6. Membership in difference list corresponds to consecutive difference index

    By induction on n.

    lines 75–94

      induction n with
      | zero =>
        rw [greedy_distinct_diff_seq_surjective_difflist_zero, List.mem_singleton]
        constructor
        · intro h; exact ⟨0, by omega, h⟩
        · rintro ⟨i, hi, he⟩
          rw [show i = 0 by omega] at he
          exact he
      | succ n ih =>
        rw [greedy_distinct_diff_seq_surjective_difflist_cons, List.mem_cons, ih]
        constructor
        · rintro (h | ⟨i, hi, he⟩)
          · exact ⟨n+1, by omega, h⟩
          · exact ⟨i, by omega, he⟩
        · rintro ⟨i, hi, he⟩
          rcases Nat.lt_or_ge i (n+1) with h' | h'
          · exact Or.inr ⟨i, h', he⟩
          · have hi' : i = n+1 := by omega
            rw [hi'] at he
            exact Or.inl he
  7. Candidate set for next greedy value is nonempty

    An explicit large integer satisfies all conditions.

    lines 100–113

      set ds := (l.zip l.tail).map (fun p => Int.natAbs ((p.1:ℤ) - (p.2:ℤ))) with hds
      refine ⟨l.sum + ds.sum + l.headD 0 + 1, ?_, ?_, ?_⟩
      · omega
      · intro hmem; have h := List.le_sum_of_mem hmem; omega
      · intro hmem
        have hle : l.headD 0 ≤ l.sum + ds.sum + l.headD 0 + 1 := by omega
        have hn : Int.natAbs (((l.sum + ds.sum + l.headD 0 + 1:ℕ):ℤ) - ((l.headD 0:ℕ):ℤ))
            = (l.sum + ds.sum + l.headD 0 + 1) - l.headD 0 := by
          have hcast : (((l.sum + ds.sum + l.headD 0 + 1):ℕ):ℤ) - ((l.headD 0:ℕ):ℤ)
              = (((l.sum + ds.sum + l.headD 0 + 1) - l.headD 0 : ℕ):ℤ) := by
            rw [Nat.cast_sub hle]
          rw [hcast, Int.natAbs_natCast]
        rw [hn] at hmem
        have h := List.le_sum_of_mem hmem; omega
  8. Specification of the greedy choice at step n+2

    The next value is the minimal valid candidate.

    lines 127–171

      set x := greedy_distinct_diff_seq a₁ a₂ with hxdef
      have hx : x (n+2) = greedy_distinct_diff_next (greedy_distinct_diff_history a₁ a₂ n) := by
        rw [hxdef]; simp [greedy_distinct_diff_seq, greedy_distinct_diff_history]
      set l := greedy_distinct_diff_history a₁ a₂ n with hl
      set S := {c : ℕ | 0 < c ∧ c ∉ l ∧
          Int.natAbs ((c:ℤ) - ((l.headD 0):ℤ)) ∉
            (l.zip l.tail).map (fun p => Int.natAbs ((p.1:ℤ) - (p.2:ℤ)))} with hS
      have hheadD : l.headD 0 = x (n+1) := by rw [hxdef]; rfl
      have hne : S.Nonempty := greedy_distinct_diff_seq_surjective_greedy_next_nonempty l
      have hmem : sInf S ∈ S := Nat.sInf_mem hne
      have hxS : x (n+2) = sInf S := by rw [hx]; rfl
      have hmemV : ∀ c, (c ∈ l ↔ c ∈ (Finset.range (n+2)).image x) := by
        intro c
        rw [hl, hxdef, greedy_distinct_diff_seq_surjective_hist_mem]
        simp only [Finset.mem_image, Finset.mem_range]
        constructor
        · rintro ⟨i, hi, h⟩; exact ⟨i, by omega, h⟩
        · rintro ⟨i, hi, h⟩; exact ⟨i, by omega, h⟩
      have hmemD : ∀ e, (e ∈ greedy_distinct_diff_seq_surjective_difflist a₁ a₂ n ↔
          e ∈ (Finset.range (n+1)).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂)) := by
        intro e
        rw [greedy_distinct_diff_seq_surjective_difflist_mem]
        simp only [Finset.mem_image, Finset.mem_range]
        constructor
        · rintro ⟨i, hi, h⟩; exact ⟨i, by omega, h.symm⟩
        · rintro ⟨i, hi, h⟩; exact ⟨i, by omega, h.symm⟩
      refine ⟨hx, ?_, ?_, ?_, ?_⟩
      · rw [hxS]; exact hmem.1
      · rw [← hmemV, hxS]; exact hmem.2.1
      · rw [← hmemD]
        have heq : greedy_distinct_diff_seq_surjective_gd a₁ a₂ (n+1)
            = Int.natAbs ((((sInf S : ℕ)):ℤ) - ((l.headD 0):ℤ)) := by
          unfold greedy_distinct_diff_seq_surjective_gd
          rw [← hxdef, hxS, hheadD]
        rw [heq]
        exact hmem.2.2
      · intro c hc0 hcV hcD
        have hcS : c ∈ S := by
          refine ⟨hc0, ?_, ?_⟩
          · rw [hmemV]; exact hcV
          · show Int.natAbs ((c:ℤ) - ((x (n+1)):ℤ)) ∉ greedy_distinct_diff_seq_surjective_difflist a₁ a₂ n
            rw [hmemD]; exact hcD
        have hle := Nat.sInf_le hcS
        rw [← hxS] at hle
        exact hle
  9. Absolute difference simplification when a <= b

    Casting to integers and back.

    lines 175–177

      have hcast : ((b:ℤ) - (a:ℤ)) = ((b - a : ℕ):ℤ) := by
        rw [Nat.cast_sub h]
      rw [hcast, Int.natAbs_natCast]
  10. Absolute difference |v - n| = n - v when v <= n

    Using symmetry of absolute value.

    lines 181–182

      have e : ((v:ℤ) - (n:ℤ)) = -(((n:ℤ) - (v:ℤ))) := by ring
      rw [e, Int.natAbs_neg, greedy_distinct_diff_seq_surjective_natAbs_sub_nat h]
  11. Absolute difference is bounded by M when both terms are <= M

    By cases on the comparison between a and b.

    lines 186–190

      rcases le_total a b with hab | hab
      · rw [greedy_distinct_diff_seq_surjective_natAbs_sub_nat hab]; omega
      · rw [show Int.natAbs ((b:ℤ) - (a:ℤ)) = Int.natAbs ((a:ℤ) - (b:ℤ)) from by
            rw [← Int.natAbs_neg]; congr 1; ring]
        rw [greedy_distinct_diff_seq_surjective_natAbs_sub_nat hab]; omega
  12. Greedy step specification reindexed for k >= 1

    Instantiating the previous specification at k-1.

    lines 199–208

      obtain ⟨-, h2, h3, h4, h5⟩ := greedy_distinct_diff_seq_surjective_spec a₁ a₂ (k-1)
      have e1 : k - 1 + 2 = k + 1 := by omega
      have e2 : k - 1 + 1 = k := by omega
      refine ⟨?_, ?_, ?_, ?_⟩
      · rw [e1] at h2; exact h2
      · rw [e1] at h3; exact h3
      · rw [e2] at h4; exact h4
      · intro c hc hcv hcd
        have h := h5 c hc (by rw [e1]; exact hcv) (by rw [e2]; exact hcd)
        rw [e1] at h; exact h
  13. Assume for contradiction that positive integer v is never attained

    Setting up the sequence and the sets of past differences.

    lines 212–223

      intro v hv
      by_contra hcon
      push_neg at hcon
      set x := greedy_distinct_diff_seq a₁ a₂ with hxdef
      set D : ℕ → Finset ℕ := fun k => (Finset.range k).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂) with hDdef
      have hx0 : x 0 = a₁ := by rw [hxdef]; rfl
      have hx1 : x 1 = a₂ := by rw [hxdef]; rfl
      have hvmiss : ∀ m, v ∉ (Finset.range m).image x := by
        intro m hm
        rw [Finset.mem_image] at hm
        obtain ⟨i, -, hi⟩ := hm
        exact hcon i hi
  14. Difference with missed value v must be in past differences

    Otherwise v would have been chosen by greediness.

    lines 224–234

      have hA : ∀ k, 1 ≤ k → x (k+1) > v → Int.natAbs ((v:ℤ) - ((x k:ℤ))) ∈ D k := by
        intro k hk hgt
        by_contra hnot
        have h4 := (greedy_distinct_diff_seq_surjective_spec_one a₁ a₂ k hk).2.2.2
        have hle : x (k+1) ≤ v := h4 v hv (hvmiss (k+1)) hnot
        exact absurd hle (not_le.mpr hgt)
      have hA' : ∀ k, 1 ≤ k → x k > v → x (k+1) > v → x k - v ∈ D k := by
        intro k hk hxk hgt
        have hh := hA k hk hgt
        rw [show Int.natAbs ((v:ℤ) - ((x k:ℤ))) = x k - v from greedy_distinct_diff_seq_surjective_natAbs_v_sub (le_of_lt hxk)] at hh
        exact hh
  15. Consecutive differences bounded by previous maximum difference

    Analyzing whether the difference with v is an old or new difference.

    lines 235–267

      have hDsucc : ∀ k, D (k+1) = D k ∪ {greedy_distinct_diff_seq_surjective_gd a₁ a₂ k} := by
        intro k
        show (Finset.range (k+1)).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂)
            = (Finset.range k).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂) ∪ {greedy_distinct_diff_seq_surjective_gd a₁ a₂ k}
        rw [Finset.range_add_one, Finset.image_insert, Finset.insert_eq, Finset.union_comm]
      have hB : ∀ k, 1 ≤ k → x k > v → x (k+1) > v → x (k+2) > v →
          greedy_distinct_diff_seq_surjective_gd a₁ a₂ k ≤ (D k).sup id := by
        intro k hk hx1 hx2 hx3
        have ha : x k - v ∈ D k := hA' k hk hx1 hx2
        have hb : x (k+1) - v ∈ D (k+1) := hA' (k+1) (by omega) hx2 hx3
        have hapos : 0 < x k - v := by omega
        have hd_eq : greedy_distinct_diff_seq_surjective_gd a₁ a₂ k
            = Int.natAbs (((x (k+1) - v : ℕ):ℤ) - ((x k - v : ℕ):ℤ)) := by
          unfold greedy_distinct_diff_seq_surjective_gd
          congr 1
          have e1 : ((x (k+1) - v : ℕ):ℤ) = (x (k+1):ℤ) - (v:ℤ) := Nat.cast_sub (le_of_lt hx2)
          have e2 : ((x k - v : ℕ):ℤ) = (x k:ℤ) - (v:ℤ) := Nat.cast_sub (le_of_lt hx1)
          rw [e1, e2]; ring
        have hb' : x (k+1) - v ∈ D k ∪ {greedy_distinct_diff_seq_surjective_gd a₁ a₂ k} := by rw [← hDsucc]; exact hb
        rw [Finset.mem_union, Finset.mem_singleton] at hb'
        rcases hb' with hbD | hbgd
        · rw [hd_eq]
          exact greedy_distinct_diff_seq_surjective_natAbs_sub_le (Finset.le_sup (f := id) ha) (Finset.le_sup (f := id) hbD)
        · have hde : greedy_distinct_diff_seq_surjective_gd a₁ a₂ k
              = Int.natAbs (((greedy_distinct_diff_seq_surjective_gd a₁ a₂ k : ℕ):ℤ) - ((x k - v : ℕ):ℤ)) := by
            rw [hbgd] at hd_eq; exact hd_eq
          rw [hde]
          have haM : x k - v ≤ (D k).sup id := Finset.le_sup (f := id) ha
          by_contra hgt
          push_neg at hgt
          have hle : x k - v ≤ greedy_distinct_diff_seq_surjective_gd a₁ a₂ k := by omega
          rw [greedy_distinct_diff_seq_surjective_natAbs_sub_nat hle] at hde
          omega
  16. Injectivity of sequence and distinctness of differences

    Each value and difference is new, so |D(k)| = k.

    lines 268–311

      have hx_out : ∀ m, 1 ≤ m → x m ∉ (Finset.range m).image x := by
        intro m hm
        rcases eq_or_lt_of_le hm with hm1 | hm2
        · subst hm1
          intro hmem
          rw [Finset.range_one, Finset.image_singleton, Finset.mem_singleton] at hmem
          rw [hx1, hx0] at hmem
          exact h hmem.symm
        · have hs := (greedy_distinct_diff_seq_surjective_spec_one a₁ a₂ (m-1) (by omega)).2.1
          have e : m - 1 + 1 = m := by omega
          rw [e] at hs
          exact hs
      have hx_ne : ∀ i j, i < j → x i ≠ x j := by
        intro i j hij heq
        have hj : 1 ≤ j := by omega
        have hout := hx_out j hj
        have hin : x i ∈ (Finset.range j).image x := by
          rw [Finset.mem_image]; exact ⟨i, Finset.mem_range.mpr hij, rfl⟩
        exact hout (heq ▸ hin)
      have hinj : Function.Injective x := by
        intro i j heq
        rcases Nat.lt_trichotomy i j with hij | hij | hij
        · exact absurd heq (hx_ne i j hij)
        · exact hij
        · exact absurd heq.symm (hx_ne j i hij)
      have hgd_ne : ∀ i j, i < j → greedy_distinct_diff_seq_surjective_gd a₁ a₂ i ≠ greedy_distinct_diff_seq_surjective_gd a₁ a₂ j := by
        intro i j hij heq
        have hj : 1 ≤ j := by omega
        have hs : greedy_distinct_diff_seq_surjective_gd a₁ a₂ j ∉ D j := (greedy_distinct_diff_seq_surjective_spec_one a₁ a₂ j hj).2.2.1
        have hi : greedy_distinct_diff_seq_surjective_gd a₁ a₂ i ∈ D j := by
          show greedy_distinct_diff_seq_surjective_gd a₁ a₂ i ∈ (Finset.range j).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂)
          exact Finset.mem_image.mpr ⟨i, Finset.mem_range.mpr hij, rfl⟩
        rw [← heq] at hs
        exact hs hi
      have hDcard : ∀ k, (D k).card = k := by
        intro k
        show ((Finset.range k).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂)).card = k
        rw [Finset.card_image_of_injOn, Finset.card_range]
        intro i hi j hj heq
        simp only [Finset.mem_coe, Finset.mem_range] at hi hj
        rcases Nat.lt_trichotomy i j with hlt | hlt | hlt
        · exact absurd heq (hgd_ne i j hlt)
        · exact hlt
        · exact absurd heq.symm (hgd_ne j i hlt)
  17. Sequence values eventually exceed v

    Finitely many values can be at most v by injectivity.

    lines 312–330

      classical
      set idx : ℕ → ℕ := fun m => if hh : ∃ k, x k = m then Classical.choose hh else 0 with hidx
      have hidx_eq : ∀ m k, x k = m → idx m = k := by
        intro m k hk
        have hex : ∃ j, x j = m := ⟨k, hk⟩
        have hchoose : x (Classical.choose hex) = m := Classical.choose_spec hex
        have hck : Classical.choose hex = k := hinj (by rw [hchoose, hk])
        simp only [idx, dif_pos hex, hck]
      have hK : ∃ K, ∀ k, K ≤ k → v < x k := by
        refine ⟨(Finset.range (v+1)).sup idx + 1, ?_⟩
        intro k hk
        by_contra hle
        push_neg at hle
        have hmem : x k ∈ Finset.range (v+1) := Finset.mem_range.mpr (by omega)
        have h1 : idx (x k) ≤ (Finset.range (v+1)).sup idx := Finset.le_sup hmem
        have h2 : idx (x k) = k := hidx_eq (x k) k rfl
        rw [h2] at h1
        omega
      obtain ⟨K, hK⟩ := hK
  18. Maximum past difference stabilizes after index K'

    The maximum cannot increase when all values exceed v.

    lines 331–346

      set K' := max K 2 with hK'
      have hstab : ∀ k, K' ≤ k → (D (k+1)).sup id = (D k).sup id := by
        intro k hk
        have hKk : K ≤ k := le_trans (le_max_left K 2) hk
        have hBk := hB k (by omega) (hK k hKk) (hK (k+1) (by omega)) (hK (k+2) (by omega))
        rw [hDsucc, Finset.sup_union, Finset.sup_singleton]
        exact max_eq_left hBk
      have hMconst : ∀ k, K' ≤ k → (D k).sup id = (D K').sup id := by
        intro k hk
        induction k with
        | zero => omega
        | succ k ih =>
          rcases Nat.lt_or_ge k K' with hlt | hge
          · have hk1 : k + 1 = K' := by omega
            rw [hk1]
          · rw [hstab k hge, ih hge]
  19. Contradiction from cardinality of past differences

    The size of D(k) grows without bound but is bounded by a constant.

    lines 347–359

      have hfinal : ∀ k, K' ≤ k → k ≤ (D K').sup id + 1 := by
        intro k hk
        have hsub : D k ⊆ Finset.range ((D K').sup id + 1) := by
          intro m hm
          rw [Finset.mem_range]
          have hle : m ≤ (D k).sup id := Finset.le_sup (f := id) hm
          rw [hMconst k hk] at hle
          omega
        have hc := Finset.card_le_card hsub
        rw [Finset.card_range, hDcard k] at hc
        exact hc
      have hcontra := hfinal (max K' ((D K').sup id + 2)) (le_max_left _ _)
      omega

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

noncomputable def greedy_distinct_diff_seq_surjective_gd (a₁ a₂ : ℕ) (i : ℕ) : ℕ :=  Int.natAbs (((greedy_distinct_diff_seq a₁ a₂ (i+1) : ℤ)) -    ((greedy_distinct_diff_seq a₁ a₂ i : ℤ)))noncomputable def greedy_distinct_diff_seq_surjective_difflist (a₁ a₂ : ℕ) (n : ℕ) : List ℕ :=  ((greedy_distinct_diff_history a₁ a₂ n).zip    (greedy_distinct_diff_history a₁ a₂ n).tail).map    (fun p => Int.natAbs ((p.1:ℤ) - (p.2:ℤ)))lemma greedy_distinct_diff_seq_surjective_hist_eq (a₁ a₂ : ℕ) (n : ℕ) :    greedy_distinct_diff_history a₁ a₂ n      = (List.range (n+2)).reverse.map (greedy_distinct_diff_seq a₁ a₂) := by  induction n with  | zero => rfl  | succ n ih =>    rw [greedy_distinct_diff_history]    rw [show (n+1)+2 = (n+2)+1 from by ring]    rw [List.range_succ, List.reverse_append, List.reverse_singleton]    simp only [List.map_cons, List.singleton_append]    have hnext : greedy_distinct_diff_next (greedy_distinct_diff_history a₁ a₂ n)        = greedy_distinct_diff_seq a₁ a₂ (n+2) := by      simp [greedy_distinct_diff_seq, greedy_distinct_diff_history]    rw [hnext, ih]lemma greedy_distinct_diff_seq_surjective_hist_mem (a₁ a₂ : ℕ) (n c : ℕ) :    c ∈ greedy_distinct_diff_history a₁ a₂ n ↔      ∃ i, i ≤ n+1 ∧ greedy_distinct_diff_seq a₁ a₂ i = c := by  rw [greedy_distinct_diff_seq_surjective_hist_eq, List.mem_map]  constructor  · rintro ⟨a, ha, rfl⟩    rw [List.mem_reverse, List.mem_range] at ha    exact ⟨a, by omega, rfl⟩  · rintro ⟨i, hi, rfl⟩    refine ⟨i, ?_, rfl⟩    rw [List.mem_reverse, List.mem_range]    omegalemma greedy_distinct_diff_seq_surjective_hist_head_eq (a₁ a₂ : ℕ) (n : ℕ) :    greedy_distinct_diff_history a₁ a₂ n      = greedy_distinct_diff_seq a₁ a₂ (n+1) ::        (List.range (n+1)).reverse.map (greedy_distinct_diff_seq a₁ a₂) := by  rw [greedy_distinct_diff_seq_surjective_hist_eq]  rw [show n+2 = (n+1)+1 from rfl, List.range_succ, List.reverse_append,      List.reverse_singleton]  simplemma greedy_distinct_diff_seq_surjective_difflist_cons (a₁ a₂ : ℕ) (n : ℕ) :    greedy_distinct_diff_seq_surjective_difflist a₁ a₂ (n+1)      = greedy_distinct_diff_seq_surjective_gd a₁ a₂ (n+1) ::        greedy_distinct_diff_seq_surjective_difflist a₁ a₂ n := by  unfold greedy_distinct_diff_seq_surjective_difflist greedy_distinct_diff_seq_surjective_gd  have hnext : greedy_distinct_diff_next (greedy_distinct_diff_history a₁ a₂ n)      = greedy_distinct_diff_seq a₁ a₂ (n+2) := by    simp [greedy_distinct_diff_seq, greedy_distinct_diff_history]  have hh : greedy_distinct_diff_history a₁ a₂ (n+1)      = greedy_distinct_diff_seq a₁ a₂ (n+2) ::        greedy_distinct_diff_history a₁ a₂ n := by    rw [show greedy_distinct_diff_history a₁ a₂ (n+1)        = greedy_distinct_diff_next (greedy_distinct_diff_history a₁ a₂ n) ::          greedy_distinct_diff_history a₁ a₂ n from rfl, hnext]  rw [hh, List.tail_cons]  rw [greedy_distinct_diff_seq_surjective_hist_head_eq a₁ a₂ n]  rw [List.zip_cons_cons, List.tail_cons]  simp only [List.map_cons]lemma greedy_distinct_diff_seq_surjective_difflist_zero (a₁ a₂ : ℕ) :    greedy_distinct_diff_seq_surjective_difflist a₁ a₂ 0      = [greedy_distinct_diff_seq_surjective_gd a₁ a₂ 0] := by  unfold greedy_distinct_diff_seq_surjective_difflist greedy_distinct_diff_seq_surjective_gd  rfllemma greedy_distinct_diff_seq_surjective_difflist_mem (a₁ a₂ : ℕ) (n e : ℕ) :    e ∈ greedy_distinct_diff_seq_surjective_difflist a₁ a₂ n ↔      ∃ i, i < n+1 ∧ e = greedy_distinct_diff_seq_surjective_gd a₁ a₂ i := by  induction n with  | zero =>    rw [greedy_distinct_diff_seq_surjective_difflist_zero, List.mem_singleton]    constructor    · intro h; exact ⟨0, by omega, h⟩    · rintro ⟨i, hi, he⟩      rw [show i = 0 by omega] at he      exact he  | succ n ih =>    rw [greedy_distinct_diff_seq_surjective_difflist_cons, List.mem_cons, ih]    constructor    · rintro (h | ⟨i, hi, he⟩)      · exact ⟨n+1, by omega, h⟩      · exact ⟨i, by omega, he⟩    · rintro ⟨i, hi, he⟩      rcases Nat.lt_or_ge i (n+1) with h' | h'      · exact Or.inr ⟨i, h', he⟩      · have hi' : i = n+1 := by omega        rw [hi'] at he        exact Or.inl helemma greedy_distinct_diff_seq_surjective_greedy_next_nonempty (l : List ℕ) :    {c : ℕ | 0 < c ∧ c ∉ l ∧      Int.natAbs ((c:ℤ) - ((l.headD 0):ℤ)) ∉        (l.zip l.tail).map (fun p => Int.natAbs ((p.1:ℤ) - (p.2:ℤ)))}.Nonempty := by  set ds := (l.zip l.tail).map (fun p => Int.natAbs ((p.1:ℤ) - (p.2:ℤ))) with hds  refine ⟨l.sum + ds.sum + l.headD 0 + 1, ?_, ?_, ?_⟩  · omega  · intro hmem; have h := List.le_sum_of_mem hmem; omega  · intro hmem    have hle : l.headD 0 ≤ l.sum + ds.sum + l.headD 0 + 1 := by omega    have hn : Int.natAbs (((l.sum + ds.sum + l.headD 0 + 1:ℕ):ℤ) - ((l.headD 0:ℕ):ℤ))        = (l.sum + ds.sum + l.headD 0 + 1) - l.headD 0 := by      have hcast : (((l.sum + ds.sum + l.headD 0 + 1):ℕ):ℤ) - ((l.headD 0:ℕ):ℤ)          = (((l.sum + ds.sum + l.headD 0 + 1) - l.headD 0 : ℕ):ℤ) := by        rw [Nat.cast_sub hle]      rw [hcast, Int.natAbs_natCast]    rw [hn] at hmem    have h := List.le_sum_of_mem hmem; omegalemma greedy_distinct_diff_seq_surjective_spec (a₁ a₂ : ℕ) (n : ℕ) :    greedy_distinct_diff_seq a₁ a₂ (n+2) =        greedy_distinct_diff_next (greedy_distinct_diff_history a₁ a₂ n) ∧    0 < greedy_distinct_diff_seq a₁ a₂ (n+2) ∧    greedy_distinct_diff_seq a₁ a₂ (n+2) ∉        (Finset.range (n+2)).image (greedy_distinct_diff_seq a₁ a₂) ∧    greedy_distinct_diff_seq_surjective_gd a₁ a₂ (n+1) ∉ (Finset.range (n+1)).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂) ∧    (∀ c, 0 < c →      c ∉ (Finset.range (n+2)).image (greedy_distinct_diff_seq a₁ a₂) →      Int.natAbs (((c:ℤ) - ((greedy_distinct_diff_seq a₁ a₂ (n+1)):ℤ))) ∉        (Finset.range (n+1)).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂) →      greedy_distinct_diff_seq a₁ a₂ (n+2) ≤ c) := by  set x := greedy_distinct_diff_seq a₁ a₂ with hxdef  have hx : x (n+2) = greedy_distinct_diff_next (greedy_distinct_diff_history a₁ a₂ n) := by    rw [hxdef]; simp [greedy_distinct_diff_seq, greedy_distinct_diff_history]  set l := greedy_distinct_diff_history a₁ a₂ n with hl  set S := {c : ℕ | 0 < c ∧ c ∉ l ∧      Int.natAbs ((c:ℤ) - ((l.headD 0):ℤ)) ∉        (l.zip l.tail).map (fun p => Int.natAbs ((p.1:ℤ) - (p.2:ℤ)))} with hS  have hheadD : l.headD 0 = x (n+1) := by rw [hxdef]; rfl  have hne : S.Nonempty := greedy_distinct_diff_seq_surjective_greedy_next_nonempty l  have hmem : sInf S ∈ S := Nat.sInf_mem hne  have hxS : x (n+2) = sInf S := by rw [hx]; rfl  have hmemV : ∀ c, (c ∈ l ↔ c ∈ (Finset.range (n+2)).image x) := by    intro c    rw [hl, hxdef, greedy_distinct_diff_seq_surjective_hist_mem]    simp only [Finset.mem_image, Finset.mem_range]    constructor    · rintro ⟨i, hi, h⟩; exact ⟨i, by omega, h⟩    · rintro ⟨i, hi, h⟩; exact ⟨i, by omega, h⟩  have hmemD : ∀ e, (e ∈ greedy_distinct_diff_seq_surjective_difflist a₁ a₂ n ↔      e ∈ (Finset.range (n+1)).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂)) := by    intro e    rw [greedy_distinct_diff_seq_surjective_difflist_mem]    simp only [Finset.mem_image, Finset.mem_range]    constructor    · rintro ⟨i, hi, h⟩; exact ⟨i, by omega, h.symm⟩    · rintro ⟨i, hi, h⟩; exact ⟨i, by omega, h.symm⟩  refine ⟨hx, ?_, ?_, ?_, ?_⟩  · rw [hxS]; exact hmem.1  · rw [← hmemV, hxS]; exact hmem.2.1  · rw [← hmemD]    have heq : greedy_distinct_diff_seq_surjective_gd a₁ a₂ (n+1)        = Int.natAbs ((((sInf S : ℕ)):ℤ) - ((l.headD 0):ℤ)) := by      unfold greedy_distinct_diff_seq_surjective_gd      rw [← hxdef, hxS, hheadD]    rw [heq]    exact hmem.2.2  · intro c hc0 hcV hcD    have hcS : c ∈ S := by      refine ⟨hc0, ?_, ?_⟩      · rw [hmemV]; exact hcV      · show Int.natAbs ((c:ℤ) - ((x (n+1)):ℤ)) ∉ greedy_distinct_diff_seq_surjective_difflist a₁ a₂ n        rw [hmemD]; exact hcD    have hle := Nat.sInf_le hcS    rw [← hxS] at hle    exact hlelemma greedy_distinct_diff_seq_surjective_natAbs_sub_nat {a b : ℕ} (h : a ≤ b) :    Int.natAbs ((b:ℤ) - (a:ℤ)) = b - a := by  have hcast : ((b:ℤ) - (a:ℤ)) = ((b - a : ℕ):ℤ) := by    rw [Nat.cast_sub h]  rw [hcast, Int.natAbs_natCast]lemma greedy_distinct_diff_seq_surjective_natAbs_v_sub {v n : ℕ} (h : v ≤ n) :    Int.natAbs ((v:ℤ) - (n:ℤ)) = n - v := by  have e : ((v:ℤ) - (n:ℤ)) = -(((n:ℤ) - (v:ℤ))) := by ring  rw [e, Int.natAbs_neg, greedy_distinct_diff_seq_surjective_natAbs_sub_nat h]lemma greedy_distinct_diff_seq_surjective_natAbs_sub_le {a b M : ℕ} (ha : a ≤ M) (hb : b ≤ M) :    Int.natAbs ((b:ℤ) - (a:ℤ)) ≤ M := by  rcases le_total a b with hab | hab  · rw [greedy_distinct_diff_seq_surjective_natAbs_sub_nat hab]; omega  · rw [show Int.natAbs ((b:ℤ) - (a:ℤ)) = Int.natAbs ((a:ℤ) - (b:ℤ)) from by        rw [← Int.natAbs_neg]; congr 1; ring]    rw [greedy_distinct_diff_seq_surjective_natAbs_sub_nat hab]; omegalemma greedy_distinct_diff_seq_surjective_spec_one (a₁ a₂ : ℕ) (k : ℕ) (hk : 1 ≤ k) :    0 < greedy_distinct_diff_seq a₁ a₂ (k+1) ∧    greedy_distinct_diff_seq a₁ a₂ (k+1) ∉ (Finset.range (k+1)).image (greedy_distinct_diff_seq a₁ a₂) ∧    greedy_distinct_diff_seq_surjective_gd a₁ a₂ k ∉ (Finset.range k).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂) ∧    (∀ c, 0 < c → c ∉ (Finset.range (k+1)).image (greedy_distinct_diff_seq a₁ a₂) →      Int.natAbs (((c:ℤ) - ((greedy_distinct_diff_seq a₁ a₂ k):ℤ))) ∉ (Finset.range k).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂) →      greedy_distinct_diff_seq a₁ a₂ (k+1) ≤ c) := by  obtain ⟨-, h2, h3, h4, h5⟩ := greedy_distinct_diff_seq_surjective_spec a₁ a₂ (k-1)  have e1 : k - 1 + 2 = k + 1 := by omega  have e2 : k - 1 + 1 = k := by omega  refine ⟨?_, ?_, ?_, ?_⟩  · rw [e1] at h2; exact h2  · rw [e1] at h3; exact h3  · rw [e2] at h4; exact h4  · intro c hc hcv hcd    have h := h5 c hc (by rw [e1]; exact hcv) (by rw [e2]; exact hcd)    rw [e1] at h; exact htheorem greedy_distinct_diff_seq_surjective (a₁ a₂ : ℕ) (h₁ : 0 < a₁) (h₂ : 0 < a₂)    (h : a₁ ≠ a₂) : ∀ v, 0 < v → ∃ n, greedy_distinct_diff_seq a₁ a₂ n = v := by  intro v hv  by_contra hcon  push_neg at hcon  set x := greedy_distinct_diff_seq a₁ a₂ with hxdef  set D : ℕ → Finset ℕ := fun k => (Finset.range k).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂) with hDdef  have hx0 : x 0 = a₁ := by rw [hxdef]; rfl  have hx1 : x 1 = a₂ := by rw [hxdef]; rfl  have hvmiss : ∀ m, v ∉ (Finset.range m).image x := by    intro m hm    rw [Finset.mem_image] at hm    obtain ⟨i, -, hi⟩ := hm    exact hcon i hi  have hA : ∀ k, 1 ≤ k → x (k+1) > v → Int.natAbs ((v:ℤ) - ((x k:ℤ))) ∈ D k := by    intro k hk hgt    by_contra hnot    have h4 := (greedy_distinct_diff_seq_surjective_spec_one a₁ a₂ k hk).2.2.2    have hle : x (k+1) ≤ v := h4 v hv (hvmiss (k+1)) hnot    exact absurd hle (not_le.mpr hgt)  have hA' : ∀ k, 1 ≤ k → x k > v → x (k+1) > v → x k - v ∈ D k := by    intro k hk hxk hgt    have hh := hA k hk hgt    rw [show Int.natAbs ((v:ℤ) - ((x k:ℤ))) = x k - v from greedy_distinct_diff_seq_surjective_natAbs_v_sub (le_of_lt hxk)] at hh    exact hh  have hDsucc : ∀ k, D (k+1) = D k ∪ {greedy_distinct_diff_seq_surjective_gd a₁ a₂ k} := by    intro k    show (Finset.range (k+1)).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂)        = (Finset.range k).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂) ∪ {greedy_distinct_diff_seq_surjective_gd a₁ a₂ k}    rw [Finset.range_add_one, Finset.image_insert, Finset.insert_eq, Finset.union_comm]  have hB : ∀ k, 1 ≤ k → x k > v → x (k+1) > v → x (k+2) > v →      greedy_distinct_diff_seq_surjective_gd a₁ a₂ k ≤ (D k).sup id := by    intro k hk hx1 hx2 hx3    have ha : x k - v ∈ D k := hA' k hk hx1 hx2    have hb : x (k+1) - v ∈ D (k+1) := hA' (k+1) (by omega) hx2 hx3    have hapos : 0 < x k - v := by omega    have hd_eq : greedy_distinct_diff_seq_surjective_gd a₁ a₂ k        = Int.natAbs (((x (k+1) - v : ℕ):ℤ) - ((x k - v : ℕ):ℤ)) := by      unfold greedy_distinct_diff_seq_surjective_gd      congr 1      have e1 : ((x (k+1) - v : ℕ):ℤ) = (x (k+1):ℤ) - (v:ℤ) := Nat.cast_sub (le_of_lt hx2)      have e2 : ((x k - v : ℕ):ℤ) = (x k:ℤ) - (v:ℤ) := Nat.cast_sub (le_of_lt hx1)      rw [e1, e2]; ring    have hb' : x (k+1) - v ∈ D k ∪ {greedy_distinct_diff_seq_surjective_gd a₁ a₂ k} := by rw [← hDsucc]; exact hb    rw [Finset.mem_union, Finset.mem_singleton] at hb'    rcases hb' with hbD | hbgd    · rw [hd_eq]      exact greedy_distinct_diff_seq_surjective_natAbs_sub_le (Finset.le_sup (f := id) ha) (Finset.le_sup (f := id) hbD)    · have hde : greedy_distinct_diff_seq_surjective_gd a₁ a₂ k          = Int.natAbs (((greedy_distinct_diff_seq_surjective_gd a₁ a₂ k : ℕ):ℤ) - ((x k - v : ℕ):ℤ)) := by        rw [hbgd] at hd_eq; exact hd_eq      rw [hde]      have haM : x k - v ≤ (D k).sup id := Finset.le_sup (f := id) ha      by_contra hgt      push_neg at hgt      have hle : x k - v ≤ greedy_distinct_diff_seq_surjective_gd a₁ a₂ k := by omega      rw [greedy_distinct_diff_seq_surjective_natAbs_sub_nat hle] at hde      omega  have hx_out : ∀ m, 1 ≤ m → x m ∉ (Finset.range m).image x := by    intro m hm    rcases eq_or_lt_of_le hm with hm1 | hm2    · subst hm1      intro hmem      rw [Finset.range_one, Finset.image_singleton, Finset.mem_singleton] at hmem      rw [hx1, hx0] at hmem      exact h hmem.symm    · have hs := (greedy_distinct_diff_seq_surjective_spec_one a₁ a₂ (m-1) (by omega)).2.1      have e : m - 1 + 1 = m := by omega      rw [e] at hs      exact hs  have hx_ne : ∀ i j, i < j → x i ≠ x j := by    intro i j hij heq    have hj : 1 ≤ j := by omega    have hout := hx_out j hj    have hin : x i ∈ (Finset.range j).image x := by      rw [Finset.mem_image]; exact ⟨i, Finset.mem_range.mpr hij, rfl⟩    exact hout (heq ▸ hin)  have hinj : Function.Injective x := by    intro i j heq    rcases Nat.lt_trichotomy i j with hij | hij | hij    · exact absurd heq (hx_ne i j hij)    · exact hij    · exact absurd heq.symm (hx_ne j i hij)  have hgd_ne : ∀ i j, i < j → greedy_distinct_diff_seq_surjective_gd a₁ a₂ i ≠ greedy_distinct_diff_seq_surjective_gd a₁ a₂ j := by    intro i j hij heq    have hj : 1 ≤ j := by omega    have hs : greedy_distinct_diff_seq_surjective_gd a₁ a₂ j ∉ D j := (greedy_distinct_diff_seq_surjective_spec_one a₁ a₂ j hj).2.2.1    have hi : greedy_distinct_diff_seq_surjective_gd a₁ a₂ i ∈ D j := by      show greedy_distinct_diff_seq_surjective_gd a₁ a₂ i ∈ (Finset.range j).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂)      exact Finset.mem_image.mpr ⟨i, Finset.mem_range.mpr hij, rfl⟩    rw [← heq] at hs    exact hs hi  have hDcard : ∀ k, (D k).card = k := by    intro k    show ((Finset.range k).image (greedy_distinct_diff_seq_surjective_gd a₁ a₂)).card = k    rw [Finset.card_image_of_injOn, Finset.card_range]    intro i hi j hj heq    simp only [Finset.mem_coe, Finset.mem_range] at hi hj    rcases Nat.lt_trichotomy i j with hlt | hlt | hlt    · exact absurd heq (hgd_ne i j hlt)    · exact hlt    · exact absurd heq.symm (hgd_ne j i hlt)  classical  set idx : ℕ → ℕ := fun m => if hh : ∃ k, x k = m then Classical.choose hh else 0 with hidx  have hidx_eq : ∀ m k, x k = m → idx m = k := by    intro m k hk    have hex : ∃ j, x j = m := ⟨k, hk⟩    have hchoose : x (Classical.choose hex) = m := Classical.choose_spec hex    have hck : Classical.choose hex = k := hinj (by rw [hchoose, hk])    simp only [idx, dif_pos hex, hck]  have hK : ∃ K, ∀ k, K ≤ k → v < x k := by    refine ⟨(Finset.range (v+1)).sup idx + 1, ?_⟩    intro k hk    by_contra hle    push_neg at hle    have hmem : x k ∈ Finset.range (v+1) := Finset.mem_range.mpr (by omega)    have h1 : idx (x k) ≤ (Finset.range (v+1)).sup idx := Finset.le_sup hmem    have h2 : idx (x k) = k := hidx_eq (x k) k rfl    rw [h2] at h1    omega  obtain ⟨K, hK⟩ := hK  set K' := max K 2 with hK'  have hstab : ∀ k, K' ≤ k → (D (k+1)).sup id = (D k).sup id := by    intro k hk    have hKk : K ≤ k := le_trans (le_max_left K 2) hk    have hBk := hB k (by omega) (hK k hKk) (hK (k+1) (by omega)) (hK (k+2) (by omega))    rw [hDsucc, Finset.sup_union, Finset.sup_singleton]    exact max_eq_left hBk  have hMconst : ∀ k, K' ≤ k → (D k).sup id = (D K').sup id := by    intro k hk    induction k with    | zero => omega    | succ k ih =>      rcases Nat.lt_or_ge k K' with hlt | hge      · have hk1 : k + 1 = K' := by omega        rw [hk1]      · rw [hstab k hge, ih hge]  have hfinal : ∀ k, K' ≤ k → k ≤ (D K').sup id + 1 := by    intro k hk    have hsub : D k ⊆ Finset.range ((D K').sup id + 1) := by      intro m hm      rw [Finset.mem_range]      have hle : m ≤ (D k).sup id := Finset.le_sup (f := id) hm      rw [hMconst k hk] at hle      omega    have hc := Finset.card_le_card hsub    rw [Finset.card_range, hDcard k] at hc    exact hc  have hcontra := hfinal (max K' ((D K').sup id + 2)) (le_max_left _ _)  omega
See it in the graphDiscuss this resultChallenge it