﻿ Euler Math Toolbox - Examples

# 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.

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