The Labyrinthians' Exchange

From Paul and Samantha's first two statements, we know the product, let's call it P, isn't prime (because neither number was 1):

But much more informative is Paul's second statement that he can't figure out where the party is with the information Samantha supplied. If P was the multiple of exactly two prime numbers, Paul would know it by now (he'd simply factor his number into its unique prime components). So he knows the address isn't two prime numbers (although it could be one prime number and a composite number). By stating this, he's telling Samantha as much.

Samantha's next statement is more telling still; she already knew Paul couldn't figure it out. So whatever sum, let's call it S, Samantha remembers, it can't be made by adding two prime numbers together- if it could, then there would have been the possibility Paul knew the answer.

When Samantha announces her prescience, Paul then knows the answer. This means that out of all the possible addresses that multiply to make P, only one has the property of S described above.

Samantha makes the same logical deductions we have, and solves the problem. once you've figured out the logical steps needed to solve the problem, described above, it's still quite a bit of work to actually find the unique pair of numbers that satisfies these properties. A computer program can simplify the task of trial and error.

A more detailed discussion of the problem can be found in our Discussion Forums.

Incidentally, the party's address is 4-13.