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.

Suppose I'm looking at prime factorizations of numbers in the vicinity of this one: $$ 1354 = 2 \times 677 $$ The smallest prime appears here, and the next prime after that does not.

Going one step in each direction, I get \begin{align} 1355 & = 5\times271 \\ 1354 & = 2\times677 \\ 1353 & = 3\times11\times 41 \end{align} The set of primes seen so far includes the following initial segment of the sequence of all primes: $\{2,3,5\}$.

Taking it another step: \begin{align} 1356 & = 2\times2\times3\times113\\ 1355 & = 5\times271 \\ 1354 & = 2\times677 \\ 1353 & = 3\times11\times 41 \\ 1352 & = 2\times2\times2\times13\times13 \end{align} The set of primes seen so far still includes only the following initial segment of the sequence of all primes: $\{2,3,5\}$.

Another step: \begin{align} 1357 & = 23\times59 \\ 1356 & = 2\times2\times3\times113\\ 1355 & = 5\times271 \\ 1354 & = 2\times677 \\ 1353 & = 3\times11\times 41 \\ 1352 & = 2\times2\times2\times13\times13 \\ 1351 & = 7\times193 \end{align} The set of primes seen so far includes the following initial segment of the sequence of all primes: $\{2,3,5,7,11,13\}$.

Another step: \begin{align} 1358 & = 2\times7\times97 \\ 1357 & = 23\times59 \\ 1356 & = 2\times2\times3\times113\\ 1355 & = 5\times271 \\ 1354 & = 2\times677 \\ 1353 & = 3\times11\times 41 \\ 1352 & = 2\times2\times2\times13\times13 \\ 1351 & = 7\times193 \\ 1350 & = 2\times3\times3\times3\times5\times5 \end{align} The initial segment doesn't get longer.

Another: \begin{align} 1359 & = 3\times3\times151 \\ 1358 & = 2\times7\times97 \\ 1357 & = 23\times59 \\ 1356 & = 2\times2\times3\times113\\ 1355 & = 5\times271 \\ 1354 & = 2\times677 \\ 1353 & = 3\times11\times 41 \\ 1352 & = 2\times2\times2\times13\times13 \\ 1351 & = 7\times193 \\ 1350 & = 2\times3\times3\times3\times5\times5 \\ 1349 & = 19\times71 \end{align} Still doesn't get longer . . . . .

Next: \begin{align} 1360 & = 2\times2\times2\times2\times5\times17 \\ 1359 & = 3\times3\times151 \\ 1358 & = 2\times7\times97 \\ 1357 & = 23\times59 \\ 1356 & = 2\times2\times3\times113\\ 1355 & = 5\times271 \\ 1354 & = 2\times677 \\ 1353 & = 3\times11\times 41 \\ 1352 & = 2\times2\times2\times13\times13 \\ 1351 & = 7\times193 \\ 1350 & = 2\times3\times3\times3\times5\times5 \\ 1349 & = 19\times71 \\ 1348 & = 2\times2\times337 \end{align} We've got three more: $\{2,3,5,7,11,13,17,19,23\}$ (The $19$ and the $23$ were already there, but we didn't have an initial segment since $17$ was missing.)

The reason for doing this is that in order to factor each number, we go down the list of primes starting at the bottom and check for divisibility by each, and the way to check for divisibility by $17$ is to look at how far the number is from the nearest other multiple of $17$, provided that's somewhere in the list we've got so far. And if the nearest other multiple of $17$ happens to be $17\times80$, and we're looking at the number $17$ more than that, we needn't do long division to know we've got $17\times81$. But if $17$ isn't there yet, then we may have to resort to long division or something else not as efficient. And if $17$ isn't there and $19$ and $23$ are, then you can check those last two but you're tasked with remembering that you still need to look at $17$ by more cumbersome methods. That's uncomfortable with mental arithmetic (which is how I did everything here, and haven't checked it further, so maybe you'll want to do that) and maybe problematic in computer programmaing as well, although I'm not sure of that.

So an open-ended question: Can anything interesting beyond the obvious be said about the growth of our list of initial segments?

share|improve this question
add comment

1 Answer 1

It is obvious that an interval of length $x$ will contain all primes $\le x$. Probabilistic reasoning suggests that it will also contain about $$ \sqrt{\frac{2x\log2}{\log x}} $$ more primes (up to the first missing prime). For example, I picked a thousand intervals of length one million. The median number of 'extra' primes was 327. The heuristic above predicts 317.

share|improve this answer
    
How were these thousand intervals of length 1 million distributed? Just the first $10^9$ integers? Or in some random way over a much longer interval? Were they pairwise disjoint? –  Michael Hardy Aug 26 '13 at 21:40
    
@MichaelHardy: Uniformly at random on [0, 10^10). I just redid it with [0, 10^20) and got 331. Also I tried intervals of length 10^8 and got 2761 vs. the prediction of 2743. –  Charles Aug 26 '13 at 23:17
    
Uniformly at random, meaning also independently of each other? If so, you're not excluding intervals that susbtantially overlap, and if you get those, you don't have as much information as your sample size might seem to suggest. –  Michael Hardy Aug 26 '13 at 23:42
    
@MichaelHardy: The expected number of overlaps on [0, 10^10) is small and the expected number on [0, 10^20) is nil. –  Charles Aug 27 '13 at 0:51
add comment

Your Answer

 
discard

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.