每日科技文摘Daily Tech Digest

DOOM 关卡里跑 MNIST、把 6502 编译进 Qwen,还有一道 1974 年的组合题MNIST in a DOOM Level, a 6502 CPU in Qwen Weights, and a 1974 Combinatorics Problem

发布于 2026-11-01Published 2026-11-01

今日深读Today's Deep Read

DOOM 关卡即神经网络:用巫毒娃娃做整数计算A DOOM Level as a Neural Network: Integer Math with Voodoo Dolls

通常『把神经网络编译进一个奇怪介质』的尝试,都是把它烧进 FPGA 或者跑在微控制器上。mottopanikeiku 选了 DOOM 的关卡系统——一个 90 年代的 2D 引擎的地图格式——作为『计算介质』,用 1355 个巫毒娃娃(voodoo dolls,DOOM 里的装饰性精灵)当神经元。这个选择本身就是文章的第一个声明:计算介质不必是现代硬件,可以是任何能忠实保存和传递整数的数据结构。The usual attempts to 'compile a neural network into an exotic medium' burn it into an FPGA or run it on a microcontroller. mottopanikeiku chose DOOM's level system — a 90s 2D engine's map format — as the 'compute medium,' using 1,355 voodoo dolls (decorative sprites in DOOM) as neurons.

第一步是把一个标准的 float 版 MNIST 分类器训练好(97.58% 准确率),然后量化成整数——这一步很关键:DOOM 地图的每一格只能存一个 16-bit 整数,没有浮点。量化误差必须控制在 NumPy 前向传播精确可比对的范围内,这意味着作者的量化方案本身就是一个独立的工程贡献,不只是『把网络搬过去』,而是『让搬过去之后仍然精确』。Step one: train a standard float MNIST classifier (97.58% accuracy), then quantize it to integers — critical because every DOOM map cell stores only a 16-bit integer; there are no floats. The quantization error must stay within NumPy's exact forward-propagation tolerance.

第二步是把量化后的权重『画进』DOOM 地图里:每个巫毒娃娃的位置编码一个神经元,娃娃之间的连接(通过关卡事件触发器)编码权重,DOOM 引擎在运行时逐格执行整数乘法。宿主程序负责渲染、读取输入,引擎本身不需要任何修改——它以为自己在跑一个游戏关卡,实际上在执行一次前向传播。Step two: 'paint' the quantized weights into the DOOM map: each voodoo doll's position encodes a neuron; connections between dolls (via level event triggers) encode the weights; the DOOM engine executes integer multiplication cell by cell at runtime.

第三步是验证。作者写了一个 Python 工具读回 DOOM 地图里每格的数值,与 NumPy 的 float 前向传播逐格比对,容差设为 0。然后对 20k 个随机 fuzzed 网络做同样比对,零 mismatch。这不是『跑一下看看』,是逐 cell 的精确验证,排除了『结果碰巧一样』的可能。Step three: verification. The author wrote a Python tool that reads back the value in every DOOM map cell and compares cell-by-cell with NumPy float forward propagation, with tolerance set to 0. Then 20,000 fuzzed random networks, same comparison, zero mismatches. This is not 'run it and see' — it is cell-exact verification.

这件事的意义:它证明『神经网络』作为一个抽象计算单元,可以在任何能存整数并做整数运算的介质里运行——哪怕那个介质是 1993 年的 2D 游戏引擎。边界不在于『是不是 GPU』,而在于『介质能不能忠实保存和传递整数』。The significance: it proves a 'neural network' as an abstract compute unit can run inside any medium that stores and faithfully transmits integers — even a 1993 2D game engine. The boundary is not 'is it a GPU'; it is 'can the medium faithfully store and transmit integers.'

对程序员的启示:下次你设计一个嵌入式系统、一个约束极强的存储格式、或者任何一个『介质不是为你的算法设计的』系统,先问『能不能把一个小网络塞进去』——如果能,你的介质就有足够的计算表达能力,即使它看起来完全不像计算设备。这个思想实验把『可计算性』和『介质是否像计算机』这两件事彻底解耦了。For programmers: next time you design an embedded system or a heavily constrained storage format, ask 'could I fit a small network in here?' If yes, your medium has enough computational expressiveness, even if it looks nothing like a computing device.

AI 思考Thinking About AI

数学之美Beauty of Mathematics

每日 Lean 谜题 · 周日Daily Lean Puzzle · Sunday ★★★★★★★

1974 年 IMO P3:一个不整除 5 的组合和IMO 1974 P3: A Combinatorial Sum Not Divisible by 5

设 $S_n = \sum_{k=0}^{n} \binom{2n+1}{2k+1} \cdot 2^{3k}$。对任意整数 $n \geq 0$,证明 $S_n$ 不能被 5 整除。Let $S_n = \sum_{k=0}^{n} \binom{2n+1}{2k+1} \cdot 2^{3k}$. For every integer $n \geq 0$, prove that $S_n$ is not divisible by 5.

Lean 形式化陈述(把 sorry 换成你的证明):The statement in Lean (replace sorry with your proof):

/-
Copyright (c) 2025 The Compfiles Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Roozbeh Yousefzadeh
-/

import Mathlib.NumberTheory.Zsqrtd.Basic
import Mathlib.Tactic

/-!
# International Mathematical Olympiad 1974, Problem 3

Prove that the sum from k = 0 to n inclusive of
   Choose[2n + 1, 2k + 1] * 2³ᵏ
is not divisible by 5 for any integer n ≥ 0.
-/

namespace Imo1974P3

open Finset

theorem imo1974_p3
    (n : ℕ) :
    ¬ 5 ∣ ∑ k ∈ Finset.range (n + 1),
            (Nat.choose (2 * n + 1) (2 * k + 1)) * (2^(3 * k)) := by
  sorry
end Imo1974P3

在浏览器中挑战 ▶Try it in your browser ▶ 下载题目 .leanDownload puzzle .lean

提示Hint

把 $S_n$ 看成一个二次扩张环 $\mathbb{Z}\sqrt{8}$ 里某个数的虚部,然后用范数(norm)建立恒等式,最后在模 5 下用二次剩余判据推导矛盾。View $S_n$ as the imaginary part of an element in the quadratic ring $\mathbb{Z}\sqrt{8}$, use the norm to build an identity, then derive a contradiction modulo 5 via a quadratic-residue test.

答案与讲解Solution & walkthrough
  1. 第一步:把求和改写成 $(1 + \sqrt{8})^{2n+1}$ 中 $\sqrt{8}$ 的系数。展开 $(1+\sqrt{8})^{2n+1}$ 的二项式,偶数项给出 $\sqrt{8}$ 的系数,$\sqrt{8}^{2k} = 8^k$,而 $2^{3k} = 8^k$,所以虚部恰好是 $S_n$。Step 1: Rewrite the sum as the coefficient of $\sqrt{8}$ in $(1 + \sqrt{8})^{2n+1}$. Expanding the binomial, even-indexed terms give the $\sqrt{8}$ coefficient; $\sqrt{8}^{2k} = 8^k$ and $2^{3k} = 8^k$, so the imaginary part is exactly $S_n$.
  2. 第二步:建立范数恒等式。在 $\mathbb{Z}\sqrt{8}$ 里,元素 $a + b\sqrt{8}$ 的范数是 $a^2 - 8b^2$。因为范数可以乘法,$\mathrm{N}\bigl((1+\sqrt{8})^{2n+1}\bigr) = \mathrm{N}(1+\sqrt{8})^{2n+1} = (-7)^{2n+1}$。设实部为 $A$,虚部为 $S_n$,则 $A^2 - 8S_n^2 = (-7)^{2n+1}$。Step 2: Build the norm identity. In $\mathbb{Z}\sqrt{8}$, the norm of $a + b\sqrt{8}$ is $a^2 - 8b^2$. Since the norm is multiplicative, $\mathrm{N}\bigl((1+\sqrt{8})^{2n+1}\bigr) = \mathrm{N}(1+\sqrt{8})^{2n+1} = (-7)^{2n+1}$. Letting the real part be $A$ and the imaginary part be $S_n$, we get $A^2 - 8S_n^2 = (-7)^{2n+1}$.
  3. 第三步:模 5 化简。假设 $5 \mid S_n$,则在 $\mathbb{Z}/5\mathbb{Z}$ 里 $S_n \equiv 0$,恒等式变成 $A^2 \equiv (-7)^{2n+1} \pmod{5}$。计算 $(-7) \equiv 3 \equiv -2 \pmod{5}$,且 $(-7)^2 \equiv -1 \pmod{5}$,所以 $(-7)^{2n+1} = (-7) \cdot ((-7)^2)^n \equiv -2 \cdot (-1)^n \pmod{5}$,即 $A^2 \equiv \pm 2 \pmod{5}$。Step 3: Reduce modulo 5. Assume $5 \mid S_n$, so $S_n \equiv 0$ in $\mathbb{Z}/5\mathbb{Z}$, and the identity becomes $A^2 \equiv (-7)^{2n+1} \pmod{5}$. Now $(-7) \equiv -2 \pmod{5}$ and $(-7)^2 \equiv -1 \pmod{5}$, so $(-7)^{2n+1} = (-7)\cdot((-7)^2)^n \equiv -2 \cdot (-1)^n \pmod{5}$, giving $A^2 \equiv \pm 2 \pmod{5}$.
  4. 第四步:用二次剩余判据。模 5 的平方只有 $0, 1, 4$;不存在 $x$ 使得 $x^2 \equiv 2$ 或 $x^2 \equiv 3 \equiv -2 \pmod{5}$。因此 $A^2 \equiv \pm 2 \pmod{5}$ 无解,矛盾。假设 $5 \mid S_n$ 不成立,即 $S_n$ 不能被 5 整除。Step 4: Use the quadratic-residue criterion. The squares mod 5 are only $0, 1, 4$; there is no $x$ with $x^2 \equiv 2$ or $x^2 \equiv 3 \pmod{5}$. Hence $A^2 \equiv \pm 2 \pmod{5}$ is impossible — a contradiction. Therefore $5 \nmid S_n$, which completes the proof.
/-
Copyright (c) 2025 The Compfiles Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Roozbeh Yousefzadeh
-/

import Mathlib.NumberTheory.Zsqrtd.Basic
import Mathlib.Tactic

/-!
# International Mathematical Olympiad 1974, Problem 3

Prove that the sum from k = 0 to n inclusive of
   Choose[2n + 1, 2k + 1] * 2³ᵏ
is not divisible by 5 for any integer n ≥ 0.
-/

namespace Imo1974P3

open Finset

/- We work in ℤ√8.  The sum in question is the coefficient of √8 in
(1 + √8)^(2n+1), so taking norms gives A² - 8·B² = (-7)^(2n+1) where B is
the sum.  If 5 ∣ B, then A² ≡ ±2 (mod 5), which is impossible. -/

lemma sum_range_two_mul {M : Type*} [AddCommMonoid M] (n : ℕ) (f : ℕ → M) :
    ∑ i ∈ range (2 * n), f i = ∑ i ∈ range n, (f (2 * i) + f (2 * i + 1)) := by
  induction n with
  | zero => simp
  | succ n ih =>
    rw [show 2 * (n + 1) = 2 * n + 1 + 1 by ring, sum_range_succ, sum_range_succ,
        sum_range_succ, ih, add_assoc]

lemma im_sum {ι : Type*} (s : Finset ι) (f : ι → ℤ√8) :
    (∑ i ∈ s, f i).im = ∑ i ∈ s, (f i).im := by
  induction s using Finset.cons_induction with
  | empty => rfl
  | cons a s ha ih => rw [sum_cons, sum_cons, Zsqrtd.im_add, ih]

lemma sqrtd_pow_two_mul (k : ℕ) :
    (Zsqrtd.sqrtd : ℤ√8) ^ (2 * k) = ((8 ^ k : ℤ) : ℤ√8) := by
  induction k with
  | zero => simp
  | succ k ih =>
    rw [show 2 * (k + 1) = 2 * k + 1 + 1 by ring, pow_succ, pow_succ, ih,
        mul_assoc, Zsqrtd.dmuld]
    push_cast
    ring

/-- The binomial sum is the coefficient of √8 in (√8 + 1)^(2n+1). -/
lemma im_pow (n : ℕ) :
    ((Zsqrtd.sqrtd + 1 : ℤ√8) ^ (2 * n + 1)).im =
      ∑ k ∈ range (n + 1), ((2 * n + 1).choose (2 * k + 1) : ℤ) * 8 ^ k := by
  rw [add_pow, im_sum, show 2 * n + 1 + 1 = 2 * (n + 1) by ring,
      sum_range_two_mul]
  refine sum_congr rfl fun k _ ↦ ?_
  rw [pow_succ Zsqrtd.sqrtd (2 * k), sqrtd_pow_two_mul]
  simp only [one_pow, mul_one, Zsqrtd.im_mul, Zsqrtd.re_mul, Zsqrtd.re_intCast,
    Zsqrtd.im_intCast, Zsqrtd.re_natCast, Zsqrtd.im_natCast, Zsqrtd.re_sqrtd,
    Zsqrtd.im_sqrtd, mul_zero, zero_mul, add_zero, zero_add]
  ring

lemma norm_pow (m : ℕ) :
    ((Zsqrtd.sqrtd + 1 : ℤ√8) ^ m).norm = (-7) ^ m := by
  have h1 : (Zsqrtd.sqrtd + 1 : ℤ√8).norm = -7 := by
    norm_num [Zsqrtd.norm_def]
  calc ((Zsqrtd.sqrtd + 1 : ℤ√8) ^ m).norm
      = Zsqrtd.normMonoidHom ((Zsqrtd.sqrtd + 1 : ℤ√8) ^ m) := rfl
    _ = ((Zsqrtd.sqrtd + 1 : ℤ√8).norm : ℤ) ^ m := by rw [map_pow]; rfl
    _ = (-7) ^ m := by rw [h1]

theorem imo1974_p3
    (n : ℕ) :
    ¬ 5 ∣ ∑ k ∈ Finset.range (n + 1),
            (Nat.choose (2 * n + 1) (2 * k + 1)) * (2^(3 * k)) := by
  intro hdvd
  set S : ℕ := ∑ k ∈ Finset.range (n + 1),
      (Nat.choose (2 * n + 1) (2 * k + 1)) * (2 ^ (3 * k)) with hS
  -- S is the coefficient of √8 in (√8 + 1)^(2n+1)
  have him : ((Zsqrtd.sqrtd + 1 : ℤ√8) ^ (2 * n + 1)).im = (S : ℤ) := by
    rw [im_pow, hS]
    push_cast
    refine Finset.sum_congr rfl fun k _ ↦ ?_
    rw [pow_mul]
    norm_num
  -- the norm equation: A² - 8 S² = (-7)^(2n+1)
  have hnorm := norm_pow (2 * n + 1)
  rw [Zsqrtd.norm_def, him] at hnorm
  -- reduce mod 5, where S vanishes
  have h5 : (S : ZMod 5) = 0 := (ZMod.natCast_eq_zero_iff _ _).mpr hdvd
  apply_fun (fun t : ℤ ↦ (t : ZMod 5)) at hnorm
  push_cast at hnorm
  rw [h5] at hnorm
  -- so A² = (-7)^(2n+1) = (-1)ⁿ * (-7) in ZMod 5, which has no solution
  obtain ⟨x, hx⟩ : ∃ x : ZMod 5, x * x - 8 * 0 * 0 = (-7) ^ (2 * n + 1) :=
    ⟨_, hnorm⟩
  rw [pow_succ, pow_mul, show ((-7 : ZMod 5)) ^ 2 = -1 by decide] at hx
  obtain h | h := neg_one_pow_eq_or (ZMod 5) n <;> rw [h] at hx <;>
    revert hx x <;> decide

end Imo1974P3

运行答案 ▶Run the solution ▶ 下载答案 .leanDownload solution .lean

人的思考A human's take

Compfiles: Imo1974P3 — Roozbeh Yousefzadeh's verified Lean proof — Roozbeh Yousefzadeh (Compfiles project)

这是 Compfiles 项目(David Renshaw 维护,Apache 2.0)里的已验证证明,由 Roozbeh Yousefzadeh 撰写,使用 Mathlib 的 ℤ√8 环。证明的核心思路:把二项式求和识别为 $(1+\sqrt{8})^{2n+1}$ 的虚部,利用范数乘法性建立 $A^2 - 8S^2 = (-7)^{2n+1}$ 的恒等式,然后在模 5 下把假设 $5\mid S$ 归约成 $A^2 \equiv \pm 2 \pmod{5}$ 这个无解的二次剩余方程,矛盾。This is the verified proof in the Compfiles project (maintained by David Renshaw, Apache 2.0), written by Roozbeh Yousefzadeh using Mathlib's ℤ√8 ring. The core idea: identify the binomial sum as the imaginary part of $(1+\sqrt{8})^{2n+1}$, use norm multiplicativity to obtain the identity $A^2 - 8S^2 = (-7)^{2n+1}$, then reduce the assumption $5 \mid S$ modulo 5 to the unsolvable quadratic-residue equation $A^2 \equiv \pm 2 \pmod{5}$, a contradiction.

Lean 里的实现用 Zsqrtd.norm 给出范数公式,用 ZMod.natCast_eq_zero_iff 把整除性翻译成 ZMod 5 的零,最后用 decide 判读 $A^2 \equiv 2$ 和 $A^2 \equiv 3$ 两个 case 都无解。整个证明没有用高级代数几何,是经典的初等数论方法。The Lean implementation uses Zsqrtd.norm for the norm formula, ZMod.natCast_eq_zero_iff to convert divisibility into ZMod 5 being zero, and finally `decide` to check that neither $A^2 \equiv 2$ nor $A^2 \equiv 3$ has a solution mod 5. The whole proof uses no advanced algebraic geometry — it is the classic elementary number theory approach.

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

这道题最让人惊讶的地方,是它的证法里藏了一个不显眼的选择:为什么选 $\mathbb{Z}\sqrt{8}$ 而不是 $\mathbb{Z}\sqrt{5}$ 或 $\mathbb{Z}\sqrt{3}$?答案是只有 $\sqrt{8}$ 的范数给出 $-7$,$-7$ 在模 5 下有一个特殊的性质:$(-7)^2 \equiv -1$,这正好把幂的奇偶性变成了 $\pm 2$,而 2 在模 5 里恰好是非平方。换成 $\sqrt{5}$,范数给出 $-4$,$(-4)^2 = 16 \equiv 1 \pmod{5}$,幂的奇偶性消失,矛盾不成立。所以选扩张环不是随意的,而是被『模 5 下范数的平方等于 -1』这一条件完全决定的。这背后是 Gauss 整理论里的一种标准套路:找一个代数整数,让它的范数在目标模数下有某种特殊的二次剩余性质。What's most surprising about this problem is an inconspicuous choice hidden in the proof: why the ring $\mathbb{Z}\sqrt{8}$ and not $\mathbb{Z}\sqrt{5}$ or $\mathbb{Z}\sqrt{3}$? The answer is that only $\sqrt{8}$'s norm gives $-7$, and $-7$ has a special property mod 5: $(-7)^2 \equiv -1$, which turns the parity of the power into $\pm 2$, and 2 happens to be a non-residue mod 5. Switch to $\sqrt{5}$, the norm gives $-4$, $(-4)^2 = 16 \equiv 1 \pmod{5}$, the parity information is lost, and the contradiction fails. So choosing the extension ring is not arbitrary — it is fully determined by the condition that the norm's square is $-1$ mod 5. This is a standard trick from the theory of Gaussian integers: find an algebraic integer whose norm has a special quadratic-residue property at the target modulus.

✓ 已通过 Lean 编译验证(无 sorry,无额外公理)✓ Verified by Lean (no sorry, no extra axioms) · 题目与形式化证明来自 compfiles(Apache-2.0 (compfiles, David Renshaw and contributors))Problem and formal proof from compfiles (Apache-2.0 (compfiles, David Renshaw and contributors)) · Lean v4.36.0-rc1 · Mathlib d875a8d

程序员随想Programmer Musings

哲学与生活Philosophy & Life

工具角Tools Corner