13
$\begingroup$

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?

$\endgroup$
17
  • $\begingroup$ By simplifying the problem and assuming $n=p^m$ for some prime $p$, what you are trying to do requires to know the length of a maximal proper partition of $m$ (the lenght of a maximal sequence $(m_1,\ldots,m_k)$ such that $m_1<m_2<\ldots<m_k$ and $m_1+\ldots+m_k=m$. I am not sure if this helps or not, since I don't know much about partitions $\endgroup$
    – Darío G
    Sep 17, 2016 at 11:24
  • $\begingroup$ @Wore Yes, that works only if $x$ has one distinct prime factor. In fact, in that case $m_i=i$ (except $m_k$, of course). $\endgroup$
    – Priyatham
    Sep 17, 2016 at 11:27
  • $\begingroup$ I think what you meant is that in this case $y_i=p^{m_i}-1$, for $i=1,\ldots,k$, but note that this is not an answer unless you know how to calculate the maximal length of a proper partition of $m$. Do you know? $\endgroup$
    – Darío G
    Sep 17, 2016 at 11:37
  • 1
    $\begingroup$ I mean that the maximal partition is probably simply, $1, 2, \dots , l-1, m - \left(\frac{l(l-1)}{2}\right)$ $l$ is the largest integer such that $m - \left(\frac{l(l-1)}{2}\right) > 0$ $\endgroup$
    – Priyatham
    Sep 17, 2016 at 11:43
  • 1
    $\begingroup$ In that case there might be a problem because you could have $m-\left(\frac{l(l-1)}{2}\right)$ equal to one of $1,2,\ldots,l-1$. However, if you have such maximal partitions, and $x=p_1^{m_1}\cdots p_r^{m_r}$, it seems that applying the method to each $p_i^{m_i}$, would solve the problem, of course combining at the end the remaining factors $p_i^{m_i-\left(\frac{l(l-1)}{2}\right)}$ by applying the same method to powers of $p_ip_j$ with $p_i\neq p_j$. $\endgroup$
    – Darío G
    Sep 17, 2016 at 12:19

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Let's define the index of a number $p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$ to be $a_1+a_2+\cdots+a_r$. Then I think you want to take all the factors of $n$ with index 1, then as many factors of index 2 as possible, then as many of index 3 (that is, of types $p^3$, $p^2q$, and $pqr$) as possible, and so on. $\endgroup$
    – Gerry Myerson
    Sep 20, 2016 at 23:02
  • $\begingroup$ How does one prove this works? $\endgroup$
    – Priyatham
    Sep 21, 2016 at 8:31
  • $\begingroup$ @Priyatham: it seems "obvious" that it does, as you use up as few of the prime factors as possible at each stage. That is why I called it a greedy algorithm. I worry about what happens if there are more factors of one prime than the others. The examples I have tried do not cause a problem, though. If $n=2^{12}3^4$ you start with $2,3,4,6,9$ and can't split the last $256$ as $16,16$, but you can do $8,32$ $\endgroup$
    – Ross Millikan
    Sep 21, 2016 at 14:13
  • $\begingroup$ @GerryMyerson You can't always take all the factors of $n$ with index $1$. For instance, consider the case where $n=p^2q$; the only valid solutions are $\{p, pq\}$ and $\{p^2, q\}$, neither of which has all the atoms. $\endgroup$
    – Steven Stadnicki
    Sep 26, 2016 at 15:50
  • $\begingroup$ @Steven, right – I should have said, take as many of index 1 as possible, then as many of index 2 as possible, and so on, where "as possible" means "as you can without making it impossible to complete the factorization". $\endgroup$
    – Gerry Myerson
    Sep 26, 2016 at 22:37
0
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ This is the exact algorithm I wrote in my question, right? I did it for $36$ as an example. $\endgroup$
    – Priyatham
    Sep 20, 2016 at 12:48
  • $\begingroup$ Unless you can prove the correctness, I am sorry to say that this is nothing new. $\endgroup$
    – Priyatham
    Sep 20, 2016 at 12:49
  • $\begingroup$ whoops sorry then $\endgroup$
    – nik
    Sep 20, 2016 at 12:52
  • 2
    $\begingroup$ If you're ordering divisors by their usual integer order (instead of some ordering based on their prime factorization), the greedy algorithm does not work. For instance, consider $x=p^{10}q^2r^3$. If $p\ll q\ll r$, you will pick $p, p^2,p^3,p^4,q,qr,r^2$. But you can do better by picking $p,p^2,p^3,q,pq,r,pr,p^2r$. $\endgroup$
    – Eric Wofsey
    Sep 20, 2016 at 19:23
  • 1
    $\begingroup$ Another example, with two primes: if $n=p^{10}q^{10}$ with $q>p^4$, then picking the smallest available divisor at each stage gets you eight ($p,p^2,p^3,p^4,q,q^2,q^3,q^4$), but you can get nine as $p,q,p^2,pq,q^2,p^3,p^2q,pq^2,q^3$. $\endgroup$
    – Gerry Myerson
    Sep 20, 2016 at 22:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .