# Project Euler #183: Maximum product of parts

# Project Euler #183: Maximum product of parts

saratherv45 + 0 comments how to calculate d(n)

stanleychen510 + 0 comments First Test is correct, but the rest are wrong. What should I be looking out for?

sivasundharam121 + 1 comment Am not able to understand the qus when ans is non-terminatin decimal.Please help me to understand.

mvanwoerkom + 0 comments A rational number q/r has a terminating decimal fraction if the equation

q/r = q'/10^k

holds for some integer q' and some natural number k. If no such solution is possible the fraction will not terminate.

It helped me to look at the examples for M(11)=(11/4)^4 and M(8)=(8/3)^3 and test my assumptions why the corresponding equation had a solution (q', k) or not.

Aniket_Gaikwad + 3 comments My code is timing out for every case except the test case. Any hints??

JitendraMishra + 1 comment Same problem i also facing ??

SJ151 + 0 comments same here

mohitkumar17 + 0 comments HOW DID U CHECK RECURRING AND NON RECURRING CONDITION PLZZZZ HELP

mvanwoerkom + 1 comment I got stuck at the first test case too until one particular optimization made the difference and tackled the remaining cases.

tomasz_gawel + 2 comments Some hint? ;)

mvanwoerkom + 0 comments ashuwp + 0 comments Use an array to cache the value(s) and reuse.

kumsawakoo + 4 comments Does anybody doing this got the required 2438 for n=100 given in the test. I keep on getting 3282 following all the steps given in the vignette to the letter ... surely I am missing something or the answer given in the test is maybe somehow not right .. unlikely .. anyone care to share their expeience.

mvanwoerkom + 1 comment I get S(100)=2438. Check your code for K(N) and D(N) calculation.

mittal_ankur15 + 2 comments [deleted]mittal_ankur15 + 0 comments I used for (double j=1;j<=N;j++) { BigDecimal num = new BigDecimal(Math.pow(N, j)); BigDecimal din = new BigDecimal(Math.pow(j, j)); BigDecimal cp = num.divide(din,MathContext.DECIMAL128);

`if(cp.compareTo(max) == 1) { max = cp; k=j; } }`

mvanwoerkom + 1 comment You have to find a K which maximizes

P(K) = (N/K)^K

You can optimize over the real numbers and then choose the best whole number.

I would suggest to plot P(K) and the K-choice of your formula for some N and K values, among them the examples, to get it right.

mittal_ankur15 + 1 comment I am able to get the value of k for maximize value of P by using

for (double j=1;j<=N;j++) { BigDecimal num = new BigDecimal(Math.pow(N, j)); BigDecimal din = new BigDecimal(Math.pow(j, j)); BigDecimal cp = num.divide(din,MathContext.DECIMAL128); if(cp.compareTo(max) == 1) { max = cp; k=j; } } but still I am not getting the D(N) = 2438 for n=100. I checked for smaller numbers like for n=10 ,D(N)= -15 for n=20 ,D(N)= 10 for n=30 ,D(N)= -29 for n=40 ,D(N)= 326 for n=50, D(N) = 781

Can you please tell me, whether this is correct.

mvanwoerkom + 0 comments The 2438 is for the sum:

so

mittal_ankur15 + 2 comments I am getting 3816 for n=100 and I do not think that there is any problem in my code. when n=10 then D(N) = -15 when n=20 then D(N) = 10 when n=30 then D(N) = -29 when n=40 then D(N) = 326 when n=50 then D(N) = 781

mittal_ankur15 + 1 comment 5 having Pmax::6.25 and value of k::2.0 SUBTRACT 6 having Pmax::9 and value of k::2.0 SUBTRACT 7 having Pmax::12.70370370370370370370370370370370 and value of k::3.0 Non-terminating: ADD 8 having Pmax::18.96296296296296296296296296296296 and value of k::3.0 Non-terminating: ADD 9 having Pmax::27 and value of k::3.0 SUBTRACT 10 having Pmax::39.0625 and value of k::4.0 SUBTRACT 11 having Pmax::57.19140625 and value of k::4.0 SUBTRACT 12 having Pmax::81 and value of k::4.0 SUBTRACT 13 having Pmax::118.81376 and value of k::5.0 SUBTRACT 14 having Pmax::172.10368 and value of k::5.0 SUBTRACT 15 having Pmax::244.140625 and value of k::6.0 SUBTRACT 16 having Pmax::359.5939643347050754458161865569273 and value of k::6.0 Non-terminating: ADD 17 having Pmax::517.3518732853223593964334705075446 and value of k::6.0 Non-terminating: ADD 18 having Pmax::743.3977727938917579288513168104155 and value of k::7.0 Non-terminating: ADD 19 having Pmax::1085.397774008157436830863719320060 and value of k::7.0 Non-terminating: ADD 20 having Pmax::1554.260068994575875212344710597989 and value of k::7.0 Non-terminating: ADD 21 having Pmax::2254.418096601963043212890625 and value of k::8.0 SUBTRACT 22 having Pmax::3270.8569488525390625 and value of k::8.0 SUBTRACT 23 having Pmax::4667.698459684848785400390625 and value of k::8.0 SUBTRACT 24 having Pmax::6818.967027384036986231773611746177 and value of k::9.0 Non-terminating: ADD 25 having Pmax::9846.400420048512199363828690020573 and value of k::9.0 Non-terminating: ADD 26 having Pmax::14116.7095653376 and value of k::10.0 SUBTRACT 27 having Pmax::20589.1132094649 and value of k::10.0 SUBTRACT 28 having Pmax::29619.6766695424 and value of k::10.0 SUBTRACT 29 having Pmax::42762.04243443046010898533829131475 and value of k::11.0 Non-terminating: ADD 30 having Pmax::62088.94281143023677305637491681485 and value of k::11.0 Non-terminating: ADD 31 having Pmax::89055.16147303798803593904627189362 and value of k::11.0 Non-terminating: ADD 32 having Pmax::129307.8191859491458129877070079275 and value of k::12.0 Non-terminating: ADD 33 having Pmax::187064.9085474610183992231734096541 and value of k::12.0 Non-terminating: ADD 34 having Pmax::267893.6019486020573151184823652992 and value of k::13.0 Non-terminating: ADD 35 having Pmax::390499.9625512558792571451935119355 and value of k::13.0 Non-terminating: ADD 36 having Pmax::563208.1490580361277758196780173392 and value of k::13.0 Non-terminating: ADD 37 having Pmax::811020.1368187556082445931426531305 and value of k::14.0 Non-terminating: ADD 38 having Pmax::1178088.327821863166694568260686230 and value of k::14.0 Non-terminating: ADD 39 having Pmax::1694774.804386968184820854945918287 and value of k::14.0 Non-terminating: ADD 40 having Pmax::2452059.386044665188370487497584519 and value of k::15.0 Non-terminating: ADD 41 having Pmax::3551313.112952973565272808815254594 and value of k::15.0 Non-terminating: ADD 42 having Pmax::5097655.355238390739197631846406351 and value of k::15.0 Non-terminating: ADD 43 having Pmax::7405861.174385538324713706970214844 and value of k::16.0 SUBTRACT 44 having Pmax::10698505.17985694110393524169921875 and value of k::16.0 SUBTRACT 45 having Pmax::15380875.99435302718850706285692680 and value of k::17.0 Non-terminating: ADD 46 having Pmax::22348659.31590190926752988261138576 and value of k::17.0 Non-terminating: ADD 47 having Pmax::32213055.54712426759048615517357762 and value of k::17.0 Non-terminating: ADD 48 having Pmax::46498311.32055068517477392485670214 and value of k::18.0 Non-terminating: ADD 49 having Pmax::67394483.39947783995478235902491358 and value of k::18.0 Non-terminating: ADD 50 having Pmax::96951601.23193151190408604113873045 and value of k::18.0 Non-terminating: ADD 51 having Pmax::140447795.8069758143871497065134976 and value of k::19.0 Non-terminating: ADD 52 having Pmax::203116456.3027184191650592283999599 and value of k::19.0 Non-terminating: ADD 53 having Pmax::291691050.3408271489696717055205807 and value of k::19.0 Non-terminating: ADD 54 having Pmax::423911582.7521620352042008576 and value of k::20.0 SUBTRACT 55 having Pmax::611862556.00892767899461091328 and value of k::20.0 SUBTRACT 56 having Pmax::881745755.4119242589963131237346843 and value of k::21.0 Non-terminating: ADD 57 having Pmax::1278694448.602842730233225871560428 and value of k::21.0 Non-terminating: ADD 58 having Pmax::1842394699.076774612209676282830379 and value of k::21.0 Non-terminating: ADD 59 having Pmax::2663454475.105414595548523719763365 and value of k::22.0 Non-terminating: ADD 60 having Pmax::3855036819.441054420129801827510631 and value of k::22.0 Non-terminating: ADD 61 having Pmax::5545713022.943844173861986667017805 and value of k::22.0 Non-terminating: ADD 62 having Pmax::8040232918.389941362959907515998993 and value of k::23.0 Non-terminating: ADD 63 having Pmax::11616957727.63847744115164564797033 and value of k::23.0 Non-terminating: ADD 64 having Pmax::16720512102.62611801455792936259201 and value of k::24.0 Non-terminating: ADD 65 having Pmax::24257763541.72472754764008127529948 and value of k::24.0 Non-terminating: ADD 66 having Pmax::34993280009.86996181811716875633589 and value of k::24.0 Non-terminating: ADD 67 having Pmax::50509125661.42340276447479379711843 and value of k::25.0 Non-terminating: ADD 68 having Pmax::73151393029.56926024369180623751378 and value of k::25.0 Non-terminating: ADD 69 having Pmax::105372443629.0869011031329131068473 and value of k::25.0 Non-terminating: ADD 70 having Pmax::152490220752.5322132277486915105673 and value of k::26.0 Non-terminating: ADD 71 having Pmax::220500723832.6475302217566860999091 and value of k::26.0 Non-terminating: ADD 72 having Pmax::317203419165.3790005823373185985552 and value of k::26.0 Non-terminating: ADD 73 having Pmax::460145936276.1061363919935069464546 and value of k::27.0 Non-terminating: ADD 74 having Pmax::664407919502.6209835433223245422854 and value of k::27.0 Non-terminating: ADD 75 having Pmax::957834547756.5086793799792667684580 and value of k::28.0 Non-terminating: ADD 76 having Pmax::1387892108150.113851283246156202812 and value of k::28.0 Non-terminating: ADD 77 having Pmax::2001314893064.476903364256904894918 and value of k::28.0 Non-terminating: ADD 78 having Pmax::2892021644287.178523347955042766629 and value of k::29.0 Non-terminating: ADD 79 having Pmax::4184501311910.153228135000786864342 and value of k::29.0 Non-terminating: ADD 80 having Pmax::6026535007799.182025048818352757106 and value of k::29.0 Non-terminating: ADD 81 having Pmax::8727963568087.712095913917824662272 and value of k::30.0 Non-terminating: ADD 82 having Pmax::12611824826231.74093462942134903558 and value of k::30.0 Non-terminating: ADD 83 having Pmax::18163868738160.24860858590692300635 and value of k::31.0 Non-terminating: ADD 84 having Pmax::26329666550208.35926334105928260864 and value of k::31.0 Non-terminating: ADD 85 having Pmax::37999176796119.77916872922467529388 and value of k::31.0 Non-terminating: ADD 86 having Pmax::54846779734271.1484375 and value of k::32.0 SUBTRACT 87 having Pmax::79399319002919.421875 and value of k::32.0 SUBTRACT 88 having Pmax::114458013083425.796875 and value of k::32.0 SUBTRACT 89 having Pmax::165542764438607.7289453662789129811 and value of k::33.0 Non-terminating: ADD 90 having Pmax::239355160618233.5381262271885288333 and value of k::33.0 Non-terminating: ADD 91 having Pmax::344671941600606.5093630021548265897 and value of k::33.0 Non-terminating: ADD 92 having Pmax::499462573218249.2639026232189196009 and value of k::34.0 Non-terminating: ADD 93 having Pmax::721335110004338.0963580081492735729 and value of k::34.0 Non-terminating: ADD 94 having Pmax::1040143653947418.482867968545188365 and value of k::35.0 Non-terminating: ADD 95 having Pmax::1506415004749622.462560450064793850 and value of k::35.0 Non-terminating: ADD 96 having Pmax::2173259587002892.913020493387982450 and value of k::35.0 Non-terminating: ADD 97 having Pmax::3139730746719680.018764342772556247 and value of k::36.0 Non-terminating: ADD 98 having Pmax::4542016392682494.982285732414233113 and value of k::36.0 Non-terminating: ADD 99 having Pmax::6546014724822020.553957018810724829 and value of k::36.0 Non-terminating: ADD 100 having Pmax::9474061716781832.403486749549623785 and value of k::37.0 Non-terminating: ADD

mittal_ankur15 + 1 comment This is my logger statements which gives sum as 3642

mittal_ankur15 + 1 comment Can anybody tell which value is wrong here?

mvanwoerkom + 1 comment D(7) is 7:

M(7) = (7/3)^3 = 343/27 = 12 + 19/27 = 38.703703.. is not terminating.

D(9) is -9:

M(9)=(9/3)^3=27 is terminating.

rssalessio + 1 comment typo: (7/3)^3 = 343/

**27**= 12 + 19/27mvanwoerkom + 0 comments Thanks I corrected it. Good I erred on the right case. :-)

shubhubanachauh1 + 0 comments d(n)=-3 ?

jamidileepkumar + 0 comments Hi, I don't know the logic you are using but I think you need to find if n and k are co-prime to each other and if not then divide them with the common divisor and then apply your logic.

brianmvance + 0 comments [deleted]

premchandmullam1 + 0 comments How to divide the number n into equal parts

SJ151 + 0 comments i am able to pass out only first test case. but when i put n of the order of 10^6 it takes less than 0.493s to give the output. but then also i am getting timeout error for all rest cases. please help.

brianmvance + 0 comments Able to optimize so that I don't time out, but now getting all answers but the test case incorrect.

brianmvance + 1 comment Using calculus, find the maximum of the function by determining the derivative and setting to zero. This gives you k without having to loop any calculations.

cvipin501 + 0 comments I tried the same ,f(x) = (n/x)^(x). Maximising f(x) got me a solution of x = e , here constant e = 2.71828, Which means for maximum power product k = n/2.71828.

Is it correct?

I am still stuck on first test case, but want to know if this approach is correct.

Sort 28 Discussions, By:

Please Login in order to post a comment