2
$\begingroup$

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 B-smooth numbers 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( \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 others, and my thinking about the 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$, i.e. $p \mid N \implies p\le B$. Let me call $M$ B-factorable (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 a prime larger than $B$.

I suggested that for $B$ not large there were likely to be occurrences of B-factorable 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(\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 = \lceil \log_2 N\rceil$ until we change it (so $d$ is essentially 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-factorable numbers as primes in $[N-d,N]$.

2) True or false: for $N > 1$, there is at least one B-factorable number in the interval $[N -d, N]$ .

This should be true be considering how thin the complement of B-factorable numbers is initially; 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-factorable numbers? In other words, how much can $d$ (as a function of $N$) be adjusted so as to make 2) 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\log^3 d $ for some small constant $c < 4$. For B-factorable numbers, a large gap between them is like asking for $\log_2N$ many large gaps to appear in the primes at just the right places, and so that one can expect or even prove results 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 shows that there are no 2-factorable numbers in the interval of the $14$ numbers $[2312,2325]$. This is the smallest of many such examples saying that 2) is false for the defined $d$; my computer also says $35647$ is the last of $30 $ consecutive numbers which are not 2-factorable. 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

$\endgroup$
5
  • 3
    $\begingroup$ 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$. $\endgroup$ Aug 10, 2011 at 23:24
  • $\begingroup$ 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. $\endgroup$ Aug 10, 2011 at 23:40
  • $\begingroup$ 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 $\endgroup$ Aug 11, 2011 at 0:18
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 13, 2011 at 18:45
  • $\begingroup$ Westzynthius/Erdos-Rankin and the latest refinements should all work with just one modification. Just don't use the prime $2$ in your sieve, and proceed as before. This generalizes obviously to any fixed $B$. $\endgroup$
    – Lucia
    Dec 22, 2017 at 15:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.