# P2456: Sharp multipliers for balanced binary products

- ID: `P2456`
- Reference: `balanced-binary-multiplier-bound`
- Page: https://theoremdb.org/statements/P2456
- Record maturity: Reviewed problem with recorded work

## 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\)?

### Remarks

- **Remark.** Leading zeros are excluded from the binary expansion.
- **Remark.** A balanced binary word has even length and half of its bits equal to 1.

### What counts as a solution

- Prove the bound and equality statement for every odd n, or give the least counterexample.

## Status

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.

## Work

### Evidence for the current status

**Computation 1 (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.

For each odd \(n\leq10^8\), the computation set \(m=\operatorname{bitlength}(n)\), \(B=2^{m-1}+1\), and tested \(k=1,2,\ldots,B\) in order. The first \(k\) for which \(kn\) had even bit length and half of its bits equal to 1 was recorded as \(k(n)\).

This loop gives a finite stopping proof for each input. Finding a balanced product at \(k\) proves minimality because every smaller multiplier has been rejected. Exhausting \(1\leq k\leq B\) would exhibit a counterexample to the bound. A hit at \(B\) is compared directly with \(n=2^m-1\), so either direction of the proposed equality characterization would stop the run on its first failure.

The run checked 50,000,000 odd values of \(n\) and 724,052,131 multiplier candidates. It found no failure. Equality occurred 26 times, at \(n=2^m-1\) for \(1\leq m\leq26\). The largest minimum in range was \(k(67108863)=33554433\). The FNV-1a checksum of the little-endian 64-bit words \((n\ll32)\mathbin{|}k(n)\), in increasing \(n\), is `6955bbea71c91c4c`.

This record certifies the stated finite range. The universal bound and the converse assertion about equality remain open in this entry.

### Background and intake notes

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.

- Original intake status: Novelty and status remain unverified. Restricted-digit multiple problems are a folklore-rich area.
- Pairing n with its binary complement inside an m-bit block is the attractive construction.
- Multiplication by the proposed small k creates carries across the complement boundary. Popcount identities without a carry state prove only special bit patterns.

- Recorded example: For n=8191, k(n)=4097 and kn has binary expansion 10000000000000111111111111.

### Other known results

- **Claim 1** (reported): For every m at least 1, k(2^m-1)=2^(m-1)+1. [1](#reference-1)

### Prior approaches

- **Route 1** (reported): Inside the interval ka<=2^m, balancedness is equivalent to an exact difference of two binary digit sums.
- **Route 2** (supported): Work on binary digit sums along arithmetic progressions supplies context, while the stated small-multiplier bound was not located. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): A self-contained C program checks the bound, minimality, and equality condition for every odd input in the stated range.

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `balanced-binary-multiplier-bound`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://arxiv.org/abs/1909.08849
   - Also cited at Complete elementary complement-block proof supplied in this record
   - preprint; primary source; arXiv:1909.08849, version checked 2026-07-24; checked 2026-08-01
   - Source use: original_summary
   - 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.