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

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

Expand Messages
  • 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 1 of 4 , Nov 2, 2002
      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 2 of 4 , Nov 3, 2002
        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 3 of 4 , Nov 3, 2002
          --- 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.