Finding the largest subset of factors of a number whose product is the number itself

Question

Given a positive integer $x$, find $k$ distinct positive integers $y_1, y_2, \dots, y_k$ such that $$ x = \prod_{i=1}^k(1+y_i) $$ The problem is to pick the $y$'s so that $k$ is as large as possible.

Now, if the restriction of distinctness of $y$'s is removed, the problem becomes really simple. Let $$ x = \prod_{i=1}^n p_i^{a_i} $$ be the prime factorization of $x$ ($p_i$ are prime numbers), then the answer is simply $k=\sum_{i=1}^n a_i$.

But I cannot seem to figure out how to solve this if $y_i$ are required to be distinct.

One approach I tried was to simply greedily pick the factors(excluding $1$) of $x$ in ascending order.

To illustrate, for $x=36$, the factors are $2,3,4,6,9,12,18,36$.

1. I choose $2$ because $2$ divides $36$.

2. I choose $3$ because it divides $18$ ($=\frac{36}{2}$).

3. Next I skip $4$ as it does not divide $6$ ($=\frac{36}{2\times3}$).

4. Finally pick $6$ which divides 6.

I end up with $k=3$. But I couldn't prove that this algorithm is correct.

EDIT: I am primarily interested in finding $k$, the size of the largest subset.

---

My initial guess for the solution to this problem if $x$ is the power of a prime seems to be true. Let $$ x = p^a $$ Consider the following problem:

Find number of integer solutions of: $$ n_1 + n_2 + \dots + n_k = a \, (n_1 > n_2 > \dots > n_k > 0) $$ Let $m_k = n_k, m_i = n_i -n_{i+1} (i\neq k)$ Then that problem can be rewritten as the number of integer solutions of: $$ m_1 + 2m_2 + \dots + km_k = a \, (m_i > 0) $$

which is the coefficient of $x^a$ in $$ \frac{x^{(1+2+\dots+k)}}{(1-x)(1-x^2)\dots(1-x^k)} $$ which is non-zero iff $\frac{k(k+1)}{2} \leq a$

---

Going back to the original problem, this means that if $x=p^a$ then $k = \lfloor{\frac{\sqrt{1+8a}-1}{2}\rfloor}$ and $y_i = p^i-1, 1 \leq i < k$ and $y_k=p^{a-\frac{k(k-1)}{2}}-1$

So for $x=8192=2^{13}$, $k = 4, y_1 = 1, y_2 = 3, y_3 = 7, y_4 = 127$. Note that the choice of $y$ is not unique. $y_1 = 1, y_2 = 3, y_3 = 15, y_4 = 63$ is also a legitimate solution.

As @Wore mentions in the comments how to we extend this to $x$ when it is not the power of a prime?

Answer 1

Deleted.

Let $x=p_1^{m_1}\cdots p_n^{m_n}=2^5 3^4 5^5$ Loop through the list of all divisors of $x$ that are $<p_n^2$, if $d_k | x$ increase counter by one and set $x= x/d_k$ , else continue

Here is the proof:

Suppose $d=\{ d_{n_1}, \ldots d_{n_k} \}$ is the list constructed by this greedy algorithm. Suppose there exists a bigger list $d'=\{ d_{m_1}, \ldots d_{m_{k'}} \}$ containing $j$ equal enteries. That would mean the divisors form the list $d$ can transform to more enteries that are not in $d$. Since the algorithm is greedy, ANY refinement ( using their factors to construct new enteries) of those divisors will give ones already contained in $d$ (because the greedy algorithm already processed any smaller divisors), a contradiction, on the other way any coarse transformation will give less new enteries than we started, also a contradiction.

Answer 2

I would suggest you try a greedy approach. I haven't developed it into an algorithm, but it is a thought. If you factor $x=p^aq^br^c \ldots$ into prime powers, the answer will only depend on the multiset $\{a,b,c,\ldots \}$. The primes will not matter. The first factors to claim are the primes dividing $x$, specifically $p,q,r,\ldots$ The next cheapest factors are of the form $pq$ or $p^2$. You don't want to use the square for primes you don't have many of. Next try $p^2q$ where you consider primes with low exponents expensive and don't square them. This seems a problem that is very hard to program, but will be obvious to a human as long as the number of prime powers is not too large.