# Efficiency in factoring lists of consecutive numbers

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?

-

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.
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