Loading ...
Sorry, an error occurred while loading the content.

9594RE: [PrimeNumbers] My brain hurts - finding smooth numbers on an AP

Expand Messages
  • Phil Carmody
    Nov 3, 2002
    • 0 Attachment
      --- Paul Leyland <pleyland@...> wrote:
      > Am I missing something?

      You're missing the fact that I'd probably scribbled about 30 pages of notes
      that day (none of which were bin-fodder, it was most productive), and was
      quite literally mentally exhausted.

      > Why don't you sieve with squares of elements from P to identify those
      > not square free (by setting the location to a large negative value),

      part of my approach (2)

      > and then sieve the
      > remaining numbers, accumulating a list of elements of P on each sieve location while adding
      > log(P) to the sieve location?

      my approach (1)

      > After the second sieve, those locations which are approximately log(X+iY) are smooth and the
      > list gives you the factorization. If you're prepared to use trial division on the smooth
      > locations, you don't need to store the list while sieving.

      The number that I'm expecting to pass now (I looked at a 100K range, and
      found nothing) are so low that I think re-TD-ing will be inexpensive, which
      was my approach (3), that it appears will play only a very minor role.

      I think that (1) and (2) pretty much commute.
      If anything, blanking the squaresome (neologism?) numbers after the log-accumulating
      sieve works even better.

      I wasn't so far out after all, I'm amazed!

      It's just a shame that the yield is so low that it's probably not worth
      doing. I'll put it on a back-burner, I've got another 20 pages of notes for
      another new technique that may aid the task I'm currently looking at.

      I'm trying to break a (minority interest) record using nothing but a single
      PPro/200 - this will be a victory for wetware if it ever works!

      Cheers for confirming my ideas,

      First rule of Factor Club - you do not talk about Factor Club.
      Second rule of Factor Club - you DO NOT talk about Factor Club.
      Third rule of Factor Club - when the cofactor is prime, or you've trial-
      divided up to the square root of the number, the factoring is over.

      Do you Yahoo!?
      HotJobs - Search new jobs daily now
    • Show all 4 messages in this topic