Setup. Suppose we are given a function $$f:\mathbb N\to\{\text{False},\text{True}\}$$ such that $$f(n)=\text{True}\implies f(n+1)=\text{True}$$ and such that $f(n)=\text{True}$ for some $n$ large enough.
In natural language. The function $f$ imposes a condition on the natural numbers which is fulfilled once $n$ is large enough.
My question 1. How can I, for any given $f$, find the smallest $n$ such that $f(n)=\text{True}$?
A first idea would be to start with $n=1$ and to increment $n$ by one until $f(n)$ is True. However, this is fairly slow. The next step is a "binary search" algorithm (see below).
My question 2. How can I implement a good algorithm in Mathematica?
Here is an example of the first algorithm that I thought of, implemented in Python:
def bin_search(cond):
n = 1
while not cond(n):
n *= 2
lower_bound = n//2
upper_bound = n
middle = (lower_bound + upper_bound)//2
while upper_bound - lower_bound > 1:
if cond(middle):
upper_bound = middle
else:
lower_bound = middle
middle = (lower_bound + upper_bound)//2
return upper_bound
For example, one such condition would be $$f(n)=[H_n\geq 10],$$
where $$H_n=\sum_{i=1}^n \frac 1i$$ is the $n$th harmonic number.
EDIT: A remark about the harmonic numbers: In fact I wanted to compare the runtime of a good brute force method against an intelligent method for this problem. For solving $H_n\geq 10$, it suffices to find the smallest integer $n$ such that $$\ln(n)+\gamma\geq 10,$$ where $\gamma$ denotes the Euler-Mascheroni constant. So we can find $$n=[ \exp(10-\gamma)],$$ where $[\cdot]$ denotes the nearest integer function.