Voucher costs of permutations: the seven exceptions are the only ones

Abstract

A buying order is a permutation v=(v₁,…,vₙ) of {1,…,n}, and its voucher cost is C_V(v)=v₁+v₁v₂+v₂v₃+…+vₙ₋₁vₙ. Call a positive integer c achievable if c=C_V(v) for some buying order of some length. The authors of [voucher], who study this quantity through its extremes, observed that 2,5,6,12,13,14,22 are not achievable and that a computer search found no further exceptions; the completeness of that list is left there as an observation supported by a counting heuristic, not as a theorem. We prove it: a positive integer is a voucher cost if and only if it is none of those seven. The proof splits at 215. Below that bound 207 explicit buying orders settle every value. Above it the argument is a deficit calculus anchored at the identity buying order: three exact reindexing identities move a permutation of {1,…,M} to one of {1,…,M+2} with a controlled change in cost, two tables of 266 inner orders at M=8,9 seed them, and the resulting cost bands overlap from [215,325] upward. All statements are machine-checked in Lean 4, and the completeness theorem uses no compiled evaluation: its finite content is 1346 explicit permutations verified by kernel reduction.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   f6dbe2828378d0f20488ea575a08d5f2035d48f0ffc97779065f2730a62d309d