Challenge: Maximum Partition Product



#16

For a positive integer N>1, what is the maximum product of a partition into the positive integers?

An example will make it clearer. {2, 2, 2, 2}, {2, 6}, and {3, 5} are three of the many possible partitions of 8 into one or more (not necessarily distinct) positive integers. That is, 2+2+2+2 = 2+6 = 3+5 = 8.

Now consider the product of the partition elements. 2*2*2*2=16, 2*6=12, 3*5=15. What is the maximum possible? (Hint: it's larger than 16.)

The challenge is to write a program on your favorite programmable handheld HP that, given N>1, produces the maximum partition product MPP(N).

Next week I'll present my (not necessarily optimal) solution, which is less than MPP(8) steps in length.


#17

Quote:
...which is less than MPP(8) steps in length.

I have a formula (or rule) for calculating this but I can't code it in anything like the number of steps you are using! That's assuming my value for MPP(8) is what I think it is. My first draft came in at ~32 steps!!! Which calc have you used to get it less than MPP(8) steps? Very puzzled!

Mark


#18

Well, I am going to submit this code so I hope my method of calculation is correct. I am also going to consider this optimised because I don't think this particular method can be reduced any further (although using MOD would save a couple of steps but I assumed most HP don't have MOD).

LBL A
ENTER
ENTER
3
/
IP
STO 1
3
*
-
STO 2
3
RCL 1
1
-
Y^X
2
ENTER
2
RCL 2
Y^X
+
*
RTN


Does it work OK?

Mark


#19

I enjoyed deciphering your formula. Very clever.

Allow me to optimize it using MOD and stack operations (on a 41C).

LBL P
RCL X
3
MOD
3
STO- Z
STO/ Z
RCL Z
INT
Y^X
2
ENTER
R^
Y^X
+
*
END

This is close to the 14 step challenge by Kiyoshi Akima! You can do a lot when you combine ideas, right?

Edited: 27 Aug 2009, 5:25 p.m.


#20

Thanks Steve :) Actually, I was going to abandon that program as everyone else was coming in with significantly shorter versions. I've got a new one to post which I'll do after Egan's further down as it is more relevant there.

I was having trouble with your optimised version due to variables appearing without being init (I'm not too familiar with the 41 ins-and-outs) until I realised you must be referencing the stack directly, hence use of X, Z, T. What a great feature! I think you can do this in the 42s but was the 41 the first calc to allow direct stack variable manipulation?

Mark

#21

One more version. 14 steps, not including initial LBL and END.

LBL P
2
RCL Y
3
STO- T
STO/ T
MOD
Y^X
2
+
3
RCL Z
INT
Y^X
*
END
#22

Here's my attempt. It's 17 steps on a calcultor with LBL and RTN. Only 13 steps on my HP-12C!

It gives MPP(8) = 18

LBL A
1
STO 01
CLX
4
X<>Y
LBL 01
X<=Y?
GTO 02
3
STO* 01
-
GTO 01
LBL 02
RCL 01
*
RTN

#23

Crikey Steve! Nice solution! Somewhat shorter than my version :( :( :(

So trying to salvage something from the rubble, I can justify my code's bloat because it has one advantage - it takes the same amount of time for all numbers. So as near as makes no difference, calculating MPP(8) should take the same time as calculating MPP(500). For small numbers, your solution wins hands-down but for large, mine will pull ahead.

Mark


#24

For the record, my current best attempt is a 14-step constant-time program on the 41C, not counting the initial LBL or the final RTN/END. Good thing I denied optimality, since a shorter version has already been posted. But like Mark's, mine is a constant-time program (more or less).

Getting an EXACT answer for MPP(500) will take a little more effort, since that's an eighty-digit number. But the approximation requires perceptibly no more time than MPP(5).

The 14-step 41 program (note the symmetry) was a straighforward translation of a 13-step RPL program. And I suspect Peter is right on one point --- it should be a one-liner on the 71B.


#25

Quote:
Getting an EXACT answer for MPP(500) will take a little more effort, since that's an eighty-digit number. But the approximation requires perceptibly no more time than MPP(5).

I converted my program to RPL and MPP(500) is:

31,853,582,177,039,572,006,128,297,181,359,762,867,862,759,052,962,792,242,225,097,317,150,555,373,883,058.0 (or 2*3^166)

Hopefully, someone somewhere in the universe will find that number useful.

Mark

Edited: 26 Aug 2009, 7:02 p.m.

#26

10 Input "N=";N @ Y=Floor(N/3)-Mod(Mod(N,3),2) @ Disp 3^Y*Max(1,N-3*Y)



gives (at least I hope) correct results. Here is how I came up with it. From reading the posts I saw that at least one had come up with a formula rather than my (wrong)iterative approach. Hmmm.



From my original thinking I knew that if you split N into 2 numbers only, you want them to be as close to the mean as possible. Secondly, more numbers is generally (but not always as I learned) better as exponentiation is more powerful than multiplication.



Given that there a)is a formula, b)we want the numbers to be as close to each other as possible or - ideally - identical, I tried to set up p = (N/X)^X and then find the best x, with N/x not necessarily integer.



A little bit of differentiation leads to x=N/e as the only maximum. So in integer world we would want the closest integer to N/x = N/(N/e) = e. Which is 3. This has the - at least for me - astonishing result that independent of N we 'love' lots of 3's! Even though the pgm seems to yield the correct result, this is still quite puzzling to me, so much so, that I don't quite trust my logic.



Anyway, following this nevertheless we now have as the first parts of the partition int(n/3) 3's.



This then leaves us with a remainder r of 0, 1 or 2 so that the sum of the parts gives N. If that r is 0 or 2 we are done - p=3^(N/3) or 3^int(N/3)*2. If we have 1 we actually want to 'steal' one 3, add it to the 1 to get to 4 as the maximum multiplication we can get from 4 is 4 and not 3*1).



This is then easily implemented in the above 1-liner for the 71B which now has the advantage that even for large N it pretty much gives the number instantaneously.



Cheers

Peter

Edited: 26 Aug 2009, 11:11 p.m.


#27

My 71B FORTH version (16 words/steps < 18):

: MPP 1 SWAP DUP BEGIN 4 > WHILE SWAP 3 * SWAP 3 - DUP REPEAT * ;

Mark mentioned MPP(500), so I thought I'd give that a try, however it looks like I am a bit late (the 71B does not have arbitrary precision integers like the 50g, so a bit of work was needed).

Output:

MPP(0100)=7412080755407364
MPP(0200)=61806308765265224723841283607058
MPP(0300)=515377520732011331036461129765621272702107522001
MPP(0400)=3820019803187300947572762807097656047679740555897372519347
415364
MPP(0500)=31853582177039572006128297181359762837862759052962792242
225097317150555373883058
MPP(0600)=265613988875874769338781322035779626829233452653394495974574
961739092490901302182994384699044001
MPP(0700)=1968752335313857038570476961751782907911826277718092885242
769438669375537688438188475685163323831238842115423364
MPP(0800)=16416620208836038650073858940285420575183017842785674138
532546555538400105430156551760426933562036665306914077007743
925536159058
MPP(0900)=136891479058588375991326027382088315966463695625337436471480
190078368997177499076593800206155688941388250484440597994042
813512732765695774566001
MPP(1000)=1014650697509413079627234489686710374303861808496103820156
013382714388841919074932817392194199171363410580468761266602
680002445025736755375715839382921059431364

Code (unoptimized, could use better algorithm):

: MYMPP ;
65 6 / CONSTANT MAXL
200 CONSTANT N
1000000 CONSTANT OBASE
N 6 / 1 + CONSTANT M
5 CONSTANT S
M S * CONSTANT E
CREATE A E NALLOT
CREATE B E NALLOT
CREATE C E NALLOT
VARIABLE D
VARIABLE F
VARIABLE G
VARIABLE H
: MPZERO DUP E + SWAP DO 0 I ! S +LOOP ;
: MPSET SWAP DUP MPZERO E + S - ! ;
: MPCOPY 2DUP - SWAP DUP E + SWAP DO I @ OVER I + ! S +LOOP 2DROP ;
: UD+ ROT + ROT ROT + ;
: 04D. <# # # # # #> TYPE ;
: 06D. <# # # # # # # #> TYPE ;
: 6D. <# #S #> TYPE ;
: MPDIV
D ! DUP DUP
M 0 DO DUP @ 0= IF S + ELSE LEAVE THEN LOOP
DUP E - ROT = IF DROP 0 ELSE
0 SWAP ROT E + SWAP DO I @ SWAP D @ UM/MOD I ! S +LOOP
DROP 1
THEN
;
: MPMULT
D ! DUP DUP E + S - M 0 DO DUP @ 0= IF S - ELSE LEAVE THEN LOOP > IF DROP ELSE
0 SWAP DUP E + S - DO I @ D @ UM* ROT 0 D+ SWAP I ! S NEGATE +LOOP DROP THEN
;
: MPSUB
2DUP - D !
0 SWAP DUP E + S - DO I D @ + DUP H ! @ 0 I @ 0 D- ROT 0 UD+ H @ !
S NEGATE +LOOP
2DROP
;
: MPPRINT
G ! N 0 DO
B G @ MPCOPY G @ OBASE MPDIV 0 = IF DROP LEAVE THEN
C G @ MPCOPY C OBASE MPMULT B C MPSUB B E + S - @
6 +LOOP
0 6D. DEPTH 1 + 1 DO 0 06D. I 1 + MAXL MOD 0= IF CR ." " THEN LOOP
;
: MPP DUP G ! 1 MPSET DUP BEGIN 4 > WHILE G @ 3 MPMULT 3 - DUP REPEAT G @ SWAP MPMULT ;
: MPPTABLE
1100 100 DO ." MPP(" I 0 04D. ." )=" I A MPP A MPPRINT CR 100 +LOOP
;
MPPTABLE
Update. Faster MPP. Using 312 when possible. Beyond this simple ~7x speed-up I'd need to start looking at multi-multi multiplication vs. single-multi.
: MPP 1 H ! DUP G ! 1 MPSET DUP
BEGIN 4 > WHILE
H @ 3 * DUP 531441 = IF G @ SWAP MPMULT 1 H ! ELSE H ! THEN 3 - DUP
REPEAT
DUP 1 <> IF G @ SWAP MPMULT THEN
H @ DUP 1 <> IF G @ SWAP MPMULT THEN
;


Edited: 27 Aug 2009, 4:06 a.m.


#28

This is the right spot to add my RPL version which is based on my original formula. I haven't optimised it, I just did a near 1:1 conversion.

Benefits of this version - significantly faster than the looping versions for very large MMP(n) and the *exact* answer for all values of n upto somewhere in the region of just above 30,000. MPP(30,000) has 4770 digits so I wont type them all in!!

\<<
DUP 3 MOD 2 SWAP ^ 2 + R\->I SWAP 3 / IP 1 - R\->I 3 SWAP ^ *
\>>

67.5 bytes

Requirements: any RPL+CAS calc (and a nice example of how powerful that combination is).

Mark

#29

On the 15C you can change:

1
STO 01
CLX
to
MATRIX 1
and,
RCL 01
*
with
RCLx 01

My 15C version of MPP(n)=3*MPP(n-3) for n > 4:

001 - 42,16, 1  MATRIX 1   (aka 1 STO 0 STO 1)   
002 - 4 4
003 - 34 x<>y
004 - 42,21, 1 LBL 1
005 - 43 10 x<=y
006 - 22 2 GTO 2
007 - 3 3
008 - 44,20, 1 STOx 1
009 - 30 -
010 - 22 1 GTO 1
011 - 42,21, 2 LBL 2
012 - 45,20, 1 RCLx 1

Just enter the number, R/S. Probably best CLEAR PRGM first.

Edited: 26 Aug 2009, 5:29 p.m.

#30

Hopefully Valentin is not around as he would have done it in 1-2 lines max. Somehow I can't quite remember the syntax for DEF FN. Below is a 71b program which I think works but due to the use of SUB instead of DEF FN takes quite long for larger X. And technically it does not deliver the right result for 2 and 3, which should be 1 and 2 ( i think).

Cheers

Peter

10 Input "N:=?";N @ P=0 @ Call M1((N),P) @ Disp P
20 SUB M1(N,P) @ IF N < 5 Then P=N @ Goto 40
30 Call M1((ceil(n/2)),p1) @ Call M1((floor(n/2)),p2) @ p=p1*p2
40 End Sub


#31

...end he would have gotten it right. While scanning the other posts now I saw that the solution for 8 is 18 (and not 16 as my thing gets). Firstly, read the question correctly, Peter!...


#32

I first read:

which is less than MPP(8) steps in length

as:

which is less than 8 steps in length

I was scratching my head for awhile.

#33

Here is mine, but I needed 50% more steps on the 33s:

X0001 LBL X
X0002 4
X0003 x<>y
X0004 x<y?
X0005 RTN
X0006 1,000
X0007 /
X0008 +
X0009 STO C
X0010 3
X0011 STO A
X0012 1
X0013 STO B
Y0001 LBL Y
Y0002 RCL C
Y0003 IP
Y0004 3
Y0005 RMDR
Y0006 x=0?
Y0007 1.5
Y0008 STOx B
Y0009 RCL B
Y0010 STO+ A
Y0011 ISG C
Y0012 GTO Y
Y0013 RCL A
Y0014 RTN

X: LN=87 CK=7F52
y: LN=66 CK=7276


Edited: 26 Aug 2009, 4:40 p.m.


#34

Slightly shorter and way faster, now using a reference and only the stack:

Z0001 LBL 
Z0002 ENTER
Z0003 ENTER
Z0004 4
Z0005 -
Z0006 ENTER
Z0007 ENTER
Z0008 3
Z0009 INT/
Z0010 2
Z0011 *
Z0012 -
Z0013 3
Z0014 x<>y
Z0015 y^x
Z0016 x<>y
Z0017 +/-
Z0018 3
Z0019 RMDR
Z0020 2
Z0021 x<>y
Z0022 y^x
Z0023 *
Z0024 RTN

LN=144 CK=4D4C

#35

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.

#36

Nicely done!

And thanks for the challenge.

#37

Thanks so much for this little challenge and great explanations! I'm very impressed with your knowledge of a wide array of programming languages for the HPs!

From your explanation it would also seem that surprisingly my thinking for the one-liner for the 71b was correct...

Lastly, if you use the Sandbox Rom from Angel Martin instead of the PPC for your very neat trick(!), you can cut th HP41C version down to 10 steps (and a tiny speed improvement)...

001 3
002 QREM
003 LastX
004 RCL Z
005 Y^X
006 X<>Y
007 -4
008 /
009 IncX
010 /

Thanks again

Peter


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP Prime - Cross product suggestion bluesun08 13 2,172 11-08-2013, 01:49 AM
Last Post: Patrice
  Product Series and Limit Expressions on the 50G Matt Agajanian 13 1,889 09-03-2013, 02:02 PM
Last Post: Simone Cerica
  Maximum number of program steps in HP-42S, 33S, and 35S? Walter B 3 832 12-18-2012, 03:44 PM
Last Post: Eric Smith
  A new product of Spee Dee Sign d;-) Walter B 180 17,670 12-01-2012, 03:29 PM
Last Post: Richard Ottosen (Denver, CO, USA)
  30b feedback on HP product review page bill platt 15 2,170 03-10-2012, 04:08 PM
Last Post: Mark Scheuern
  WP 34S: missing vector cross product fhub 15 1,898 07-24-2011, 03:54 PM
Last Post: fhub
  June's over - No new calcs :) - Interesting TI product John Stark 5 882 07-07-2011, 07:09 PM
Last Post: John Stark
  Hp15c (limited edition) june? and a new product? Miguel Saiz 1 513 05-07-2011, 07:31 PM
Last Post: miguel saiz
  Product suggestion for HP... BruceH 8 1,211 09-16-2007, 08:35 AM
Last Post: Jerome Fryer (New Zealand)
  A new product introduction Giancarlo (Italy) 7 1,031 08-03-2007, 01:22 PM
Last Post: Vincze

Forum Jump: