4
$\begingroup$

This numerical problem arose in one of my projects. It seems simple at first sight, but I can't seem to find a good approach. Maybe someone else has an idea:

We have two integers, $n$ and $N$. Let's say that $n \approx 10^6$ and $N>10^{18}$.

I need to create a list of all numbers between n and $\sqrt N$ that divide some number in the interval $[N,N+n-1]$.

Obviously, each number can divide at most one, and the total number of answers is approximately $n \ln{\sqrt N \over n}$; $6.9*10^6$ for $10^{18}$.

The most straightforward approach is to enumerate all integers from $n$ to $\sqrt N$ and to try each one, and that takes $O(\sqrt N)$ operations. Surely we can do much better?

$\endgroup$
  • $\begingroup$ Can you change the title to a more descriptive one? I guess that in the future, there will be many questions about numerical computing (also, is this really a question about numerical computing?). A title can be long, as explained on MathOverflow.net. $\endgroup$ – Tsuyoshi Ito Oct 9 '10 at 12:02
  • $\begingroup$ I'd say this is more of a computational number theory question than a numerical computing question. $\endgroup$ – Warren Schudy Oct 9 '10 at 14:41
  • $\begingroup$ I've been able to derive a formula that gives me approximate locations of some divisors: $q+(k-\sqrt{4*q*k-k^2})/2$ where $q=\sqrt{N}$ and k is a small integer (assuming that N is a perfect square). But that does not generalize well enough ... $\endgroup$ – user1703 Oct 9 '10 at 20:12
  • $\begingroup$ Now it is crossposted on MathOverflow with a little different formulation (I presume that the poster is the same person): mathoverflow.net/questions/41725/factoring-blocks-of-numbers $\endgroup$ – Tsuyoshi Ito Oct 11 '10 at 20:48
2
$\begingroup$

Your problem is more or less equivalent to the problem of factoring $N,N+1,\ldots,N+n$. To get from these factorizations to the solution to your problem, simply enumerate the factors. To get from the solution to your problem to the factorization, simply test each factor for primality. In the future you may wish to state this problem in this other form, as it sounds more natural and fundamental that way.

One way to factor these numbers is to simply use a standard factorization algorithm on each one. Note that most numbers have lots of small divisors and therefore are a lot easier to factor than the products of two large primes that need to be factored to break RSA public key cryptography. According to Wikipedia the Lenstra elliptic curve factorization method works well on numbers with small factors and the Quadratic Sieve works well for numbers under 100 digits. I would give those two factorization algorithms a try.

In light of the above I suggest something along the lines of the following algorithm:

Iterate over all numbers X between $N$ and $N+n$. For each such X:

  1. Compute its prime factors as follows:

    i. Use trial division by 2,3,5 and 7 to dispose of tiny factors

    ii. Run the Lenstra or Quadratic Sieve factorization method to factor what's left.

  2. Use the prime factorization to generate all factors (prime or composite) of X. Insert all of these factors that are between $n$ and $\sqrt{N}$ to your output list.

$\endgroup$
  • $\begingroup$ That is an intriguing approach, but I have doubts about the running time. As far as I understand, Lenstra gives me the one prime factor per invocation. The complexity of quadratic sieve works out to ~600 operations for N~10^18. Worth a try though. $\endgroup$ – user1703 Oct 9 '10 at 20:07
  • $\begingroup$ Here's another suggestion: build a table with the current known prime factors of $N,\ldots,N+n$, initialized to empty. Then for every prime $p<n$, update this table to account for divisibility by $p$. This process finds each prime factor using $O(1)$ arithmetic operations. I suggest stopping at $p\approx n$ because larger primes need not divide any number in the range $N,\ldots,N+n$. This preliminary step will find an awful lot of factors, leaving the quadratic sieve with much smaller numbers to factor. $\endgroup$ – Warren Schudy Oct 10 '10 at 0:55
  • $\begingroup$ You should of course use a primality test (e.g. Rabin-Miller) to verify compositeness before trying to factor a number. $\endgroup$ – Warren Schudy Oct 10 '10 at 2:12
  • $\begingroup$ Correction: A random number between $M^2$ and $4M^2$ is a product of two primes between $M$ and $2M$ with probability $\Theta(\frac{1}{(\log M)^2})$, which follows easily from the distribution of primes (en.wikipedia.org/wiki/Prime_number_theorem) and the uniqueness of prime factorizations. This implies that tricks to get rid of smaller factors don't significantly help the asymptotic performance. $\endgroup$ – Warren Schudy Oct 10 '10 at 14:32
  • $\begingroup$ The quadratic sieve factoring algorithm takes time $o(N^\epsilon)$ for every $\epsilon>0$, so factoring all of the numbers can be done in time $O(n N^\epsilon)$. Unless $n$ is close to $\sqrt{N}$ this is still faster than your naive method. $\endgroup$ – Warren Schudy Oct 10 '10 at 14:33
0
$\begingroup$

You might as well list all numbers from 1 to $\sqrt{N}$. Then the problem is more or less the same as finding all prime factors of all numbers in an interval. Using the Sieve of Atkin to generate primes you can get $ O(\sqrt{N}/\log \log N) $.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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