# Algorithm to generate the number of tuples that satisfy the sum equals product problem.

Problem Statement: Let $$n\geq 2$$ be a natural number. We are interested in sequences $$(x_1,x_2,...,x_n)$$ of natural numbers such that $$x_1+x_2+...+x_n = x_1x_2...x_n\text{ and }x_1\leq x_2\leq...\leq x_n.$$ Let $$A(n)$$ denote the set of all such sequences. Moreover, we denote by $$a(n)$$ the cardinality of the set $$A(n).$$ The goal is to generate $$a(n)$$ for $$n\geq 2.$$

Attempt: Naive attempt in Python 3.5

from itertools import product

def prod(tup):
"""
Computes the product of all elements in the tuple.
"""
p = 1
for i in tup:
p = p*i
return p

def a(n):
"""
Check Sum Equals Product Property.
"""
list_of_tuples = list(product(range(1,2*n+1), repeat = n))
count = 0
for tup in list_of_tuples:
if sum(tup) == prod(tup):
count = count + 1
return count


It can be proved that for all $$n\geq 3$$ that $$x_1+x_2+...+x_n\leq 2n.$$ So I just used the bound $$1\leq x_i\leq 2n$$ for all $$i=1,2,...,n.$$ I know this is really bad because it is $$O((2n)^n)$$ and I not generating non-decreasing sequences. I guess one would want to reduce the number of tuples to check, but I am not sure how to do this. Perhaps someone has an idea?

• Your code doesn't take into account the fact that $x_1 \leq x_2 \leq \cdots \leq x_n$. – Yuval Filmus Oct 1 '18 at 22:25
• For $n \leq 10^4$, you can use the table on OEIS: oeis.org/A033178. – Yuval Filmus Oct 1 '18 at 22:27

One simple optimization you can use is as follows: since $$x_1 + \cdots + x_n \leq 2n$$, it follows that at most $$\log_3 (2n)$$ values are at least 3. You can go over all possible values for these $$O(\log n)$$ elements, and for each of them it should be easy to determine whether they can be completed (by adding only 1s and 2s) to a solution.
Taking this one step further, you can start adding elements to the sequence, from $$x_n$$ down, keeping track of the current product. If it exceeds $$2n$$, you can immediately halt.
Alternatively, OEIS has your sequence as A033178, and a table for $$n \leq 10000$$.