Number of solutions of equation

Question

I have equation: x + y + xy = n. And my code:

#include <iostream>
#include <cstring>

using namespace std;

long c;

int main()
{
   long x = 0;
   cin >> c;
   if(c == 0)
   {
       cout << 1 << endl;
       return 0;
   }
   for(long i = 1; i <= c / 2; i ++)
   {
       for(long j = 1; j <= c; j ++)
           if(i + j + i * j == c)
           {
                       x ++;
                   break;
           }
   }
   cout << x + 2 << endl;
}

Of course this code is very slow. How can i find positive number of solutions in faster way? Maybe there is specific algorithm?

There are infinitely many; x = (n - y) / (y + 1). With fewer variables than equations, this is unsurprising. Or are there further constraints that you should have mentioned in the question? — Wintermute, Mar 07 '15 at 08:31
@Wintermute From the above code, it's probably just (positive?) integer solutions. — Sinkingpoint, Mar 07 '15 at 08:34
With working code such as this, you may do better to post over at CodeReview.se. — Sinkingpoint, Mar 07 '15 at 08:34
For positive integer solutions, at least there's no reason to step through the value range for both x and y (since knowing one determines the other). The number of solutions is the number of values of y for which (n - y) is cleanly divisible by (y + 1). Add: That, in turn, is the number of values for which (n + 1) is cleanly divisible by (y + 1) because (n - y) / (y + 1) = (n + 1) / (y + 1) - 1, so really you have to find the divisors of (n + 1). — Wintermute, Mar 07 '15 at 08:40
You may be interested in https://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number — Wintermute, Mar 07 '15 at 08:56
You wrote `x + y + xy = n` at the top of the question, the least you could do is to use the same variable names in your code, instead of letting the readers go through your code before they understand that `c` is `n`, `i` is `x`, `j` is `y`, and `x` is actually the number of solutions. A little bit of order and clarity wouldn't hurt anyone! — barak manos, Mar 07 '15 at 09:28

score 1 · Answer 1 · answered Mar 07 '15 at 10:43

We can write:

x + y + xy = n
x + y(x + 1) = n
y = (n - x) / (x + 1)
  = (n + 1 - (x + 1)) / (x + 1)
  = (n + 1) / (x + 1) - (x + 1) / (x + 1)
  = (n + 1) / (x + 1) - 1

So you can iterate all values of x and see for which of them the above expression for y yields an integer result (when n + 1 is divisible by x + 1).

However, we don't have to iterate either: this will only happen for the divisors of n + 1. How can we efficiently find the divisors of n + 1?

We can use the formula for the number of divisors:

n = p1^e1 * p2^e2 * ... , pi = prime numbers
=> divisor_count(n) = (e1 + 1)*(e2 + 1)*...

So your algorithm can be replaced with (untested, might have some off by one error):

divisors = 1
for i = 2 to sqrt(n):
  ei = 0
  while n % i == 0:
    n = n / i
    ei++

  divisors = divisors * (ei + 1)

  if n > 1:
    divisors = divisors * 2

Which should be fast enough even for very large numbers. It can still be improved though, by only checking divisibility by prime numbers, which you can generate with the Sieve of Eratosthenes for example.

score 0 · Answer 2 · answered Mar 07 '15 at 11:46

0

1 + x + y + x y = (1 + x)(1 + y) = n + 1

The number of solutions is the number of factors of n + 1, i.e. the product of the multiplicities plus one of the prime factors.

answered Mar 07 '15 at 11:46

Number of solutions of equation

2 Answers2