Background
===========
I have seen a few variants of this Sum-and-Product puzzle in the past. The premise of these puzzles is as follows
>Sam hears the sum of two numbers, Polly the product. The numbers are known to be between m and M.
>S: "You don't know the numbers"
>P: "That was true, but now I do"
>S: "Now I do too"
>What are the numbers?
A [set of papers from 2006](https://www.win.tue.nl/~gwoegi/papers/) refer to this as the Freudenthal Problem `Freudenthal(m,M)`. I have been specifically interested in classifying solutions when $m=3$, and $M$ is unbounded.
Assuming a modified form of Goldbach's conjecture, the authors prove that whether the numbers are known to be distinct or not does not change the solutions when $m=2$ and $m=3$, so I have removed their superscript distinguishing the case.
The authors also give a rather naive algorithm that enumerates solutions ordered by sum. They generate solutions for `Freudenthal(3,*)` up to a sum of 50,000, and find that there are 804 stable solutions, and 288 phantom solutions that rely on the presence of an upper bound.
My own findings
===============
I wrote [a program](https://pastebin.com/YDiy5R6g) that very efficiently generates solutions, also ordered by sum, and improved the highest sum by an order of magnitude overnight.
I then defined the "Freudenthal Partition Function" $F(s)$. The domain of this function is any sum $s$ which allows the first statement by Sam. The value $F(s)$ is the number of options remaining in Sam's mind after Polly's statement.
There is a lot to unpack in this function, so I will go into detail.
Domain of $F$
-------------
With $m=3$, the products which allow Polly to immediately deduce the numbers are any of the following:
* Odd semiprimes
* 4 times an odd prime (numbers must be 4 and p)
* 2 times the square of an odd prime (numbers must be p and 2p)
For Sam to make his first claim, the number cannot be the sum of two odd primes, sum of a prime and 4, or 3p for some p. What remains is the set $S$, which is the domain of $F$.
Assume the Goldbach conjecture so that all even numbers are eliminated from $S$ outright. Then $s\in S$ iff $s$ is odd, $s-4$ is composite, and $s\ne 3p$ for some prime $p$. This set can be efficiently generated.
Computing $F(s)$
---------------
Start with a list of all even integers. Iterate over all pairs $\{(s,a)\mid s \in S, a \in \mathbb{Z}, 3 \le a \le s/2\}$ and place a tally next to $a(s-a)$. For computability's sake, proceed lexicographically by $s$ then $a$.
After this procedure passes $s_0$, all tally counts on integers up to $3s_0-9$ are stable. Define the set $P$ to be all the integers with exactly one tally.
$p \in P$ has the following properties:
* $p$ is not uniquely factorable into two divisors in the set $\{z\mid z \in \mathbb{Z}, z\ge 3\}$ (guaranteed since they were reached from $S$).
* $p$ has a unique divisor pair $\{d,p/d\}$ such that $d + p/d \in S$.
Equivalently, if Polly was told the number $p$, then the first two lines of the puzzle are satisfiable.
To compute $F(s)$ given $P$, iterate over $\{a \mid 3\le a\le s/2\}$ and count the number of $a$ for which $a(s-a) \in P$.
Using $F(s)$
-------------
If $F(s)=1$, then Sam, upon hearing Polly's statement, can deduce the numbers. This corresponds to a solution to the puzzle. Other claims I will make about the behavior of $F(s)$ are just conjectures.
If $F(s)=0$, then there seems to always exists some upper bound $M$ such that an integer which had two tallies loses one, and $P$ gets a new element which causes the puzzle to be satisfiable. These correspond identically to what the authors of the 2006 paper called "phantom solutions". Indeed, for $s<50,000$, there are 804 instances where $F(s)=1$, and 288 instances where $F(s)=0$.
[A graph of $F(s)$ is found here](https://cdn.discordapp.com/attachments/397115645193355274/444260032746356736/Freudenthal_Comet_NMIN__3.png) for $s$ up to around 260,000. The function has three very distinct branches, corresponding to congruence classes mod 3. The bottom branch, which produces all known solutions, has $s\equiv 2 \pmod{3}$.
The solution pairs themselves
-----------------------------
A [list of the 3141 smallest pairs ordered by sum can be found here](https://pastebin.com/3xptpMfR). I list the even number, then the odd number. The same pairs ordered by even number can be found [here, and is more illuminating](https://pastebin.com/2mVXz16R).
A notable oddity is $(4, 137233)$, the only currently-known pair to include the value 4. This was missed entirely by the original papers.
The pairs seem to all be of the form $(4^np,q)$, where $n>0$, $p$ is either 1 or prime, and $q$ is either prime or the product of a small number of primes. All prime factors of $p$ and $q$ are congruent to $1 \pmod{3}$.
Non-solutions and what we can learn from them
---------------------------------------------
For every $s$, there are $F(s)$ pairs that can be considered "candidate solutions." If $F(s)>1$, they are not solutions, but in the lowest branch they share many properties of solutions.
For example, $F(53) = 2$, and the contributing pairs are $(4,49)$ and $(16,37)$. This could have allowed one to see that 4 is viable as one of the two numbers, even without finding the first example of $(4, 137233)$.
Looking at all candidate solutions for $s\equiv 2 \pmod{3}$, we find a very small set of exceptions to the $(4^np,q)$ trend.
The exceptional pairs with sum less than 500,000 are
* $(32,27)$
* $(128,9)$
* $(512,3)$
* $(2048,3)$
* $(32768,3)$
* $(32768,27)$
All are $(2^k,3^l)$ for $k$ odd and $l$ small. They all have $F(s)>1$ for their sum, so they are not solutions, but they lie in the bottom branch of the partition function and allow the puzzle to proceed through its first two statements.
I checked (inefficiently) all pairs $(2^k,3^l)$ for odd $k\le 31$ and $l\le 10$, and found 5 other pairs which allow the first two statements to be satisfied, but in every case $F(s)>1$. It remains open whether there exists a true solution with this form.
Edit: improved bound to $k\le 199$ and $l\le 25$. There are 95 pairs but in every case I found a witness of the form $(4^np,q)$ to show $F(s) > 1$.
Results for $m\ge 4$
====================
I used the same program to examine other values of the lower bound, with what I believe were the appropriate changes and assumptions. The header comment can help others verify the correctness. I did not find any solutions, in agreement with the conjecture put forth in in the papers. [Graphs of the corresponding Freudenthal Partition Functions](https://cdn.discordapp.com/attachments/397115645193355274/444260166679134220/Freudenthal_Comet_NMIN__4.png) diverge from 0, leaving no branch which could be believed to provide solutions.
So, my question to mathoverflow is: Has there been anyone else thinking about this problem, and do they have results that supplement/contradict/dwarf those I have gathered?