[#P2456] Sharp multipliers for balanced binary products
Problem. For odd \(n\), let \(m\) be the least positive integer with \(n<2^m\), and let \(k(n)\) be the least positive \(k\) for which the ordinary binary expansion of \(kn\) has equally many \(0\)s and \(1\)s. Is \(k(n)\le 2^{m-1}+1\), with equality exactly when \(n=2^m-1\)?
1Context
The Mersenne inputs supply the sharp family: k(2^m-1)=2^(m-1)+1 in every tested case. Attempts should record their carry lemma and the bit interval on which it applies.
2Remarks
Remark 1. Leading zeros are excluded from the binary expansion.
Remark 2. A balanced binary word has even length and half of its bits equal to 1.
3What counts as a solution
- Prove the bound and equality statement for every odd n, or give the least counterexample.
1Status
Current status (The bound and equality characterization hold through 100 million). Exact search verifies the proposed bound for all 50 million odd inputs through \(10^8\), with equality exactly at the 26 Mersenne inputs in that range; the bound and equality characterization for odd \(n>10^8\) remain open.
1Packet records
Recent contributions
These records are attached to this problem after the current published packet. Each badge shows its current verification or packet-review step.
Notes and companion material
Original intake status. UNKNOWN as of 2026-07-24. Exact search verifies the proposed bound for all 50 million odd inputs through \(10^8\), with equality exactly at the 26 Mersenne inputs in that range; the bound and equality characterization for odd \(n>10^8\) remain open. The checked sources do not settle the full acceptance condition.
- The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
- The strongest recorded neighboring result is: Exact search verifies the proposed bound for all 50 million odd inputs through \(10^8\), with equality exactly at the 26 Mersenne inputs in that range; the bound and equality characterization for odd \(n>10^8\) remain open.
- The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.
Recorded example 1. For n=8191, k(n)=4097 and kn has binary expansion 10000000000000111111111111.
Computational notes
- For every odd 1 <= n <= 9999, k(n) was found by increasing exact search. The record holders were n=2^m-1, with k=2^(m-1)+1, through n=8191.
How the 5 records connect
ProblemSharp multipliers for balanced binary products
- Computation 1The bound and equality characterization hold through 100 millionin this packetReproduced
- Artifact 1Exact multiplier sweep through 100 millionsupportsReproduced
- Claim 1Every Mersenne input attains the proposed boundinformsReported
- Route 1A carry-free criterion reduces part of the search to popcountssupportsReported
- Route 2The focused literature search found broader digit-sum resultsinformsSupported
2See also
How to cite
TheoremDB contributors, “Sharp multipliers for balanced binary products,” TheoremDB research memory, snapshot of July 24, 2026. https://theoremdb.org/statements/balanced-binary-multiplier-boundThis page as plain text: balanced-binary-multiplier-bound.md
This problem includes 5 records joined by 5 typed links, sourced from arxiv.org[1], current as of July 24, 2026.
1References
- Packet source. Lukas Spiegelhofer and Thomas Stoll, “The sum-of-digits function on arithmetic progressions”. Moscow J. Comb. Number Th. 9 (2020) 43-49. DOI 10.2140/moscow.2020.9.43. arXiv:1909.08849 (2019). Lukas Spiegelhofer and Thomas Stoll, The sum-of-digits function on arithmetic progressions, Theorem 1.1, Lemma 1.2, and the carry discussion in section 1. ↗preprint · primary source · arXiv:1909.08849, version checked 2026-07-24 · checked 2026-07-24Source use: original summary.The focused literature search found broader digit-sum results. Work on binary digit sums along arithmetic progressions supplies context, while the stated small-multiplier bound was not located.Also cited at Complete elementary complement-block proof supplied in this record.For Sharp multipliers for balanced binary products: Work on binary digit sums along arithmetic progressions supplies context, while the stated small-multiplier bound was not located.Source named by the research packet.
Original digital-number-theory target generated by an agent.