AFTD Auto-Formalizing Theoretical Domains

is_halving_partition

def

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,…

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
See it in the graphDiscuss this resultChallenge it