Background
===========
I have seen a few variants of this [Sum-and-Product puzzle](https://en.wikipedia.org/wiki/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: I have a program running to find pairs $(2^k,3^l)$ for which the first two statements can be satisfied, and for each pair, search for a witness to $F(s)>1$. For $k\le 219$ and $m\le 25$, there are 13 pairs with no witness of the form $(4^n,q)$. The much more computationally intensive task of confirming absence of a witness of the form $(4^n p,q)$ is likely intractable if the pair is a solution. Witnesses have been found for the smallest 7 pairs, the first pair with no known witness yet is $(2^{141}, 3)$.
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?
# Asymptotic behavior of $F(s)$ #
I did some asymptotic analysis of $F(s)$. For a given $s$, I determined all the products with at most 3 odd factor sums such that one of those sums is $s$, and what numbers on the order of $s$ must be prime for $F(s)$ to increase by 1. This gives remarkably good fits for the three congruence classes. To reduce noise, I show here a moving average of $F(s)$, averaging the nearest hundred values in the same branch.
[![Moving average of $F(s)$ with the labelled fits][1]][1]
Notably, those $s \equiv 2 \pmod{3}$ have no growth at order $s/\log(s)^3$, always requiring an additional number to be prime and resulting in asymptotic growth at order $s/\log(s)^4$. This keeps $F(s)$ very near zero for those values we have seen, but means that $F(s)$ still grows without bound for these $s$.
This has potential to imply that there are only finitely many solutions, although such a claim is still far off. I don't know how best to determine $\liminf\limits_{s \to \infty} F(s)$.
# Arithmetic progressions $s_a$ with $F(s_a)$ exceptionally low #
If one rephrases the argument which gave the asymptotic formula in terms of the probability $F(s)=1$, they predict that there are only finitely many solutions, and that over 95% have been seen by the point $s=100,000$. We know at least the latter to be false, so there are systematic failures of the argument.
The leading order contribution to the lowest branch of $F(s)$ counts the instances where three things hold:
* $s=4^kp+q$ for primes $p$ and $q$ with $k\ge 2$
* $s^\prime=4^k+pq \not\in S$, that is, $4^k+pq-4$ is prime.
* $s^{\prime\prime}=4^kq+p \not\in S$, that is, $4^kq+p-4$ is prime.
Note that $s^{\prime}-s=(4^k-p)(q-1)$ and $s^{\prime\prime}-s=(4^k-1)(q-p)$. The factor $4^k-1$ is independent of $p$ and $q$. When $s-4$ shares a factor with $4^k-1$, $s^{\prime\prime}$ is not prime for any $p,q$.
Since $s\equiv 2\pmod{3}$ is necessary, $s-4$ cannot be a multiple of 3. If we define $k_m(s)$ to be the smallest $k\ge 2$ such that $(k,s-4)=1$, then we can refine the first bullet point above:
* $s=4^kp+q$ for primes $p$ and $q$ with $k\ge k_m(s)$
We then refine our prediction about the asymptotic behavior of the low branch of $F(s)$:
$F(s) \sim s\log(s)^{-4}4^{-k_m(s)}$
We may define $g(k)$ to be the smallest value for which $k_m(g(k))=k$, then $g(3)=5$, $g(5)=35$, $g(7)=385$, etc. Each defines an arithmetic progression with exceptionally low values of $F(s)$. Specifically,
$s_{a,k}=\left\{\begin{array}{11}
(6a+1)g(k) & g(k)\equiv 1\pmod{6}\\
(6a+5)g(k) & g(k)\equiv 5\pmod{6}
\end{array}
\right.$
Determining whether $F(s)$ takes the value 1 often, we must know the growth pattern of $g(k)$.
$F(s_{0,k})\sim g(k)\log(g(k))^{-4}4^{-k}$
This appears to grow unbounded, though erratically. It returns to values near 1 at $k=30$ and $k=60$ before jumping upward. I conjecture that $\liminf\limits_{s \to \infty} F(s) = \liminf\limits_{k \to \infty} F(s_{0,k})$.
To determine $g(k)$, we must make a statement about the smallest prime factor of $(4^k-1)/3$.
If $k$ is composite, then the smallest prime factor of $(4^k-1)/3$ is the smallest prime factor of $(4^d-1)/3$ for some divisor $d$ of $k$. This factor is present in $g(q)$ for all $q\ge d$, so if $k$ is composite we must have $g(k)=g(k-1)$.
If $k$ and $2k+1$ are both prime, then given the recurrence $r_0=0$,
$r_{n+1}=4r_n+3 \pmod{2k+1}$, we have $r_k=0$, and so $4^k-1$ is divisible by $2k+1$.
If $k$ is prime and there is not a value of the form $ck+1$ for which the recurrence relation above holds, then the smallest prime factor of $(4^k-1)/3$ might be $(2^k+1)/3$. This happens for $k=7,13,17,19,31,61,...$. At the moment I don't have a full understanding of why primality of both $k$ and $6k+1$ is able to predict a factor of $6k+1$ in $4^k-1$ when $k=37$, but not when $k=17$.
The jumps upward in $g(k)$ when it must now include a factor of $(2^k+1)/3$ have increasing magnitude and seem to indicate unbounded growth of the expression $g(k)\log(g(k))^{-4}4^{-k}$, although proving this is beyond my ability.
Unbounded growth of this expression would imply with high certainty that there are finitely many solutions to the Freudenthal problem `Freudenthal(3,*)`. Is there an approach to proving this?
[1]: https://i.sstatic.net/M3GLz.png