Member Avatar for catcit

Here is a problem in my hand that I need so solve it. It sounds like this: Given a number (between 4 and 30000) x, which is the greatest number that can be written as a product made from numbers that have the sum x.

Example:
For x = 7 the result is 12.
Explanation:
12 = 2 x 3 x 3
7 = 2 + 2 + 3

I do not want to abridge the path for solving the problem and I do not want complete code for this problem. I only need some directions and documentation about the method that I could use in order to solve it.

Edited by catcit because: n/a
  • 3 Contributors
  • 4 Replies
  • 138 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by cam875

Dani AI

Generated

The typo that pointed out aside, the heuristic from is the right idea. A short justification and a few practical notes will make that method robust and easy to implement.

Proof sketch (why only 2s and 3s are needed): if any summand k >= 4 appears, replacing k by 2 and k-2 does not reduce the product (and strictly increases it for k >= 5), because 2(k-2) >= k. Also any occurrence of a lone 1 can be removed by turning a 3+1 into 2+2 (since 22 > 3*1). From these two facts an optimal partition can contain only 2s and 3s, with at most two 2s in the final multiset.

Algorithmic outline (what to implement): take as many 3s as possible and fix the small remainder so no 1 remains. The final answer can be represented compactly by the counts of 3s and 2s (this is usually all that is needed). To produce the numeric product, raise 3 and 2 to those counts and multiply.

Pseudocode (high-level):

q = x // 3
r = x % 3
if r == 1:
  q = q - 1
  product = 3^q * 2^2
elif r == 2:
  product = 3^q * 2
else:
  product = 3^q

Practical cautions: for x up to 30000 the numeric result has only a few thousand decimal digits (use big-integer libraries: Python's int, Java BigInteger, or boost::multiprecision). Use fast exponentiation (or language built-ins like pow) and modular exponentiation if a modulus is required. If you want extra confidence implement a small dynamic-programming check for low x to validate the greedy rule before scaling up.

Recommended Answers

All 4 Replies

Member Avatar for Ancient Dragon

2x3x3 = 18, not 12. I suppose you meant 2x2x3??

Member Avatar for catcit

2x3x3 = 18, not 12. I suppose you meant 2x2x3??

Yes, my bad. It`s 2 x 2 x 3.

Member Avatar for cam875

found a major mistake in my previous method so nvm.

Edited by cam875 because: n/a
Member Avatar for cam875

Ok I think i figured it out now but I could still be wrong anyways here it goes.

Any number > 3 can be represented as the sum of 2's and 3's and combinations of these seem to yield the largest products when the terms are all multiplied together. (could be wrong on that)

So you take the number x and start with the 3's and find out how many times you can subtract a 3. If you arrive with remainder 1 it means you have to go back and instead of taking off of a 3 with a 1 leftover take off 2 2's which is better because 2*2 > 3*1.

If you get a remainder of 1 then the answer is 3^((quotient of x/3)-1) * 2^2
If you get a remainder of 0 then the answer is 3^(x/3)
If youi get a remainder of 2 when x/3 then the answer is the 3^(quotient of x/3) * 2

heres some examples
x = 21
21/3 = 7 rem 0 therefore the answer will be 3^7

x = 22
22/3 = 7 rem 1 therefore we go one back to 6 so we have 3^6 * 2^2

x = 23
23/3 = 7 rem 2 therefore the answer is 3^7 *2

now lets run back to the original x = 7
x = 7
7/3 = 2 rem 1 therefore the answer is 3^1 * 2^2 according to our above rules which is exactly 12. I don't know for sure if this is all correct but it seems to be so correct me if the theory is wrong.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.