import Std namespace OmegaTransport def scale : Nat := 1000000000000000 def coefficient : Nat := 339949771344778 def steps : Nat := 23 def maxSeed : Nat := 32767 def step (d : Nat) : Nat := coefficient * d / scale /-- The least integer whose image under the floor map is at least y. -/ def first (y : Nat) : Nat := (scale * y + (coefficient - 1)) / coefficient theorem step_bounds (d : Nat) : scale * step d ≤ coefficient * d ∧ coefficient * d < scale * (step d + 1) := by simp only [step, scale, coefficient] omega theorem first_bounds (y : Nat) : scale * y ≤ coefficient * first y ∧ coefficient * first y < scale * y + coefficient := by simp only [first, scale, coefficient] omega theorem fiber (d y : Nat) : step d = y ↔ first y ≤ d ∧ d < first (y + 1) := by have hd := step_bounds d have hl := first_bounds y have hu := first_bounds (y + 1) simp only [scale, coefficient] at hd hl hu omega def rank (d : Nat) : Nat := d - first (step d) theorem first_add_rank (d : Nat) : first (step d) + rank d = d := by have h := ((fiber d (step d)).mp rfl).1 unfold rank omega theorem rank_lt_three (d : Nat) : rank d < 3 := by have hd := step_bounds d have hb := first_bounds (step d) simp only [scale, coefficient] at hd hb unfold rank omega def terminal : Nat → Nat → Nat | 0, d => d | n+1, d => terminal n (step d) def ranks : Nat → Nat → List Nat | 0, _ => [] | n+1, d => rank d :: ranks n (step d) def trace : Nat → Nat → List Nat | 0, d => [d] | n+1, d => d :: trace n (step d) def restore (t : Nat) : List Nat → List Nat | [] => [t] | r :: rs => let suffix := restore t rs (first (suffix.headD 0) + r) :: suffix theorem trace_head (n d : Nat) : (trace n d).headD 0 = d := by cases n <;> rfl theorem history_recovery (n d : Nat) : restore (terminal n d) (ranks n d) = trace n d := by induction n generalizing d with | zero => rfl | succ n ih => simp only [terminal, ranks, restore, trace, ih, trace_head, first_add_rank] theorem ranks_length (n d : Nat) : (ranks n d).length = n := by induction n generalizing d with | zero => rfl | succ n ih => simp [ranks, ih] theorem ranks_lt_four (n d : Nat) : ∀ r ∈ ranks n d, r < 4 := by induction n generalizing d with | zero => simp [ranks] | succ n ih => intro r hr simp only [ranks, List.mem_cons] at hr rcases hr with h | h · subst r exact Nat.lt_trans (rank_lt_three d) (by decide) · exact ih (step d) r h theorem step_mono {d e : Nat} (h : d ≤ e) : step d ≤ step e := by have hd := (step_bounds d).1 have he := (step_bounds e).2 simp only [scale, coefficient] at hd he omega theorem step_le_self (d : Nat) : step d ≤ d := by have h := (step_bounds d).1 simp only [scale, coefficient] at h omega theorem trace_in_domain (n d : Nat) (hd : d ≤ maxSeed) : ∀ state ∈ trace n d, state ≤ maxSeed := by induction n generalizing d with | zero => simpa [trace] using hd | succ n ih => intro state hs simp only [trace, List.mem_cons] at hs rcases hs with h | h · subst state exact hd · exact ih (step d) (Nat.le_trans (step_le_self d) hd) state h theorem terminal_mono (n : Nat) {d e : Nat} (h : d ≤ e) : terminal n d ≤ terminal n e := by induction n generalizing d e with | zero => exact h | succ n ih => exact ih (step_mono h) theorem terminal_zero (d : Nat) (hd : d ≤ maxSeed) : terminal steps d = 0 := by have hm : terminal steps maxSeed = 0 := by decide have h := terminal_mono steps hd omega def packRanks : List Nat → Nat | [] => 0 | r :: rs => r + 4 * packRanks rs def unpackRanks : Nat → Nat → List Nat | 0, _ => [] | n+1, word => word % 4 :: unpackRanks n (word / 4) theorem unpack_pack (rs : List Nat) (hr : ∀ r ∈ rs, r < 4) : unpackRanks rs.length (packRanks rs) = rs := by induction rs with | nil => rfl | cons r rs ih => have h : r < 4 := hr r (List.mem_cons_self ..) have ht : ∀ t ∈ rs, t < 4 := fun t ht => hr t (List.mem_cons_of_mem r ht) have hmod : (r + 4 * packRanks rs) % 4 = r := by omega have hdiv : (r + 4 * packRanks rs) / 4 = packRanks rs := by omega simp [packRanks, unpackRanks, hmod, hdiv, ih ht] theorem pack_bound (rs : List Nat) (hr : ∀ r ∈ rs, r < 4) : packRanks rs < 4 ^ rs.length := by induction rs with | nil => decide | cons r rs ih => have h : r < 4 := hr r (List.mem_cons_self ..) have ht := ih (fun t ht => hr t (List.mem_cons_of_mem r ht)) simp only [packRanks, List.length_cons, Nat.pow_succ] omega def toBytes : Nat → Nat → List Nat | 0, _ => [] | n+1, word => word % 256 :: toBytes n (word / 256) def fromBytes : List Nat → Nat | [] => 0 | b :: bs => b + 256 * fromBytes bs theorem bytes_length (n word : Nat) : (toBytes n word).length = n := by induction n generalizing word with | zero => rfl | succ n ih => simp [toBytes, ih] theorem byte_bound (n word : Nat) : ∀ b ∈ toBytes n word, b < 256 := by induction n generalizing word with | zero => simp [toBytes] | succ n ih => intro b hb simp only [toBytes, List.mem_cons] at hb rcases hb with h | h · subst b exact Nat.mod_lt _ (by decide) · exact ih (word / 256) b h theorem from_to_bytes (n word : Nat) (h : word < 256 ^ n) : fromBytes (toBytes n word) = word := by induction n generalizing word with | zero => have hw : word < 1 := h have hz : word = 0 := by omega simp [toBytes, fromBytes, hz] | succ n ih => have hd : word / 256 < 256 ^ n := by apply (Nat.div_lt_iff_lt_mul (by decide : 0 < 256)).2 simpa [Nat.pow_succ] using h simp only [toBytes, fromBytes, ih _ hd] exact Nat.mod_add_div _ _ def packet (d : Nat) : List Nat := toBytes 6 (packRanks (ranks steps d)) /-- Decoding on the image of packet. The programs also check malformed inputs. -/ def decodePacket (bytes : List Nat) : List Nat := restore 0 (unpackRanks steps (fromBytes bytes)) theorem packet_length (d : Nat) : (packet d).length = 6 := bytes_length _ _ theorem packet_padding (d : Nat) : fromBytes (packet d) < 2 ^ 46 := by have hp := pack_bound (ranks steps d) (ranks_lt_four steps d) rw [ranks_length] at hp have hword : packRanks (ranks steps d) < 256 ^ 6 := Nat.lt_trans hp (by decide) rw [packet, from_to_bytes _ _ hword] exact hp theorem packet_recovers_history (d : Nat) (hd : d ≤ maxSeed) : decodePacket (packet d) = trace steps d := by have hr := ranks_lt_four steps d have hp := pack_bound (ranks steps d) hr rw [ranks_length] at hp have hword : packRanks (ranks steps d) < 256 ^ 6 := Nat.lt_trans hp (by decide) have hu := unpack_pack (ranks steps d) hr rw [ranks_length] at hu rw [decodePacket, packet, from_to_bytes _ _ hword, hu] simpa only [terminal_zero d hd] using history_recovery steps d theorem packet_injective (d e : Nat) (hd : d ≤ maxSeed) (he : e ≤ maxSeed) (h : packet d = packet e) : d = e := by have ht := congrArg decodePacket h rw [packet_recovers_history d hd, packet_recovers_history e he] at ht have hh := congrArg (fun states : List Nat => states.headD 0) ht simpa only [trace_head] using hh /-- Two little-endian bytes for each state, oldest first. -/ def traceBytes (states : List Nat) : List Nat := states.flatMap (toBytes 2) theorem packet_recovers_trace_bytes (d : Nat) (hd : d ≤ maxSeed) : traceBytes (decodePacket (packet d)) = traceBytes (trace steps d) := congrArg traceBytes (packet_recovers_history d hd) theorem packet_399 : packet 399 = [9, 6, 0, 0, 0, 0] := by decide end OmegaTransport