From child's play to Sophie Germain primes and more

Having a child interested in numbers means inventing rather than only playing games with numbers. One such game took place a year ago, during a summer relaxing afternoon. All started with a recent May 2016 puzzle published on Matematika + (a web site in Macedonian that I manage), that asks to find three positive integers which sum equals to their product. At that time, it was a challenging problem for a boy with a satisfactory understanding in addition, but beginner's experience in multiplication. It took him some time to find the 1, 2, 3 solution, maybe because of the number 1 in it and its identity property for the multiplication. The next thing was his observation that if we look for two numbers with the same property (equal sum and product), then the numbers are 2 and 2. And, that was the start for the game.

The game

We started to look for four, five numbers with the same property, so we took the little whiteboard and we started to put solutions of the equal-sum-product problem for different size of \(n\)-tuples of positive integers on it. We had been looking only for at least one solution for different sizes of \(n\), starting with already discovered solutions for \(n=2\) and \(n=3\). I must admit that our approach was not a systematic one. The rediscovered identity property of the number 1 guided us to look for \(n\)-tuples with many 1s, just for easy calculation of the product. Soon, the little whiteboard looked like this:

When the whiteboard was finished, the game finished too. At least for my boy. The fact is that all these numbers were left in my head all together with many unanswered questions. Is there always a solution of the equal-sum-product problem for any \(n \in \mathbb{N}\)? How many solutions are there for an arbitrary \(n\)? How the form of the solutions or the number of the solutions depend on \(n\)?

First observations

Another glance at the whiteboard and the \(n\)-tuples containing the number \(n\), can be quite easily spotted. These multiples on the whiteboard are: \((2,2)\), \((1,2,3)\), \((1, 1, 2, 4)\), \((1, 1, 1, 2, 5)\), \((1, 1, 1, 1, 2, 6)\), \((1, 1, 1, 1, 1, 2, 7)\), \((1, 1, 1, 1, 1, 1, 2, 8)\), \((1, 1, 1, 1, 1, 1, 1, 2, 9)\), \((1, 1, 1, 1, 1, 1, 1, 1, 2, 10)\) and \((1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 12)\). Here is the picture of the whiteboard with underlined solutions of \(n\)-tuples containing the number \(n\):

In general, each of these \(n\)-tuples contains \((n-2)\) ones, the number 2 and the number \(n\) i.e. they have the form  \((1, 1, ..., 1, 2,n)\), where there are \((n-2)\) ones. Let us check. The sum of the numbers is

\(1 + 1 + ...+ 1 + 2 + n = n - 2 + 2 + n = 2n\), 

and the product of the numbers is

\(1 \cdot 1 \cdot ...\cdot 1 \cdot 2 \cdot n = 2n\).

So, the sum equals to the product, and \((1, 1, ..., 1, 2,n)\), with \((n-2)\) ones, is a solution of the equal-sum-product problem for an arbitrary \(n\). The solution of this form is called a basic solution. This means that for each \(n\) there are \(n\) numbers which sum equals their product. And it is not a new result, I've just rediscovered it here. The following references are at least three places where you can find this result and much more about the equal-sum-product problem:

(*) When the sum equals the product by Leo Kurlandchik and Andrzej Nowicki
(**) An Algorithm to Solve the Equal-Sum-Product Problem by M. A. Nyblom and C. D. Evans
(***) When Does a Sum of Positive Integers Equal Their Product? by Michael W. Ecker

Fill free to explore these references before continue reading my post. I did it too. You can find very interesting results there. For example, you can find that there are finite number of solutions of the equal-sum-product problem for each \(n\), or that for any number \(s\) there exists \(n\) for which the number of solutions is greater than \(s\), for example, for \(n=2^{2s}+1\), there are at least \(s+1\) solutions for the equal-sum-product problem. The form of these solutions can be found in (*).

Exceptional values

In (*) there is also a table with the number of solutions of the equal-sum-product problem for each \(1 \leq n \leq 100\). In this table, \(a(n)\) denotes the number of \(n\)-tuples that have equal sum and product:

I must admit that without any intention, we actually find almost all solutions for  \(2 \leq n \leq 15\). We only missed the basic solution \((1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 11)\) for \(n=11\), the nonbasic solution \((1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2)\) for \(n=12\), two of four solutions for \(n=13\) and the basic solutions for \(n=14\) and \(n=15\). Well, quite a lot.

In the references I mentioned before, you can also find that the common value of the sum and the product for any solution \(n\)-tuple is at most \(2n\), and this value is reached for the basic solution. Such statement and similar ones can lead to construction of an algorithm for finding all solutions for the equal-sum-product problem, as it is done in (**).

It is common knowledge that actually it can not exist only one research question in a scientific investigation. Almost always one question leads to another, and results that are found may be answers to other questions. In our case, searching for all solutions, their form and number, leads us to values of \(n\) for which there is only one solution, the basic solution i.e. \(a(n)=1\). These values of \(n\) are called exceptional values. From the above table, such values for \(n \geq 2\) are \(n=2, 3, 4, 6, 24\). There are researchers that have investigated this topic more deeply. In (***) there is a conjecture that the set of all exceptional values \(n \geq 2\) is finite i.e. the set of all exceptional values is \(E=\{2, 3, 4, 6, 24, 114, 174, 444\}\). This conjecture is tested up to \(n=10^{10}\) and no other exceptional values are found. But, what is the importance of the exceptional values?

Sophie Germain primes

As it is proven in (*), if \(n>2\) is an exceptional value i.e. \(a(n)=1\), then \(n-1\) is a prime number. In (**) it is proven that if \(a(n)=1\) for \(n>2\), then \(n-1\) is a Sophie Germain prime (a prime number \(p\) is a Sophie Germain prime, if \(p\) and \(2p+1\) are both primes). Let us check one exceptional value, say \(n=24\). It is true that \(n-1=23\) and  \(2(n-1)+1=47\) are both primes, so 23 is a Sophie Germain prime. Some historic note: Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. Here are some of the first Sophie Germain primes:

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, ...

So, exceptional values of the equal-sum-product problem and Sophie Germain primes are somehow in a relation. On the other hand, Sophie Germain primes play a big role in cryptography, where the number \(2p+1\), associated with a Sophie Germain prime \(p\), is called a safe prime. And safe primes are related to strong primes (a prime number \(q\) is a strong prime if \(q-1\) and \(q+1\) both have some large prime factors). The both of them, safe and strong primes, are used as the factors of secret keys in some cryptosystems, because they prevent the system being broken by certain factorization algorithms. Having infinitely many Sophie Germain primes (the Sophie Germain primes conjecture, which is still unsolved), will insure efficient secret key generating procedures. Let us go back to the set E of all exceptional values. If it is possible to prove that the set E is infinite, then the infinitude of Sophie Germain primes would immediately follow and the Sophie Germain primes conjecture will be solved. Voilà! But, it can not be that easy to prove such a deep conjecture with an elementary approach, as it is said in (**).

Something more

Now, leave the cryptography, leave the Sophie Germain primes, and let us go back to the equal-sum-product problem. Recall that \(a(n)\) denotes the number of \(n\)-tuples that have equal sum and product. We have listed these values up to \(n=100\) in a table. Let us plot that list:

From the line plot, the increasing trend in values \(a(n)\) is obvious and also the increase in the dispersion of these values (there are small and big values for \(a(n)\), as \(n\) increases). The high values of \(a(n)\) are expected due to the previous mentioned property that for any number \(s\) there exists \(n\) for which \(a(n)>s\). This might be true also for the small values of \(a(n)\), i.e. we can also expect them, due to the observed increasing dispersion. 

We can also plot the distribution of the numbers \(a(n)\) for the first 100 values: 

We can see that the distribution of the values \(a(n)\) is highly unsymmetrical and positively skewed. Due to previously observed increasing trend in values of \(a(n)\) and increasing dispersion, it is expected that the distribution will remain unsymmetrical and positively skewed, but with increasing mode. This means that the small values are also expected, but with decreasing probability as \(n\) increases.   

All statements presented in the section 'Something more' are intuitively made, and are still unproven.

  

After all

The last year equal-sum-product game/problem inspired me to compose a problem for finding all five-tuples of positive integers which sum equals their product and to post it as the Problem of the Month on Matematika + for September 2017. It was nice recreational math problem for young mathematicians.

It will also be interesting to see where the next family game will take us. I can not wait.