From: "Schroeppel, Richard" <rschroe@sandia.gov>
Speculations on finding "smooth" X^2+1:
[What was wrong with "round"? That's what Hardy & Wright use.]
That's sooooo last century!
You can generate ordinary integers in order, along with their prime factorizations, using a priority-queue-like scheme.
"Lenstra's Algorithm". By default doesn't give you the factorisations, but that part is trivial post facto.
A similar method should work for X+i, using complex primes. Unclear if it's any faster than just sieving large blocks of X+i.
The set { x^2+1 } is so sparse that sieving just along that polynomial will be fairly fast. O(R^(1/2)).
Both methods are faster than factoring N (or X^2+1) one-at-a-time.
But using Euler's factoring shortcut (the original block-GCD method), factoring is exceptionally fast. One needs to add extra prime powers, and could still miss extreme cases, but we're not after exhaustive searching are we, merely computationally efficient searching. My 1-line GP/Pari script finds all P-smooth X^2+1 numbers up to (10^7)^2 in only seconds using this not-completely-naive factoring technique. I only wen't to p=100, and found the following 10^6<X<10^7 1984933 2343692 3449051 6225244
Both methods adapt to ignoring large prime divisors, just keeping those up to some limit.
Lenstra's method is defined in those terms. Alas it's something like O(f(R)*#p) for f(R)=o(R) by default - the larger your set, the more collisions you have, and the more time you spend hopping down lists trying to find the right place to insert values. So it tends to slow down for large sets of divisors, and may take a while before the smoothness-contraint causes the unspecified o(R) to become preferable to the square+1 constraint's O(R^(1/2)). I have a 'Lenstra Engine' somewhere - if someone wants me to perform some actual hunts for smooth numbers with it, just let me know the details, and I'll get a spare machine onto it immmediately. Phil () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani] __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com