My question is related to this question posted on math.SE:
Given an odd number, what is the quickest (constant-time) algorithm for finding its largest factor and suppose you can call a helper function $B$ which takes as its input $(N, k)$ and outputs True iff $N$ has a factor greater than or equal to $k$? Obviously, the factor cannot be itself.
My slightly altered problem statement goes like this.
Given an odd integer $n$, find its largest factor (that is not itself). You can call a function $B(m,k)$ that returns $1$ iff $m$ has a factor smaller than $k$. The function runs in constant time.
Can this be done faster than $O(\log n)$ in the average case (assuming the input is chosen uniformly at random)? Is my altered problem statement any better than the original? Specifically, I know that the probability some large number will have no factor smaller than $M$ is asymptotic to $\frac{1}{\log M}$ (see A, and B). Can you use this to your advantage?
You can also assume that division is constant time.
Edit and Attempt Solution:
$ \newcommand{\ha}[2]{\left[#1 \dots #2\right)} \newcommand{\expa}[1]{2^{#1}} \newcommand{\expb}[1]{2^{2^{#1}}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\expv}[1]{\mathrm{E}\left(#1\right)} \newcommand{\sch}{\mathbb{S}} \newcommand{\floor}[1]{\left\lfloor#1 \right\rfloor} \newcommand{\logb}[1]{\log \log #1} $ The difference between my problem statement and the original, is the definition of the function $B$. In the original, $B(N,k)$ returns $1$ if $N$ has a factor greater than or equal to $k$; in my version, this happens if $N$ has a factor less than $k$.
By making this change, I aim to capitalize on the fact that the probability of a large $N$ having no factors smaller than $M$ is asymptotic to $(\log M)^{-1}$. While this fact does not change the worst-case performance of an algorithm, it can change average-case performance. Here, by average case, I mean probabilistic analysis of the algorithm over random, uniformly distributed inputs.
(Note that my question involves only exact algorithms)
I conjectured in my comment to the related question that you can benefit from the probability by changing the way in which you partition your search space when performing a binary search (since it is much more likely for the solution to be in $\ha{1}{1000}$ instead of $\ha{1000}{N}$). I also conjectured the algorithm could run in $O(\logb N)$ average-case.
Attempted Solution
I decided to do some work on the problem myself, and I think I have a solution. I haven't really done this sort of analysis previously, so I may have some error, and there is definitely a lot missing in terms of details. I think the idea is correct, though. Note that here I find the smallest factor of $N$. We can easily find the largest factor by division (which I assume to be contstant time).
I'm posting it as part of the question because I'm not sure if it's correct, and I still want to know if there's a better way.
Let us partition the search space $\sch = \ha{1}{N}$ into disjoint integer intervals, $$ r_k = \ha{\expb k}{\expb {k+1}} \qquad 0 \leq k \leq \floor{\logb N}$$
Note that it can be that, $$ \expb{\floor{\logb N+1}} > N$$ That doesn't really matter; all we want from the partitioning $r$ is to contain the entire search space.
Now, the probability that the smallest factor of $N$, which we will call $A$, is greater than $m$ is asymptotic to $(\log m)^{-1}$. Then let, $P(A > \expb{k}) = 2^{-k}$, where $A$ is taken to be a random variable. If we let $P(r_k)$ denote the probability that $A \in r_i$, we can calculate this as: $$P(r_k) = P(a > \expb{k}) - P(a > \expb{k+1}) = 2^{-(k+1)}$$
We can identify which partition $r_k$ contains $A$ by calling the function $B(N,\expb{k})$ up to $\floor{\logb N} + 1$ times. After finding the $r_k$, we then perform a binary search for $A$ in the partition, which involves $\log \abs{r_k}$ operations. Here we note that: $$|r_k|=\expb{k+1}-\expb{k} = \expb{k}\left(\expb{k} - 1\right)\leq \expb{k+1}$$
Let $X$ be a random variable representing the number of operations taken by the binary search. The value of $X$ for the case when $A \in r_k$ is given $X_k = \log \expb{k+1} = 2^{k+1}$. The expected value of $X$ is then, $$\expv{X} = \sum_{k=0}^{\floor{\logb N} + 1} X_i P(r_i) = \sum_{k=0}^{\floor{\logb N} + 1} 2^{k+1}\cdot 2^{-(k+1)} = \floor{\logb N} +1$$
Notes
I've considered partitioning the search space using triple-exponentiation (e.g. $\expa{\expb{k}}$), but that provides no benefit. There might be a way to make the search algorithm inside the partitions faster though, but I'm not sure how.
You can also reduce the search space drastically (such as to something like $\sqrt{N}$), but I think this will have a constant speedup at most.
