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

theoretical question

Expand Messages
  • asposer
    Let s say you have an arbitrarily long list of primes (but it is bounded). Is it always possible to make a list of multipliers, with a one-to- one
    Message 1 of 4 , Mar 2 4:41 PM
    • 0 Attachment
      Let's say you have an arbitrarily long list of primes (but it is
      bounded).

      Is it always possible to make a list of multipliers, with a one-to-
      one correspondence to the primes list, which generates via
      multiplication a string of integers with a constant difference, n?
      An example:

      List of primes:
      ---------------

      3
      5
      7
      11


      Desired n: 3

      5 * 12 = 60
      7 * 9 = 63
      11 * 6 = 66
      3 * 23 = 69

      List of multipliers: 12, 9, 6, 23



      Which leads to two related questions; is it possible to do this with
      an infinitely large list of primes? Also, is it possible to produce
      lists for all n, n = 0, 1, 2, etc...

      Just a thought I had today, if someone knows of a site or sites which
      address these problems I'd be happy to get links. Thanks!

      -Andrew-
    • Jens Kruse Andersen
      ... This is always possible for any n and any order of the primes. The problem is just solving a set of modular equations. Your example, with x for the first
      Message 2 of 4 , Mar 2 8:36 PM
      • 0 Attachment
        asposer wrote:
        > Desired n: 3
        >
        > 5 * 12 = 60
        > 7 * 9 = 63
        > 11 * 6 = 66
        > 3 * 23 = 69

        This is always possible for any n and any order of the primes.
        The problem is just solving a set of modular equations.
        Your example, with x for the first product, is the smallest solution to:
        x = 0 (mod 5)
        x = -3 (mod 7)
        x = -6 (mod 11)
        x = -9 (mod 3)
        CRT (Chinese Remainder Theorem) says it can always be solved when the numbers
        are relatively prime, and primes are that.

        Setting up such a system of modular equations with carefully chosen residues
        (not k*n) is a great way to find large prime gaps, by ensuring many numbers with
        a small factor.

        > is it possible to do this with
        > an infinitely large list of primes?

        No. A solution must have given finite values for x and n. The average prime gap
        tends to infinite, so infinitely many of the primes will be larger than the
        number they would have to divide.

        --
        Jens Kruse Andersen
      • mikeoakes2@aol.com
        I wrote ... For some reason I had not seen Jens s post, which is (a) neater and (b) proves the general case. So I am erasing my post - sorry for wasting your
        Message 3 of 4 , Mar 3 1:16 AM
        • 0 Attachment
          I wrote
          >Probably, this argument can be extended, by induction, to derive the same
          >affirmative conclusion for any (finite) number of primes.

          For some reason I had not seen Jens's post, which is (a) neater and (b)
          proves the general case.
          So I am erasing my post - sorry for wasting your time.

          Mike


          [Non-text portions of this message have been removed]
        • asposer
          Thanks for your reply, I ve read about the Chinese Remainder Theorem but I ve struggled with understanding its implications. I m also interested in functions
          Message 4 of 4 , Mar 3 5:44 PM
          • 0 Attachment
            Thanks for your reply, I've read about the Chinese Remainder Theorem
            but I've struggled with understanding its implications.

            I'm also interested in functions which produce as their output the
            positive integers or lists of integers whose composition (with
            multiplicity) follows that of the positive integers. In this case,
            finding difference between successive pairs of prime/integer which
            satisfy the requirements and the starting term produces the sequence
            3, 6, 9, 12, etc. (which reduces to 1, 2, 3, 4, etc.) and Omega(n) of
            the resulting sequence is equal to Omega(n) + 1 of the positive
            integers. If anyone happens to know where I can find more info about
            functions with these properties, I'd appreciate a pointer in the
            right direction (books, links, etc). Thanks!

            -Andrew-


            --- In primenumbers@yahoogroups.com, "Jens Kruse Andersen"
            <jens.k.a@g...> wrote:
            > asposer wrote:
            > > Desired n: 3
            > >
            > > 5 * 12 = 60
            > > 7 * 9 = 63
            > > 11 * 6 = 66
            > > 3 * 23 = 69
            >
            > This is always possible for any n and any order of the primes.
            > The problem is just solving a set of modular equations.
            > Your example, with x for the first product, is the smallest
            solution to:
            > x = 0 (mod 5)
            > x = -3 (mod 7)
            > x = -6 (mod 11)
            > x = -9 (mod 3)
            > CRT (Chinese Remainder Theorem) says it can always be solved when
            the numbers
            > are relatively prime, and primes are that.
            >
            > Setting up such a system of modular equations with carefully chosen
            residues
            > (not k*n) is a great way to find large prime gaps, by ensuring many
            numbers with
            > a small factor.
            >
            > > is it possible to do this with
            > > an infinitely large list of primes?
            >
            > No. A solution must have given finite values for x and n. The
            average prime gap
            > tends to infinite, so infinitely many of the primes will be larger
            than the
            > number they would have to divide.
            >
            > --
            > Jens Kruse Andersen
          Your message has been successfully submitted and would be delivered to recipients shortly.