每日科技文摘Daily Tech Digest

进步被兑换成了产出,而不是时间Progress Was Cashed In as Output, Not as Time

发布于 2026-11-14Published 2026-11-14

今日深读Today's Deep Read

为什么我们还在工作这么拼命:工资同时干着两份互相打架的活Why Are We Still Working This Hard: A Wage Is Doing Two Clashing Jobs

先看一个几乎没人核对过的数字:按美国经济分析局(BEA)的投入产出表,1973 年四十小时才造出来的产出,今天约十六小时就能造出来——每个岗位已被机器替掉二十四小时。可四十小时一周纹丝未动,2024 年美国人均工时甚至比 1973 年还高百分之十。凯恩斯 1930 年预言的「十五小时工作制」,按小时产出算早就到来,只是没有落进日历。作者问:这五十年的进步,去哪了?Start with a number almost nobody checks: according to the US Bureau of Economic Analysis input-output tables, what took a full forty-hour week to produce in 1973 takes about sixteen hours today. Twenty-four hours per job have quietly been handed to the machines. Yet the forty-hour week written into American law in 1938 hasn't budged — in 2024 the US actually works about 10 percent more hours per head than in 1973. Keynes predicted in 1930 that his grandchildren would enjoy a fifteen-hour week; the usual verdict is that he was right about wealth and wrong about leisure. But measured by output per hour, the fifteen-hour week really did arrive — it just never landed in the calendar. The author asks: where did fifty years of progress go?

他的答案要从「工资是干什么用的」说起。工资同时身兼三职:它是一束价格,告诉企业一小时值多少、告诉人哪种活被需要;它是一张门票,你几乎只能通过出卖时间,才能分到社会生产的东西——面包到你手里不是按需要,而是因为你卖了工时换来了钱;它还是一个场所,给一天一个形状,给你一群人。两个世纪以来这三份活相安无事,因为工业时代的机器是「强壮而愚蠢的」:只能举、转、冲压,不能看、不能判断、不能决定。机器的主人不得不竞标人的时间——工资随生产率一起上涨,这价格铸成的门票,是一张好门票。His answer starts from a question about the wage itself: what is a wage for? A wage holds three jobs at once. It is a price, telling firms what an hour costs and telling people which work is wanted. It is a ticket: nearly everyone gets a share of what society produces only by selling hours — bread reaches you not because you need it but because you have money, and money because you sold time. And it is a place: it gives the day a shape, a set of people, a sign that someone needs you. For two centuries the three roles pulled in the same direction, because the machines of the industrial age were strong and stupid: they could lift, spin, stamp and haul, but not see, judge or decide. Nearly everything worth making needed both kinds of ability, so every new machine needed a person beside it, and machine owners had to bid for people's hours. Wages rose with productivity, and a ticket minted from that price was a good ticket.

今天造的机器能看、能读、能写、能判断。作者以写软件为生,说自己一年比一年难说出哪类工作「稳在它们够不着的地方」。于是价格与门票开始互相拉扯。先算那十八小时去哪了:付给美国人的钱里 66% 是劳动报酬、34% 归机器的所有者;最富的十分之一拿走全部财产收入的三分之二,而税收每一美元里 68 美分恰恰来自工资——其余九成家庭其实活在别人的工资上。Acemoglu 与 Restrepo 估计,四十年间工资结构变动的 50%–70% 来自被自动化行业常规工序工人的相对贬值:机器先学会了普通人的活。机器学会你那份工作的那天,你和昨天一样努力,但你的一小时不值钱了。作为价格这很正确;拿它决定谁配过上好日子,就很古怪。这是价格正在啃食门票。The machines being built now can see, read, write and judge. The author, who writes software for a living and uses them daily, says it gets harder each year to name work that is safely out of their reach. So price and ticket have been pulling each other apart. First, the eighteen hours: chase a dollar spent in a shop through America's national accounts, and of what is paid to Americans, 66 percent is pay for work and 34 percent goes to owners — of the oven, the truck, the building, the ground. The richest tenth takes two-thirds of all income from ownership, while 68 cents of every tax dollar is raised from wages, so nine households in ten live on each other's wages. Acemoglu and Restrepo estimate that 50–70 percent of the change in the US wage structure over four decades came from relative wage declines of workers doing routine tasks in rapidly automating industries — machines learned ordinary jobs before they touched the best-paid ones. The day a machine learns your job, you work exactly as hard as the day before, and your hour is worth less. That is how a price ought to behave; it is a strange way to decide who gets to live well. This is the price shrinking the ticket.

再算那六小时:普通工资确实涨了约五分之一,本可以换来六小时闲暇,工时反而更长了。作者的解释是信息论的:价格传递真实信息的前提是我可以说「不」。我付三美元买面包,面包师才得知面包对我至少值三美元,因为我本可以走掉;工资本该反向携带同样的信息,但这只在「我付得起拒绝的代价」时成立。如果卖时间是我唯一的活法,工资只记录了我多需要这笔钱,几乎不记录那一个小时本可以是什么——陪孩子的下午、看望母亲的一天;用作者的话说,它们「输掉了一场根本不许它们参赛的比试」。一方无法离场的拍卖,出价再高也测不出真实价值:因为无法拒绝,很多并不值得做的活被认真地做完了。Now the six hours: ordinary pay did rise by about a fifth — enough to buy six hours off the week — yet hours went up instead. The author's explanation is informational. A price carries true information only if I can say no. When I pay three dollars for bread, the baker learns the bread was worth at least that to me, because I could have walked away. The wage is supposed to carry the same message in reverse: taking fifteen dollars an hour should mean the hour was worth less than fifteen to me. But that only holds if refusing is affordable. If selling hours is the only way I eat, the wage records how badly I needed the money and almost nothing about what the hour would otherwise have been — an afternoon with my child, a visit to my mother. 'Those lost a contest they were never allowed to enter.' An auction where one side cannot walk away measures value very poorly. The ticket spoils the price in turn: because people can't refuse, work that isn't worth doing gets done earnestly.

这套框架还顺手解释了为什么人们恐惧本应是好消息的机器——怕的不是机器,是门票功能的塌缩。作者说这指向一个比他预想「更简单、更近」的出路,完整论证挂在他的 SSRN 论文里。带走物不是政策方案,而是一把拆问题的刀:下次看到四天工作制、全民基本收入、AI 税之争,先问一句——这条理由谈的是工资的价格、门票,还是场所?许多对立的立场,只是把三个职位当成了一个。The frame also explains the fear of machines that ought to be good news: what people fear is the collapse of the ticket function. The author says this points to a way out that is simpler and nearer than he expected — the full derivation and data sit in his SSRN paper, which he invites readers to try to break. The takeaway isn't a policy; it's a knife for carving problems. Next time you see a fight about four-day weeks, universal basic income or an AI tax, ask first: is this argument about the price of the wage, the ticket, or the place? Many opposing positions turn out to be three jobs mistaken for one.

AI 思考AI Thinking

数学之美The Beauty of Math

每日 Lean 谜题 · 周六Daily Lean Puzzle · Saturday ★★★★★★☆

★6|USAMO 2012 第3题:无穷多条方程,两个素数,一次 Bézout★6 | USAMO 2012 Problem 3: Infinitely Many Equations, Two Primes, One Bézout

确定所有满足下列性质的整数 $n > 1$:存在一个由非零整数组成的无穷序列 $a_1, a_2, a_3, \ldots$,使得对每个正整数 $k$,都有 $a_k + 2a_{2k} + \cdots + n\,a_{nk} = 0$。Determine all integers $n > 1$ with the following property: there exists an infinite sequence $a_1, a_2, a_3, \ldots$ of nonzero integers such that $a_k + 2a_{2k} + \cdots + n\,a_{nk} = 0$ holds for every positive integer $k$.

「确定」意味着你不仅要构造,还要说明哪些 $n$ 不可能做到。在 Lean 题目文件里,答案集本身是要你自己定义的(`abbrev SolutionSet : Set ℕ := sorry`),然后证明「$n$ 属于答案集」与「这样的序列存在」互为充要——猜错答案集,第二问就证不动。'Determine' means you must both construct sequences and prove impossibility for the rest. In the Lean problem file you define the answer set yourself (`abbrev SolutionSet : Set ℕ := sorry`) and then prove the iff — guess the set wrong and the theorem won't budge.

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

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

import Mathlib.Algebra.Order.Ring.Star
import Mathlib.Algebra.Ring.IsFormallyReal
import Mathlib.Algebra.Order.Star.Int
import Mathlib.NumberTheory.Bertrand
import Mathlib.Tactic.NormNum.Prime

/-!
# USA Mathematical Olympiad 2012, Problem 3

Determine which integers n > 1 have the property that there exists an infinite
sequence a₁, a₂, a₃, ... of nonzero integers such that the equality

  aₖ + 2a₂ₖ + ⋯ + naₙₖ = 0

holds for every positive integer k.
-/

namespace Usa2012P3

namespace factorization

open Nat

end factorization

abbrev SolutionSet : Set ℕ := sorry

theorem usa2012_p3 (n : ℕ) (hn : 1 < n) :
    n ∈ SolutionSet ↔ ∃ a : ℕ → ℤ, (∀ i, 1 ≤ i → a i ≠ 0) ∧
      ∀ k, 1 ≤ k → ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * a (j * k) = 0 := by
  sorry

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

提示Hint

先在 $n=2$ 上做点小实验:只沿 $1, 2, 4, 8, \ldots$ 这条子列看方程会逼出什么。构造那一侧,不妨要求序列完全乘性($a_{jk}=a_j a_k$)——这一步会把无穷多个方程压缩成只有一个。First play with $n=2$: look at the equations only along the subsequence $1, 2, 4, 8, \ldots$ and see what they force. On the construction side, you may demand complete multiplicativity ($a_{jk} = a_j a_k$) — that collapses infinitely many equations into a single one.

答案与讲解Solution & walkthrough
  1. 答案:所有 $n \ge 3$。Lean 证明(solution.lean)先立下 `SolutionSet := { n | 2 < n }`,然后分两个方向。先把不可能的那一个钉死:$n=2$ 时方程是 $a_k + 2a_{2k} = 0$。取 $k = 1, 2, 4, \ldots, 2^{j-1}$ 一路迭代,得 `key : a 1 = (-2)^j * a (2^j)`——即 $2^j$ 整除 $a_1$ 对一切 $j$ 成立。非零整数不可能被 2 的任意高次幂整除(Lean 用 `Nat.lt_two_pow_self`,$|a_1| < 2^{|a_1|}$,取 $j = |a_1|$ 即矛盾)。这一步对应 lemma `not_property_two`。The answer: all $n \ge 3$. The Lean proof (solution.lean) starts by declaring `SolutionSet := { n | 2 < n }` and splits into two directions. First, the impossibility: for $n=2$ the relation is $a_k + 2a_{2k} = 0$. Iterating along $k = 1, 2, 4, \ldots, 2^{j-1}$ gives `key : a 1 = (-2)^j * a (2^j)` — so $2^j$ divides $a_1$ for every $j$. A nonzero integer cannot be divisible by arbitrarily high powers of 2 (Lean uses `Nat.lt_two_pow_self`: $|a_1| < 2^{|a_1|}$, contradicting divisibility at $j = |a_1|$). This is lemma `not_property_two`.
  2. 构造的主杠杆:把序列做成「完全乘性」的——$a_m$ 由它在素数上的取值决定,$a_m = \prod_r c(r)^{v_r(m)}$(Lean 的 `mulSeq P c`,$v_r$ 是 $r$ 在 $m$ 中的指数)。这样 $a(jk) = a(j)\,a(k)$,于是对任何 $k$,$\sum_j j\,a(jk) = a(k)\sum_j j\,a_j$:无穷多条方程全部是 $k=1$ 那一条的倍数,只要 $\sum_{j=1}^n j\,a_j = 0$ 一条成立就全都成立。这对应 lemma `condition_of_sum_eq_zero`——整个证明里最省力气的一步,也是「用对称性消元」的教科书演示。The master lever for construction: make the sequence completely multiplicative — $a_m = \prod_r c(r)^{v_r(m)}$ is determined by its values on primes (Lean's `mulSeq P c`, where $v_r$ is the exponent of $r$ in $m$). Then $a(jk) = a(j)\,a(k)$, so for any $k$, $\sum_j j\,a(jk) = a(k)\sum_j j\,a_j$: all infinitely many equations are scalar multiples of the $k=1$ one, and it suffices that $\sum_{j=1}^n j\,a_j = 0$. That's lemma `condition_of_sum_eq_zero` — the cheapest step in the proof and a textbook demo of killing variables with symmetry.
  3. $n \ge 9$ 时的棋子:Bertrand 公设($m>1$ 时 $(m, 2m]$ 内有素数,Lean 的 `Nat.exists_prime_lt_and_le_two_mul`)用两次——先取素数 $q$ 使 $\lceil n/2 \rceil \le q \le n+1$ 并可推出 $q \le n$、$n < 2q$;再取素数 $p$ 使 $\frac{q-1}{2} < p \le q-1$,于是 $p < q \le 2p$、$n < 4p$。素数的作用是把「动过手脚的位置」隔离开:除了 $p, q$ 以外的所有素数(注意包括 2 和 3!)一律令 $a_r = 1$,那么在 $1 \le j \le n$ 中只有 $j \in \{p, 2p, 3p, q\}$ 四个位置可能让 $a_j \ne 1$——$4p > n$ 挡住了 $4p$,$2q > n$ 挡住了 $2q$,而 $a_{2p} = a_{2}a_p = a_p$、$a_{3p} = a_{3}a_p = a_p$ 恰是因为 2、3 被设成了 1。这对应 `term_eq_zero` 与 `sum_mulSeq_cfun_sub_one`。Choosing the pieces for $n \ge 9$: Bertrand's postulate (a prime in $(m, 2m]$ for $m>1$; Lean's `Nat.exists_prime_lt_and_le_two_mul`) is used twice — first for a prime $q$ with $\lceil n/2 \rceil \le q \le n+1$, yielding $q \le n$ and $n < 2q$; then for a prime $p$ with $\frac{q-1}{2} < p \le q-1$, giving $p < q \le 2p$ and $n < 4p$. Primes isolate the tampered positions: set $a_r = 1$ for every prime $r \notin \{p, q\}$ — note this includes 2 and 3! Then among $1 \le j \le n$ only $j \in \{p, 2p, 3p, q\}$ can have $a_j \ne 1$: $4p > n$ blocks $4p$, $2q > n$ blocks $2q$, and $a_{2p} = a_2 a_p = a_p$, $a_{3p} = a_3 a_p = a_p$ precisely because 2 and 3 were set to 1. Lemmas `term_eq_zero` and `sum_mulSeq_cfun_sub_one` do this bookkeeping.
  4. 现在方程只剩两个未知数 $x = a_p$、$y = a_q$。记 $S = 1 + 2 + \cdots + n = n(n+1)/2$,把 $\sum_j j\,a_j = 0$ 按「哪些倍数落在 $[1,n]$ 里」分成三种情形:$3p \le n$ 时修正项是 $p + 2p + 3p = 6p$,方程为 $6p\,x + q\,y = 6p + q - S$;$2p \le n < 3p$ 时为 $3p\,x + q\,y = 3p + q - S$;$n < 2p$ 时为 $p\,x + q\,y = p + q - S$。三种情形各自的系数 $m \in \{6p, 3p, p\}$ 都与 $q$ 互素($q$ 是大于 $p \ge 5$ 的奇素数,除不掉 $6p$),Bézout 保证整数解存在。Now the equation has two unknowns $x = a_p$, $y = a_q$. Let $S = n(n+1)/2$; expanding $\sum_j j\,a_j = 0$ by which multiples land in $[1,n]$ gives three cases: if $3p \le n$ the correction is $p + 2p + 3p = 6p$ and $6p\,x + q\,y = 6p + q - S$; if $2p \le n < 3p$ it is $3p\,x + q\,y = 3p + q - S$; if $n < 2p$ it is $p\,x + q\,y = p + q - S$. In each case the coefficient $m \in \{6p, 3p, p\}$ is coprime to $q$ (an odd prime $> p \ge 5$, so it divides none of 6 or $p$), and Bézout guarantees integer solutions.
  5. Bézout 解还得「非零」——$a_p, a_q$ 不许取 0。Lean 的 lemma `bezout_nonzero` 把这件事做成了机械动作:拿到一组特解 $(uc, vc)$ 后,沿齐次方向平移 $(x, y) = (uc + Bt,\; vc - At)$,其中 $t = |uc| + |vc| + 1$。因为 $A, B > 0$ 且平移一步跨过零,新解一正一负、双双非零,一行 `lia` 收尾。主证明在 `exists_good_seq_of_nine_le` 里按 $2p, 3p$ 是否入区间挑好 $m$($p$、$3p$ 或 $6p$),调用它,再交回 `condition_of_sum_eq_zero`。But the Bézout solution must be nonzero — $a_p, a_q$ may not vanish. Lean's lemma `bezout_nonzero` mechanizes this: from any particular solution $(uc, vc)$, slide along the homogeneous direction, $(x, y) = (uc + Bt,\; vc - At)$ with $t = |uc| + |vc| + 1$; since $A, B > 0$, the shifted pair is nonzero in both coordinates (one positive, one negative), closed by one line of `lia`. The main lemma `exists_good_seq_of_nine_le` picks $m$ per case ($p$, $3p$ or $6p$), invokes Bézout, and hands the result back to `condition_of_sum_eq_zero`.
  6. 小情形 $3 \le n \le 8$ 不硬撑理论,直接给六个完全乘性序列(Lean 里逐个 `interval_cases n` 后 `decide`+`simp` 验算):$n=3$:$a_m = (-1)^{v_3(m)}$;$n=4$:$a_m = (-1)^{v_2(m)+v_3(m)}$;$n=5$:$a_m = (-2)^{v_5(m)}$;$n=6$:$a_m = 5^{v_2(m)}3^{v_3(m)}(-42)^{v_5(m)}$;$n=7$:$a_m = (-3)^{v_7(m)}$;$n=8$:$a_m = (-2)^{v_5(m)+v_7(m)}$。验算 $n=8$ 这条:$1+2+3+4-10+6-14+8 = 0$ ✓。有趣的是 $n=8$ 其实是 Bertrand 构造以 $(p,q)=(5,7)$ 的特例——官方风格的暴力与小构造在这里接上了。The small cases $3 \le n \le 8$ are not forced through theory — six explicit completely multiplicative sequences (Lean: `interval_cases n`, then `decide` plus `simp` arithmetic): $n=3$: $a_m = (-1)^{v_3(m)}$; $n=4$: $a_m = (-1)^{v_2(m)+v_3(m)}$; $n=5$: $a_m = (-2)^{v_5(m)}$; $n=6$: $a_m = 5^{v_2(m)}3^{v_3(m)}(-42)^{v_5(m)}$; $n=7$: $a_m = (-3)^{v_7(m)}$; $n=8$: $a_m = (-2)^{v_5(m)+v_7(m)}$. Check $n=8$: $1+2+3+4-10+6-14+8 = 0$ ✓. Delightfully, $n=8$ is in fact the Bertrand construction with $(p,q) = (5,7)$ — the brute force and the general construction meet at its edge.
/-
Copyright (c) 2026 The Compfiles Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kimi K3
-/

import Mathlib.Algebra.Order.Ring.Star
import Mathlib.Algebra.Ring.IsFormallyReal
import Mathlib.Algebra.Order.Star.Int
import Mathlib.NumberTheory.Bertrand
import Mathlib.Tactic.NormNum.Prime

/-!
# USA Mathematical Olympiad 2012, Problem 3

Determine which integers n > 1 have the property that there exists an infinite
sequence a₁, a₂, a₃, ... of nonzero integers such that the equality

  aₖ + 2a₂ₖ + ⋯ + naₙₖ = 0

holds for every positive integer k.
-/

namespace Usa2012P3

/-- A completely multiplicative sequence built from values assigned on a
finite set of primes: `mulSeq P c j = ∏ r ∈ P, c r ^ (Nat.factorization j r)`. -/
def mulSeq (P : Finset ℕ) (c : ℕ → ℤ) (j : ℕ) : ℤ :=
  ∏ r ∈ P, c r ^ (Nat.factorization j r)

lemma mulSeq_mul (P : Finset ℕ) (c : ℕ → ℤ) {u v : ℕ} (hu : u ≠ 0) (hv : v ≠ 0) :
    mulSeq P c (u * v) = mulSeq P c u * mulSeq P c v := by
  simp only [mulSeq, Nat.factorization_mul hu hv, Finsupp.add_apply, pow_add,
    Finset.prod_mul_distrib]

lemma mulSeq_ne_zero (P : Finset ℕ) (c : ℕ → ℤ) (hc : ∀ r ∈ P, c r ≠ 0) (j : ℕ) :
    mulSeq P c j ≠ 0 :=
  Finset.prod_ne_zero_iff.mpr fun r hr => pow_ne_zero _ (hc r hr)

/-- If the sum `∑ j ∈ [1, n], j * a j` vanishes for a completely multiplicative
sequence `a`, then `a` satisfies all the required identities. -/
lemma condition_of_sum_eq_zero {n : ℕ} {P : Finset ℕ} {c : ℕ → ℤ}
    (h : ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * mulSeq P c j = 0) (k : ℕ) (hk : 1 ≤ k) :
    ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * mulSeq P c (j * k) = 0 := by
  have hk0 : k ≠ 0 := by lia
  calc ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * mulSeq P c (j * k)
      = ∑ j ∈ Finset.Icc 1 n, mulSeq P c k * ((j : ℤ) * mulSeq P c j) := by
        apply Finset.sum_congr rfl
        intro j hj
        have hj0 : j ≠ 0 := by
          have h1 := (Finset.mem_Icc.mp hj).1
          lia
        rw [mulSeq_mul P c hj0 hk0]; ring
    _ = mulSeq P c k * ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * mulSeq P c j := by
        rw [Finset.mul_sum]
    _ = 0 := by rw [h, mul_zero]

/-- Bézout's identity, arranged so that both coefficients are nonzero. -/
lemma bezout_nonzero {A B c : ℤ} (hA : 0 < A) (hB : 0 < B) (h : IsCoprime A B) :
    ∃ x y : ℤ, x ≠ 0 ∧ y ≠ 0 ∧ A * x + B * y = c := by
  obtain ⟨u, v, huv⟩ := h
  have huc2 : -((u * c).natAbs : ℤ) ≤ u * c := by
    have h1 := Int.le_natAbs (a := -(u * c))
    rw [Int.natAbs_neg] at h1
    lia
  have hvc1 : v * c ≤ ((v * c).natAbs : ℤ) := Int.le_natAbs
  set t : ℤ := ((u * c).natAbs : ℤ) + ((v * c).natAbs : ℤ) + 1 with ht
  have ht0 : 0 < t := by lia
  have hBt : ((u * c).natAbs : ℤ) < B * t := by
    have h1 : t ≤ B * t := by
      have h2 : (1 : ℤ) * t ≤ B * t :=
        mul_le_mul_of_nonneg_right (by lia) (le_of_lt ht0)
      rwa [one_mul] at h2
    lia
  have hAt : ((v * c).natAbs : ℤ) < A * t := by
    have h1 : t ≤ A * t := by
      have h2 : (1 : ℤ) * t ≤ A * t :=
        mul_le_mul_of_nonneg_right (by lia) (le_of_lt ht0)
      rwa [one_mul] at h2
    lia
  refine ⟨u * c + B * t, v * c - A * t, by lia, by lia, ?_⟩
  have e : A * (u * c + B * t) + B * (v * c - A * t) = c * (u * A + v * B) := by ring
  rw [e, huv, mul_one]

/-- The case `n = 2` is impossible: the relation `a k + 2 * a (2 * k) = 0`
forces `2 ^ j ∣ a 1` for every `j`, so `a 1 = 0`. -/
lemma not_property_two {a : ℕ → ℤ} (ha : ∀ i, 1 ≤ i → a i ≠ 0)
    (h : ∀ k, 1 ≤ k → a k + 2 * a (2 * k) = 0) : False := by
  have key : ∀ j : ℕ, a 1 = (-2 : ℤ) ^ j * a (2 ^ j) := by
    intro j
    induction j with
    | zero => simp
    | succ j ih =>
      have h2j : 1 ≤ 2 ^ j := Nat.one_le_two_pow
      have hk := h (2 ^ j) h2j
      have e : (2 : ℕ) * 2 ^ j = 2 ^ (j + 1) := by ring
      rw [e] at hk
      have hstep : a (2 ^ j) = -2 * a (2 ^ (j + 1)) := by linarith [hk]
      rw [ih, hstep]; ring
  have hdvd : ∀ j : ℕ, (2 : ℤ) ^ j ∣ a 1 := by
    intro j
    refine ⟨(-1 : ℤ) ^ j * a (2 ^ j), ?_⟩
    have h2j : (-2 : ℤ) ^ j = (-1 : ℤ) ^ j * 2 ^ j := by
      rw [← mul_pow]; norm_num
    rw [key j, h2j]; ring
  have hdvdn : ∀ j : ℕ, (2 : ℕ) ^ j ∣ (a 1).natAbs := by
    intro j
    have h2 : ((2 : ℤ) ^ j).natAbs = 2 ^ j := by
      rw [Int.natAbs_pow]; simp
    rw [← h2]
    exact Int.natAbs_dvd_natAbs.mpr (hdvd j)
  have hpos : 0 < (a 1).natAbs := by
    rw [Nat.pos_iff_ne_zero, ne_eq, Int.natAbs_eq_zero]
    exact ha 1 le_rfl
  have hj : (a 1).natAbs < 2 ^ (a 1).natAbs := Nat.lt_two_pow_self
  have hle := Nat.le_of_dvd hpos (hdvdn (a 1).natAbs)
  lia

/-- The coefficient function assigning `x` to `p`, `y` to `q`, and `1` to
everything else. -/
def cfun (p q : ℕ) (x y : ℤ) (r : ℕ) : ℤ := if r = p then x else if r = q then y else 1

lemma mulSeq_cfun_apply {p q : ℕ} {x y : ℤ} (hpq : p ≠ q) (j : ℕ) :
    mulSeq {p, q} (cfun p q x y) j
      = x ^ (Nat.factorization j p) * y ^ (Nat.factorization j q) := by
  have hmem : p ∉ ({q} : Finset ℕ) := by
    simp only [Finset.mem_singleton]
    exact hpq
  rw [mulSeq, Finset.prod_insert hmem, Finset.prod_singleton]
  simp [cfun, hpq.symm]

lemma mulSeq_cfun_p {p q : ℕ} {x y : ℤ} (hp : p.Prime) (hplt : p < q) :
    mulSeq {p, q} (cfun p q x y) p = x := by
  have hpq : p ≠ q := ne_of_lt hplt
  rw [mulSeq_cfun_apply hpq, hp.factorization_self,
    Nat.factorization_eq_zero_of_not_dvd (Nat.not_dvd_of_pos_of_lt hp.pos hplt)]
  simp

lemma mulSeq_cfun_2p {p q : ℕ} {x y : ℤ} (hp : p.Prime) (hq : q.Prime) (hp5 : 5 ≤ p)
    (hq7 : 7 ≤ q) (hplt : p < q) :
    mulSeq {p, q} (cfun p q x y) (2 * p) = x := by
  have hpq : p ≠ q := ne_of_lt hplt
  have hfac1 : Nat.factorization (2 * p) p = 1 := by
    rw [Nat.factorization_mul (by norm_num) hp.ne_zero, Finsupp.add_apply,
      Nat.factorization_eq_zero_of_not_dvd
        (Nat.not_dvd_of_pos_of_lt (by norm_num) (by lia)),
      hp.factorization_self]
  have hfac2 : Nat.factorization (2 * p) q = 0 := by
    apply Nat.factorization_eq_zero_of_not_dvd
    intro h
    rcases hq.dvd_mul.mp h with h2 | hp'
    · exact Nat.not_dvd_of_pos_of_lt (by norm_num) (by lia) h2
    · exact Nat.not_dvd_of_pos_of_lt hp.pos hplt hp'
  rw [mulSeq_cfun_apply hpq, hfac1, hfac2]
  simp

lemma mulSeq_cfun_3p {p q : ℕ} {x y : ℤ} (hp : p.Prime) (hq : q.Prime) (hp5 : 5 ≤ p)
    (hq7 : 7 ≤ q) (hplt : p < q) :
    mulSeq {p, q} (cfun p q x y) (3 * p) = x := by
  have hpq : p ≠ q := ne_of_lt hplt
  have hfac1 : Nat.factorization (3 * p) p = 1 := by
    rw [Nat.factorization_mul (by norm_num) hp.ne_zero, Finsupp.add_apply,
      Nat.factorization_eq_zero_of_not_dvd
        (Nat.not_dvd_of_pos_of_lt (by norm_num) (by lia)),
      hp.factorization_self]
  have hfac2 : Nat.factorization (3 * p) q = 0 := by
    apply Nat.factorization_eq_zero_of_not_dvd
    intro h
    rcases hq.dvd_mul.mp h with h3 | hp'
    · exact Nat.not_dvd_of_pos_of_lt (by norm_num) (by lia) h3
    · exact Nat.not_dvd_of_pos_of_lt hp.pos hplt hp'
  rw [mulSeq_cfun_apply hpq, hfac1, hfac2]
  simp

lemma mulSeq_cfun_q {p q : ℕ} {x y : ℤ} (hp : p.Prime) (hq : q.Prime) (hplt : p < q) :
    mulSeq {p, q} (cfun p q x y) q = y := by
  have hpq : p ≠ q := ne_of_lt hplt
  have hfac : Nat.factorization q p = 0 := by
    apply Nat.factorization_eq_zero_of_not_dvd
    intro h
    exact hpq ((Nat.prime_dvd_prime_iff_eq hp hq).mp h)
  rw [mulSeq_cfun_apply hpq, hfac, hq.factorization_self]
  simp

/-- Terms `j * (a j - 1)` vanish when `j ∈ [1, n]` is none of `p, 2p, 3p, q`:
such a `j` is divisible by neither `p` nor `q`, so `a j = 1`. -/
lemma term_eq_zero {n p q j : ℕ} {x y : ℤ} (hplt : p < q)
    (h2q : n < 2 * q) (h4p : n < 4 * p) (hj1 : 1 ≤ j) (hjn : j ≤ n)
    (h1 : j ≠ p) (h2 : j ≠ 2 * p) (h3 : j ≠ 3 * p) (h4 : j ≠ q) :
    (j : ℤ) * (mulSeq {p, q} (cfun p q x y) j - 1) = 0 := by
  have hpq : p ≠ q := ne_of_lt hplt
  have h4p' : n < p * 4 := by lia
  have h2q' : n < q * 2 := by lia
  have hpdvd : ¬ p ∣ j := by
    rintro ⟨e, rfl⟩
    have he1 : 1 ≤ e := by
      rcases Nat.eq_zero_or_pos e with he | he
      · subst he; simp at hj1
      · exact he
    have he4 : e < 4 := Nat.lt_of_mul_lt_mul_left (lt_of_le_of_lt hjn h4p')
    interval_cases e
    · exact h1 (by ring)
    · exact h2 (by ring)
    · exact h3 (by ring)
  have hqdvd : ¬ q ∣ j := by
    rintro ⟨e, rfl⟩
    have he1 : 1 ≤ e := by
      rcases Nat.eq_zero_or_pos e with he | he
      · subst he; simp at hj1
      · exact he
    have he2 : e < 2 := Nat.lt_of_mul_lt_mul_left (lt_of_le_of_lt hjn h2q')
    interval_cases e
    · exact h4 (by ring)
  rw [mulSeq_cfun_apply hpq, Nat.factorization_eq_zero_of_not_dvd hpdvd,
    Nat.factorization_eq_zero_of_not_dvd hqdvd]
  simp

/-- The correction terms in `∑ j ∈ [1,n], j * (a j - 1)`: the only nonzero
contributions come from `j ∈ {p, 2p, 3p, q} ∩ [1, n]`. -/
lemma sum_mulSeq_cfun_sub_one {n p q : ℕ} {x y : ℤ} (hp : p.Prime) (hq : q.Prime)
    (hp5 : 5 ≤ p) (hq7 : 7 ≤ q) (hplt : p < q)
    (h2q : n < 2 * q) (h4p : n < 4 * p) (hpn : p ≤ n) (hqn : q ≤ n) :
    ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * (mulSeq {p, q} (cfun p q x y) j - 1)
      = (p : ℤ) * (x - 1)
        + (if 2 * p ≤ n then ((2 * p : ℕ) : ℤ) * (x - 1) else 0)
        + (if 3 * p ≤ n then ((3 * p : ℕ) : ℤ) * (x - 1) else 0)
        + (q : ℤ) * (y - 1) := by
  have hpq : p ≠ q := ne_of_lt hplt
  have h2p_ne : 2 * p ≠ q := by
    have hqodd : q % 2 = 1 := by
      rcases hq.eq_two_or_odd with h | h
      · lia
      · exact h
    lia
  have h3p_ne : 3 * p ≠ q := by
    intro h
    exact hpq ((Nat.prime_dvd_prime_iff_eq hp hq).mp ⟨3, by rw [mul_comm]; exact h.symm⟩)
  by_cases h2 : 2 * p ≤ n
  · by_cases h3 : 3 * p ≤ n
    · -- case `3 * p ≤ n`: multiples of `p` in `[1, n]` are `p, 2p, 3p`
      rw [ite_eq_left h2, ite_eq_left h3]
      have hss : ({p, 2 * p, 3 * p, q} : Finset ℕ) ⊆ Finset.Icc 1 n := by
        intro j hj
        simp only [Finset.mem_insert, Finset.mem_singleton] at hj
        rw [Finset.mem_Icc]
        rcases hj with rfl | rfl | rfl | rfl
        · exact ⟨by lia, hpn⟩
        · exact ⟨by lia, h2⟩
        · exact ⟨by lia, h3⟩
        · exact ⟨by lia, hqn⟩
      have hvan : ∀ j ∈ Finset.Icc 1 n, j ∉ ({p, 2 * p, 3 * p, q} : Finset ℕ) →
          (j : ℤ) * (mulSeq {p, q} (cfun p q x y) j - 1) = 0 := by
        intro j hj hjs
        simp only [Finset.mem_insert, Finset.mem_singleton] at hjs
        rw [Finset.mem_Icc] at hj
        push Not at hjs
        exact term_eq_zero hplt h2q h4p hj.1 hj.2 hjs.1 hjs.2.1 hjs.2.2.1 hjs.2.2.2
      have hsub := (Finset.sum_subset hss hvan).symm
      rw [hsub, Finset.sum_insert (by simp; lia),
        Finset.sum_insert (by simp; lia), Finset.sum_insert (by simp; lia),
        Finset.sum_singleton, mulSeq_cfun_p hp hplt, mulSeq_cfun_2p hp hq hp5 hq7 hplt,
        mulSeq_cfun_3p hp hq hp5 hq7 hplt, mulSeq_cfun_q hp hq hplt]
      ring
    · -- case `2 * p ≤ n < 3 * p`: multiples of `p` in `[1, n]` are `p, 2p`
      rw [ite_eq_left h2, ite_eq_right h3]
      have hss : ({p, 2 * p, q} : Finset ℕ) ⊆ Finset.Icc 1 n := by
        intro j hj
        simp only [Finset.mem_insert, Finset.mem_singleton] at hj
        rw [Finset.mem_Icc]
        rcases hj with rfl | rfl | rfl
        · exact ⟨by lia, hpn⟩
        · exact ⟨by lia, h2⟩
        · exact ⟨by lia, hqn⟩
      have hvan : ∀ j ∈ Finset.Icc 1 n, j ∉ ({p, 2 * p, q} : Finset ℕ) →
          (j : ℤ) * (mulSeq {p, q} (cfun p q x y) j - 1) = 0 := by
        intro j hj hjs
        simp only [Finset.mem_insert, Finset.mem_singleton] at hjs
        rw [Finset.mem_Icc] at hj
        push Not at hjs
        exact term_eq_zero hplt h2q h4p hj.1 hj.2 hjs.1 hjs.2.1 (by lia) hjs.2.2
      have hsub := (Finset.sum_subset hss hvan).symm
      rw [hsub, Finset.sum_insert (by simp; lia),
        Finset.sum_insert (by simp; lia), Finset.sum_singleton,
        mulSeq_cfun_p hp hplt, mulSeq_cfun_2p hp hq hp5 hq7 hplt,
        mulSeq_cfun_q hp hq hplt]
      ring
  · by_cases h3 : 3 * p ≤ n
    · lia
    · -- case `n < 2 * p`: the only multiple of `p` in `[1, n]` is `p`
      rw [ite_eq_right h2, ite_eq_right h3]
      have hss : ({p, q} : Finset ℕ) ⊆ Finset.Icc 1 n := by
        intro j hj
        simp only [Finset.mem_insert, Finset.mem_singleton] at hj
        rw [Finset.mem_Icc]
        rcases hj with rfl | rfl
        · exact ⟨by lia, hpn⟩
        · exact ⟨by lia, hqn⟩
      have hvan : ∀ j ∈ Finset.Icc 1 n, j ∉ ({p, q} : Finset ℕ) →
          (j : ℤ) * (mulSeq {p, q} (cfun p q x y) j - 1) = 0 := by
        intro j hj hjs
        simp only [Finset.mem_insert, Finset.mem_singleton] at hjs
        rw [Finset.mem_Icc] at hj
        push Not at hjs
        exact term_eq_zero hplt h2q h4p hj.1 hj.2 hjs.1 (by lia) (by lia) hjs.2
      have hsub := (Finset.sum_subset hss hvan).symm
      rw [hsub, Finset.sum_insert (by simp; lia), Finset.sum_singleton,
        mulSeq_cfun_p hp hplt, mulSeq_cfun_q hp hq hplt]
      ring

/-- Construction for `9 ≤ n`: pick primes `p`, `q` via Bertrand's postulate with
`⌈n/2⌉ < q ≤ 2⌈n/2⌉` and `(q-1)/2 < p ≤ q-1`, take `a r = 1` for primes `r ∉ {p, q}`,
and choose nonzero `a p`, `a q` by Bézout so that `∑ j ∈ [1,n], j * a j = 0`. -/
lemma exists_good_seq_of_nine_le {n : ℕ} (hn : 9 ≤ n) :
    ∃ a : ℕ → ℤ, (∀ i, 1 ≤ i → a i ≠ 0) ∧
      ∀ k, 1 ≤ k → ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * a (j * k) = 0 := by
  obtain ⟨q, hq, hm_lt, hq_le⟩ :=
    Nat.exists_prime_lt_and_le_two_mul ((n + 1) / 2) (by lia)
  have hq6 : 6 ≤ q := by lia
  have hq7 : 7 ≤ q := by
    rcases lt_or_ge q 7 with h | h
    · interval_cases q
      · norm_num at hq
    · exact h
  have hqodd : q % 2 = 1 := by
    rcases hq.eq_two_or_odd with h | h
    · lia
    · exact h
  have h2q : n < 2 * q := by lia
  have hq_le_n : q ≤ n := by
    by_contra hlt
    push Not at hlt
    have hqn1 : q = n + 1 := by lia
    subst hqn1
    lia
  obtain ⟨p, hp, hp_gt, hp_le⟩ :=
    Nat.exists_prime_lt_and_le_two_mul ((q - 1) / 2) (by lia)
  have hp4 : 4 ≤ p := by lia
  have hp5 : 5 ≤ p := by
    rcases lt_or_ge p 5 with h | h
    · interval_cases p
      · norm_num at hp
    · exact h
  have hplt : p < q := by lia
  have h2p_ge : q ≤ 2 * p := by lia
  have h4p : n < 4 * p := by lia
  have hpn : p ≤ n := by lia
  set S : ℤ := ∑ j ∈ Finset.Icc 1 n, (j : ℤ) with hS
  have build : ∀ m : ℕ, 0 < m → Nat.Coprime m q →
      (m : ℤ) = (p : ℤ) + (if 2 * p ≤ n then ((2 * p : ℕ) : ℤ) else 0)
        + (if 3 * p ≤ n then ((3 * p : ℕ) : ℤ) else 0) →
      ∃ a : ℕ → ℤ, (∀ i, 1 ≤ i → a i ≠ 0) ∧
        ∀ k, 1 ≤ k → ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * a (j * k) = 0 := by
    intro m hm0 hcop_nat hm_eq
    have hcop : IsCoprime (m : ℤ) (q : ℤ) := Nat.isCoprime_iff_coprime.mpr hcop_nat
    obtain ⟨x, y, hx, hy, hbez⟩ := bezout_nonzero (A := (m : ℤ)) (B := (q : ℤ))
      (c := (m : ℤ) + q - S) (Nat.cast_pos.mpr hm0) (Nat.cast_pos.mpr hq.pos) hcop
    refine ⟨mulSeq {p, q} (cfun p q x y), ?_, ?_⟩
    · intro i _
      apply mulSeq_ne_zero
      intro r hr
      simp only [Finset.mem_insert, Finset.mem_singleton] at hr
      rcases hr with hrp | hrq
      · rw [hrp]
        show (if p = p then x else if p = q then y else 1) ≠ 0
        rw [ite_eq_left rfl]
        exact hx
      · rw [hrq]
        show (if q = p then x else if q = q then y else 1) ≠ 0
        rw [ite_eq_right (ne_of_lt hplt).symm, ite_eq_left rfl]
        exact hy
    · intro k hk
      apply condition_of_sum_eq_zero _ k hk
      have hsplit : ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * mulSeq {p, q} (cfun p q x y) j
          = S + ∑ j ∈ Finset.Icc 1 n,
              (j : ℤ) * (mulSeq {p, q} (cfun p q x y) j - 1) := by
        rw [hS, ← Finset.sum_add_distrib]
        exact Finset.sum_congr rfl fun j _ => by ring
      rw [hsplit, sum_mulSeq_cfun_sub_one hp hq hp5 hq7 hplt h2q h4p hpn hq_le_n]
      by_cases h3 : 3 * p ≤ n
      · have h2 : 2 * p ≤ n := by lia
        simp only [ite_eq_left h2, ite_eq_left h3] at hm_eq hbez ⊢
        rw [hm_eq] at hbez
        linear_combination hbez
      · by_cases h2 : 2 * p ≤ n
        · simp only [ite_eq_right h3, ite_eq_left h2] at hm_eq hbez ⊢
          rw [hm_eq] at hbez
          linear_combination hbez
        · simp only [ite_eq_right h3, ite_eq_right h2] at hm_eq hbez ⊢
          rw [hm_eq] at hbez
          linear_combination hbez
  rcases lt_or_ge n (3 * p) with h3 | h3
  · rcases lt_or_ge n (2 * p) with h2 | h2
    · -- here the only multiple of `p` in `[1, n]` is `p`, and `p` is coprime to `q`
      have hcop : Nat.Coprime p q := by
        apply Nat.Coprime.symm
        rw [hq.coprime_iff_not_dvd]
        exact Nat.not_dvd_of_pos_of_lt hp.pos hplt
      exact build p (by lia) hcop (by
        rw [ite_eq_right (by lia : ¬ 2 * p ≤ n), ite_eq_right (by lia : ¬ 3 * p ≤ n)]
        ring)
    · -- here the multiples of `p` in `[1, n]` are `p, 2p`, and `3 * p` is coprime to `q`
      have hcop : Nat.Coprime (3 * p) q := by
        apply Nat.Coprime.symm
        rw [hq.coprime_iff_not_dvd]
        intro h
        rcases hq.dvd_mul.mp h with h3' | hp'
        · exact Nat.not_dvd_of_pos_of_lt (by norm_num) (by lia) h3'
        · exact Nat.not_dvd_of_pos_of_lt hp.pos hplt hp'
      exact build (3 * p) (by lia) hcop (by
        rw [ite_eq_left h2, ite_eq_right (by lia : ¬ 3 * p ≤ n)]
        push_cast
        ring)
  · -- here the multiples of `p` in `[1, n]` are `p, 2p, 3p`, and `6 * p` is coprime to `q`
    have hcop : Nat.Coprime (6 * p) q := by
      apply Nat.Coprime.symm
      rw [hq.coprime_iff_not_dvd]
      intro h
      rcases hq.dvd_mul.mp h with h6 | hp'
      · exact Nat.not_dvd_of_pos_of_lt (by norm_num) (by lia) h6
      · exact Nat.not_dvd_of_pos_of_lt hp.pos hplt hp'
    exact build (6 * p) (by lia) hcop (by
      have h2 : 2 * p ≤ n := by lia
      rw [ite_eq_left h2, ite_eq_left h3]
      push_cast
      ring)

/-- The small cases `3 ≤ n ≤ 8`, each given by an explicit completely
multiplicative sequence. -/
lemma small_case (n : ℕ) (P : Finset ℕ) (c : ℕ → ℤ) (hc : ∀ r ∈ P, c r ≠ 0)
    (hsum : ∑ j ∈ Finset.range n, (j + 1 : ℤ) * mulSeq P c (j + 1) = 0) :
    ∃ a : ℕ → ℤ, (∀ i, 1 ≤ i → a i ≠ 0) ∧
      ∀ k, 1 ≤ k → ∑ j ∈ Finset.range n, (j + 1 : ℤ) * a ((j + 1) * k) = 0 := by
  refine ⟨mulSeq P c, fun i _ => mulSeq_ne_zero P c hc i, fun k hk => ?_⟩
  replace hsum : ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * mulSeq P c j = 0 := by
    simpa [← Finset.Ico_add_one_right_eq_Icc, Finset.sum_Ico_eq_sum_range, add_comm] using hsum
  have := condition_of_sum_eq_zero hsum k hk
  simpa [← Finset.Ico_add_one_right_eq_Icc, Finset.sum_Ico_eq_sum_range, add_comm]

/-! Lemmas for factorization of small numbres. -/
namespace factorization

open Nat

lemma f22 : factorization 2 2 = 1 := by norm_num

lemma f23 : factorization 2 3 = 0 := by norm_num

lemma f25 : factorization 2 5 = 0 := by norm_num

lemma f27 : factorization 2 7 = 0 := by norm_num

lemma f32 : factorization 3 2 = 0 := by norm_num

lemma f33 : factorization 3 3 = 1 := by norm_num

lemma f35 : factorization 3 5 = 0 := by norm_num

lemma f37 : factorization 3 7 = 0 := by norm_num

lemma f42 : factorization 4 2 = 2 := by
  rw [show (4 : ℕ) = 2 * 2 from rfl, factorization_mul, Finsupp.add_apply, f22]
  all_goals norm_num

lemma f43 : factorization 4 3 = 0 := by
  rw [Nat.factorization_eq_zero_of_not_dvd]
  norm_num

lemma f45 : factorization 4 5 = 0 := by
  rw [Nat.factorization_eq_zero_of_not_dvd]
  norm_num

lemma f47 : factorization 4 7 = 0 := by
  rw [Nat.factorization_eq_zero_of_not_dvd]
  norm_num

lemma f52 : factorization 5 2 = 0 := by norm_num

lemma f53 : factorization 5 3 = 0 := by norm_num

lemma f55 : factorization 5 5 = 1 := by norm_num

lemma f57 : factorization 5 7 = 0 := by norm_num

lemma f62 : factorization 6 2 = 1 := by
  rw [show 6 = 2 * 3 by norm_num, factorization_mul]
  all_goals norm_num

lemma f63 : factorization 6 3 = 1 := by
  rw [show 6 = 2 * 3 by norm_num, factorization_mul]
  all_goals norm_num

lemma f65 : factorization 6 5 = 0 := by
  rw [Nat.factorization_eq_zero_of_not_dvd]
  norm_num

lemma f67 : factorization 6 7 = 0 := by
  rw [Nat.factorization_eq_zero_of_not_dvd]
  norm_num

lemma f75 : factorization 7 5 = 0 := by
  rw [Nat.factorization_eq_zero_of_not_dvd]
  norm_num

lemma f77 : factorization 7 7 = 1 := by norm_num

lemma f85 : factorization 8 5 = 0 := by
  rw [Nat.factorization_eq_zero_of_not_dvd]
  norm_num

lemma f87 : factorization 8 7 = 0 := by
  rw [Nat.factorization_eq_zero_of_not_dvd]
  norm_num

end factorization

abbrev SolutionSet : Set ℕ := { n | 2 < n }

theorem usa2012_p3 (n : ℕ) (hn : 1 < n) :
    n ∈ SolutionSet ↔ ∃ a : ℕ → ℤ, (∀ i, 1 ≤ i → a i ≠ 0) ∧
      ∀ k, 1 ≤ k → ∑ j ∈ Finset.Icc 1 n, (j : ℤ) * a (j * k) = 0 := by
  show (2 < n) ↔ _
  constructor
  · intro h2n
    rcases lt_or_ge n 9 with h9 | h9
    · interval_cases n
      open factorization in
      · refine small_case 3 {3} (fun _ => -1) (by decide) ?_
        simp [Finset.sum_range_succ, mulSeq, f23, f33]
      · refine small_case 4 {2, 3} (fun _ => -1) (by decide) ?_
        simp [Finset.sum_range_succ, mulSeq, f22, f23, f32, f33, f42, f43]
      · refine small_case 5 {5} (fun _ => -2) (by decide) ?_
        simp [Finset.sum_range_succ, mulSeq, f25, f35, f45, f55]
      · refine small_case 6 {2, 3, 5} (fun r => if r = 2 then 5 else if r = 3 then 3 else -42) (by decide) ?_
        simp [Finset.sum_range_succ, mulSeq,
          f22, f23, f25, f32, f33, f35, f42, f43, f45, f52, f53, f55, f62, f63, f65]
      · refine small_case 7 {7} (fun _ => -3) (by decide) ?_
        simp [Finset.sum_range_succ, mulSeq, f27, f37, f47, f57, f67, f77]
      · refine small_case 8 {5, 7} (fun _ => -2) (by decide) ?_
        simp [Finset.sum_range_succ, Finset.range_one, Finset.sum_singleton, mulSeq,
          f25, f27, f35, f37, f45, f47, f55, f57, f65, f67, f75, f77, f85, f87]
    · exact exists_good_seq_of_nine_le (by lia)
  · rintro ⟨a, ha, hsum⟩
    by_contra hlt
    push Not at hlt
    have hn2 : n = 2 := by lia
    subst hn2
    have h2 : ∀ k, 1 ≤ k → a k + 2 * a (2 * k) = 0 := by
      intro k hk
      have hk0 := hsum k hk
      rw [show Finset.Icc (1 : ℕ) 2 = {1, 2} by decide,
        Finset.sum_insert (by decide : (1 : ℕ) ∉ ({2} : Finset ℕ)),
        Finset.sum_singleton] at hk0
      simp only [Nat.cast_one, Nat.cast_two, one_mul] at hk0
      exact hk0
    exact not_property_two ha h2

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

人的思考A human's take

USAMO 2012 Solution Notes(§1.3 USAMO 2012/3,题出 Gabriel Carroll) — Evan Chen(陈谊廷)

Evan Chen 在开头交代这些笔记是「我的解法+组委会官方解法+社区解法」的混合,文字由他统一维护,并且风格比官方解答更先进、更紧凑——他明说不回避标准工具。Evan Chen states up front that these notes mix his own solutions, the organizers' official ones, and community-found solutions, with all writing maintained by him — and warns the style runs more advanced and terse than the official answers, deliberately not shying away from standard tools.

他对本题的路线:答案是所有 $n>2$。$n=2$ 由 $a_{2^k} = a_1/2^{k+1}$ 逐层除下去直接否掉;构造侧他先把序列设成完全乘性($a_{ij} = a_i a_j$,由素数取值决定),并点明「想法是取两个大素数然后用 Bézout 定理,但细节需要相当的小心」。His route through this problem: the answer is all $n>2$. The $n=2$ case dies by iterating $a_{2^k} = a_1/2^{k+1}$; on the construction side he first demands complete multiplicativity ($a_{ij} = a_i a_j$, determined by prime values) and names the plan — 'take two large primes and use Bezout's theorem, but the details require significant care.'

Bertrand 公设用两次钉出 $\lceil n/2 \rceil < q < 2\lceil n/2 \rceil$ 与 $\frac{1}{2}(q-1) < p < q-1$,其余素数(包括 2 和 3)全赋 1,于是和式里只有 $p, 2p, 3p, q$ 四个修正位置;按 $2p, 3p$ 是否落入 $[1,n]$ 分三种情形,分别得到 $6p x + q y = 6p + q - \tfrac12 n(n+1)$、$3p$ 版、$p$ 版——每种都因为 $\gcd(\cdot, q) = 1$ 而被 Bézout 解开。Bertrand's postulate is invoked twice to pin $\lceil n/2 \rceil < q < 2\lceil n/2 \rceil$ and $\frac{1}{2}(q-1) < p < q-1$; every other prime, 2 and 3 included, gets value 1, so the sum has only four correction positions $p, 2p, 3p, q$. Splitting by whether $2p, 3p$ lie in $[1,n]$ yields $6p x + q y = 6p + q - \tfrac12 n(n+1)$ and its $3p$ and $p$ variants — each solvable by Bézout because the leading coefficient is coprime to $q$.

他特意补了一句:第三种情形(只有 $p$ 入区间)在个别边缘值上也可能成立,比如 $n=9$ 配 $(q,p)=(7,5)$。He adds an honest edge-case remark: the third case can also hold for isolated values, for example $n=9$ with $(q,p)=(7,5)$.

小情形他老老实实枚举:$n=3,4,5,6,7$ 各给一个显式的乘性公式($(-1)^{\nu_3}$、$(-1)^{\nu_2+\nu_3}$、$(-2)^{\nu_5}$、$5^{\nu_2}3^{\nu_3}(-42)^{\nu_5}$、$(-3)^{\nu_7}$),$n=8$ 则指出可以直接沿用前面的大构造取 $(p,q)=(5,7)$,最后一句「This completes the constructions for all $n > 2$」。页面还挂了本题的 AoPS 讨论帖链接(aops.com/community/p2669119)。For the small $n$ he simply enumerates: explicit multiplicative formulas for $n=3,4,5,6,7$ ($(-1)^{\nu_3}$, $(-1)^{\nu_2+\nu_3}$, $(-2)^{\nu_5}$, $5^{\nu_2}3^{\nu_3}(-42)^{\nu_5}$, $(-3)^{\nu_7}$), and for $n=8$ a note that the general construction already works with $(p,q)=(5,7)$ — closing with 'This completes the constructions for all $n > 2$.' The page also links the AoPS discussion thread (aops.com/community/p2669119).

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

这道题最迷人的地方,是它把「无限」驯服成了「有限」。条件是无穷多条方程——对每个 $k$ 都成立一条——看上去像要管理无穷多个自由度。而完全乘性这个要求,等于主动给序列加上最大的对称性:对称性一加,无穷多条方程立刻降秩成一条,剩下的工作全是数数与解一个丢番图方程。这是数学里反复出现的招:与其穷举无穷,不如先假设答案有足够对称性,把无穷问题压回有限。Bertrand 公设的角色也值得玩味:一个关于「素数分布足够密」的存在性定理,在这里被用来精准布置两个「安全的位置」——$p$ 与 $q$ 大到让 $2q、4p$ 越过 $n$,又小到留在 $[1,n]$ 里,恰好圈出四个修正项。竞赛题的表面是初等的,骨头却是「用深的定理干准的活」。Lean 形式化还额外教了一课:题目文件里 `SolutionSet` 是要你自己定义的——「确定所有」意味着答案本身就是开放格,猜错集合,后面的 iff 一步都动不了。证明里那段 `bezout_nonzero` 把「非零解」写成显式平移 $t = |uc| + |vc| + 1$,人类解答常常一句话带过的「显然可取非零」,机器逼着你把显然拆开——拆开后你会发现,那个显然里藏着整道题最老实的一步。What makes this problem delightful is how it domesticates the infinite. The condition is infinitely many equations — one for every $k$ — which looks like managing infinitely many degrees of freedom. Demanding complete multiplicativity is volunteering the maximum possible symmetry, and symmetry collapses the infinite system down to a single equation; the rest is bookkeeping and one Diophantine solve. It's a recurring move in mathematics: rather than enumerate the infinite, assume the answer is symmetric enough to compress it back to the finite. Bertrand's postulate plays an equally interesting role: an existence theorem about how densely primes fall, used here to place two 'safe positions' just right — $p$ and $q$ large enough that $2q$ and $4p$ overshoot $n$, small enough to stay inside it, fencing in exactly four correction sites. The surface of the problem is elementary; the bones say 'aim a deep theorem at a precise job.' The Lean formalization teaches one more thing: in the problem file `SolutionSet` is a blank you must fill yourself — 'determine all' means the answer set is itself an open hole, and a wrong guess freezes every later step. And the `bezout_nonzero` lemma, making nonzero-ness explicit as a shift by $t = |uc| + |vc| + 1$, forces you to unpack the human solution's breezy 'clearly we can arrange nonzero' — unpacked, that 'clearly' turns out to be the most honest step in the whole proof.

✓ 已通过 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-rc2 · Mathlib 1c2b155

程序员随想Programmer Reflections

哲学与生活Philosophy and Life

工具角Tools Corner