# How small can intervals be and still contain a prime times a power of 2?

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

-
There are existing proofs of prime gaps around $N$ of size larger than any constant times $\log N$ (Westzynthius 1931, Rankin 1938). My suspicion is that those proofs can be quickly modified to show that there are gaps in the 2-factorable numbers around $N$ of size larger than any constant times $\log N$. – Greg Martin Aug 10 '11 at 23:24
The numbers that aren't 2-factorable appear in oeis.org/A105441 although there is no further information about them there. I note that there are 7 in a row starting at 285, 9 in a row from 527. – Gerry Myerson Aug 10 '11 at 23:40
Indeed Greg, Westzynthius's paper is a starting point on a personal journey which includes this question. I don't know about Rankin's result, but I doubt that W's method can be so extended. However, I am no expert, and can be convinced otherwise. Gerry's data alone I find inspiring. Gerhard "Ask Me About System Design" Paseman, 2011.08.10 – Gerhard Paseman Aug 11 '11 at 0:18
@Gerhard: No way to know whether W's method can be extended without trying (good luck!). Constructions of large prime gaps usually use the Chinese remainder theorem to ensure that each integer in the interval has a specified-in-advance prime factor; the same construction should prevent numbers from being primes times a power of 2, not just from being primes. That's my feeling anyway. – Greg Martin Aug 13 '11 at 18:45