 Challenge: Maximum Partition Product - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: Challenge: Maximum Partition Product (/thread-155144.html) Challenge: Maximum Partition Product - Kiyoshi Akima - 08-26-2009 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. Re: Challenge: Maximum Partition Product - Mark Edmonds - 08-26-2009 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 Re: Challenge: Maximum Partition Product - Steve Perkins - 08-26-2009 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 ``` Re: Challenge: Maximum Partition Product - Mark Edmonds - 08-26-2009 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 Re: Challenge: Maximum Partition Product - Mark Edmonds - 08-26-2009 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 Re: Challenge: Maximum Partition Product - PeterP - 08-26-2009 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 ``` Re: Challenge: Maximum Partition Product - Gerson W. Barbosa - 08-26-2009 Here is mine, but I needed 50% more steps on the 33s: ```X0001 LBL X X0002 4 X0003 x<>y X0004 x 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. Re: Challenge: Maximum Partition Product - PeterP - 08-26-2009 ...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!... Re: Challenge: Maximum Partition Product - Egan Ford - 08-26-2009 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. Re: Challenge: Maximum Partition Product - Gerson W. Barbosa - 08-26-2009 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 ``` Re: Challenge: Maximum Partition Product - Kiyoshi Akima - 08-26-2009 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. Re: Challenge: Maximum Partition Product - Mark Edmonds - 08-26-2009 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. Re: Challenge: Maximum Partition Product - PeterP - 08-26-2009 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. Re: Challenge: Maximum Partition Product - Egan Ford - 08-27-2009 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. Re: Challenge: Maximum Partition Product - Steve Perkins - 08-27-2009 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. Re: Challenge: Maximum Partition Product - Steve Perkins - 08-27-2009 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 ``` Re: Challenge: Maximum Partition Product - Mark Edmonds - 08-27-2009 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 Re: Challenge: Maximum Partition Product - Mark Edmonds - 08-27-2009 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 Re: Challenge: Maximum Partition Product - Kiyoshi Akima - 08-31-2009 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. Re: Challenge: Maximum Partition Product - Steve Perkins - 08-31-2009 Nicely done! And thanks for the challenge. Re: Challenge: Maximum Partition Product - PeterP - 08-31-2009 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