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^(Q-1) = 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 13-step program

<<

3. DUP2 / IP ^ 1. ROT 3. MOD 4. / - /

>>

Translated to the 41C, this led me to the 14-step 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 TI-86 it's a one-liner:

:Prompt N:3^int (N/3)/(1-.25(mod N,3

The one-liner 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((N-2)/3) and R=(N-2) 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((N-2)/3)) * (2 + ((n-2) mod 3))

This led me to a 13-step 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 10-step 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.