2
$\begingroup$

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?

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

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.

You can probably optimize this much further, but this is already a good start.

Alternatively, OEIS has your sequence as A033178, and a table for $n \leq 10000$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.