Number of Integer Solutions to an Equation

Skippums

I am wondering if there is a general formula to find the number of integer solutions to an equation in two variables? For example: Given that x, y are both positive integers, find the number of distinct (x, y) pairs that yield a given value z in the following equation: 3x^2 + y^2 = z Essentially, I am attempting to find an f(z) that yields the following values (the pairs x,y are included after the function value):

f( 1) = 0
f( 2) = 0
f( 3) = 0
f( 4) = 1 {(1, 1)}
f( 5) = 0
f( 6) = 0
f( 7) = 1 {(1, 2)}
f( 8) = 0
f( 9) = 0
f(10) = 0
f(11) = 0
f(12) = 1 {(1, 3)}
f(13) = 1 {(2, 1)}
...
f(28) = 3 {(1, 5), (2, 4), (3, 1)}
...
f(91) = 2 {(3, 8), (5, 4)}
...

I don't care about finding the pairs that yield the solution, only the number of solutions (actually, I only care if the number of solutions is odd or even, if that helps). If there is such a function, what is the methodology of derivation? Thanks,

Sounds like somebody's got a case of the Mondays -Jeff

Sauro Viti

Let's rewrite your equation as y2 = z - 3x2. Then y = sqrt(z - 3x2). We can easily see that there are no solutions for z < 3. Now we can write the following code (is C code, but it's easy to port it to another language):

int f(int z)
{
int result = 0;
int x = 0;
double m = 0; // m is 3*x*x
double y;

if (z < 3) return 0; // You could remove this line (the function will continue to work properly)

while (m <= z)
{
y = sqrt(z - m);

  // Test if y is integer...
  if (y == floor(y)) result++;

  x++;
  m = 3\*x\*x;

}

return result;
}

Note that this function has a complexity of O(z-2) as it checks for all possible integers values of x. Also note that this implementation accept solutions where x and/or y are zero (e.g. f(4) returns 2 and the solutions found are { 0, 2 } and { 1 ,1 }). If you want solutions with x and y stricly positive you should initialize the loop with x = 1 and m = 3, and inside the loop ignore solutions with y == 0.

Luc Pattyn

Hi Jeff, In my experience formulas giving the number of solutions of some problem are rare in number theory (Diophantine equations). As an example, there are some formulas that estimate the number of primes in a given range, however all they give is an approximation, not a exact value. So I'm afraid you need some loops, as Sauro suggested. You may organize it differently though: by calculating z from x and y, and storing all the results, you could build a large table much faster than you could analyze a large number of z values one by one; this is similar to the concept of the Sieve or Eratosthenes. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

Skippums

The code that I have implemented actually does exactly what you suggest. I have an outer loop for y and an inner loop for x, and just flip a boolean value in an array each time I find a solution (since I only need to know the number of solutions mod 2). However, the algorithm I am attempting to implement claims to have a better O() runtime than another algorithm I implemented to do the same thing, and I am just not seeing this claim play out in my implementation of the two algorithms. In fact, I am seeing just the opposite, and determining the number of solutions to this equation is really the only difference between the two. I guess I'll just have to look a bit harder at my loops to see if I can do anything more efficiently. Thanks,

Sounds like somebody's got a case of the Mondays -Jeff

Luc Pattyn

if you want to do a mapping approach such as Eratostenes over a huge range, applying a banding technique pays off big time. I investigated prime generation more than a year ago (still should finish the article!), and upped the performance more than 10 times by making sure the output mapped well into the level two cache. IIRC I am getting 20 million primes per second on a typical machine. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

_Erik_

If you will check several values of Z per session, and memory usage is not a problem, you might store the work of the algorithm as you check for a value of Z. Errr... confusing, It's hard for me to explain this in English. Let me give you an example in C#:

public class Solutions
{
Dictionary<int, bool> matches = new Dictionary<int, bool>();
int maxZ = 0;

public bool? EvenSolutions(int z)
{
    if (z > maxZ)
    {
        int maxY = (int)Math.Sqrt(z - 3);
        int maxX = (int)(Math.Sqrt(z - 1 / 3d));
        int n = 4;

        for (int x = 1; x < maxX; x++)
        {
            for (int y = 1; y < maxY && (n = 3 \* x \* x + y \* y) <= z; y++)
            {
                if (n > maxZ)
                {
                    if (!matches.ContainsKey(n))
                        matches.Add(n, false);
                    else
                        matches\[n\] = !matches\[n\];
                }
            }
        }

        maxZ = z;
    }

    return (matches.ContainsKey(z)) ? (bool?)matches\[z\] : null;
}

}

The method returns true if there is a even number of solutions; false if the number of solutions is odd; and null if there are no solutions but, at the same time, it stores the possible values of Z which have solutions and are lesser than the given Z. So, if you are later checking for a smaller value of Z, you will already have it in matches dictionary and you will not have to repeat the process... and if it is not in the dictionary then it means that there weren't solutions for that value of Z.

Alain Rist

Hi Jeff, With VC2010 (or gcc 4.5) C++0x implementation:

#include <utility>
#include <array>
#include <algorithm>

template <unsigned int z>
size_t NumSolutions()
{
typedef std::pair<unsigned int, unsigned int> Solution;
std::array<Solution, z * z + 2 * z> All;

std::generate(All.begin(), All.end(), 
	\[\]()->Solution{
	static unsigned int x = 0, y = 0;
	return y == z ? Solution(++x, y = 0) : Solution(x , ++y);});

return std::count\_if(All.begin(), All.end(), 
	\[\](const Solution& sol){return z == 3 \* sol.first \* sol.first + sol.second \* sol.second;});

}

With previous C++03 compilers:

#include <utility>
#include <vector>
#include <algorithm>

typedef std::pair<unsigned int, unsigned int> Solution;

template <unsigned int z>
bool IsSolution(const Solution& sol)
{
return z == 3 * sol.first * sol.first + sol.second * sol.second;
}

template <unsigned int z>
Solution Next()
{
static unsigned int x = 0, y = 0;
return y == z ? Solution(++x, y = 0) : Solution(x , ++y);
}

template <unsigned int z>
size_t NumSolutions()
{
std::vector<Solution> All(z *z + 2 * z);
std::generate(All.begin(), All.end(), Next<z>);
return std::count_if(All.begin(), All.end(), IsSolution<z>);
}

You may test both with:

#include <iostream>
int main()
{
using std::cout;
using std::endl;

cout << "NumSolutions<4>(): " << NumSolutions<4>() << endl;
cout << "NumSolutions<7>(): " << NumSolutions<7>() << endl;
cout << "NumSolutions<28>(): " << NumSolutions<28>() << endl;
return 0;

}

cheers, AR Edited for correct size of All vector. Edited for use of adequate std::array in C++0x version.

When the wise (person) points at the moon the fool looks at the finger (Chinese proverb)

modified on Friday, November 26, 2010 4:45 PM