There was a question on MathOverflow which has since disappeared, that was on sums of at most M B-smooth numbers. It asked several questions related to how many could be found in the interval $[N-d,N]$, where $N$ was given and $d$ was some parameter of size to be determined, but a starting guess for $d$ was $O(\text{log}N)$. I can't refer to it, but I can refer to another question on factoring some number in an interval, namely this question.
These questions, and other questions, and my thinking about Jacobsthal function, lead me to present the following. Recall a positive integer $N$ is B-smooth if every prime factor which divides $N$ is less than B, or $N$ is B-smooth and $p \mid N$ implies $p <=$ B . Let me call $M$ B-factored (there may be standard terminology but I do not recall it) if $M=PN$, where $N$ is B-smooth and $P$ is either 1 or $P$ is a prime larger than B.
I suggested that for B not large there were likely to be occurrences of B-factored numbers in an interval of the form $[N-d,N]$ as above, and that if a probabilistic algorithm to find one was wanted, a simple one could be devised using trial factorization, Fermat tests, and other handy ingredients. Also, if $d$ were $O(\text{log}N)$, the chances of success at finding one (and then later verifying the complete factorization using some computationally expensive test) were very high.
I am now convincing myself that the probability of success is in fact 1, and this would jar (but not necessarily contradict) with the intuition I am developing about gaps between primes. So I ask for help with some questions to create some clarity.
In the following, B=2, and I will ask the reader to create her or his own variation with larger B. Also let $d = \text{ceil}(\text{log}_2(N))$ until we change it (so for most $N$, $d$ is the number of bits used in writing $N$ in binary. First a (hopefully true) result.
1) For $N > 2$ there are $\pi(N)$ B-factorable numbers in the interval $(N/2,N]$ .
This result suggests (but does not imply) there are at least twice as many B-factored numbers as primes in $[N-d,N]$.
2) True or false: for $N > 1$, there is at least one B-factored number in the interval $[N -d, N]$ .
This should be true be considering how thin the complement of B-factored numbers is intially; even though they grow to an eventual density of 1, I imagine (but do not know) that they do so slowly enough for 2) to be true.
3) How small are the gaps between B-factored numbers? In other words, how much can $d$ (as a function of $N$) can be adjusted so as to be made true?
Even though there are gaps between primes which are several times larger than the average gap d, it is suspected such gaps get no larger than $O(d^2)$, and observed gaps are much smaller. I am working with the idea that such gaps get no larger than something like $cd(\text{log} d)^3$ for some small constant $c < 4$. For B-factored numbers, a large gap between them is like asking for $\text{log}_2N$-many large gaps to appear in the primes at just the right places, and so that one can expect or even prove reults much better than 2) above. Also, one can ask for $d$ as a function of B and $N$, but I prefer the simple version with B=2 for now
EDIT 2011.08.10 A computer run suggests that there are no 2-factored numbers in the interval $[2312,2325]$. This is the smallest of many such examples saying that 2) is false; my computer also says 35647 is the last of 30 consecutive numbers which are not 2-factored. It may be that Greg Martin is right and that some proofs in the literature can be expanded to include this case. However, there is still B$>2$ to be considered. END EDIT 2011.08.10
Gerhard "Ask Me About System Design" Paseman, 2011.08.10
