AFTD Auto-Formalizing Theoretical Domains

halving_partition_count

def

The number of halving partitions of $n$, denoted $a(n)$, is the cardinality (using Set.ncard) of the set of lists $p$ of positive integers that are halving partitions of $n$ (satisfying is_halving_partition n p), which are sequences $(p_1, \dots, p_k)$ summing to $n$ where $p_1 \in \{\lfloor n/2 \rfloor, \lceil n/2 \rceil\}$ and each successive part $p_i \in \{\lfloor p_{i-1}/2 \rfloor, \lceil p_{i-1}/2 \rceil\}$, with the empty list being the unique halving partition of $0$.

Statement

noncomputable def halving_partition_count (n : ℕ) : ℕ
Defined in
arXiv:2611.01243 Definition 1
Verified
03 Nov 2026
Axioms
none listed
Built on 1
  • is_halving_partitionA sequence of positive integers $(p_1, \dots, p_k)$ is a halving partition of $n \ge 1$ if…
Used by 3

Read back from the Lean

The function halving_partition_count assigns to each natural number $n$ the cardinality (as a natural number via Set.ncard) of the set of lists $p$ of natural numbers satisfying is_halving_partition n p. Here, is_halving_partition n p asserts: 1. Every element $x$ in $p$ is strictly positive ($x > 0$). 2. The sum of the elements of $p$ is equal to $n$ (p.sum = n). 3. If $p$ is empty, then $n = 0$. 4. If $p$ is non-empty with first element $p_1$, then: - $p_1 = \lfloor n / 2 \rfloor$ or $p_1 = \lfloor (n + 1) / 2 \rfloor$, and - for every adjacent pair of elements $(x, y)$ in $p$ (where $x$ immediately precedes $y$), $y = \lfloor x / 2 \rfloor$ or $y = \lfloor (x + 1) / 2 \rfloor$ (via List.IsChain).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The number of halving partitions of n, denoted a(n) in arXiv:2611.01243. -/
noncomputable def halving_partition_count (n : ℕ) : ℕ := Set.ncard { p : List ℕ | is_halving_partition n p }
See it in the graphDiscuss this resultChallenge it