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

Percent of infinity divisible by X?

Expand Messages
  • Alec Smart
    I was doing some thinking the other day, and ran into some neat stuff: What percentage of all integers are even, or divisible by 2? At first, I thought it
    Message 1 of 8 , Jun 8, 2007
    • 0 Attachment
      I was doing some thinking the other day, and ran into some neat stuff: What percentage of all integers are even, or divisible by 2? At first, I thought it would be an easy answer... 50%, which seems obvious, but actually, after I ran the numbers, it turns out to be a series that converges on 50%, but never actually reaches it. The result is always slightly higher or lower than 50%.

      I have several questions about this that someone can probably answer :)

      So I decided, what about the percentage of Infinity that is divisible by 3, and only 3, not 2 as well (whats the terminology for that?)

      So then I find out that every prime number represents a percentage of infinity that is solely divisible by that number alone; 2 has 50%, 3 has 16.6667% , 5 has 3.333%, 7 has .4762% and so on. There is a logical progression to these "chunks" of infinity, and I was wondering what the series was called, or where I could find more information on it?

      It goes like this:
      1/2
      (1/3)/2
      ((1/5)/3)/2
      (((1/7)/5)/3)/2
      ((((1/11)/7)/5)/3)/2

      It appears that the sum of these percentages of infinity converges to something less than 100%... if so, what makes up the rest of the numbers?
      It also appears that a larger percent of infinity is divisible by 11 and 13 than 7, although this may be a mistake on my part. Weird, to say the least :)

      How would I write an equation that describes this series? I have an excel spreadsheet which does the job for me, but I'd like to see it in its mathematical form.

      For 2, its easy, because I don't have to remove any concurrent factors:
      Sum the number of numbers from 1 to n that divide evenly by 2. Divide the resulting sum by n (representing the average, or percentage).

      For 3, it would go something like this:
      Sum the number of numbers from 1 to n that divide evenly by 3, and not 2. Divide the resulting sum by n.

      For 5:(incidentally, all numbers divisible by 4 are contained within the domain of numbers divisible by 2, so they arent counted as a unique segment of infinity.)

      Sum the number of numbers from 1 to n that divide evenly by 5, and not 3, and not 2. Divide the resulting sum by n.

      ... and so on? Is there an easy to way to represent that mathematically?

      The graph for 3, n=100, is interesting, because it creates a bouncy ball type look to the graph. Interesting, to me anyway. I think for every number >2 there are "bounces", but it is most apparent in the 3 series.

      Thanks for any help!


      ---------------------------------
      Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more.

      [Non-text portions of this message have been removed]
    • Phil Carmody
      ... Research Natural Density . The limsup and liminf converge to 50%, so it s 50%. Quite why you don t think the density on the sets {0,1} and {0,1,2,3}, ...
      Message 2 of 8 , Jun 8, 2007
      • 0 Attachment
        --- Alec Smart <pvp4tw@...> wrote:
        > I was doing some thinking the other day, and ran into some neat stuff: What
        > percentage of all integers are even, or divisible by 2? At first, I thought
        > it would be an easy answer... 50%, which seems obvious, but actually, after I
        > ran the numbers, it turns out to be a series that converges on 50%, but never
        > actually reaches it. The result is always slightly higher or lower than 50%.

        Research "Natural Density".

        The limsup and liminf converge to 50%, so it's 50%.
        Quite why you don't think the density on the sets {0,1} and {0,1,2,3}, ... is
        not actually 50%, I don't know.

        > I have several questions about this that someone can probably answer :)
        >
        > So I decided, what about the percentage of Infinity that is divisible by 3,
        > and only 3, not 2 as well (whats the terminology for that?)

        The concept you're alluding to seems to be numbers with a least prime factor
        (lpf) of 3. You don't mean "only", or "solely" below.

        > So then I find out that every prime number represents a percentage of
        > infinity that is solely divisible by that number alone; 2 has 50%, 3 has
        > 16.6667% , 5 has 3.333%, 7 has .4762% and so on. There is a logical
        > progression to these "chunks" of infinity, and I was wondering what the
        > series was called, or where I could find more information on it?

        Does it need a name? They're the reciprocals of the promorials.

        > It goes like this:
        > 1/2
        > (1/3)/2
        > ((1/5)/3)/2
        > (((1/7)/5)/3)/2
        > ((((1/11)/7)/5)/3)/2
        >
        > It appears that the sum of these percentages of infinity converges to
        > something less than 100%...

        Research slowly converging series. Don't be fooled by slow convergence.

        > if so, what makes up the rest of the numbers?

        There is no rest of the numbers. This is most easily proved by showing that if
        any number was left out, then it couldn't have any prime factors, which is an
        absurdity.

        > It also appears that a larger percent of infinity is divisible by 11 and 13
        > than 7, although this may be a mistake on my part. Weird, to say the least :)

        Mistake on your part.

        > How would I write an equation that describes this series? I have an excel
        > spreadsheet which does the job for me, but I'd like to see it in its
        > mathematical form.

        Sum_{prime p=2}^{p_max} 1/p#

        > For 2, its easy, because I don't have to remove any concurrent factors:
        > Sum the number of numbers from 1 to n that divide evenly by 2. Divide the
        > resulting sum by n (representing the average, or percentage).
        >
        > For 3, it would go something like this:
        > Sum the number of numbers from 1 to n that divide evenly by 3, and not 2.
        > Divide the resulting sum by n.
        >
        > For 5:(incidentally, all numbers divisible by 4 are contained within the
        > domain of numbers divisible by 2, so they arent counted as a unique segment
        > of infinity.)
        >
        > Sum the number of numbers from 1 to n that divide evenly by 5, and not 3, and
        > not 2. Divide the resulting sum by n.
        >
        > ... and so on? Is there an easy to way to represent that mathematically?

        You're confusing a procedure with a result. The mathematician generally only
        cares about the result. For each prime p it's fairly easy to write an
        expression for the natural density of numbers whose lpf is p.

        Phil

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

        [stolen with permission from Daniel B. Cristofani]



        ____________________________________________________________________________________
        Sick sense of humor? Visit Yahoo! TV's
        Comedy with an Edge to see what's on, when.
        http://tv.yahoo.com/collections/222
      • Alec Smart
        Thanks! Much appreciated, really interesting stuff. ... Boardwalk for $500? In 2007? Ha! Play Monopoly Here and Now (it s updated for today s economy) at
        Message 3 of 8 , Jun 8, 2007
        • 0 Attachment
          Thanks! Much appreciated, really interesting stuff.


          ---------------------------------
          Boardwalk for $500? In 2007? Ha!
          Play Monopoly Here and Now (it's updated for today's economy) at Yahoo! Games.

          [Non-text portions of this message have been removed]
        • Jens Kruse Andersen
          ... I m not sure what you mean by solely divisible by that number alone . Phil guessed you meant least prime factor (lpf). I also guess that, but then your
          Message 4 of 8 , Jun 8, 2007
          • 0 Attachment
            Alec Smart wrote:
            > So then I find out that every prime number represents a percentage
            > of infinity that is solely divisible by that number alone; 2 has 50%,
            > 3 has 16.6667% , 5 has 3.333%, 7 has .4762% and so on.

            I'm not sure what you mean by "solely divisible by that number alone".
            Phil guessed you meant least prime factor (lpf). I also guess that, but then
            your percentages from 5 are wrong.
            1/2 of numbers have 2 as lpf, and 1/2 don't.
            3 is lpf for 1/3 of the numbers where it isn't 2: 1/3 * 1/2 = 1/6.
            5 is lpf for 1/5 of the numbers where it isn't 2 or 3:
            1/5 * (1 - 1/2 - 1/6) = 1/15.
            7 is lpf for 1/7 of the numbers where it isn't 2, 3 or 5:
            1/7 * (1 - 1/2 -1/6 - 1/15) = 4/105.
            And so on. The sum of all these fractions is 1.

            The density of integers with no prime factor <= p can be computed as
            f(p) = 1/2 * 2/3 * 4/5 * ... * (p-1)/p.
            This is because 1/2 of integers are not divisible by 2, and 2/3 of the rest
            are not divisible by 3, and 4/5 of the rest are not divisible by 5, and so
            on.

            Mertens theorem
            (see http://primes.utm.edu/glossary/page.php?sort=MertensTheorem)
            says that f(p) is approximately e^(-gamma) / log p
            where log is the natural logarithm, gamma = 0.5772156649... is Euler's
            constant, and e^(-gamma) = 0.561459483...

            Varying prime gaps can make it a poor estimate for tiny p but it's great for
            large p.
            For p = 10^9 it predicts 0.0270931950.
            An evaluation of f(p) with double float precision gives 0.0270931548.

            --
            Jens Kruse Andersen
          • Phil Carmody
            ... I didn t spot that, and tacitly, but incorrectly, supported them. Yours are of course correct. Phil () ASCII ribbon campaign () Hopeless ribbon
            Message 5 of 8 , Jun 8, 2007
            • 0 Attachment
              --- Jens Kruse Andersen <jens.k.a@...> wrote:
              > Phil guessed you meant least prime factor (lpf). I also guess that, but then
              > your percentages from 5 are wrong.

              I didn't spot that, and tacitly, but incorrectly, supported them.
              Yours are of course correct.

              Phil

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

              [stolen with permission from Daniel B. Cristofani]


              ____________________________________________________________________________________
              Shape Yahoo! in your own image. Join our Network Research Panel today! http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7
            • Alec Smart
              Ahh, good catch. Yeah, my numbers were off... I m kind of interested in what the graphs look like, because I ve never encountered another series of numbers
              Message 6 of 8 , Jun 8, 2007
              • 0 Attachment
                Ahh, good catch. Yeah, my numbers were off... I'm kind of interested in what the graphs look like, because I've never encountered another series of numbers that look like the trail of a bouncing ball. I'm trying to figure out the significance of the bounces :)

                If the lines change in some predictable manner, which I think they do, then couldn't you describe a function that takes X as the Xth prime number and outputs the numbers in it's line, without knowing the Xth prime number to begin with? Unless you have to know all primes preceding X.

                E.G. output the graph for 7 by taking 4 as the argument?

                I've found that by tweaking the graph for a prime, it intersects all primes greater than itself at the point where X is equal to the product of the two. For 7 and 13, it intersects at 91. If you didn't have to know the prime itself, then solving for prime factors would be simplified just by knowing the point of intersection.

                Anyway, I appreciate all the comments, I'm beginning to see some of the difficult oddities in prime numbers.


                ---------------------------------
                Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more.

                [Non-text portions of this message have been removed]
              • Alec Smart
                Actually, I was wondering if there was a way to predict the lines without knowing the primes in question... an approximation, at the very least. I was thinking
                Message 7 of 8 , Jun 9, 2007
                • 0 Attachment
                  Actually, I was wondering if there was a way to predict the lines without knowing the primes in question... an approximation, at the very least.

                  I was thinking that the PNT could provide 2 values which you could use to output 2 lines (the % of ∞), then you could potentially predict a high and low limit range for both factors of the product of 2 primes, P. By choosing the smallest range, you'd be able to optimize factorization of large numbers. Depending on the (P) in question, it might speed things up considerably. Knowledge of the ranges would also, I believe, allow further optimizations based on other number theory concepts, although I don't know of any specifically...

                  I'm working with Python, currently... is there a specific programming language that is designed for math, or a package thats not as expensive as Mathematica? Pythons great for simple things, but not as optimized as I'd like it to be, and C is a pain in the butt for me.

                  Danny Fleming <bsmath2000@...> wrote: If I am understanding correctly, all you have to do is take each prime and do the following:
                  3-9-15-... (3+2*3n), 5-15-25-... (5+2*5n), the general formula is p+2*pn. The even numbers
                  are all factors of the only even prime 2 (2-4-6-8-...).
                  Sincerely yours,
                  Danny Karl Fleming


                  Alec Smart <pvp4tw@...> wrote:
                  Ahh, good catch. Yeah, my numbers were off... I'm kind of interested in what the graphs look like, because I've never encountered another series of numbers that look like the trail of a bouncing ball. I'm trying to figure out the significance of the bounces :)

                  If the lines change in some predictable manner, which I think they do, then couldn't you describe a function that takes X as the Xth prime number and outputs the numbers in it's line, without knowing the Xth prime number to begin with? Unless you have to know all primes preceding X.

                  E.G. output the graph for 7 by taking 4 as the argument?

                  I've found that by tweaking the graph for a prime, it intersects all primes greater than itself at the point where X is equal to the product of the two. For 7 and 13, it intersects at 91. If you didn't have to know the prime itself, then solving for prime factors would be simplified just by knowing the point of intersection.

                  Anyway, I appreciate all the comments, I'm beginning to see some of the difficult oddities in prime numbers.

                  ---------------------------------
                  Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more.

                  [Non-text portions of this message have been removed]






                  ---------------------------------
                  Don't get soaked. Take a quick peak at the forecast
                  with theYahoo! Search weather shortcut.

                  ---------------------------------
                  Got a little couch potato?
                  Check out fun summer activities for kids.

                  [Non-text portions of this message have been removed]
                • Alan Eliasen
                  ... You ll probably note, if you follow the discussions in this group, that a large number of participants use the free PARI/GP package for number theory
                  Message 8 of 8 , Jun 10, 2007
                  • 0 Attachment
                    Alec Smart wrote:
                    > I'm working with Python, currently... is there a specific programming
                    > language that is designed for math, or a package thats not as
                    > expensive as Mathematica? Pythons great for simple things, but not as
                    > optimized as I'd like it to be, and C is a pain in the butt for me.

                    You'll probably note, if you follow the discussions in this group,
                    that a large number of participants use the free PARI/GP package for
                    number theory calculations. Their speed and simplicity is often very
                    impressive. GP is a unique programming language that provides an
                    interface to the PARI C library of functions.

                    http://en.wikipedia.org/wiki/PARI/GP

                    It is usually compiled with the very fast GMP multi-precision library
                    which makes most of its calculations with big numbers quite competitive
                    with the fastest mathematical packages out there. It has a wide variety
                    of algorithms already implemented efficiently, and should perform as
                    well or better as something that most programmers could implement in
                    about any language.

                    It's not designed to be as much of a general-purpose language as
                    Python, (Turing-completeness aside,) and you may find some things (e.g.
                    processing text) much more difficult to do in GP.

                    As an interesting data point, you might note that in the Project
                    Euler programming competition, there are a small number of users who
                    claim to use PARI/GP as their language of choice for solving the puzzle,
                    but their average number of puzzles solved is very high:

                    http://projecteuler.net/index.php?section=statistics

                    --
                    Alan Eliasen | "Furious activity is no substitute
                    eliasen@... | for understanding."
                    http://futureboy.us/ | --H.H. Williams
                  Your message has been successfully submitted and would be delivered to recipients shortly.