The answer depends upon the ranges from which the numbers are chosen.
The unique solution for the ranges [2,62] through [2,500+] is:
SUM PRODUCT X Y 17 52 4 13
The unique solution for the ranges [3,94] through [3,500+] is:
SUM PRODUCT X Y 29 208 13 16
There are no unique solutions for the ranges starting with 1, and there are no solutions for ranges starting with numbers above 3.
A program to compute the possible pairs is included below.
#include <stdio.h>
/*
BEGINNING OF PROBLEM STATEMENT:
Mr. S. and Mr. P. are both perfect logicians, being able to correctly
deduce any truth from any set of axioms. Two integers (not necessarily
unique) are somehow chosen such that each is within some specified
range. Mr. S. is given the sum of these two integers; Mr. P. is given
the product of these two integers. After receiving these numbers, the
two logicians do not have any communication at all except the following
dialogue:
<<1>> Mr. P.: I do not know the two numbers.
<<2>> Mr. S.: I knew that you didn't know the two numbers.
<<3>> Mr. P.: Now I know the two numbers.
<<4>> Mr. S.: Now I know the two numbers.
Given that the above statements are true, what are the two numbers?
END OF PROBLEM STATEMENT
*/
#define SMALLEST_MIN 1
#define LARGEST_MIN 10
#define SMALLEST_MAX 50
#define LARGEST_MAX 500
long P[(LARGEST_MAX + 1) * (LARGEST_MAX + 1)]; /* products */
long S[(LARGEST_MAX + 1) + (LARGEST_MAX + 1)]; /* sums */
find(long min, long max)
{
long i, j;
/*
* count factorizations in P[]
* all P[n] > 1 satisfy <<1>>.
*/
for(i = 0; i <= max * max; ++i)
P[i] = 0;
for(i = min; i <= max; ++i)
for(j = i; j <= max; ++j)
++P[i * j];
/*
* decompose possible SUMs and check factorizations
* all S[n] == min - 1 satisfy <<2>>.
*/
for(i = min + min; i <= max + max; ++i) {
for(j = i / 2; j >= min; --j)
if(P[j * (i - j)] < 2)
break;
S[i] = j;
}
/*
* decompose SUMs which satisfy <<2>> and see which products
* they produce. All (P[n] / 1000 == 1) satisfy <<3>>.
*/
for(i = min + min; i <= max + max; ++i)
if(S[i] == min - 1)
for(j = i / 2; j >= min; --j)
if(P[j * (i - j)] > 1)
P[j * (i - j)] += 1000;
/*
* decompose SUMs which satisfy <<2>> again and see which products
* satisfy <<3>>. Any (S[n] == 999 + min) satisfies <<4>>
*/
for(i = min + min; i <= max + max; ++i)
if(S[i] == min - 1)
for(j = i / 2; j >= min; --j)
if(P[j * (i - j)] / 1000 == 1)
S[i] += 1000;
/*
* find the answer(s) and print them
*/
printf("[%d,%d]\n",min,max);
for(i = min + min; i <= max + max; ++i)
if(S[i] == 999 + min)
for(j = i / 2; j >= min; --j)
if(P[j * (i - j)] / 1000 == 1)
printf("{ %d %d }: S = %d, P = %d\n",
i - j, j, i, (i - j) * j);
}
main()
{
long min, max;
for (min = SMALLEST_MIN; min <= LARGEST_MIN; min ++)
for (max = SMALLEST_MAX; max <= LARGEST_MAX; max++)
find(min,max);
}
-------------------------------------------------------------------------
= Jeff Kenton (617) 894-4508 =
= jkenton@world.std.com =
-------------------------------------------------------------------------