Partitioning into products

Question

Consider partitions where every summand has a factor in common with its neighbors and only $x_n$ can be one:

$$x_0 x_1 + x_1 x_2 + x_2 x_3 + \cdots + x_{n-1} x_n = N \qquad x_i \in \mathbb{N}$$

Example $($apart from the trivial case $N \cdot 1 = N)$

$$15 = 2 \cdot 5 + 5 \cdot 1 = 4 \cdot 3 + 3 \cdot 1 = 3 \cdot 3 + 3 \cdot 2 = 3 \cdot 2 + 2 \cdot 3 + 3 \cdot 1$$

How can these partitions be generated efficiently by a program? I currently generate all permutations of the partitions of a number and then check for common divisors between neighbors (after first discarding all partitions with multiple primes or ones).

Furthermore, can we estimate the number of such partitions for a given $N$?

Thanks in advance.

Answer 1

This recursive program returns the $x_i$s in a list:

def f(n,L):
    s = n                   # subtract the current sum of the list
    for i in range(len(L) - 1): s -= L[i]*L[i+1]

    if s == 0: print(L)     # end the recursion
    elif s%L[-1] == 0 and s//L[-1] < L[-1]: 
        print(L + [s//L[-1]])

    for x in range(2,s//L[-1] + 1): f(n,L + [x])

n = 0
for x0 in range(2,n//2 + 1): f(n,[x0])

Answer 2

You don't have to generate all. If you are looping over the entire generating set and checking this seems aweful slow. Instead you can work backwards and generate up the string from x_n. This allows you to not have to check GCD's as you are just inserting it from the previous term.

That is, you start with $x_0 = 1$ then generate $x_1$ from a counter(all this will be recursively generated). E.g., let $x_1 = 3$. You then compute the value(N) from the new values and be done differentially(so you just keep track of it at each stage and update it when recursing). Since $x_1=3$ you want $x_2 = k*m$ where $k$ is some divisor of $x_1$ and $m$ is some integer(ideally it is relatively prime to $k$). Now when P > N you stop. You can also bound your lower bounds so you are not constantly trying pointless values. [Essentially implement some alpha-beta pruning]

In any case, you can optimize all this greatly by, say, iterating only over primes and tracking various things. It should be much faster than brute force. The idea is that one could almost get away generating only the values that work rather than generating invalid combinations and wasting time on that.

If you repose this problem though as primes it gets much easier.

Essentially in this case you are just adding up n numbers to get N but you want each of those numbers to have common factors. First, you can assume they all do not have any common factors because if they did then you could pull it out and reduce N.

From this you know that basically, if you think as each product as a combination of primes that as a set of values, then each set must have a common value with another.

That is, you are generating sets such that their pairwise intersection is non empty(has a common prime factor).

Hence, let P = set of primes. Then choose n subsets of P such that there exists one pairwise non-disjoint combination for every pair(with only one subset having 1 in it).

This might seem harder but I believe you can generate that set by just iterating through the primes. The easy way to do this is to simply iterate over the disjoint subjects, have a list, then add in the primes between all consecutive elements. This is constructing the elements from the bottom up.

This will ultimately be faster since the primes are, for large N, much sparser yet it still is an exponential problem.

As far as a rough estimate, it is easy: $x_k \leq N \rightarrow \sum_{k=0}^{n-1} x_k x_{k+1} \leq n N^2$. Of course you probably are looking for a better estimate.

Answer 3

This can be handled by iterating upwards.

Consider that you can categorise any sequence for value $n$ based on its first factor ($x_0$). We have a set of such expressions - so, for $n=15$, we have $$ S_{15,2}=\{2\cdot5+5\cdot1\}\\ S_{15,3}=\{3\cdot3+3\cdot2,\quad3\cdot2+2\cdot3+3\cdot1\}\\ S_{15,15}=\{15\cdot 1\} $$

Once you have this basic structure, it is easy to iterate to get all of the possible partitions. In particular, for a given $n$, you identify products that can occur at the beginning of the set - that is, a product of two values, $a>1$ and $b>1$, such that $ab<n-b$ (this catches all cases except $ab=n$ and $n\times 1=n$, which are special cases).

Once you have obtained such a pair ($a$ and $b$), you prepend this product to every entry in $S_{n-ab,b}$ - this is precisely the set of sequences that can follow $a\cdot b$ in partitions. All entries of this form, for a given $a$, are now members of $S_{n,a}$.

If $S_{n-ab,b}$ is empty, then there are no entries beginning with $a\cdot b$ for length $n$.

The benefit to this structure is that you can grow the partitions in a way that prevents duplication of effort, and it is easy to implement this as a code, if you think it through.

To demonstrate the process, let's generate the first few relevant sets (note: I will leave out empty sets and trivial sets ($S_{n,n}=\{n\cdot 1\}$))

The first non-trivial set is $S_{4,2}$. As there is no $a>1,b>1$ such that $ab<4$, and $4=2\times 2$, we see that $$ S_{4,2}=\{2\cdot2\} $$

The next non-trivial set is $S_{6,2}$, which is a little more interesting. The product $4=2\times2$ satisfies our requirements on $a$ and $b$, which gives us $2\cdot2+S_{2,2}=\{2\cdot2+2\cdot1\}$. Additionally, we have $6=2\times 3$. This gives us $$ S_{6,2}=\{2\cdot2+2\cdot1,\ 2\cdot3\} $$ Meanwhile, we also have $$ S_{6,3}=\{3\cdot2\} $$ If we look at the case of $n=7$, we quickly see that there are no non-empty sets except the trivial $S_{7,7}$. To confirm this, note the only possible $(a,b)$ pair with $a>1,b>1,ab\leq n-b$ is $(2,2)$, which would then require $S_{3,2}$, which is empty.

For $n=8$, we again get a more interesting one. The possible $(a,b)$ pairs that satisfy $a>1,b>1,ab\leq n-b$ are $(2,2)$ and $(3,2)$. In addition, we have $(2,4)$ and $(4,2)$ as straight products. Looking at the ones with $a=2$, we have $$ S_{8,2}=(2\cdot 2+S_{4,2})\cup\{2\cdot 4\}=\{2\cdot 2+2\cdot 2,\ 2\cdot 4\} $$ And for $a=3$, we have $$ S_{8,3}=3\cdot 2+S_{2,2}=\{3\cdot2+2\cdot 1\} $$

If this is to be implemented, there are a number of approaches, each of which has drawbacks, but should still be more efficient than the naïve approach. You could iterate up, starting with $n=4$ and working up until you get to the desired $N$... this is great if you want a lot of different $N$ values at the same time, but it will calculate partitions that you don't need along the way otherwise.

Alternatively, you can start with $N$, and constructively iterate over the sets (like $S_{N-4,2}$, for example) - the downside, there, is that you either have to manually handle memory of previous calculations, or you have to let it repeat its calculations if, say, it needs $S_{15,3}$ multiple times.

Note that, when doing this, you need only track the follow-on values. That is, $S_{15,2}$ can be expressed as $\{[5,1]\}$, while $S_{15,3}$ can be expressed as $\{[3,2],\ [2,3,1]\}$.

You can also use the same method for calculating the number of partitions, with only a little tweaking.

Also, if $15=3\cdot3+6\cdot1$ is a valid partition (as each one has a common factor with the next one), then it will require some additional tweaking... but your examples don't include this, so I'll assume you don't need to handle it.