Longest strict partition of a positive integer?

I have just finished my 1st year in Computer Science. Since the holidays began, I've been studying algorithms and different computer science problems.

The following problem has proved quite difficult for me:

Let there be N, k two positive integers. Find the max k such that (Y1+1)(Y2+1)...(Yk+1) = N, where the Ys are also positive distinct integers;

Ok, so here was my take on this problem: 1) Break N in prime factors. A simple example: 42 = 2 * 3 * 7. I can already see that "I don't care" about the "+1" inside the paranthesis, since 42 = (1+1) * (2+1) * (6+1), so Y1 = 1, Y2 = 2, Y3 = 6. 2) But what if the powers of the prime factors are bigger, like: N = 2^3 * 7^2 * 3^6 and so on. Well, now I have many more possibilities to study. For this case, max k would be 6, because N = 2^1 * 2^2 * 7^2 * 3^1 * 3^2 * 3^3 = 2 * 4 * 49 * 3 * 9 * 27 = (1+1)(3+1)(48+1)(2+1)(8+1)(26+1). I can see that the idea is to break the power of each prime factor into the longest sum of distinct positive integers. By longest, I mean to have as many terms as possible in the sum. Because that would give me the most distinct terms in the product of N. The last example: N = 2^(1+2) * 7^2 * 3^(1+2+3) = 2^1 * 2^2 * 7^2 * 3^1 * 3^2 * 3^3 = 2 * 4 * 49 * 3 * 9 * 27 => max k = 6.

I've searched the internet for some time and I've found some very interesting concepts (I actually regretted not doing the math major). One of these concepts is partitions; more exactly, it seems that I need the longest strict partition of a positive integer (that is, for every power of the prime factors of N).

Any help (references/notes/suggestions/ other ideas!) would be greatly appreciated :)

Solution 1:

Let $\triangle_m \equiv \frac{m(m+1)}{2}$ be the $m$-th trangular number, and let $L(n)$ be the number of entries in the longest strict additive partition of the numbers from $1$ to $n$. Then $$ \triangle_{L(n)} \leq n $$ and $L(n)$ is the largest integer for which that relation holds. So for example, $L(8) = 3$ because $\triangle_{3} = 6 \leq 8$ but $\triangle_{4} = 10 >8$.

I have been trying to express $L(n)$ in closed form using expressions involving $\sqrt{2n}$ and floor or ceiling functions, but it does not seem to be easy.