I'm trying to solve the following question https://open.kattis.com/problems/listgame2 and I am successfully able to generate all the prime factors of a given number but the problem demands that I need to get a list of unique numbers only.
for example - 1099511627776 = 2^40 but since the number 2 is repeated 40 times, the problem is to simplify 2^40 as 2*4*8* .... == 1099511627776 without repeating any integers to arrive that the product.
I found a similar question on Stackoverflow at Algorithm: Factorize a integer X to get as many distinct positive integers(Y1...Yk) as possible so that (Y1+1)(Y2+1)...(Yk+1) = X but there was no logic provided
A counter example from the above link is the number 10307264 = 2^6 * 11^5 this should possibly reduce to 2 * 4 * 11* 22 * 44 * 121 == 10307264
I don't seek a solution but rather a discussion towards a concrete logic to find the optimal solution. Thanks in advance!
Stop thinking of these as unique integers; think of them as tuples of powers. Your first example is 2^40; you have to partition 40 into as many distinct integers as possible. For this simple example, a greedy approach makes it trivial: you grab 1, then 2, ... until the remaining number isn't large enough to separate without stepping on a previous number. This is a simple application of triangle numbers:
`1 2 3 4 5 6 7 8`, and a remainder of 4
... that you can distribute among the upper numbers as you see fit (without duplication); you will get 8 distinct integers for your score. For instance: 1 2 3 4 6 7 8 9 are the powers of 2 you might want.
For a complex number, such as 2^6 11^5, you now have a pair (6, 5) to partition into distinct pairs. Now, you can have 0 components, so long as no pair is entirely 0. Your given 5-opint solution is sub-optimal; the linked question gives 6, represented by the power pairs
1 0
2 0
0 1
0 2
1 1
2 1
Giving us six 2s and 5 11s.
This is where a multi-dimansional solution comes in handy. The given solution is formed from the product of available small factors (again greedy) for 2 and 11:
{0 1 2} x {0 1 2}
... taking the least-cost choice at each juncture. Imagine this as a lattice in 2D space. Starting near the origin, we work outward through the lattice, consuming the least-cost point each time. "Least-cost" is the choice the leaves us the greatest range of options. I'll number the axes and label the choices in order:
11 \ 2 0 1 2
0 A C
1 B E F
2 D
There are various ways to work at "least-cost": fewest factors consumed (i.e. lowest tuple sum), greatest remaining product of powers (i.e. we take 2^1 first, because that leaves 5x5 factors, rather than 4x6 if we'd taken 11^1).
If recursion appeals to you, then you can write a simple recursive routine that iterates through the inner shell of the N-dim space, considering all of the tuples adjacent to the points already consumed (including the disqualified origin). Each choice leaves a separable, independent sub-problem. BTW, it's trivial to prove that this "inner shell" is sufficient to find the optimal solution.
For instance, in the above (6 5) examples, the two inner-shell points to try are (1 0) and (0 1), leaving sub-problems of (5 5) and (6 4). It's easy to see that the solution paths will converge: I strongly suggest that, if you attack this solution, that you memoize your results (dynamic programming) to avoid duplication.
Does that get you moving?