Need help to solve this equation

[aravindsubramanian]

I have an equation of type

(x+y) + xy = C

C is known & both x,y,c are even numbers.Whether is it possible to find x & y from this equation?
How many posiible x & y in that equation?


Ex:
(x+y) + xy = 6496

 

[Zurtex]

Well there are obviously 2 trivial solutions:

x = 0
y = C

and

x = C
y = 0

I'm not sure there is any way of tackling it other than a case by case basis for C, sorry.

 

[LittleWolf]

Using your example I think this will help:(x+y)+xy+1=6496+1 then (1+x)(1+y)=6497. The number of solutions can then be determined from the prime factorization of 6497.
x=72 and y=88

 

[aravindsubramanian]

Thank You very much for replying my queries.I need no of solutions available for this equation,

 

[Zurtex]

Thank You very much for replying my queries.I need no of solutions available for this equation,

Think about what LittleWolf has said:

(x+y) + xy = C

Goes to:

(x + 1)(y + 1) = (C + 1)

So, if you let $\alpha$ be the number of prime divisors of C + 1, do you think you could work out the number of solutions?

I'd try with quite a few varied examples. If you need help factoring numbers just use this web page: http://www.alpertron.com.ar/ECM.HTM

 

[LittleWolf]

If the prime factorization of C+1=(P1)^(k1)*(P2)^(k2)*...*(Pn)^(kn) then the number of divisors of C+1 equals (k1+1)*(k2+1)*...*(kn+1). The number of paired solutions becomes the smallest integer >=[(k1+)*(k2+1)*...*(kn+1)]/2 . Take for example x+y+xy=(3^4)*(5^2)*(7^3)-1 then C+1= =(3^4)*(5^2)*(7^3) and there should be (4+1)*(2+1)*(3+1)/2=30 pairs of solutions.

 

[J1618]

(x+y) + xy = C
C is known & both x,y,c are even numbers.Whether is it possible to find x & y from this equation? How many posiible x & y in that equation?

y = -2 is the only special case
x – 2 – 2x =c
-x = c + 2
x = -c – 2
Find all even c such that x is even.
c = 2n for all integer n.
Thus, for all possible c, y = -2 and x = -c – 2 is a solution.

All other possibilities take this form:

If y = 2 then x + 2 + 2x = c
3x = c – 2
x = (c-2)/3
Find all even c such that x is even.
c = 6n +2 for all integer n

If y = 4 then x + 4 + 4x = c
5x = c – 4
x = (c-4)/5
Find all even c such that x is even.
c = 10n +4 for all integer n

If y = 6 then x + 6 + 6x = c
7x = c – 6
x = (c-6)/7
Find all even c such that x is even.
c = 14n +6 for all integer n

The pattern is valid for all even y, including y = -2 :
c = 2(y + 1)n + y for all integer n

Given c, find all possible x and y

c = 2(y + 1)n + y
Each unique y you find determines a unique x, so we only need to find all possible y’s

c = 2ny + 2n + y
c = (2n + 1)y + 2n
c – 2n = (2n + 1)y
(c – 2n)/(2n + 1) = y

Find all integer n such that (c – 2n)/(2n + 1) is an even number.

If (c – 2n)/(2n + 1) is even then ((c – 2n)/(2n + 1))/2 is an integer.
((c – 2n)/(2n + 1))/2 = (c – 2n)/(4n + 2)

Find all integer n such that (c – 2n)/(4n + 2) is an integer.

Since as the absolute value of n becomes large, (c – 2n)/(4n + 2) approaches (-2)/4 , we know we only need to test a finite number of possible n.

We only need to test all n such that AbsoluteValue (c – 2n) >= AbsoluteValue (4n + 2)

You can verify that the desired range of n is:
If c > -1 then
RoundDown ((-c - 2)/2) up to
RoundUp ((c - 2)/6)
If c < -1 then
RoundDown ((c - 2)/6) up to
RoundUp ((-c - 2)/2)

Create the following computer program:

if c > -1 then
for j := RoundDown ((-c - 2)/2) up to
RoundUp ((c - 2)/6) do
if RoundDown ((c – 2j)/(4j + 2)) = ((c – 2j)/(4j + 2)) then
j is a unique solution and
y = (c – 2j)/(2j + 1)
x = (c – y)/(y + 1)
else
for j := RoundDown ((c - 2)/6) up to
RoundUp ((-c - 2)/2) do
if RoundDown ((c – 2j)/(4j + 2)) = ((c – 2j)/(4j + 2)) then
j is a unique solution and
y = (c – 2j)/(2j + 1)
x = (c – y)/(y + 1)

 

[J1618]

I coded the answer I came up with, and it appears to work.

For c = 6496 the solutions are
(-6498,-2), (-90,-74), (0,6496), (72,88)

For c = -6496 the solutions are
(-2166,2), (-1300,4), (-434,14), (-16,432), (-6,1298), (-4,2164), (-2,6494), (0,-6496)


Here is the pascal code:

program xyc;
Var c,x,y,j: longint; m,n,p,q,r,s:real;
begin
c:=6496;
m:=((-c - 2)/2)-1;
n:=((c - 2)/6)+1;
p:=((c - 2)/6)-1;
q:=((-c - 2)/2)+1;
if (c > -1) then
for j := Round(m) to round(n) do
if (Round ((c-2*j)/(4*j + 2)) = ((c-2*j)/(4*j + 2))) then begin
y := round((c-2*j)/(2*j + 1));
x := round((c-y)/(y + 1));
writeln (x,' ',y); end else
else
for j := Round(p) to round(q) do
if (Round ((c-2*j)/(4*j + 2)) = ((c-2*j)/(4*j + 2))) then begin
y := round((c-2*j)/(2*j + 1));
x := round((c-y)/(y + 1));
writeln (x,' ',y); end;
end. {main}

 

[J1618]

LittleWolf said:
If the prime factorization of C+1=(P1)^(k1)*(P2)^(k2)*...*(Pn)^(kn) then the number of divisors of C+1 equals (k1+1)*(k2+1)*...*(kn+1). The number of paired solutions becomes the smallest integer >=[(k1+)*(k2+1)*...*(kn+1)]/2 . Take for example x+y+xy=(3^4)*(5^2)*(7^3)-1 then C+1= =(3^4)*(5^2)*(7^3) and there should be (4+1)*(2+1)*(3+1)/2=30 pairs of solutions.

In this case, c = 694574
I ran my program and got 30 nonnegative solutions, as predicted.

 

[aravindsubramanian]

Hai l1618,
Thank You very much for your excellent workz.Now I am analyzing your solutions.I need only positive x & y.

 

[J1618]

"I need only positive x & y."

Your original request did not mention this, so I solved the more general problem.

For LittleWolf's c=694574 example, one of the 30 solutions is (0,c)

Here are the 30 solutions:
(0,694574)
(2,231524)
(4,138914)
(6,99224)
(8,77174)
(14,46304)
(20,33074)
(24,27782)
(26,25724)
(34,19844)
(44,15434)
(48,14174)
(62,11024)
(74,9260)
(80,8574)
(104,6614)
(134,5144)
(146,4724)
(174,3968)
(188,3674)
(224,3086)
(244,2834)
(314,2204)
(342,2024)
(404,1714)
(440,1574)
(524,1322)
(566,1224)
(674,1028)
(734,944)

For the original problem, c=6496, and we want to factor 6497=73x89. LittleWolf's analysis calls for 2 solutions:
(0,6496)
(72,88)

LittleWolf is solving for x+1 and y+1, not x and y. The number of solutions is derived from (c+1) = (x+1)(y+1). He calculated the number of solutions of the form ((x+1),(y+1)), where (x+1) and (y+1) are both positive numbers. One of the solutions is always (1,(c+1)). We actually want the solutions in the form (x,y), where x and y are both positve. Littlewolf's solution of (1,(c+1)) translates to (x,y) = (0,c), so this solution does not qualify.

Thus, the number of solutions where both x and y are positive is LittleWolf's calculation minus 1. For c=694574, there are 30 - 1 = 29 solutions.

Here is the revised program. It creates an output file. It only outputs the positive solutions. It only works for positive even values of c. It also includes a counter to output the total number of solutions. For c=694574 it prints out exactly 29 solutions.

program xyc;
Var c,x,y,j,k,t,yprev: longint; m,n:real; fo:text;done:boolean;
begin
c:=214748364;
assign(fo,'c:\freepascal\_xyc.txt');
rewrite(fo);
writeln(fo,'C = ',c); writeln(fo);
writeln(fo,'The solutions to x + y + xy = C');
t:=0;
done:=false;
yprev:=-1;
j:= -1;
k:=round(((c - 2)/6)+1);
if ((c >= 2) and ((round(c/2)) = (c/2))) then
repeat
j:=j+1;
if (Round ((c-2*j)/(4*j + 2)) = ((c-2*j)/(4*j + 2))) then begin
y := round((c-2*j)/(2*j + 1));
x := round((c-y)/(y + 1));
if (x=yprev) then done:=true
else if (x>0) and (y>0) then begin
t:=t+1; writeln (fo,'(',x,',',y,')'); yprev:=y; end; end;
until ((j>k) or done);
writeln(fo); writeln(fo,'Total number of solutions = ',t);
close(fo);
end. {xyc}

Here is a sample output:

C = 214748364

The solutions to x + y + xy = C
(4,42949672)
(12,16519104)
(40,5237764)
(60,3520464)
(64,3303820)
(204,1047552)
(304,704092)
(532,402904)
(792,270804)
(1320,162564)
(2500,85864)
(2664,80580)
(3964,54160)
(6604,32512)
(12504,17172)

Total number of solutions = 15

 

[aravindsubramanian]

Hai J1618
your method is quite simple.But take more time than LittleWolf's method.

 

[J1618]

Here is the final version:

program xyc;
Var c,x,y,n,t,yprev: longint; yy,src:real; fo:text; done:boolean;
begin
c:=214748364;
src:=sqrt(c);
assign(fo,'c:\freepascal\_xyc.txt');
rewrite(fo);
writeln(fo,'C = ',c); writeln(fo);
writeln(fo,'The solutions to x + y + xy = C');
t:=0;
done:=false;
yprev:=-1;
n:= -1;
if ((c >= 2) and ((round(c/2)) = (c/2))) then
repeat
n:=n+1;
yy:=((c-2*n)/(2*n + 1));
if (yy>src) then
if (Round (yy/2) = (yy/2)) then begin
y := round(yy);
x := round((c-y)/(y + 1));
if ((x<y) and (x<>0)) then begin
t:=t+1; writeln (fo,'(',x,',',y,')'); yprev:=y; end
else end
else
else done:=true;
until done;
writeln(fo); writeln(fo,'Total number of solutions = ',t);
writeln(fo,'Logic loop ran n = ',n+1,' times');
close(fo);
end. {xyc}

For c = 214748364 , my new program's repeat until loop only ran 7328 times. For c = 694574 , the loop runs 417 times.

Knowing that that y/2 = (c – 2n)/(4n + 2) is a positive integer makes it possible to solve the problem quickly.

If n < 0 then (c – 2n)/(4n + 2) < 0. So we start with n=0.

Also, if (a,b) is a solution, then (b,a) is a solution also. But we consider them to be the same solution.

y = (c - 2n)/(2n + 1). As n increases, y decreases. Once we find a y <= SquareRoot(c) we know we are done. Why? Because x+y+xy=c. Once y <= SquareRoot(c) is found, any further solutions found will be duplicates, since (a,b) = (b,a) for our purposes. My new program starts at n=0, and stops (done:=true) as soon as a y value <= SquareRoot(c) is found.

The new program prints the loop index, n, to verify how many times the loop ran. We can compare this with the expected value. y = (c – 2n)/(2n + 1) = SquareRoot(c). Square both sides and simplify, and you get a quadratic equation:
(4c - 4)n^2 + (8c)n + (c - c^2) = 0
Using the quadratic formula, we find the expected values are the same as the actual values.

Now here is an interesting thing. For a prime factorization algorithm, the simplest and least efficient way to proceed is to test consecutive odd numbers as factors of (c/2), since c is even. In the worst case, you will have to test all odd numbers up to SquareRoot(c/2).

For our 2 examples, how would the worst case performance compare to my method?

You need to test n = (SquareRoot(c/2))/2 numbers.
c = 214748364, n = 5181, my method = 7328
c = 694574, n = 295, my method = 417

The ratio of (worst case prime factorization) to (my method) is 1:(SquareRoot(2)).

In other words, my algorithm runs slightly longer than the worst case performance of an inefficient prime factorization algorithm.

I expected my algorithm to be slower. What surprises me is how close its performance is to the prime factorization method.

The beauty of my method is that the whole program is only about 20 lines long. The inefficient prime factorization algorithm discussed above would probably require at least 50-100 lines of code, and an efficient prime factorization algorithm that generates prime numbers directly would be even longer.

Here are some links on prime number generation:
http://alumnus.caltech.edu/~chamness/prime.html
http://bach.dynet.com/primes/
http://www.freevbcode.com/ShowCode.asp?ID=2114
http://www.olympus.net/personal/7seas/primes.html

 

[Zurtex]

J1618 your naïve algorithm isn’t that good for factoring a number, here is one of the best on the web for factoring numbers: http://www.alpertron.com.ar/ECM.HTM (I think that is part of what you are trying to do, my Pascal isn’t up to scratch, I’m just working it out from what it looks like)

Plus, given you know the number of prime divisors then you can work out the number of solutions.

Try your method with a much bigger number, somewhere in the region of 10^100 to really test your method.

 

[J1618]

"your naïve algorithm isn’t that good for factoring a number"

My algorithm is the best solution available for this problem that does not involve factoring.

You don't need to be able to read pascal to notice that this algorithm does no factoring. Also, as explained above, it will run (SquareRoot(c))/2 tests for any number, big or small.

By the way, how can you tell an algorithm is naive if you are unable to read it?

 

[Zurtex]

You don't need to be able to read pascal to notice that this algorithm does no factoring. Also, as explained above, it will run (SquareRoot(c))/2 tests for any number, big or small.

By the way, how can you tell an algorithm is naive if you are unable to read it?

Well running to sqrt(c)/2 isn't in polynomial time so you can't exactly call it efficient. Oh and I'm afraid the few languages I've programmed in look nothing like Pascal, so it's mainly just gibberish to me.

I was kind of hoping that this thread would get to more interesting number theory than just a simple program that seen barely above brute force. I thought the Totient Function might even come into place. The point is, just being able to calculate it through writing a program I didn't think was particularly a solution to the persons problems. If you know the number