patternMinor
Factor a number in the longest possible product of distinct numbers
Viewed 0 times
distinctnumberthenumbersproductpossiblefactorlongest
Problem
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
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
Solution
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.
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?
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.
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?
Context
StackExchange Computer Science Q#150485, answer score: 2
Revisions (0)
No revisions yet.