is_halving_partition
A sequence of positive integers $(p_1, \dots, p_k)$ is a halving partition of $n \ge 1$ if $p_1 \in \{\lfloor n/2 \rfloor, \lceil n/2 \rceil\}$, $p_i \in \{\lfloor p_{i-1}/2 \rfloor, \lceil p_{i-1}/2 \rceil\}$ for $2 \le i \le k$, and $\sum_{i=1}^k p_i = n$; the empty sequence is the unique halving partition of $0$.
Statement
def is_halving_partition (n : ℕ) (p : List ℕ) : Prop
- Defined in
- arXiv:2611.01243 Definition 1
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Used by 4
- halving_partition_countThe number of halving partitions of $n$, denoted $a(n)$, is the cardinality (using
Set.ncard) of the set of lists $p$ of positive… - halving_partition_length_leFor every positive integer n and every halving partition p of n, the length of p is at most Nat.log 2 n + (Nat.digits 2 n).sum.
- 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,…
- halving_partition_countThe number of halving partitions of $n$, denoted $a(n)$, is the cardinality (using
Read back from the Lean
A natural number n and a list of natural numbers p satisfy is_halving_partition n p if and only if:
1. Every element x of p is strictly positive (0 < x),
2. The sum of the elements of p equals n (p.sum = n), and
3. Either:
- p is empty and n = 0, or
- p is non-empty with head p1, such that p1 = n / 2 or p1 = (n + 1) / 2 (using natural number division), and for every pair of adjacent elements x followed by y in p, y = x / 2 or y = (x + 1) / 2 (i.e., List.IsChain (fun x y => y = x / 2 ∨ y = (x + 1) / 2) p).
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
/-- Predicate that a list of positive integers is a halving partition of n. -/ def is_halving_partition (n : ℕ) (p : List ℕ) : Prop := (∀ x ∈ p, 0 < x) ∧ p.sum = n ∧ match p with | [] => n = 0 | p1 :: _ => (p1 = n / 2 ∨ p1 = (n + 1) / 2) ∧ List.IsChain (fun x y => y = x / 2 ∨ y = (x + 1) / 2) p