If we define $\nu(n)$ as the binary digit sum of the natural number $n$. I want to quickly calculate a strange floor and ceiling of a rational $x$:
$\lceil x\rceil_b=\min(\{m\in N|m\ge x,\nu(m)\le b\})$
$\lfloor x\rfloor_b=\max(\{m\in N|m\le x,\nu(m)\le b\})$
I am spending the vast majority of my computer time calculating these bounds in a search for a counterexample to the second part of Knuth's question 43 in Vol 2 4.6.3 TAOCP. This is exact equality in the Scholz-Brauer conjecture from addition chains.
I calculate two bounds on an integer $x$ with positive integers $t,l$: $\lfloor {n-t\over a}\rfloor_b \ge x \ge \lceil {n-t.l\over a}\rceil_b$
It strikes me that doing these divisions on the current 128 bit candidate $n=2^{127}-1$ then adjusting the result up and down based on the binary digit sum is a waste. I should either code up my own division and bail out early based on the leading MSB of the quotient or code using floating point and try to do the same. I am assuming that in most cases I can get away with a single precision (64 bit divide) to calculate the upper bits of the quotient since it will have a digit sum greater than $1\le b\le8$. Might be unlikely the upper bit's sum doesn't exceed $b$ since $b < 64$. I am interested if people have done this kind of optimization before? Thoughts on this problem?
Here is an example from the running program:
$n = 170141183460469231731687303715884105727$, $a = 12215343170424930634021$, $t = 1498815112880766320924$,$l = 13510798882111488$, $b=2$
$\lfloor {n - t \over a} \rfloor_2 \le 13928481671510059$
$\lceil {n - t*l \over a} \rceil_2 \ge 12270714937569271$
Both of the bounds converge to $13510798882111488$ once we look at the binary digit sum.