Finding the largest subset of factors of a number whose product is the number itself 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$. 


*

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

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

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

*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?
 A: 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.
A: 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.
