Euler Examples

Search

The Freudenthal Problem

The following problem is due to Freudenthal a Dutch mathematician. He published it in a journal for mathematical interested public in 1969.

Wikipedia

p and q are two different integers, greater than 1 and less than 100. S and P are two mathematicians; S knows the sum p+q, P knows the product pq, and both know the information in these two sentences. The following conversation occurs.

P says "I cannot find these numbers."
S says "I was knew that you could not find them. I cannot either."
P says "Then, I found these numbers."
S says "If you could find them, then I also found them."

What are these numbers?

Solution

The solution in Euler is our challenge.

First we generate vectors p and q, such that p[i] and q[i] contain all possible variations once.

>function pq () ...
 p=[]; q=[];
 for i=2 to 99
    for j=2 to i
        p=p|j; q=q|i;
    end;
 end;
 return {p,q}
 endfunction

>{p,q}=pq();

Here are the first 11 combinations.

>(p'|q')[1:11]

            2             2 
            2             3 
            3             3 
            2             4 
            3             4 
            4             4 
            2             5 
            3             5 
            4             5 
            5             5 
            2             6 

We will need a function, which select the indices of a vector, which occur only once.

>function isonce(v) := nonzeros(getmultiplicities(v,v)==1);

Information 1

The fact that P cannot deduce the numbers means that the product pq occurs more than once in all possible products.

We select the indices as P1, where P would know the answer.

>P1=isonce(p*q);
>unique((p*q)[P1]); %[1:20]

[4,  6,  8,  9,  10,  14,  15,  21,  22,  25,  26,  27,  33,  34,  35,
38,  39,  46,  49,  51]

Note that 8 is among these numbers. Others are products or squares of primes. Here is a list of the first 10 elements.

>(p'|q')[P1][1:10]

            2             2 
            2             3 
            3             3 
            2             4 
            2             5 
            3             5 
            5             5 
            2             7 
            3             7 
            5             7 

Information 2

S says: "I knew you would not know the number."

Thus his sum p+q is not among the sums of numbers for which P would have known. So we must exclude all sums p+q which are not among the sums (p+1)[P1].

>function notin(v,x) := nonzeros(indexof(v,x)==0);

With this function we generate a list of indices S1, which are possible sums such that S would now that P does not know.

>S1=notin((p+q)[P1],p+q);

There are not many sums left.

>unique((p+q)[S1])

[11,  17,  23,  27,  29,  35,  37,  41,  47,  53]

Information 3

P: "Now I know!"

Thus P has a product, which is only in one way representable as pq such that p+q is in the list of left over sums.

We extract a list P2 of possible indices. For this, we select under all p, q with correct sum those that have a unique product.

>P2=S1[isonce((p*q)[S1])];

There are surprisingly many combinations left.

>length(P2)

86

Information 4

S: "Now I know too!"

This is the same as above, but with sums.

>S2=P2[isonce((p+q)[P2])]

69

Finally

There is only one index left.

>p[S2]|q[S2]

[4,  13]

Examples