The Impossible Problem: Torsten Sillke, Dec. 1997
-----------------------
Sum-Product Problem (Martin Gardner Version)
Two numbers (not necessarily different) are chosen from the range of
positive integers greater than 1 and not greater than 20. Only the
sum of the two numbers is given to mathematician S. Only the product
of the two is given to mathematician P.
On the telephone S says to P, "I see no way you can determine my sum."
An hour later P calls him back to say, "I know your sum."
Later S calls P again to report, "Now I know your product."
What are the two numbers?
Martin Gardner,
Mathematical Games, Scientific American, 241 (Dec. 1979) 22 -- the problem
Mathematical Games, Scientific American, 242 (May 1980) -- 2nd postscript
A discussion of this puzzle and variants can be found in (Sallow 1995).
He give a table with all possible solution pairs for different
upper bounds up to 100. The unique solution for the bound 20 is (2, 6).
Lee Sallows;
The Impossible Problem,
The Mathematical Intelligenzer, 17:1 (1995) 27-33
mailto:SALLOWS@psych.kun.nl
The Impossible Problem Revisited Again,
The Mathematical Intelligenzer, 17:4 (1995) 4-6
-----------------------------------------------------------------------------
Sum-Product Problem (Freudenthal/Sprows Version)
Let x and y be two numbers with 1 < x < y and x+y <= 100.
Suppose S is given the value x+y and P is given the value x*y.
<<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.
What are the two numbers?
Hans Freudenthal;
Nieuw Archief Voor Wiskunde, Ser 3, 17 (1969) 152 -- the problem
Nieuw Archief Voor Wiskunde, Ser 3, 18 (1970) 102-106 -- the solution
David J. Sprows;
Mathematics Magazine, 49:2 (March 1976) 96 -- Problem 977
Mathematics Magazine, 50 (1977) 268 -- the solution
-----------------------------------------------------------------------------
Sum-Product Problem (Brian Smith Version)
Well, we are all in agreement that S and P are wizards who know the
sum and product, respectively, of two integers chosen from some range,
most often {2,...,99}. The dialogue is:
<<1>> Mr. P.: I do not know the two numbers.
<<2>> Mr. S.: I knew you didn't. Neither do I.
<<3>> Mr. P.: Now I know the two numbers.
<<4>> Mr. S.: Now I know the two numbers.
What are the two numbers?
This is the one that appeared in Brian Smith's ``The Semantics of
Clocks'' with the note ``This puzzle appeared in the AI community in
the late 1970's but its origins or author seem to have been lost.'' I
suspect the problem is not nearly so young.
The assumption in these problems that is hardly ever mentioned is that
the ground rules in the first paragraph are to be considered ``public
knowledge''. That is to say, both P and S know the other knows these
things, each knows the other knows he knows, and so forth. The most
common fallacious solutions involve omitting the range of the numbers
from the public knowledge.
The problem as stated in the rec.puzzles article omits the second
sentence of <<2>>, but I suspect the latter is an editing error
rather than a case of addressing a different problem.
< Dan Hoey, mail-fun 1993 >
Brian Smith;
The Semantics of Clocks,
?year?
-----------------------------------------------------------------------------
Sum-Product Puzzle: (rec.puzzles logic/number problem)
==> logic/number.p <==
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 absolutely truthful,
what are the two numbers?
==> logic/number.s <==
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.
[...]
= Jeff Kenton (617) 894-4508 =
= jkenton@world.std.com =
-----------------------------------------------------------------------------
Sum-Product Puzzle: (Kiltinen/Young unbounded version)
The situation we explore involves choosing two integers r and s,
both of with are at least 2. Their sum m=r+s is given to one
mathematician, Sam, while their product n=r*s is given to another,
Prudence. Suppose that after some thought, they exchange the
following information:
Scenario I:
<<1>> P.: I do not know your sum, Sam.
<<2>> S.: I knew you didn't, Prudence.
<<3>> P.: Now I know your sum.
<<4>> S.: And now I know your product.
Do we now have sufficient information to deduce values for m and n?
Yes but not uniquely. The smallest solution is m = 17 = 4 + 13 and
n = 52 = 4*13. Other solutions (s,r,m,n) are (16,111,127,1776),
(201,556,757,111756), and (421,576,997,242496).
Scenario II:
<<1>> P.: I do not know your sum.
<<2>> S.: Thanks for that information.
<<3>> P.: I still don't know your sum.
<<4>> S.: Now I know your product.
<<5>> P.: And now I know your sum.
The reader is encouraged to verify that m=8 and n=16 is a solution
for this puzzle.
Scenario III:
<<1>> P.: I do not know your sum.
<<2>> S.: Thanks for that information.
<<3>> P.: I still don't know your sum.
<<4>> S.: Thanks for that information.
<<5>> P.: Thanks for that information.
<<6>> S.: Now I know your product.
<<7>> P.: And now I know your sum.
The reader may wish to find solutions for this bigger challange.
[no solution given.]
John O. Kiltinen, Peter B. Young;
Goldbach, Lemoine, and a Know/Don't Know Problem
(Sum knoledge is productive, product knoledge is better,
but Goldbach and Lemoine determine the limits.)
Mathematical Magazine, 58:4 (Sep. 1985) 195-203
-----------------------------------------------------------------------------
Sum-Product Puzzle: (Gosper/Schroeppel version)
Three people, S, P, and the Settor, are in a room together,
and can hear each other, are perfect reasoners, etc.
The Settor thinks up two numbers between 2 and 99 inclusive.
He tells the sum to S, and the product to P.
He asks S "What are the two numbers?" S replies "I don't know."
He asks P "What are the two numbers?" P replies "I don't know."
At this point, S says "Now I know!"
And then P says "Now I know!"
What are the two numbers?
I think I originally heard this from Gosper some years ago.
"Richard Schroeppel" letter to math-fun from Nov. 1993
The solution given in math-fun are (3,4), (69,96), and (84,84).
-----------------------------------------------------------------------------
Sum-Product Puzzle: (Hess version)
Mathematicians S and P. Two positive integers, each greater than 1, are
chosen. The sum is revealed to S; the product is revealed to P. Both S
and P are given the information in this problem. The conversation between
them goes as follows:
<<1>> S: There is no way you can know my number.
<<2>> P: I still don?t know your number.
<<3>> S: I now know your number.
What are the numbers S and P?
email from Dick Hess on 4. Dec. 1997
-----------------------------------------------------------------------------
Sum-Sum of Squares Puzzle: (Hess version)
Two positive integers <50 are choosen.
The sum is revealed to A;
the sum of the squares is revealed to B.
Both A and B are given the information in this problem.
The conservation between them goes as follows:
<<1>> B: I can't tell what the numbers are.
<<2>> A: I can't tell what the numbers are.
<<3>> B: I can't tell what the numbers are.
<<4>> A: I can't tell what the numbers are.
<<5>> B: I can't tell what the numbers are.
<<6>> A: I can't tell what the numbers are.
<<7>> B: Now I can tell what the numbers are.
What are the two numbers.
The answers section only states:
Through a long set of logical steps one can deduce that
the numbers are 8 and 9.
R. Hess;
Puzzles from around the world, 1997, Problem 41
T. Ferguson;
Mathematics Magazine, 56 (1983) 177 -- Problem 1173
Mathematics Magazine, 57 (1984) 180-181 -- Solution 1173
-----------------------------------------------------------------------------
Erich Friedman -- P and S are given the product and sum of two non-zero digits (1 to 9).
1. P says "I don't know the numbers".
S says "I don't know the numbers".
2. P says "I don't know the numbers".
S says "I don't know the numbers".
3. P says "I don't know the numbers".
S says "I don't know the numbers".
4. P says "I don't know the numbers".
S says "I don't know the numbers".
5. P says "I know the numbers".
what are they?
http://www.mathpuzzle.com/ at (2000-12-28)
=============================================================================
Below there is a further variant, which was discussed in math-fun 1993.
Note that the order of S and P have been changed.
-----------------------------------------------------------------------------
D I S C U S S I O N from M A T H - F U N (1993)
-----------------------------------------------------------------------------
From: "Richard Schroeppel" To: math-fun
Subject: S & P puzzle
I'm trying to recall the following puzzle. The answer depends
on the detailed wording, so I'd like to get it right. I think
I originally heard this from Gosper some years ago.
An Approximate Version of The S & P Puzzle.
Three people, S, P, and the Settor, are in a room together,
and can hear each other, are perfect reasoners, etc.
The Settor thinks up two numbers between 2 and 99 inclusive.
He tells the sum to S, and the product to P.
He asks S "What are the two numbers?" S replies "I don't know."
He asks P "What are the two numbers?" P replies "I don't know."
At this point, S says "Now I know!"
And then P says "Now I know!"
What are the two numbers?
Rich
-----------------------------------------------------------------------------
Date: Fri, 19 Nov 93
From: "cal" To: math-fun
Subject: number puzzle on sum and product
starting with the version rich gave,
by construction the product is composite,
so we (i.e., everybody) knows that
we know the sum is ambiguous (though this doesn't seem like much
of a restriction - perhaps the S and P questions are in the other order),
even if we don't all know what it is
we know the product is ambiguous,
even if we don't all know what it is -
this would greatly limit the choices
among those choices, i guess there are very few that can be factored in
two different ways with the same sum -
since that fact determines the sum,
it must be the case that there is only one pair that works that way -
a number that has two different factorizations into integers between 2 and 99
(inclusive)
that have the same sum -
i imagine that a little algebra could find them now
this isn't quite enough analysis to determine the proper sequence of questions
oh, well
more later,
cal
----------------------------------------------------------------------------------
Date: Tue, 23 Nov 93
From: "Shel Kaphan" To: math-fun
Subject: S&P Puzzle: SPOILER (with surprise ending!)
I showed this puzzle to some friends, as it has been a favorite of
mine since Rich showed it to me in 1977 or so... Here's an
interesting result that Dan Bornstein came up with. It turns out that
the upper bounds do matter -- they actually introduce two additional solutions!
--Shel Kaphan
>From Dan:
I find these three solutions to the problem as stated:
(3,4)
(69,96)
(84,84)
Here's a breakdown of info for each possible sum (below). Part A is
the different ways to get the sum of the two numbers when S knows
nothing about P. Part B is the different ways that P can get the
product when P knows that S doesn't know the pair. Part C is the
different ways that S can get the sum knowing that P doesn't know the
product. This can be either because for a given pair, there's only one
unique factoring into two numbers or because all the other factorings
have one or other of the numbers be out of the given range. Part D is
the different ways that P can get the product knowing that S knows the
pair. A solution is a pair such that sizeof(A) != 1 and sizeof(B) != 1
and sizeof(C) == 1 and sizeof(D) == 1.
So, if there's only one solution and it's (3,4), where's the flaw
in my reasoning (or my numbers)?
Sum A B C D
-------------------------
4: 1 -- -- --
5: 1 -- -- --
6: 2 1 -- --
7: 2 2 1 1 --> (3,4)
-------------------------------------
SOLUTION (3,4):
A: S knows nothing
7 = 2 + 5
7 = 3 + 4
B: P knows S doesn't know
12 = 2 * 6
12 = 4 * 3
C: S knows that P doesn't know
7 = 3 + 4
D: P knows that S knows
12 = 4 * 3
-------------------------------------
8: 3 2 2 --
9: 3 2 2 --
10: 4 1 -- --
11: 4 3 4 --
12: 5 4 3 --
13: 5 3 4 --
14: 6 1 -- --
15: 6 3 5 --
16: 7 3 5 --
17: 7 5 7 --
18: 8 2 6 --
19: 8 5 7 --
20: 9 4 7 --
21: 9 3 8 --
22: 10 1 -- --
23: 10 5 10 --
24: 11 7 8 --
25: 11 5 10 --
26: 12 1 -- --
27: 12 3 12 --
28: 13 4 11 --
29: 13 6 13 --
30: 14 4 10 --
31: 14 8 13 --
32: 15 3 13 --
33: 15 3 13 --
34: 16 1 -- --
35: 16 3 16 --
36: 17 5 13 --
37: 17 3 17 --
38: 18 1 -- --
39: 18 4 16 --
40: 19 5 16 --
41: 19 8 19 --
42: 20 3 16 --
43: 20 5 19 --
44: 21 2 17 --
45: 21 2 20 --
46: 22 1 -- --
47: 22 4 22 --
48: 23 7 17 --
49: 23 6 22 --
50: 24 1 -- --
51: 24 3 23 --
52: 25 2 19 --
53: 25 4 25 --
54: 26 2 20 --
55: 26 6 25 --
56: 27 4 20 --
57: 27 2 25 --
58: 28 1 -- --
59: 28 3 27 --
60: 29 7 22 --
61: 29 3 27 --
62: 30 1 -- --
63: 30 2 27 --
64: 31 2 23 --
65: 31 6 28 --
66: 32 2 22 --
67: 32 3 29 --
68: 33 2 24 --
69: 33 3 28 --
70: 34 2 25 --
71: 34 8 30 --
72: 35 5 26 --
73: 35 2 30 --
74: 36 1 -- --
75: 36 2 29 --
76: 37 2 26 --
77: 37 3 30 --
78: 38 1 -- --
79: 38 5 32 --
80: 39 4 28 --
81: 39 2 32 --
82: 40 1 -- --
83: 40 2 33 --
84: 41 5 30 --
85: 41 2 32 --
86: 42 1 -- --
87: 42 2 33 --
88: 43 2 29 --
89: 43 6 35 --
90: 44 3 32 --
91: 44 3 34 --
92: 45 2 31 --
93: 45 2 35 --
94: 46 1 -- --
95: 46 2 36 --
96: 47 4 32 --
97: 47 4 38 --
98: 48 1 -- --
99: 48 3 36 --
100: 49 1 -- --
101: 49 3 38 --
102: 49 1 -- --
103: 48 3 38 --
104: 48 1 -- --
105: 47 1 -- --
106: 47 1 -- --
107: 46 1 -- --
108: 46 2 28 --
109: 45 4 35 --
110: 45 1 -- --
111: 44 4 31 --
112: 44 3 30 --
113: 43 3 32 --
114: 43 1 -- --
115: 42 2 29 --
116: 42 1 -- --
117: 41 1 -- --
118: 41 1 -- --
119: 40 1 -- --
120: 40 5 19 --
121: 39 1 -- --
122: 39 1 -- --
123: 38 1 -- --
124: 38 1 -- --
125: 37 2 24 --
126: 37 2 20 --
127: 36 4 25 --
128: 36 1 -- --
129: 35 2 21 --
130: 35 1 -- --
131: 34 2 22 --
132: 34 2 12 --
133: 33 1 -- --
134: 33 1 -- --
135: 32 1 -- --
136: 32 1 -- --
137: 31 2 17 --
138: 31 1 -- --
139: 30 1 -- --
140: 30 2 12 --
141: 29 1 -- --
142: 29 1 -- --
143: 28 1 -- --
144: 28 3 8 --
145: 27 1 -- --
146: 27 1 -- --
147: 26 1 -- --
148: 26 1 -- --
149: 25 1 -- --
150: 25 1 -- --
151: 24 2 9 --
152: 24 1 -- --
153: 23 1 -- --
154: 23 1 -- --
155: 22 2 5 --
156: 22 1 -- --
157: 21 1 -- --
158: 21 1 -- --
159: 20 1 -- --
160: 20 1 -- --
161: 19 2 6 --
162: 19 1 -- --
163: 18 1 -- --
164: 18 1 -- --
165: 17 1 -- --
166: 17 1 -- --
167: 16 1 -- --
168: 16 2 1 1 --> (84,84)
-------------------------------------
SOLUTION (84,84):
A: S knows nothing
168 = 69 + 99
168 = 70 + 98
168 = 71 + 97
168 = 72 + 96
168 = 73 + 95
168 = 74 + 94
168 = 75 + 93
168 = 76 + 92
168 = 77 + 91
168 = 78 + 90
168 = 79 + 89
168 = 80 + 88
168 = 81 + 87
168 = 82 + 86
168 = 83 + 85
168 = 84 + 84
B: P knows S doesn't know
7056 = 72 * 98
7056 = 84 * 84
C: S knows that P doesn't know
168 = 84 + 84
D: P knows that S knows
7056 = 84 * 84
-------------------------------------
169: 15 1 -- --
170: 15 1 -- --
171: 14 1 -- --
172: 14 1 -- --
173: 13 1 -- --
174: 13 1 -- --
175: 12 1 -- --
176: 12 1 -- --
177: 11 1 -- --
178: 11 1 -- --
179: 10 1 -- --
180: 10 1 -- --
181: 9 1 -- --
182: 9 1 -- --
183: 8 1 -- --
184: 8 1 -- --
185: 7 1 -- --
186: 7 1 -- --
187: 6 1 -- --
188: 6 1 -- --
189: 5 1 -- --
190: 5 1 -- --
191: 4 1 -- --
192: 4 1 -- --
193: 3 1 -- --
194: 3 1 -- --
195: 2 1 -- --
196: 2 1 -- --
197: 1 -- -- --
198: 1 -- -- --
-dan
danfuzz@kaleida.com Will you dance with me, my little pickled herring?
-- Legendary Pink Dots
----------------------------------------------------------------------------------
From the rec.puzzles FAQ-List part1.
==> logic/number.p <==
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 absolutely truthful, what are the two
numbers?
==> logic/number.s <==
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
/*
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 absolutely truthful, 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 =
-------------------------------------------------------------------------
END OF ARCHIVE ENTRY
-----------------------------------------------------------------------------
Date: Sat, 27 Nov 1993
From: "Shel Kaphan" To: math-fun
Subject: beating a dead S&P horse
If we're sharing programs for this problem, here's the one I wrote to
solve it. It follows the logic of the problem (the way it is stated
anyway) a little more closely than the other program, but maybe isn't
as general, though I don't quite get what his "lower limit" means anyway.
-----------------------------------------------------------------------------
#include
#include
main() {
int a,b;
int s, p;
for(s=4; s<= 198; s++) {
if ((a=satisfiesRule4(s)) != 0)
printf("winning sum %d (%d + %d)\n", s, a,
s-a);
}
}
/* Mr. S: I know! */
/* Given s, for all pairs (a,b), a+b=s, 2 <= a,b <= 99,
true if exactly one pair satisfies rules 2 and 3 */
int satisfiesRule4(int s)
{
int a,b;
int limit = s/2;
int winner=0;
if (!satisfiesRule2(s)) /* this is really necessary --
some false answers */
return 0; /* are produced without it. */
for(a=2; a<=limit; a++) {
b = s-a;
if (satisfiesRule3(a*b)) {
if (winner)
return 0;
winner=a;
}
}
return winner;
}
/* Mr. P: I know! */
/* Given p, for all pairs (a,b), ab=p, 2 <= a,b <= 99,
true if exactly one pair satisfies rule 2 */
int satisfiesRule3(int p)
{
int i;
int limit;
int winner=0;
limit = (int)sqrt((double)p);
for(i=2; i<=limit; i++) {
if (p%i == 0) {
int j = p/i;
if (!inRange(j))
continue;
if (satisfiesRule2(i+j)) {
if (winner)
return 0;
winner=1;
}
}
}
return winner;
}
/* Mr. S: I knew you didn't know */
/* Given s, for all pairs (a,b), a+b=s, 2 <= a,b <= 99,
true if at least one of a or b is composite */
int satisfiesRule2(int s)
{
return isAlwaysSumOfComposite(s);
}
int inRange(int x)
{
return (2<=x && x<=99);
}
int isAlwaysSumOfComposite(int s)
{
int a;
int limit = s/2;
for(a=2; a<=limit; a++) {
if (isPrime(a) && isPrime(s-a)) {
return 0;
}
}
return 1;
}
/* dumbest possible way to compute this, almost. */
int isPrime(int x)
{
int i;
int limit;
if (x<=3) return 1;
limit = (int)sqrt((double)x);
for(i=2; i<=limit; i++) {
if ((x%i)==0)
return 0;
}
return 1;
}
-----------------------------------------------------------------------------
Date: Sat, 27 Nov 1993
From: "Shel Kaphan" To: math-fun
Subject: Re: S&P puzzle
Beating this into the ground just a bit further... I modified the
program I sent out to remove the upper limit. (Well, I set it to
10,000 and made a table for determining primality so it would finish
while I'm still alive). I ran it out to S=5000. S is the outermost
iteration in my algorithm. I determined that there are 15 pairs of
numbers which solve the problem (up to S=5000, and it looks an awful
lot like that's going to be it), and they have some similarities:
4 13
4 61
16 73
16 111
64 73
32 131
16 163
4 181
64 127
4 229
8 239
13 256
32 311
32 641
32 821
I *think* the program is correct. Notice that all the answers consist
of a power of two and another number, which is a prime in all cases
but one (16,111). Can anyone make a stab at explaining why that
should be so? (Or, maybe just stab me for being wrong?!) Any
opinions about whether there might be more solutions?
-----------------------------------------------------------------------------
Date: Sat, 27 Nov 1993
From: "Shel Kaphan" To: math-fun
Subject: S&P: spoke too soon
The previous small number of solutions I mentioned had to do with the
upper limit of 10000 I still had in part of the program (the "inRange"
check). With no upper limit, it seems that there are more
"exceptions", and also (of course) more solutions. I annotated the
ones that are not {2^n, prime}
17 = 4 + 13
65 = 4 + 61
89 = 16 + 73
127 = 16 + 111 111 is a composite
137 = 64 + 73
163 = 32 + 131
179 = 16 + 163
185 = 4 + 181
191 = 64 + 127
233 = 4 + 229
247 = 8 + 239
269 = 13 + 256
305 = 64 + 241
343 = 32 + 311
427 = 8 + 419
457 = 8 + 449
547 = 128 + 419
569 = 256 + 313
583 = 71 + 512
613 = 101 + 512
637 = 128 + 509
667 = 8 + 659
673 = 32 + 641
697 = 128 + 569
733 = 32 + 701
757 = 201 + 556 201 is a composite 556 is a composite
779 = 256 + 523
787 = 128 + 659
817 = 8 + 809
821 = 64 + 757
853 = 32 + 821
929 = 256 + 673
967 = 128 + 839
977 = 40 + 937 40 is a composite 937 is a prime
989 = 256 + 733
997 = 421 + 576 421 is a prime 576 is a composite
1045 = 32 + 1013
1087 = 36 + 1051 36 is a composite 1051 is a prime
1117 = 8 + 1109
1207 = 16 + 1191 1191 is composite
1267 = 8 + 1259
1273 = 512 + 761
1289 = 256 + 1033
1297 = 8 + 1289
1327 = 8 + 1319
1345 = 128 + 1217
1357 = 128 + 1229
etc.
-----------------------------------------------------------------------------
Date: Sun, 28 Nov 1993
From: "Shel Kaphan" To: math-fun
Subject: Re: S&P: spoke too soon
From: "John Conway"
Date: Sun, 28 Nov 93
what IS this problem - I'm lost, but would like to know. JHC
As per the restatement Rich recently posted:
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.
This is different from the other version which I think Rich slightly
mis-remembered, as I also had, in which <<2>> was "I don't know either".
That problem had (3,4) as a solution (as well as (69,96) and (84,84) if
the two numbers are limited to [2,99]). This one has (4,13) as a
solution if the same limits are used, but lots of additional solutions
if no upper limit is imposed. I'm still wondering if any of the more
numerologically inclined can explain why the solutions are *usually*
but not always (2^n, prime). BTW I have the answers up to S=8000 if
anyone wants them.
Shel
-----------------------------------------------------------------------------
Date: Mon, 29 Nov 93
From: hoey To: math-fun
Subject: Messrs S and P
Well, we are all in agreement that S and P are wizards who know the
sum and product, respectively, of two integers chosen from some range,
most often {2,...,99}. The dialogue I've seen most often is:
<<1>> Mr. P.: I do not know the two numbers.
<<2>> Mr. S.: I knew you didn't. Neither do I.
<<3>> Mr. P.: Now I know the two numbers.
<<4>> Mr. S.: Now I know the two numbers.
There are, of course, any number of variants of this statement, but
this is the one that appeared in Brian Smith's ``The Semantics of
Clocks'' with the note ``This puzzle appeared in the AI community in
the late 1970's but its origins or author seem to have been lost.'' I
suspect the problem is not nearly so young. The problem Rich set
omitted the first sentence of <<2>>. The problem as stated in the
rec.puzzles article omits the second sentence of <<2>>, but I suspect
the latter is an editing error rather than a case of addressing a
different problem.
The assumption in these problems that is hardly ever mentioned is that
the ground rules in the first paragraph are to be considered ``public
knowledge''. That is to say, both P and S know the other knows these
things, each knows the other knows he knows, and so forth. The most
common fallacious solutions involve omitting the range of the numbers
from the public knowledge.
As I recall, there's a version in which the range has a lower bound
but no upper bound. The interesting part there is that you need to
actually prove something, rather than just write a program to check
all the possible pairs. I seem to recall a variant that depends on
Goldbach's conjecture, too.
Dan Hoey
Hoey@AIC.NRL.Navy.Mil
-----------------------------------------------------------------------------
From - Thu Jan 29 10:21:13 1998
From: evan@scd.hp.com (Evan Whitney)
Newsgroups: rec.puzzles
Subject: Variation of Mr. P and Mr. S
Date: 28 Jan 1998 17:00:01 GMT
Here's a variation of Mr. P and Mr. S that I just made up. I
believe the solution is unique and the problem completely defined.
One logician, Mr. S, is told the sum of two integers. The other
logician, Mr. P, is told the product of the same two integers.
Mr. P knows that Mr. S knows the sum, and Mr. S knows that
Mr. P knows the product. The following conversation ensues,
you decide who is who:
Mr. X: "I don't know what the two integers are."
Mr. Y: "I knew you didn't know what they are."
Mr. X: "I knew you knew that."
Mr. Y: "This conversation could go on forever."
Mr. X: "I still don't know what the integers are."
Mr. Y: "Now I know what they are."
Mr. X: "Now I know what they are, too."
What are the two integers?
Evan Whitney
evan@scd.hp.com