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

My brain hurts - finding smooth numbers on an AP

Expand Messages
  • Phil Carmody
    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
    Message 1 of 4 , Nov 2, 2002
    • 0 Attachment
      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/
    • David Cleaver
      Hello Phil, ... As for finding the smooth values (if I remember correctly you have C&P:PNaCP) sections 3.2.5 and 3.2.6 are great at explaining a good way of
      Message 2 of 4 , Nov 2, 2002
      • 0 Attachment
        Hello Phil,

        Phil Carmody wrote:
        >
        > 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?

        As for finding the smooth values (if I remember correctly you have
        C&P:PNaCP) sections 3.2.5 and 3.2.6 are great at explaining a good way
        of sieving for finding smooth numbers.

        Now, as for finding square-free numbers, well,

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

        I think this one might not be a good idea because you might skip over
        some numbers that fit your criteria. However, it is also good because
        you are guaranteed to get only the numbers you want. So, its up to you
        to do this one depending on whether you want all numbers fitting your
        criteria in a range or if you don't mind missing a few in your range.

        > 2) sieving by removing bad numbers that have unwanted factors,
        > like a conventional sieve

        This one is good because you can easily sieve your p-smooth numbers to
        see if they are divisble by {4,9,25,...,p^2}. Actually, you might want
        to do this at the same time you are testing for p-smoothness so that you
        can do it all in one pass.

        > 3) just trial divide every number, looks painful, and I'm
        > guessing won't play too much a role.

        I agree, this is one method to stay away from.

        > 4) one of the dozen permutations/combinations of the above.

        I hope the above was helpful. I have to get ready to go to work, but
        when I get back if you want any help or advice in coding this up I would
        love to help.

        -David C.

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

        P.S. does "P = { 2,3,5, ... p }, say p is 10000" mean that 10000 is a
        Carmody-prime? ;)
      • 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 3 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 4 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.