BQD Iterator and split points

How can you get multiple solutions for a sum of squares? Turns out an easy way is with my binary quadratic Diophantine iterator or BQD Iterator for short:

If: u² + Dv² = F

then it must be true that

(u-Dv)² + D(u+v)² = F(D+1)

-------------------------------------------------------------

The BQD Iterator lets you start with one known solution and get new ones by iterating. And at each iteration you have split points, where you may get two new solutions.

For example let u = 1, and v = 2, and D = 4, where I'm picking to get a sum of squares.

Then 1 + 4*4 = 17, so F = 17. Now you can get new values.

The first iteration then with all positives is:

(-7)² + 4(3)² = 17*5

But I have a split point around negatives, as u = -1 and v = 2, will also give F = 17, since you're squaring, so using those:

(-9)² + 4(-1)² = 17*5

So each iteration actually gives me two potential solutions, and you can find multiple solutions that sum to give the same thing.

To demonstrate I'll give one more iteration with each.

For (-7)² + 4(3)² = 17*5, next iteration:

(-19)² + 4(-4)² = 17*5² and (-5)² + 4(10)² = 17*5²


For (-9)² + 4(-1)² = 17*5, next iteration:

(-5)² + 4(-10)² = 17*5² and (13)² + 4(8)² = 17*5²


Which is interesting as ignoring signs, one solution shows up twice. So you don't always get unique solutions or you'd have the total number doubling at each split point. Also if u = v, or -v, you will not have a split point either.

And just using positives so I can make it look pretty, and pulling the 4 into the square, I have:

19² + 8² = 5² + 20² = 13² + 16² = 17*5²

Which demonstrates how to use split points to generate multiple sums of squares for the same value.

The power of D+1 matches iterations, and maximum number of solutions for n iterations is 2ⁿ but as we see above, you can get the same solution more than once, or have u = v, or -v. So though that maximum value is 4, we only had 3 uniques by sign with our example.

You can do more than a sum of two squares though, and I have a post showing how to sum a specific number of squares, so you can go looking for multiple solutions for exactly the number of squares you decide.

That could be useful for many fun things.


James Harris