3
$\begingroup$

I got stuck with quite a simple problem:

Given a positive number $X$ find the largest number $k$, for which exists the positive distinct integers $Y_1,…,Y_k$ such that $(Y_1+1)(Y_2+1)⋯(Y_k+1)=X$

Any of my approaches based on integer factorization or working with the divisors of the $X$ have failed. For example all my tries have failed to solve the problem for $X=684913065984000$. A correct solution in this case is $k=15$, with $Y=[1,2,3,4,5,6,7,8,9,11,15,19,23,31,63]$.

Can anyone help me with a solution? My guess is that we may need some DP but I can't come with any kind of practical approach.You may find this problem on the Kattis online judge here

$\endgroup$
6
  • 2
    $\begingroup$ Why $Y_k+1$ and not just $Y_k$ ? $\endgroup$
    – user16034
    Commented May 9, 2022 at 7:28
  • $\begingroup$ @YvesDaoust So that each factor is greater than 1. $\endgroup$
    – John L.
    Commented May 9, 2022 at 12:40
  • 1
    $\begingroup$ @JohnL.: that's a useless complication of the notation. It makes the reading of the solution cumbersome. $\endgroup$
    – user16034
    Commented May 9, 2022 at 12:49
  • 1
    $\begingroup$ @JohnL.: "greater then one" is way better. $\endgroup$
    – user16034
    Commented May 9, 2022 at 12:53
  • 1
    $\begingroup$ Suppose there is an oracle that returns the factorization of the given number, then put its factors into a multiset like $\{2,2,3,3,3,5,5,5,5\}$, then the problem is to find a maximum partition of the multiset such that no two subsets of the partition are the same. $\endgroup$
    – Mengfan Ma
    Commented Jul 10, 2022 at 15:45

4 Answers 4

2
$\begingroup$

This answer is on the dynamic programming algorithm to solve the problem. I think it's better to present it as a new answer, instead of attaching it to my previous answer about the backtracking algorithm.

Define a distinct factorization as the factorization of distinct factors. Let the order of a factorization be the number of factors in that factorization. And let an optimal factorization be a feasible factorization of the maximum number of factors. Note that $1$ is not considered in all factorizations.

Given $n, m\in \mathbb{N}$, let $f[n,m]$ be the maximum order of distinct factorizations of $n$ whose smallest factor $\ge m$. Thus, $f[n,2]$ is exactly what we want. We distinguish between two cases depending on whether $m$ is chosen as a factor or not. If not, then we increment $m$ by $1$ and have $f[n,m]=f[n,m+1]$. Otherwise, we have $f[n,m]=f[n/m,m+1]$. Note that if $m/n$ is not an integer, the procedure has to stop. Also, if $n< m$, by the definition of $f[n,m]$, the procedure also terminates. Finally, if $n=m$, we have $f[n,m]=1$. The transition function is as follows:

$$ f[n,m]= \left\{ \begin{array}{} -1, & \text{if } n \notin \mathbb{Z} \text{ or } n < m \\ 1, & \text{if } n=m \\ \max\{f[n,m+1], f[n/m,m+1]+1\}, & \text{otherwise} \end{array}. \right. $$

The dynamic programming algorithm runs in $O(n^2)$. It is pseudo-polynomial time.

Note: The intuition is that given an integer $n$, instead of carrying out the prime factorization immediately and then dealing with the prime factors, we can just divide $n$ by $2$, if divisible, we divide $n/2$ by $3$, if divisible, divide $n/(2\cdot3)$ by $4$, and so on and so forth (that's what I did before I came up with this dynamic programming algorithm). Of course, the method may give a non-distinct factorization, for instance, $12=2\cdot 3 \cdot 2$. Even when a distinct factorization is obtained by this method, it may not be the one of the maximum order (the number $684913065984000$ given by the OP is of this case).

$\endgroup$
2
$\begingroup$

First, we factorize the integer and then we convert the problem to a multiset partition problem. The multiset partition problem can be solved by a backtracking algorithm.

Given an integer $n$, let its factorization be $n=p^{a_1}_1\cdot p^{a_2}_2 \cdots p^{a_m}_m$ where $p_1, \cdots, p_m$ are distinc primes. We list all the primes in a multiset $S=\{p_1, \dots, p_1, \dots, p_m,\dots, p_m\}$. For example, if $n=3600=2^4\cdot3^2\cdot5^2$, we have $S=\{2,2,2,2,3,3,5,5\}$. Then the problem is equivalent to partition $S$ into distinct subsets such that the number of the subset is maximized. This is because, if two sets of primes are different, then the product of primes in one set is not equal to that in another set.

Then we can use a standard backtracking algorithm to solve the multiset partition problem. In each step of the algorithm, a subset that hasn't been subtracted yet is obtained and deleted from the current $S$. The search acts like a depth-first search for trees. As an example, the backtracking tree of a set $\{a, a, b\}$ is given below. Each non-root node stands for the currently obtained subset. The red leaf means that after we subtract the subset of the red leaf from $S$, all the subsets of $S$ are already used in previous steps. The path from the root to a white leaf stands for a feasible partition.

enter image description here

Note: This is the most naive backtracking algorithm. I believe it can be improved by some observations. For example, the subset that contains exactly one element must be in one optimal solution (can someone prove it?). And if the number of two elements is the same in $S$, can one element be pruned in the recursion tree?

$\endgroup$
0
$\begingroup$

Solving this problem will in the worst case require an exhaustive search with possibly exponential growth. We modifiy the problem slightly to reduce the search space.

Given $X ≥ 2$, we call $X_1, X_2, ... , X_k$ an "exact factoring of $X$" if the $X_i$ are all distinct, greater than 1, and their product $P$ equals $X$. An "optimal exact factoring of $X$" is an exact factoring that has the largest possible number $k$ of factors, and we want to find an "optimal exact factoring of $X$".

Instead we call $X_1, X_2, ... , X_k$ a "factoring of $X$" if their product $P$ is not necessarily equal to $X$, but only divides $X$. An "optimal factoring of $X$" is a factoring with the largest number $k$ of factors.

Given an optimal factoring of $X$ with $k$ factors we can easily solve the original problem: An optimal factoring has $k ≥ 1$ since $X_1 = X$ is one possible factoring. As long as $P ≠ X$, let $p$ be any prime factor of $X / P$, find an $X_i$ that has the factor $p$ raised to the highest power (which may be 0), and multiply $X_i$ by $p$. Eventually this gives us an exact optimal factoring with the same $k$. Since an exact optimal factoring of $X$ is also an optimal factoring, it cannot have more than $k$ factors; and we found an exact optimal factoring that has exactly $k$ factors, therefore the exact optimal factoring has indeed $k$ factors, and we found it.

We may assume that $X$ has the form $X = 2^{n_1} \cdot 3^{n_2} \cdot 5^{n_3} ...$. If not, then we factor $X$ into a product of prime powers, arrange the product by sorting the exponents in non-descending order, replace the primes with 2, 3, 5, 7 and so on, solve the problem, then replace the primes back with the original ones. For example if $X = 3 \cdot 7^3$ then we find an optimal factoring of $X = 2^3 \cdot 3$ with the solution [2, 3, 4], and replace it with [7, 2, 49].

So we just solve the problem of finding an optimal factoring of $X$. Next we add a restriction to the solution that we want to find: We want an optimal factoring of $X$ with the property that if $X_i$ is a factor, and $2 ≤ Y < X_i$ divides $X_i$, then Y is also one of the factors: If this is not the case, then we replace $X_i$ with Y and get another optimal factoring with smaller numbers, and we can repeat this until no such Y exists.

We call such a factoring a restricted optimal factoring. There is always a restricted optimal factoring with the same number $k$ of factors, and it should be easier to find because the search space is smaller. This means that for example a restricted optimal factoring containing a factor $a \cdot p$ with $a ≥ 2$ and p prime, then it must also contain factors a and p, therefore $X$ is divisible by $p^2$.

If $X$ has a factor $p$ but not $p^2$ for some prime $p$, then one of the factors must therefore be $X_i$ = p. So in this case we can solve our problem by finding a restricted optimal covering for $X / p$ and adding a factor $p$. This will simplify many problems; as a special case, the optimal factoring for a square free number is the set of its prime factors.

If a restricted optimal covering has a factor $X_i = p^n$ for some prime p, $n ≥ 2$, then it has also factors $p^j$ for $1 ≤ j < n$. $X$ is therefore divisible by $p^{t(n)}$, where t(n) is the n-th triangular number (number in the sequence 1, 3, 6, 10, 15, 21, ...)

If $X$ has a factor $X_i = a \cdot p^n$ for some prime $p$, $a ≥ 2$, and $n ≥ 1$, then it also has factors $a \cdot p^j$ for $0 ≤ j < n$, and factors $p^j$ for $1 ≤ j ≤ n$, so $X$ is $X$ is divisible by $a^{n+1}$ and by $p^{2 t(n)}$.

With the example number $𝑋=2^{30} \cdot 3^6 \cdot 5^3 \cdot 7$ (more to follow ...)

$\endgroup$
-1
$\begingroup$

It does indeed have to do with divisors and factorisation. Let the factorisation be $N=p_1^{a_1} p_2^{a_2}\cdots p_k^{a_k}$ with $a_i \geq 1,$ and $p_1<p_2<\cdots<p_k$ be the distinct primes dividing $N.$

Form the list of all prime powers dividing $N$ so that for example $p_1$ is represented as $p_1,p_1^2,\ldots,p_1^{a_1}$ in this list. Sort the list from small to large entries and denote the list by $[x_1,x_2,\ldots,x_{a_1+a_2+\cdots+a_v}].$

By a greedy heuristic you should first divide by the smallest number in this list, remove that entry, and then apply the same algorithm to the remaining list and to $N/a_1.$ Then repeat. Some powers won't divide evenly, ignore them, they've been represented as parts of lower powers.

Example Code from Online Magma Calculator at here:

enter image description here

Output:

enter image description here

$\endgroup$
2
  • $\begingroup$ Thank you for your answer, but it looks like your solution still only finds a product of 14 numbers for $N=684913065984000$ , while as I showed in the problem statement $N$ can be written as a product of $15$ distinct numbers. $\endgroup$
    – motoras
    Commented Apr 9, 2022 at 18:52
  • $\begingroup$ In that case it seems the greedy heuristic may need to be modified. $\endgroup$
    – kodlu
    Commented Apr 9, 2022 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.