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
