## Order to products of Gaussian primes...

Expand Messages
• 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.
• ... 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-----
• 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/
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/
• 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
• ... 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-----
• ... 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.