/*
This program computes the solution to this riddle:
----
Two integers, m and n, each between 2 and 100 inclusive, have been
chosen. The product, mn, is given to mathematician X.
The sum, m + n, is given to mathematician Y. Their conversation is as
follows:
X: I don't have the foggiest idea what your sum is, Y.
Y: That's no news to me, X. I already knew that you didn't know.
X: Ahah, NOW I know what your sum must be, Y!
Y: And likewise X, I have surmised your product !!
Find the integers m and n.
----
In this program, the maximum value of the integers m and n is not fixed as 100, but is chosen by the user.
Note:
1. I dont know the "correct" way of solving this riddle, this is my way
2. The program could have been coded in a more efficient way. I just wanted to get the answers hence this inefficient coding.
-Gaurang Khetan (http://gaurang.org)
*/
#include
// define the following if you are compiling for windows
// in a windows compile, the program will prompt for a Enter keypress before ending
// so that the program window does not close immediately as the program displays the solution
//#define WINDOWS_COMPILE
int main()
{
void end_of_prog();
int max;
/* take input */
do
{
printf("Enter maximum possible value of the integers m and n (5 to 2000, typically 100): ");
scanf("%d", &max);
fflush(stdin); //scanf() does not eat the enter key character
}
while (max > 2000 || max < 5); // 2000 requires around 16MB prod array, more than 2000 would require HUGE memory
/* allocate memory required for computation */
int* prod = new int[max*max+1];
int* sum = new int[max+max+1];
if (prod==NULL || sum==NULL)
{
printf("\n INSUFFICIENT MEMORY!!\n");
end_of_prog();
return 1;
}
/* start computing */
printf("\nComputing...may take some time...");
int i,j;
prod[0] = prod[1] = prod[2] = prod[3] = sum[0] = sum[1] = sum[2] = sum[3] = 0; //impossible
//process sentence 1
for (i=4; i<=max*max; i++)
prod[i] = 1; //mark as unvisited yet
for (i=2; i<=max; i++)
for (j=i; j<=max; j++)
{
if (prod[i*j] == 1)
prod[i*j] = i+j; //first time
else
{ //non-first time
if (prod[i*j] != 0) //not yet assigned as having non-unique sums
if (i+j != prod[i*j])
prod[i*j] = 0; //it has non-unique possible sums
}
}
for (i=0; i<=max*max; i++)
prod[i] = ( (prod[i]==0)? 1 : 0 ); //only those with non-unique possible sums are possible in this riddle
//those with unique possible sums and the unvisited ones are not possible
//process sentence 2
for (i=4; i<=max+max; i++)
{
sum[i] = 1;
for (j=2; j<=i/2; j++)
if (prod[j*(i-j)] == 0)
{
sum[i] = 0; //not possible in this riddle, since it has a possible product with unique possible sum
break;
}
}
//process sentence 3
for (i=2; i<=max; i++)
for (j=i; j<=max; j++)
if (prod[i*j] != 0 && sum[i+j] == 1)
{
if (prod[i*j] == 1)
prod[i*j] = i+j; //it has one possible sum
else if (i+j != prod[i*j])
prod[i*j] = 0; //it has multiple possible non-unique sums
}
for (i=0; i<=max*max; i++)
prod[i] = ( (prod[i]>1)? 1 : 0 ); //only those with ONE unique possible sum are possible in this riddle
//those with none or more than one unique possible sums are not possible
//process sentence 4
for (i=4; i<=max+max; i++)
if (sum[i] != 0)
{
int count = 0;
for (j=2; j<=i/2; j++)
if (prod[j*(i-j)] == 1)
count++;
if (count!=1)
sum[i] = 0; //not possible in this riddle, only those with ONE unique possible product are possible in this riddle
}
/* print the solutions */
printf("done.\n\nSolutions: \n");
for (i=4; i<=max+max; i++)
if (sum[i] == 1)
for (j=2; j<=i/2; j++)
if (prod[j*(i-j)] == 1)
printf("m & n = %d & %d; X:mn=%d; Y:m+n=%d\n", j, i-j, j*(i-j),i);
printf("\nSolution Complete.\n\n");
/* end */
delete [] prod;
delete [] sum;
end_of_prog();
return 0;
}
void end_of_prog()
{
#ifdef WINDOWS_COMPILE
char str[10];
printf("\n Press the enter key to terminate...");
fgets(str, 10, stdin);
#endif
}