The base-\(b\) representation of \(N\) may have \(d = 2, 3, \ldots, \lfloor \log_2 N \rfloor + 1\) digits. For each \(d\), we want to find fast enough the number of integers \(b\) such that the base-\(N\) representation of \(N\) has \(d\) digits, each of which is \(0\) or \(1\).

Now we fix \(d\) and count the number of integers \(b\) (which we call good integers) such that the base-\(N\) representation of \(N\) has \(d\) digits.

If \(d=2\), \(b = N-1\) (if \(N \geq 3\)) and \(b = N\) are the good integers.

Next, we assume \(d \geq 3\). \(b\) is a good integers only if \(N\) is between \(1000\ldots 0\) and \(111\ldots 1\), base \(b\); in other words, only if \(N\) is contained in the segment \([l_b, r_b] \coloneqq [b^{d-1}, b^{d-1} + b^{d-2} + \cdots + b + 1]\). Here, if \(b \neq b'\), then two segments \([l_b, r_b]\) and \([l_{b'}, r_{b'}]\) are disjoint; indeed we have

\[r_{b} = \sum_{i=0}^{d-1} b^i \lt \sum_{i=0}^{d-1}\binom{d-1}{i}b^i = (b+1)^{d-1} = l_{b+1}\]

(whose inequality is due to \(d \geq 3\)). Therefore, the only candidate of a good integer \(b\) is the maximum integer \(\hat{b}\) such that \(\hat{b}^{d-1} \leq N\). Hence, all that left is actually representing \(N\) in base \(\hat{b}\) and check if every digit is \(0\) or \(1\). One can find fast enough the maximum integer \(\hat{b}\) such that \(\hat{b}^{d-1} \leq N\) with a binary search.