quadint.sums exposes helpers for decomposing numbers into non-negative integer solutions of:
x^2 + d*y^2 = n
For d=1, this is the classic sum-of-two-squares problem. For other supported values of d, the same public API can be used for related quadratic forms.
Every solution is found, for every d. The algorithm below is the one for the class-number-one values d in {1, 2, 3, 7, 11, 19, 43, 67, 163}, where every prime that is a norm at all is the norm of some element. With any other d, some primes are not: neither 3 nor 7 is x^2 + 5*y^2, but 21 == 4^2 + 5*1^2. There, the same combinatorics run on the ideals of norm n instead of elements, and only the principal ones (the ones with a generator) give solutions.
This builds on the algorithm described by Stan Wagon (1990), based on work by Serret and Hermite (1848), and Cornacchia (1908).
The first thing to know is that there is a deterministic algorithm to quickly find the 1 and only solution for primes
-
Factor
$n$ . This is the hardest, most time-consuming step. We'll say this factoring has the form$2^t * (p_1 ^ {k_1} * p_2 ^ {k_2} * ...) * (q_1 ^ {j_1} * q_2 ^ {j_2} * ...)$ Where$t$ is the 2's exponent, all of the primes$p$ are$\equiv 1 \bmod 4$ , and all of the primes$q$ are$\equiv 3 \bmod 4$ .- If any of primes
$q$ (which are$\equiv 3 \bmod 4$ ) have an exponent$j$ that is odd, then there are no solutions. - If there are no primes
$p$ (that are$\equiv 1 \bmod 4$ ), there are no solutions.
- If any of primes
-
Construct a "base number" to use during the combinatorics later. We'll start with the 2's power, we will start the base number off as
$(1 + i)^t$ . This is because$2 = 1^2 + 1^2$ . However while it is possible to solve for 2, it does not need to participate in the combinatorics due to it being the only possible symmetric solution. -
Now, for each prime
$q^j$ in the factoring (the ones$\equiv 3 \bmod 4$ ):- Multiply the base number by
$q^{ j / 2 }$ . Note that from the rules laid out in step 1 above,$j$ is guaranteed to be even so this will always be an integer.
- Multiply the base number by
-
Next will begin the combinatorics for the
$p$ group, however 1 member of the$p$ group does not need to engage in this combinatorics (reasons why below). So we'll select the first prime$p \equiv 1 \bmod 4$ , and create its "imaginary decomposition". This is a complex number$x+yi$ made from the solution$x^2 + y^2 = p$ . Multiply the base number by this number too.- If the exponent for this
$p$ (the$k$ value) was 1 then$p$ can be removed entirely from the group. - If
$k$ was greater than 1, it should be decremented, and the remaining instances of$p$ in the factorization still need to undergo the following combinatorics.
- If the exponent for this
-
Now for the combinatorics. Each factor
$p$ left is used$k$ times, and each time it can be either its "imaginary decomposition"$x+yi$ or the conjugate$x-yi$ . Multiplication does not care about order, so all that matters is how many of the$k$ copies are$x+yi$ . That leaves$k + 1$ options for each$p$ :$(x+yi)^m (x-yi)^{k-m}$ for$m = 0, 1, \ldots, k$ . (Trying every sequence of$k$ true/false choices gives exactly the same products, just$2^k$ of them instead of$k + 1$ , which gets slow fast for higher powers.)For every combination of those options (Python has a product method for this):
-
Start this solution with the base number.
-
For each factor
$p$ left, multiply the total number by the option chosen for it. -
The real and imaginary part of the total number now constitute a solution for
$x^2 + y^2 = n$ ! Amazing!!- The numbers are then sorted so that
$x < y$ , and this is a solution that may or may not have been found already.
- The numbers are then sorted so that
-
Doing this we can rapidly break any number
Note: Remember how we didn't do combinatorics for a single exponent of the
Note: That is not entirely true, as skipping all of the combinatorics with this number and 2 means we will not get back all trivial solutions.
To get all trivial solutions with this package, pass the argument no_trivial_solutions=False to decompose_number.
As an example, lets look at
Starting with the rules we can see that all of the primes
The 2's exponent is 1, so we will say our base number is
There is only a single prime in the
We'll take the first prime in the
Now for combinatorics to produce all the different solutions. The remaining 2 primes
- Using the positive values: Multiply the base number by
$2+3i$ and$1+4i$ (from the solutions for both of these primes), and we get$-69 + 123i$ , which using the absolute values of this is magically our first solution:$19890 = 69^2 + 123^2$ . - Using the negative values: Multiply the base number by
$2-3i$ and$1-4i$ , and we get$129 - 57i$ , which gives our next solution:$19890 = 129^2 + 57^2$ . - Using positive for 13 and negative for 17: Multiply the base number by
$2+3i$ and$1-4i$ , and we get$3 + 141i$ , which again gives our next solution:$19890 = 3^2 + 141^2$ . - Lastly it should be obvious: Multiply the base number by
$2-3i$ and$1+4i$ , we get our final answer:$19890 = 87^2 + 111^2$ .
So in conclusion, the following are all equal to
Everything laid out in this example is performed by the following Python code:
from quadint.sums import decompose_number
print(decompose_number(19890))
# {(69, 123), (57, 129), (3, 141), (87, 111)}