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

Greatest Prime Factor Sets?

Expand Messages
  • joel.levenson
    Hi everybody. I have been looking at sets that consist of all the integers which have the same greatest prime factor. I haven t been able to find any standard
    Message 1 of 7 , Jan 30, 2007
    • 0 Attachment
      Hi everybody.

      I have been looking at sets that consist of all the integers which
      have the same greatest prime factor.

      I haven't been able to find any standard terminology for, or a body of
      work about, these sets.

      If anybody knows of anything, or even a likely place to look, I'd
      appreciate hearig from you.

      Thanks.
    • Payam Samidoost
      Joel http://mathworld.wolfram.com/SmoothNumber.html May it be helpful. Payam [Non-text portions of this message have been removed]
      Message 2 of 7 , Jan 30, 2007
      • 0 Attachment
        Joel

        http://mathworld.wolfram.com/SmoothNumber.html
        May it be helpful.

        Payam


        [Non-text portions of this message have been removed]
      • Phil Carmody
        ... I would have expected the field most likely to have coined a term for such sets would be that of small prime sieves. However, quickly looking through a
        Message 3 of 7 , Jan 30, 2007
        • 0 Attachment
          --- "joel.levenson" <joel.levenson@...> wrote:
          > Hi everybody.
          >
          > I have been looking at sets that consist of all the integers which
          > have the same greatest prime factor.
          >
          > I haven't been able to find any standard terminology for, or a body of
          > work about, these sets.
          >
          > If anybody knows of anything, or even a likely place to look, I'd
          > appreciate hearig from you.

          I would have expected the field most likely to have coined a term for such sets
          would be that of small prime sieves. However, quickly looking through a pile of
          Pritchard, Dunten, Sorensen, et al., I'm unable to find such sets used and give
          a name. The obverse, those which have the same least prime factor, are used
          extensively.

          Just give it an abstract symbolic name, and a tight definition, and you'll be
          fine. Something like:

          H_p := { n : p|n /\ (q|n->q<=p) }

          However, you'll possibly want to be using a 'hpf' or 'gpf' function anyway, so
          you might as well define that first, and then define the set in terms of that
          function.

          Phil

          () ASCII ribbon campaign () Hopeless ribbon campaign
          /\ against HTML mail /\ against gratuitous bloodshed

          [stolen with permission from Daniel B. Cristofani]



          ____________________________________________________________________________________
          Don't pick lemons.
          See all the new 2007 cars at Yahoo! Autos.
          http://autos.yahoo.com/new_cars.html
        • joel.levenson
          Hello again. It has taken me approximately a week to analyze and rigourosly formulate this fundamental truth: the default address for replies in Yahoo groups
          Message 4 of 7 , Feb 2, 2007
          • 0 Attachment
            Hello again.

            It has taken me approximately a week to analyze and rigourosly
            formulate this fundamental truth: the default address for replies in
            Yahoo groups is the author of the message.

            Before I made this independent discovery, I sent two messages to
            myself and one to Payam Samidoost, who kindly and brilliantly replied.

            So this is actually my third response to Phil and Payam., whom I thank
            (for the third time!) for their useful and enlightening help.

            I guess I should explicitly state what I've worked out so far so my
            questions aren't so cryptic. First, these sets are a way of mapping
            the primes to the integers; second, they have a very simple iterative
            structure, and because of this there is a unique, finite set of
            integers associated with each prime.

            1) Mapping:. every integer can be uniquely identified by the prime
            that is its greatest (or the prime that is its least) prime factor and
            its "position" in these sets. That is, if all the integers whose
            greatest prime factor is 3 are arranged (for instance) in ascending
            order, 3 is first, 6 is second and so one. In general, there is a
            total function f(p,k)=x where S is the set of all integers with
            greatest prime factor p and the integers in S are ordered such that x
            is the kth integer in S.

            My questions are: what is it called when you map the integers to the
            primes using factorizations? Are there many ways of doing it? What
            is this way called? (It's all very well to stumble over these things,
            but trying to track them down isn't working out for me.)


            2) I have the same two question about these sets:

            {2}
            {4, 3}
            {8, 6, 9, 5}
            {16, 12, 18, 27, 10, 15, 25, 7}

            Among their characteristics is that, where P(n) is the nth prime
            number, designating 2 as the first prime, each set contains 2^(n-1)
            integers, including P(n) and 2^n.

            Here's where they come from: each "greatest prime factor set" can be
            divided into subsets based on the number of "not necessarily distinct
            prime numbers" in the factorization.

            (The symbol for that is a big omega. I'll call it G(m) where m is an
            integer.)

            For the greatest prime factor set of P(n), the number of integers
            Where G(m)=r is C(n+r-1,n) i.e., n choose k with repetitions.

            (I won't work that out here, it's pretty straightforward.)

            There are several ways to show the next step, but here's the coolest
            one: a table using the combination formula above:

            n=1 n=2 n=3 n=4
            r=1 1 1 1 1
            r=2 1 2 3 4
            r=3 1 3 6 10
            r=4 1 4 10 20

            Each number represents how many integers are in the subset. The
            finite sets are based on the diagonals. To show it with the actual
            integers,


            n=1 n=2 n=3
            r=1 2 3 5
            r=2 4 6, 9 10, 15, 25
            r=3 16 12, 18, 27 20, 30, 45. 50, 75, 125


            Well, I'm a rank amateur and I'm very proud of having worked that out
            myself, but what do you call it? It feels kind of deep.
          • joel.levenson
            Hi Phil ... I must have at some point looked at the Wolfram article on least prime factor but I somehow missed the connection. Wolfram says that lpf(n) is
            Message 5 of 7 , Feb 3, 2007
            • 0 Attachment
              Hi Phil

              >The obverse, those which have the same least prime factor, are used
              > extensively.

              I must have at some point looked at the Wolfram article on "least
              prime factor" but I somehow missed the connection. Wolfram says
              that lpf(n) is standard, so I guess I can use gpf(n).

              There are two properties that "gpf" sets have that interest me, and
              "lpf" sets have only one of them, but it took me a while to see that
              it doesn't have the other.

              The property they share is that each integer, by definition, has one
              and only one least- or greatest- prime factor, so you get the mapping.

              The property they don't share is the one that leads to the finite sets
              (although it may be there and I'm not seeing it). This is because
              using the gpf puts an upper limit on the number of integers with the
              same "not necessarily distinct factors".

              lpf gpf

              3 3
              3*2 3*2*2 ... 2*3 3*3
              3*3 3*3*3 ... 2*2*3 2*3*3 3*3*3
              3*5 ...

              lpf sets are n-dimensional, so to speak. gpf sets are two dimensional.

              >
              > Just give it an abstract symbolic name, and a tight definition, and
              you'll be
              > fine. Something like:
              >
              > H_p := { n : p|n /\ (q|n->q<=p) }

              For my purposes, it's useful to define everything in terms of the n in
              P(n), as defined above, with P(1)=2. So I don't use n for anything
              else, and I was using S_n for the sets. (Except I either wrote it in
              pencil or used word, so I got to use subscripts and symbols and stuff.
              I never tried to do all this in text until I joined this group.)

              I can't think of a way to define P(n) without using words, so my
              (latest) inelegant definition was:

              Where P(n) is the nth prime number, S_n={x: gpf(x)=P(n)}

              (Except I wrote out "P(n) is the greatest prime factor of x" until you
              guided me to lpf sets.)

              Another way of defining gpf sets is "all possible products of a prime
              with every possible positive integer exponent of every prime less than
              or equal to itself."

              I don't know how to say "every possible positive integer exponent"
              symbolically.

              Sorry, I am a wordy guy and I write long posts. I am very grateful
              for your and Payam's help.
            • Phil Carmody
              ... p-smooth sets are infinite for all p. Therefore so are sets of numbers with the same gpf. ... Countable and countable. I m not sure I see the difference.
              Message 6 of 7 , Feb 3, 2007
              • 0 Attachment
                --- "joel.levenson" <joel.levenson@...> wrote:
                > Hi Phil
                >
                > >The obverse, those which have the same least prime factor, are used
                > > extensively.
                >
                > I must have at some point looked at the Wolfram article on "least
                > prime factor" but I somehow missed the connection. Wolfram says
                > that lpf(n) is standard, so I guess I can use gpf(n).
                >
                > There are two properties that "gpf" sets have that interest me, and
                > "lpf" sets have only one of them, but it took me a while to see that
                > it doesn't have the other.
                >
                > The property they share is that each integer, by definition, has one
                > and only one least- or greatest- prime factor, so you get the mapping.
                >
                > The property they don't share is the one that leads to the finite sets
                > (although it may be there and I'm not seeing it). This is because
                > using the gpf puts an upper limit on the number of integers with the
                > same "not necessarily distinct factors".

                p-smooth sets are infinite for all p. Therefore so are sets of numbers with the
                same gpf.

                > lpf gpf
                >
                > 3 3
                > 3*2 3*2*2 ... 2*3 3*3
                > 3*3 3*3*3 ... 2*2*3 2*3*3 3*3*3
                > 3*5 ...
                >
                > lpf sets are n-dimensional, so to speak. gpf sets are two dimensional.

                Countable and countable. I'm not sure I see the difference.

                Dense and not dense is the distinction that you could draw. P-smooth numbers
                are not dense in the integers, so neither are sets sharing gpfs.

                Phil

                () ASCII ribbon campaign () Hopeless ribbon campaign
                /\ against HTML mail /\ against gratuitous bloodshed

                [stolen with permission from Daniel B. Cristofani]



                ____________________________________________________________________________________
                Need a quick answer? Get one in minutes from people who know.
                Ask your question on www.Answers.yahoo.com
              • joel.levenson
                Hi Phil ... numbers with the same gpf. gpf sets are infinite, and their union is the set of all integers greater than one, and their intersection is empty.
                Message 7 of 7 , Feb 3, 2007
                • 0 Attachment
                  Hi Phil

                  > p-smooth sets are infinite for all p. Therefore so are sets of
                  numbers with the same gpf.

                  gpf sets are infinite, and their union is the set of all integers
                  greater than one, and their intersection is empty.

                  What interests me about organizing the integers in terms of their gpfs
                  is that each one can be uniquely identified by its gpf and its
                  position among the rest of the integers with that gpf (when they are
                  placed in ascending order, for instance.) But a p-smooth number is
                  also p-smooth for every prime greater or equal to p, so it isn't
                  uniquely identified. (Payam suggested calling numbers with the same
                  gpf "strictly p-smooth numbers" But, I think, from my point of view,
                  it is simpler to think in terms of gpfs. Then you don't have to bring
                  in any concepts beyond the fundamental theorem of arithmetic and the
                  definition of "greatest.")

                  I don't know if mapping the primes to the integers is interesting or
                  useful, or how many ways it can be done, but this way caught my
                  attention.

                  > > lpf gpf
                  > >
                  > > 3 3
                  > > 3*2 3*2*2 ... 2*3 3*3
                  > > 3*3 3*3*3 ... 2*2*3 2*3*3 3*3*3
                  > > 3*5 ...
                  > > >
                  >> lpf sets are n-dimensional, so to speak. gpf sets are two dimensional.

                  > > Countable and countable. I'm not sure I see the difference.
                  > > Dense and not dense is the distinction that you could draw.
                  > > P-smooth numbers are not dense in the integers, so neither
                  > > are sets sharing gpfs.

                  (I was using n-dimensional sort of whimsically. I just meant that if
                  you try to write out all the lpf numbers on a piece of paper you have
                  to go off in all directions.)

                  What I am interested in here is the combinatorial structure, involving
                  subsets of gpf sets, defined by the number of "not necessarily
                  distinct primes." There are an infinite number of these subsets,
                  their union is the gpf set, and their intersection is the null set.
                  But each one is finite, and the formula for how many elements there
                  are in each set, where P(n) is the nth prime and r is the number of
                  not necessarily distinct prime factors, is "n choose r with
                  repetitions" which is C(n+r-1, n). So you can get a very simple
                  structure associating the integers with the primes, and with a little
                  manipulation you get these finite sets:

                  {2}
                  (4,3}
                  {8, 6, 9, 5}
                  (16, 12, 18, 27, 10, 15, 25, 7}

                  This pattern goes on forever. Among other things, the nth set has
                  2^(n-1) and contains P(n) and 2^n. The pattern of the other numbers
                  has to do with the "not necessarily distinct prime factor" subsets.
                  (My second post has enough detail to explain it adequately, I think.)

                  I was just surprised to find so much structure, and have been
                  exploring it as best I can.

                  Thanks for your help! And your time. I'm sorry, I can't help being
                  so wordy.
                Your message has been successfully submitted and would be delivered to recipients shortly.