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

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

Expand Messages
  • Paul Leyland
    Am I missing something? 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
    Message 1 of 4 , Nov 3, 2002
    • 0 Attachment
      Am I missing something? 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), 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?

      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.


      Paul


      > -----Original Message-----
      > From: Phil Carmody [mailto:thefatphil@...]
      > Sent: 02 November 2002 18:10
      > To: primenumbers
      > Subject: [PrimeNumbers] My brain hurts - finding smooth
      > numbers on an AP
      >
      >
      > Lets say I have a set P = { 2,3,5, ... p }, say p is 10000
      > And an AP X+iY where Y is about 10^50,
      >
      > Is there an effective way of finding any terms on the AP that are
      > square-free and entirely factorable using members of P?
      >
      > My head's been spinning with other maths today, and has
      > finally worn out!
      >
      > What makes sense -
      > 1) sieving by adding good numbers
      > like a QS approach, finding smooths, but on an AP not a QP.
      > 2) sieving by removing bad numbers that have unwanted factors,
      > like a conventional sieve
      > 3) just trial divide every number, looks painful, and I'm
      > guessing won't play too much a role.
      > 4) one of the dozen permutations/combinations of the above.
      >
      >
      > What are the heuristics - say I needed 100 such numbers, what
      > range of i
      > would I need to look at? Squarefreeness messes things up a bit, alas.
      >
      > Any ideas?
      >
      > Phil
      >
      >
      > =====
      > 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
      > http://hotjobs.yahoo.com/
      >
      > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      > The Prime Pages : http://www.primepages.org/
      >
      >
      >
      > Your use of Yahoo! Groups is subject to
      http://docs.yahoo.com/info/terms/
    • Phil Carmody
      ... 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
      Message 2 of 4 , 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,
        Phil


        =====
        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
        http://hotjobs.yahoo.com/
      Your message has been successfully submitted and would be delivered to recipients shortly.