← 完整题目索引

PROJECT EULER · #0623

拉姆达计数

Lambda Count

仅题目 · 待解原题 ↗

lambda 演算是函数式编程语言核心的通用计算模型。它基于lambda-terms,这是一种最小的编程语言,仅具有函数定义、函数调用和变量。 Lambda 术语根据以下规则构建:

  • 任何变量 x(来自某个无限字母表的单个字母)都是 lambda 项。
  • 如果 MN 是 lambda 项,则 (MN) 是 lambda 项,称为 MN应用
  • 如果 x 是变量,M 是项,则 (λx.M) 是 lambda 项,称为抽象。抽象定义了一个匿名函数,以 x 作为参数并发送回 M

如果对于所有变量 xT 中出现的所有 x 都包含在 T 中的某个抽象 (λx.M) 中,则称 lambda 项 T封闭的。最小的这样的抽象被认为是绑定变量x的出现。换句话说,如果 lambda 项的所有变量都绑定到封闭函数定义的参数,则该 lambda 项是封闭的。例如,项 (λx.x) 是封闭的,而项 (λx.(xy)) 不是封闭的,因为 y 没有绑定。

此外,只要绑定抽象不发生变化,我们就可以重命名变量。这意味着 (λx.x)(λy.y) 应该被认为是等效的,因为我们只是重命名了一个参数。与此类重命名等效的两个项称为α-equivalent。请注意, (λx.(λy.(xy)))(λx.(λx.(xx))) 不等价于 α,因为绑定第一个变量的抽象是外部变量,并成为内部变量。然而,(λx.(λy.(xy)))(λy.(λx.(yx)))α等价的。

下表重新组合了最多可以使用 15 符号编写的 lambda 项,符号包括括号、λ、点和变量。

(λx.x)(λx.(xx))(λx.(λy.x))(λx.(λy.y))(λx.(x(xx)))(λx.((xx)x))(λx.(λy.(xx)))(λx.(λy.(xy)))(λx.(λy.(yx)))(λx.(λy.(yy)))(λx.(x(λy.x)))(λx.(x(λy.y)))(λx.((λy.x)x))(λx.((λy.y)x))((λx.x)(λx.x))(λx.(x(x(xx))))(λx.(x((xx)x)))(λx.((xx)(xx)))(λx.((x(xx))x))(λx.(((xx)x)x))

Λ(n) 为最多可以使用 n 符号编写的不同封闭 lambda 项的数量,其中 α 彼此等价的项只应计算一次。已知 Λ(6)=1Λ(9)=2Λ(15)=20Λ(35)=3166438

查找 Λ(2000)。给出答案以 1000000007 为模。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。