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

Order to products of Gaussian primes...

Expand Messages
  • David Cleaver
    Hello all, As you may know I ve recently been delving into finding out how to express a number as the sum of two squares in multiple ways. Well, through
    Message 1 of 6 , May 29, 2003
    • 0 Attachment
      Hello all,

      As you may know I've recently been delving into finding out how to
      express a number as the sum of two squares in multiple ways. Well,
      through various sources, this led me to the decomposition of the factors
      of the number into Gassian primes, then multiplying those Gaussian
      primes together giving me the numbers used in the sum of two squares.
      Let me give a small example:
      1105 = 5*13*17
      5 = (2+i)*(2-i)
      13 = (3+2i)*(3-2i)
      17 = (4+i)*(4-i)
      (2+i)*(3+2i)*(4+i) = 9+32i, so 9^2 + 32^2 = 1105
      (2+i)*(3+2i)*(4-i) = 23+24i, so 23^2 + 24^2 = 1105
      (2+i)*(3-2i)*(4+i) = 33+4i, so 33^2 + 4^2 = 1105, and finally
      (2+i)*(3-2i)*(4-i) = 31-12i, so 31^2 + 12^2 = 1105
      Let me refer to the above multiplications by +++, ++-, +-+, and +--,
      respectively. So, my question is, is there a way I can find out (before
      doing the multiplication) which one of the above will return the biggest
      result? ie, can I write a function that, when I ask for the "first
      match" it will return the +-+ case? Let me show you the order I'm
      looking for in the above:
      +-+ -> 33+4i
      +++ -> 9+32i
      +-- -> 31-12i
      ++- -> 23+24i
      The reason for this ordering is I'm looking for the largest coefficient
      in each of the complex numbers, ie 33, 32, 31, 24. So, does anyone know
      of an algorithmic way this particular order can be returned? And, can
      this be generalized for even larger cases? The reason I'm looking for
      this is because I don't want to do all the multiplications and store
      them and then sort them. I just want to generate them as I go. Any
      insight into this problem would be greatly appreciated.

      -David C.
    • Décio Luiz Gazzoni Filho
      ... Hash: SHA1 Have you thought of working in polar coordinates? As I understand, maximizing the result per your definition means max(max(Re[x]),max(Im[x])).
      Message 2 of 6 , May 29, 2003
      • 0 Attachment
        -----BEGIN PGP SIGNED MESSAGE-----
        Hash: SHA1

        Have you thought of working in polar coordinates? As I understand, maximizing
        the result per your definition means max(max(Re[x]),max(Im[x])). Since all
        norms are the same, what you're looking for are solutions as close to the
        complex axes as possible (i.e. arg(x) ~ k pi/2, k = 0..3), so working in
        polar coordinates may simplify the problem somewhat (since the angle of the
        product is given by the sum of the angles of the factors). Perhaps this
        reduces to an optimization/LP problem? (I'm conjecturing wildly here, though)

        Now, if you still want all results (but sorted): trust me, no homebrew
        solution of yours is going to match the speed of generating them all followed
        by sorting the set (sorting's a very developed branch of computer science,
        you know).

        Décio

        On Thursday 29 May 2003 15:41, David Cleaver wrote:
        > Hello all,
        >
        > As you may know I've recently been delving into finding out how to
        > express a number as the sum of two squares in multiple ways. Well,
        > through various sources, this led me to the decomposition of the factors
        > of the number into Gassian primes, then multiplying those Gaussian
        > primes together giving me the numbers used in the sum of two squares.
        > Let me give a small example:
        > 1105 = 5*13*17
        > 5 = (2+i)*(2-i)
        > 13 = (3+2i)*(3-2i)
        > 17 = (4+i)*(4-i)
        > (2+i)*(3+2i)*(4+i) = 9+32i, so 9^2 + 32^2 = 1105
        > (2+i)*(3+2i)*(4-i) = 23+24i, so 23^2 + 24^2 = 1105
        > (2+i)*(3-2i)*(4+i) = 33+4i, so 33^2 + 4^2 = 1105, and finally
        > (2+i)*(3-2i)*(4-i) = 31-12i, so 31^2 + 12^2 = 1105
        > Let me refer to the above multiplications by +++, ++-, +-+, and +--,
        > respectively. So, my question is, is there a way I can find out (before
        > doing the multiplication) which one of the above will return the biggest
        > result? ie, can I write a function that, when I ask for the "first
        > match" it will return the +-+ case? Let me show you the order I'm
        > looking for in the above:
        > +-+ -> 33+4i
        > +++ -> 9+32i
        > +-- -> 31-12i
        > ++- -> 23+24i
        > The reason for this ordering is I'm looking for the largest coefficient
        > in each of the complex numbers, ie 33, 32, 31, 24. So, does anyone know
        > of an algorithmic way this particular order can be returned? And, can
        > this be generalized for even larger cases? The reason I'm looking for
        > this is because I don't want to do all the multiplications and store
        > them and then sort them. I just want to generate them as I go. Any
        > insight into this problem would be greatly appreciated.
        >
        > -David C.
        -----BEGIN PGP SIGNATURE-----
        Version: GnuPG v1.2.2 (GNU/Linux)

        iD8DBQE+1mbxce3VljctsGsRAi6vAJwMtkUjQbMu4bM8SU9yo8CM/ySmdgCgkGm8
        6ZTi4ZwkjFQv+flc6ZLQu6Q=
        =SytH
        -----END PGP SIGNATURE-----
      • Jon Perry
        In this example, the 2nd two components give; (10+/-11i) and (14+/-5i) Of these we require 2*a-(b) to be maximal. and as 14=10+4 but 11-5 is only 6, the real
        Message 3 of 6 , May 29, 2003
        • 0 Attachment
          In this example, the 2nd two components give;

          (10+/-11i) and (14+/-5i)

          Of these we require 2*a-(b) to be maximal.

          and as 14=10+4 but 11-5 is only 6, the real max. comes from 14-5i, the +-+
          case.

          Simlarly for the imag. max.

          Jon Perry
          perry@...
          http://www.users.globalnet.co.uk/~perry/maths/
          http://www.users.globalnet.co.uk/~perry/DIVMenu/
          BrainBench MVP for HTML and JavaScript
          http://www.brainbench.com

          -----Original Message-----
          From: David Cleaver [mailto:wraithx@...]
          Sent: 29 May 2003 19:41
          To: Primes List
          Subject: [PrimeNumbers] Order to products of Gaussian primes...


          Hello all,

          As you may know I've recently been delving into finding out how to
          express a number as the sum of two squares in multiple ways. Well,
          through various sources, this led me to the decomposition of the factors
          of the number into Gassian primes, then multiplying those Gaussian
          primes together giving me the numbers used in the sum of two squares.
          Let me give a small example:
          1105 = 5*13*17
          5 = (2+i)*(2-i)
          13 = (3+2i)*(3-2i)
          17 = (4+i)*(4-i)
          (2+i)*(3+2i)*(4+i) = 9+32i, so 9^2 + 32^2 = 1105
          (2+i)*(3+2i)*(4-i) = 23+24i, so 23^2 + 24^2 = 1105
          (2+i)*(3-2i)*(4+i) = 33+4i, so 33^2 + 4^2 = 1105, and finally
          (2+i)*(3-2i)*(4-i) = 31-12i, so 31^2 + 12^2 = 1105
          Let me refer to the above multiplications by +++, ++-, +-+, and +--,
          respectively. So, my question is, is there a way I can find out (before
          doing the multiplication) which one of the above will return the biggest
          result? ie, can I write a function that, when I ask for the "first
          match" it will return the +-+ case? Let me show you the order I'm
          looking for in the above:
          +-+ -> 33+4i
          +++ -> 9+32i
          +-- -> 31-12i
          ++- -> 23+24i
          The reason for this ordering is I'm looking for the largest coefficient
          in each of the complex numbers, ie 33, 32, 31, 24. So, does anyone know
          of an algorithmic way this particular order can be returned? And, can
          this be generalized for even larger cases? The reason I'm looking for
          this is because I don't want to do all the multiplications and store
          them and then sort them. I just want to generate them as I go. Any
          insight into this problem would be greatly appreciated.

          -David C.


          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/
        • leenstra37
          Hello David, For this, I have to agree with Décio - in order to extract enough information from the coefficients of your set of gaussian primes to make any
          Message 4 of 6 , May 29, 2003
          • 0 Attachment
            Hello David,

            For this, I have to agree with Décio - in order to extract enough
            information from the coefficients of your set of gaussian primes to
            make any sequencing decisions, you will have to do as much work as
            the multiply and sort. I would make one modification: I suggest you
            multiply each one and sort with an insert-sort as you go. Especially
            if you're using a language that has a complex number type that does
            the multiplies for you.

            However, If you're doing the complex stuff yourself, the following
            might work.
            For the 3 factor case like your example:
            (2+1i)(3+-2i)(4+-1i) =
            (a+di)(b+-ei)(c+-fi)

            +++ = abc - aef - bdf - dec + (+abf + ace + bcd - def)i
            ++- = abc + aef + bdf - dec + (-abf + ace + bcd + def)i
            +-+ = abc + aef - bdf + dec + (+abf - ace + bcd + def)i
            +-- = abc - aef + bdf + dec + (-abf - ace + bcd - def)i

            Note the signs in the table:
            +++ = + - - - + + + -
            ++- = + + + - - + + +
            +-+ = + + - + + - + +
            +-- = + - + + - - + -

            Notice there are always 3 of one sign, and 1 of the other, for both
            the real and imaginary parts.
            Multiply out the 4 partial real terms and sort them. (Or add any
            terms > 1 and sort). To list the real coefficients biggest to
            smallest, select the case with the off sign on the terms smallest to
            biggest. Do the same for the imaginary coefficients. For the example:

            Term Multiply or + Case Coeff| Term Multiply or + Case Coeff
            bdf =3.1.1= 3 or 3 +-+ __ 33 | def =1.2.1= 2 or 2 +++ __ 32
            aef =2.2.1= 4 or 4 +-- __ 31 | abf =2.3.1= 6 or 5 ++- __ 24
            dec =1.2.4= 8 or 6 ++- __ 23 | bcd =3.4.1=12 or 7 +-- __ 12
            abc =2.3.4=24 or 9 +++ ___ 9 | ace =2.4.2=16 or 8 +-+ ___ 4

            I don't think you can intermingle the real and imaginary sorts. And
            there may be cases where one or two coefficients are out of order -
            especially if you add instead of multiply. But with more factors, if
            you keep 1 or 2 coefficients for each half, and merge-sort them; you
            should be able to list them in order keeping a queue of at most 5.

            There may be a solution using matrices or determinants, I don't
            know. Perhaps someone else could speak to that.

            -Bruce
          • Décio Luiz Gazzoni Filho
            ... Hash: SHA1 I ve put together an heuristic that might be of some help to you. It s a greedy algorithm that multiplies together the gaussian integers (or
            Message 5 of 6 , May 30, 2003
            • 0 Attachment
              -----BEGIN PGP SIGNED MESSAGE-----
              Hash: SHA1

              I've put together an heuristic that might be of some help to you. It's a
              greedy algorithm that multiplies together the gaussian integers (or their
              conjugates if it deems more appropriate) found in an array, choosing at each
              point whether an integer or its conjugate would keep the product closer to
              one of the Re/Im axes. However, first of all the routine sorts the array by
              descending order of phase (i.e. theta in the polar representation of a
              complex number as r*exp(j theta)) -- the idea here is to ``close in'' on the
              result, seeing as ever-smaller phase values assure the result is bounded (in
              a sense) -- of course there are situations where it might fail, but I expect
              it to do very well on average.

              A possible optimization, if you're working with really large sets of gaussian
              integers, is to evaluate all 2^k possibilities for the sign on the last k
              products: if k is fixed and small,you avoid the exponential increase on the
              amount of possibilities to be tested, while obtaining a result that's still
              pretty near optimal.

              By the way, all inputs of the vector are expected to have positive real and
              imaginary parts.

              - ---------- cut here ----------
              biggest(v) =
              {
              sz = matsize(v)[2];
              m = matrix(sz,2,i,j,
              if(j==1,
              v[i]
              ,
              if(real(v[i])!=0,
              atan(imag(v[i])/real(v[i]))
              ,
              sign(imag(v[i]))*Pi/2 % (2*Pi)
              )
              );
              );
              m = vecsort(m~,2,4)~;
              cumprod = 1;
              cumsum = 0;
              for(count=1,sz,
              phase = m[count,2];
              if(abs(cumsum+phase % (Pi/2)) <= abs(cumsum-phase % (Pi/2)),
              print(m[count,1]);
              cumsum = cumsum + phase % (2*Pi);
              cumprod *= m[count,1];
              ,
              print(conj(m[count,1]));
              cumsum = cumsum - phase % (2*Pi);
              cumprod *= conj(m[count,1]);
              );
              );
              print(cumsum);
              print(cumprod);
              }
              - ---------- cut here ----------

              Décio

              On Thursday 29 May 2003 15:41, David Cleaver wrote:
              > Hello all,
              >
              > As you may know I've recently been delving into finding out how to
              > express a number as the sum of two squares in multiple ways. Well,
              > through various sources, this led me to the decomposition of the factors
              > of the number into Gassian primes, then multiplying those Gaussian
              > primes together giving me the numbers used in the sum of two squares.
              > Let me give a small example:
              > 1105 = 5*13*17
              > 5 = (2+i)*(2-i)
              > 13 = (3+2i)*(3-2i)
              > 17 = (4+i)*(4-i)
              > (2+i)*(3+2i)*(4+i) = 9+32i, so 9^2 + 32^2 = 1105
              > (2+i)*(3+2i)*(4-i) = 23+24i, so 23^2 + 24^2 = 1105
              > (2+i)*(3-2i)*(4+i) = 33+4i, so 33^2 + 4^2 = 1105, and finally
              > (2+i)*(3-2i)*(4-i) = 31-12i, so 31^2 + 12^2 = 1105
              > Let me refer to the above multiplications by +++, ++-, +-+, and +--,
              > respectively. So, my question is, is there a way I can find out (before
              > doing the multiplication) which one of the above will return the biggest
              > result? ie, can I write a function that, when I ask for the "first
              > match" it will return the +-+ case? Let me show you the order I'm
              > looking for in the above:
              > +-+ -> 33+4i
              > +++ -> 9+32i
              > +-- -> 31-12i
              > ++- -> 23+24i
              > The reason for this ordering is I'm looking for the largest coefficient
              > in each of the complex numbers, ie 33, 32, 31, 24. So, does anyone know
              > of an algorithmic way this particular order can be returned? And, can
              > this be generalized for even larger cases? The reason I'm looking for
              > this is because I don't want to do all the multiplications and store
              > them and then sort them. I just want to generate them as I go. Any
              > insight into this problem would be greatly appreciated.
              >
              > -David C.
              -----BEGIN PGP SIGNATURE-----
              Version: GnuPG v1.2.2 (GNU/Linux)

              iD4DBQE+18a6ce3VljctsGsRAmUSAJ0dwPPrIaS52d55VCrAZOiNdbpm1QCXVgLm
              US0wo+D8PuwExIIvrIfXWg==
              =3IyT
              -----END PGP SIGNATURE-----
            • Décio Luiz Gazzoni Filho
              ... Hash: SHA1 I ve improved a bit on that heuristic. Consider my previous program (thinking in degrees not radians): it sorted and compared number based on
              Message 6 of 6 , May 31, 2003
              • 0 Attachment
                -----BEGIN PGP SIGNED MESSAGE-----
                Hash: SHA1

                I've improved a bit on that heuristic. Consider my previous program (thinking
                in degrees not radians): it sorted and compared number based on the absolute
                value of their angles, so 89 degrees would be considered bigger than 45
                degrees. However. 45 degrees is the farthest one can get from either axis,
                whereas 89 degrees is pretty close to an axis, and is actually equivalent to
                1 degree. So I've updated my program to reflect that. While it also doesn't
                give perfect results every time, at least not with randomly chosen gaussian
                integers, it improves a bit on the previous heuristic, particularly as the
                number of gaussian integers to consider goes up.

                Décio

                - ---------- cut here ----------
                biggest(v) =
                {
                sz = matsize(v)[2];
                m = matrix(sz,3,i,j,
                if(j==1,
                v[i]
                ,
                if(real(v[i])!=0,
                atan(imag(v[i])/real(v[i]))
                ,
                Pi/2
                )
                );
                );
                for(i=1,sz,
                if(m[i,2] > Pi/4,
                m[i,3] = Pi/2 - m[i,2]
                )
                );
                m = vecsort(m~,3,4)~;
                cumprod = 1;
                cumsum = 0;
                for(count=1,sz,
                phase = m[count,2];
                orig = abs((cumsum+phase) % (Pi/2));
                cnj = abs((cumsum-phase) % (Pi/2));
                if(orig > Pi/4,
                orig = Pi/2 - orig
                );
                if(cnj > Pi/4,
                cnj = Pi/2 - cnj
                );
                print("orig = "orig" cnj = "cnj);
                if(orig <= cnj,
                print(m[count,1]);
                cumsum = (cumsum + phase) % (2*Pi);
                cumprod *= m[count,1];
                ,
                print(conj(m[count,1]));
                cumsum = (cumsum - phase) % (2*Pi);
                cumprod *= conj(m[count,1]);
                );
                );
                print("phase of result = "cumsum);
                cumsum = cumsum % (Pi/2);
                if(cumsum > Pi/4,
                cumsum = Pi/2 - cumsum;
                );
                print("phase of result (reduced) = "cumsum);
                print("result = "cumprod);
                }
                - ---------- cut here ----------

                Décio
                -----BEGIN PGP SIGNATURE-----
                Version: GnuPG v1.2.2 (GNU/Linux)

                iD8DBQE+2JdYce3VljctsGsRAi/MAJ0R/QExYTsr9iPFoYJD10qC97W1DACgsRAE
                ZaEPvF7NaqttYWyjz8eDt9Q=
                =2+Bz
                -----END PGP SIGNATURE-----
              Your message has been successfully submitted and would be delivered to recipients shortly.