Re: Challenge: Maximum Partition Product Message #20 Posted by Kiyoshi Akima on 31 Aug 2009, 12:08 p.m., in response to message #1 by Kiyoshi Akima
Nice to see that no one tried to generate all the possible partitions for a given N. For those who don't see where the scheme comes from, here's a brief analysis leading to my initial result.
First, there is no point in putting any 1s in the partition, since 1+M > 1*M. Because of that, the only partitions for 2 and 3 are the trivial ones. For 4, {2, 2} and {4} produce the same result (2*2=4). For the rest of this analysis, I'll always use {2, 2}.
For 5, {2, 3} is better than {5}.
For 6, {3, 3} is better than {2, 2, 2} or {6}
For 7, {3, 2, 2} is the best.
Define Q=floor(N/3) and R=N mod 3. This splits the problem into three cases.
If R=0, then MPP(N) = 3^Q
If R=1, then MPP(N) = 4 * 3^(Q1) = 3^Q * 4/3
If R=2, then MPP(N) = 2 * 3^Q
The formula seems to require getting as many 3s as possible, only throwing in 2s when necessary. Not very surprising, considering that 3 is the integer closest to e, and 2 the next closest.
Given the 3^Q term in each, the formula can be written as MPP(N) = F(R) * 3^Q, where F(0) = 1, F(1) = 4/3, F(2) = 2. There's an infinite number of functions F(R) which will produce the desired result, including a quadratic, but is there something better?
Consider G(R) = 1/F(R) so that MPP(N) = 3^Q / G(R). Then G(0) = 1, G(1) = 3/4, G(2) = 1/2. Note something about G? It's linear! G(R) = 1  R/4.
Thus, MPP(N) = 3^Q / (1  R/4), or written out in full, MPP(N) = 3^(floor(N/3)) / (1  (N mod 3)/4)
In RPL this led me to the 13step program
<<
3. DUP2 / IP ^ 1. ROT 3. MOD 4. /  /
>>
Translated to the 41C, this led me to the 14step program
001 3
002 RCL Y
003 3
004 /
005 INT
006 Y^X
007 1
008 R^
009 3
010 MOD
011 4
012 /
013 
014 /
Okay, I know I'm cheating a little, since the "RCL Y" is not available on most RPN machines. But then, "Y^X", "R^" and "MOD" aren't universally available, either. So, continuing to cheat, if the PPC ROM is available the program comes down to 11 steps:
001 3
002 XEQ 'QR
003 3
004 RCL Z
005 Y^X
006 X<>Y
007 4
008 /
009 1
010 +
011 /
QR is a routine that provides the integer quotient and remainder in one shot.
On a TI86 it's a oneliner:
:Prompt N:3^int (N/3)/(1.25(mod N,3
The oneliner on a 71B should be very similar.
This was as far as I'd gotten when I initially posted this little challenge. But after reading some of the early responses, I was inspired to do a little more.
Continuing to cheat, let's take another look at the problem. This time, define Q=floor((N2)/3) and R=(N2) mod 3. Then:
If R=0, then MPP(N) = 2 * 3^Q
If R=1, then MPP(N) = 3 * 3^Q
If R=2, then MPP(N) = 4 * 3^Q
This leads to MPP(N) = 3^(floor((N2)/3)) * (2 + ((n2) mod 3))
This led me to a 13step 41C program
001 2
002 
003 RCL X
004 3
005 STO T
006 MOD
007 ST Y
008 2
009 +
010 X<> T
011 /
012 Y^X
013 *
and, again using the PPC ROM, this time a 10step program
001 2
002 
003 3
004 XEQ 'QR
005 2
006 +
007 3
008 RCL Z
009 Y^X
010 *
This is still 13 steps in RPL
<<
2.  3. DUP2 / IP ^ SWAP 3. MOD 2. + *
>>
but it has the advantage of being easily convertible to work in exact mode for 1 < n <= 30001. The limitation seems to be that ^ will not accept an argument >9999 in exact mode.
<<
2  3 DUP2 / IP >NUM R>I ^ SWAP 3 MOD 2 + *
>>
There are ways around the limitation, using the relationship 3^(a+b) = 3^a * 3^b, but I think this is enough for now.
