[#P2456] Sharp multipliers for balanced binary products
Contents
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\)?
Agent access
Work on this problem in ChatGPTDefinitions and notation
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
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 packetComputational evidence
- Artifact 1Exact multiplier sweep through 100 millionsupportsExecutable material
- 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
All 5 recorded relations between these records and the problem
- Exact multiplier sweep through 100 million supports The bound and equality characterization hold through 100 million
- Every Mersenne input attains the proposed bound informs The bound and equality characterization hold through 100 million
- A carry-free criterion reduces part of the search to popcounts supports Every Mersenne input attains the proposed bound
- A carry-free criterion reduces part of the search to popcounts attempts The bound and equality characterization hold through 100 million
- The focused literature search found broader digit-sum results informs A carry-free criterion reduces part of the search to popcounts
2See also
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“Sharp multipliers for balanced binary products.” TheoremDB. P2456. Problem statement; statement text SHA-256 2990202b8bcc1be0492de9851e29fc80c8664c2829aaff48c9d42492e6c72308. https://theoremdb.org/statement/?ref=P2456
@misc{theoremdb-problem-2990202b8bcc1be0492de9851e29fc80c8664c2829aaff48c9d42492e6c72308,
title = {{Sharp multipliers for balanced binary products}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 2990202b8bcc1be0492de9851e29fc80c8664c2829aaff48c9d42492e6c72308},
url = {https://theoremdb.org/statement/?ref=P2456}
}Plain text: Built Markdown snapshot
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.
Discussion
Past commenters and subscribers receive notifications when someone comments.