Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$ \begin{align} 1100 & = 2\times2\times5\times5\times11 \\ 1101 & =3\times 367 \\ 1102 & =2\times19\times29 \\ 1103 & =1103 \\ 1104 & = 2\times2\times2\times2\times 3\times23 \\ 1105 & = 5\times13\times17 \\ 1106 & = 2\times7\times79 \end{align} $$ In looking at this list of prime factorizations, I see that all of the first 10 prime numbers, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, appear within the factorizations of only seven consecutive integers. (The next prime number, 31, has its multiples as far from 1100 as it could hope to get them (1085 and 1116).) So no nearby number could hope to be divisible by 29 or 23, nor even by 7 for suitably adjusted values of "nearby". Consequently when you're factoring nearby numbers, you're deprived of those small primes as potential factors by which they might be divisible. So nearby numbers, for lack of small primes that could divide them, must be divisible by large primes. And accordingly, not far away, we find $1099=7\times157$ (157 doesn't show up so often---only once every 157 steps---that you'd usually expect to find it so close by) and likewise 1098 is divisible by 61, 1008 by 277, 1096 by 137, 1095 by 73, 1094 by 547, etc.; and 1097 and 1109 are themselves prime.

So if an unusually large number of small primes occur unusually close together as factors, then an unusually large number of large primes must also be in the neighborhood.

Are there known precise results quantifying this phenomenon?

share|improve this question
Here is a way to rephrase your question: Let $P(n)$ be the largest prime factor dividing $n$. Then we are looking at the statistics of $P(n)$. In particular, your statement corresponds to a statement concerning the average of $P(n)$ on a short interval. If we can prove that in a particular neighborhood of $x$, $P(n)$ will always have a particular average, then it follows that if I have a sequence of $n$ such that $P(n)$ is small, then on some larger interval I will have a disproportionate number of $n$ such that it is large. –  Eric Naslund Oct 18 '11 at 21:19
You're asking us to do a lot of work. To make any sense of your question, we have to quantify what you mean by small primes, and what you mean by large primes, and how close is unusually close, and how many small primes it takes to be an unusually large number, and what's a neighborhood, and how many large primes it takes to be an unusually large number. And then we still have to answer the question! So it's only fair to ask: is it worth it? Is there any payoff? Will you be able to use the answer to do something else? –  Gerry Myerson Oct 19 '11 at 2:19
@Gerry: My question was "Are there known precise results quantifying this phenomenon?" To know the answer to that question is to know that all that hard work has already been done. But I don't know that; hence my question. –  Michael Hardy Oct 19 '11 at 16:01
Just to make it doubly clear to whom it may concern that you were not asking for extra work, I have added the "reference-request" tag to your excellent question. –  Mike Jones Oct 20 '11 at 9:43
Question also posted to MathOverflow, mathoverflow.net/questions/78626/… –  Gerry Myerson Oct 20 '11 at 11:52
show 4 more comments

2 Answers

The phenomenon you describe seems to be the concept behind the Sieve of Eratosthenes.

Every number below $ \sqrt{N} $ where $ N $ is the number you want to factorize will appear at least once in the list of possible factors. Looking at the list generated by the Sieve, it will become obvious that only primes remain. A factorization using the Sieve then implies trial division by the primes up to $ \sqrt{N}$. This concept lets us see that obviously, if "many" small primes were used to remove elements in the Sieve, the remaining elements will have larger prime factors, possibly being primes themselves.

However: no generalization of any kind is possible, since every number's occurence is cyclic. Think of a Fourier Transform , using prime factors as frequencies. 2 appears every second number, 3 every third and so on. At any point $N$, there is no way to determine if there are primes nearby of if the numbers nearby will have "large primes" as factors without it's value.

I could also relate what you're saying to the concept of Mersenne Primes. Essentially, primes in the form $2^{n}–1$ the largest known being $(2^{43,112,609} – 1)$, which also happens to be the largest prime known. In this case, they are looking for primes in the viscinity of exponents of 2, which is also saying the that largest factor is a large prime, right?

So yes, it stands to reason that if $N$ isn't a prime and has small factors, numbers nearby have a chance to have greater factors. No quantification of that is useful, however.

share|improve this answer
I'd like to point you towards Factorial Primes as well since it is an other way people look for primes and test their surroundings. I believe those type of numbers fit the criterion of appropriate surroundings, but keeping the Sieve in mind, I can assume no generalization is possible. –  user1178317 Feb 2 '12 at 17:15
"the largest prime possible in the viscinity of $N$ has to be close to the value of $\sqrt{N}$": That's not true. $\sqrt{74}$ is between $8$ and $9$, and its largest prime factor is $37$. And $73$ is a prime in the vicinity of $74$, and $73$ is not close to $\sqrt{74}$. –  Michael Hardy Feb 23 '12 at 2:02
"Every number below $\sqrt{N}$ where $N$ is the number you want to factorize will appear at least once in the list of previous numbers." I don't know what that means. The only statement involving $\sqrt{N}$ that I know is true and that immediately comes to mind as something related to this is that if $N$ has no prime factors less than or equal to $\sqrt{N}$, then $N$ is prime. But that doesn't look like what you're trying to say. –  Michael Hardy Feb 23 '12 at 2:07
@MichaelHardy Thank you for your comments, I tried to fix it as best as I could. You should see why I was talking about $ \sqrt{N}$ at the same time as the Sieve, now. –  user1178317 Feb 23 '12 at 19:38
add comment

It seems to me you could examine your conjecture experimentally by taking suitable definitions of "small window" and "large window", S(.) and L(.) say. You also need some notion of 'density of small prime factors', say D.

Your conjecture then seems to be that the frequency of large prime factors in L(.) is monotonically related to DS(.). i.e. as one increases, so does the other.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.