halving_partition_count
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
- halving_partition_kernel_even_reductionFor all natural numbers e, r, and n, the halving partition count satisfies halving_partition_count (2 ^ (e + 1) * n + 2 * r) =…
- halving_partition_count_two_powFor every natural number e, the number of halving partitions of 2^e is equal to 1, that is, halving_partition_count (2 ^ e) = 1.
- halving_partition_count_two_mulFor every natural number n, the number of halving partitions of 2n equals the number of halving partitions of n, that is,…
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 }