How many integral solutions does $2x + 3y + 5z = 900$ have when $ x, y, z \ge 0$?

1.3k Views Asked by At

Solution: Let $2x + 3y = u.$ Then we must solve $\begin{align} u + 5z = 900 \tag 1 \\ 2x + 3y = u \tag 2 \end{align}$

For $(1),$ a particular solution is $(u_0, z_0) = (0, 180).$ Hence, all the integral solutions of $(1)$ are $\begin{cases} u = 5t \\ z = 180 - t \end{cases} (t \in \mathbb Z)$

Substituting $u = 5t$ into $(2)$ gives $2x + 3y = 5t$ whose particular solution is $(x_0, y_0) = (t, t).$ Hence all the integral solutions of $(2)$ are $\begin{cases} x = t - 3s \\ y = t + 2s \end{cases} (t \in \mathbb Z)$

Thus all the integral solutions of $2x + 3y + 5z = 900$ are given by $$\begin{cases} x = t - 3s \\ y = t + 2s \\ z = 180 - t \end{cases} (s,t \in \mathbb Z)$$

Now suppose $x, y, z \ge 0.$

Note, $180 - t \ge 0 \implies t \le 180$ and so $t + 2s \ge 0 \implies s \ge -90$ and $t - 3s \ge 0 \implies s \le 60.$ Thus we have $-90 \le s \le 60.$

Consider $0 \le s \le 60.$ Now $t \le 180, \ t \ge 3s \implies 3s \le t \le 180$. Thus in this range of $s$, there are $180 - 3s + 1 = 181 - 3s$ of $t$'s.

Consider $-90 \le s < 0.$ Now $t \le 180, \ t \ge -2s \implies -2s \le t \le 180$. Thus in this range of $s$, there are $180 + 2s + 1 = 181 + 2s$ of $t$'s.

Range $0 \le s \le 60$ has the following points:

$(0, 181 - 3(0)), \ (1, 181 - 3(1)), (2, 181 - 3(2), \ldots (60, 181 - 3(60))$ of which there are $61.$

The range $-90 \le s < 0$ must have $91$ points. In sum, we have $61 + 91 = 152$ points for $x, y, z \ge 0.$

My question:

According to the book the answer is $\displaystyle{\sum_{s = 0}^{60}(181 - 3s) + \sum_{s = -90}^{-1}(181 + 2s) = 13651.}$ I don't understand why they took the sum of all $t$'s in the range of $s$. That means some of my denotations and labels above must be incorrect. Where's the mistake? Thanks.

edit:

I think I see my mistake. The number $181 - 3s$ is the number of $t$'s, not necessarily the form of $t$. Given that, the number of ordered pairs (in the given range) must be $(181 - 3s)*61$ by the product rule.

5

There are 5 best solutions below

0
On

Not an answer, but potentially helpful:

The following MiniZinc model confirms, that there are actually $13651$ solutions.

set of int: Domain = 0..900;
var Domain: x;
var Domain: y;
var Domain: z;

constraint (2*x + 3*y + 5*z) == 900;
0
On

The number of nonnegative integer solutions of $2x + 3y + 5z = 900$ is the coefficient of $t^{900}$ in the following generating function

$$f (t) := \frac{1}{ \left( 1 - t^2 \right) \left( 1 - t^3 \right) \left( 1 - t^5 \right)}$$

Using SymPy:

>>> from sympy import *
>>> t = Symbol('t')
>>> f = 1 / ((1 - t**2) * (1 - t**3) * (1 - t**5))
>>> f.series(t,0,901)
1 + t**2 + t**3 + t**4 + 2*t**5 + 2*t**6 + 2*t**7 + 3*t**8 + 3*t**9 + 4*t**10 + 4*t**11 + 5*t**12 + 5*t**13 + 6*t**14 + 7*t**15 + 7*t**16 + 8*t**17 + 9*t**18 + 9*t**19 + 11*t**20 + 11*t**21 + 12*t**22 + 13*t**23 + 14*t**24 + 15*t**25 + 16*t**26 + 17*t**27 + 18*t**28 + 19*t**29 + 21*t**30 + 21*t**31 + 23*t**32 + 24*t**33 + 25*t**34 + 27*t**35 + 28*t**36 + 29*t**37 + 31*t**38 + 32*t**39 + 34*t**40 + 35*t**41 + 37*t**42 + 38*t**43 + 40*t**44 + 42*t**45 + 43*t**46 + 45*t**47 + 47*t**48 + 48*t**49 + 51*t**50 + 52*t**51 + 54*t**52 + 56*t**53 + 58*t**54 + 60*t**55 + 62*t**56 + 64*t**57 + 66*t**58 + 68*t**59 + 71*t**60 + 72*t**61 + 75*t**62 + 77*t**63 + 79*t**64 + 82*t**65 + 84*t**66 + 86*t**67 + 89*t**68 + 91*t**69 + 94*t**70 + 96*t**71 + 99*t**72 + 101*t**73 + 104*t**74 + 107*t**75 + 109*t**76 + 112*t**77 + 115*t**78 + 117*t**79 + 121*t**80 + 123*t**81 + 126*t**82 + 129*t**83 + 132*t**84 + 135*t**85 + 138*t**86 + 141*t**87 + 144*t**88 + 147*t**89 + 151*t**90 + 153*t**91 + 157*t**92 + 160*t**93 + 163*t**94 + 167*t**95 + 170*t**96 + 173*t**97 + 177*t**98 + 180*t**99 + 184*t**100 + 187*t**101 + 191*t**102 + 194*t**103 + 198*t**104 + 202*t**105 + 205*t**106 + 209*t**107 + 213*t**108 + 216*t**109 + 221*t**110 + 224*t**111 + 228*t**112 + 232*t**113 + 236*t**114 + 240*t**115 + 244*t**116 + 248*t**117 + 252*t**118 + 256*t**119 + 261*t**120 + 264*t**121 + 269*t**122 + 273*t**123 + 277*t**124 + 282*t**125 + 286*t**126 + 290*t**127 + 295*t**128 + 299*t**129 + 304*t**130 + 308*t**131 + 313*t**132 + 317*t**133 + 322*t**134 + 327*t**135 + 331*t**136 + 336*t**137 + 341*t**138 + 345*t**139 + 351*t**140 + 355*t**141 + 360*t**142 + 365*t**143 + 370*t**144 + 375*t**145 + 380*t**146 + 385*t**147 + 390*t**148 + 395*t**149 + 401*t**150 + 405*t**151 + 411*t**152 + 416*t**153 + 421*t**154 + 427*t**155 + 432*t**156 + 437*t**157 + 443*t**158 + 448*t**159 + 454*t**160 + 459*t**161 + 465*t**162 + 470*t**163 + 476*t**164 + 482*t**165 + 487*t**166 + 493*t**167 + 499*t**168 + 504*t**169 + 511*t**170 + 516*t**171 + 522*t**172 + 528*t**173 + 534*t**174 + 540*t**175 + 546*t**176 + 552*t**177 + 558*t**178 + 564*t**179 + 571*t**180 + 576*t**181 + 583*t**182 + 589*t**183 + 595*t**184 + 602*t**185 + 608*t**186 + 614*t**187 + 621*t**188 + 627*t**189 + 634*t**190 + 640*t**191 + 647*t**192 + 653*t**193 + 660*t**194 + 667*t**195 + 673*t**196 + 680*t**197 + 687*t**198 + 693*t**199 + 701*t**200 + 707*t**201 + 714*t**202 + 721*t**203 + 728*t**204 + 735*t**205 + 742*t**206 + 749*t**207 + 756*t**208 + 763*t**209 + 771*t**210 + 777*t**211 + 785*t**212 + 792*t**213 + 799*t**214 + 807*t**215 + 814*t**216 + 821*t**217 + 829*t**218 + 836*t**219 + 844*t**220 + 851*t**221 + 859*t**222 + 866*t**223 + 874*t**224 + 882*t**225 + 889*t**226 + 897*t**227 + 905*t**228 + 912*t**229 + 921*t**230 + 928*t**231 + 936*t**232 + 944*t**233 + 952*t**234 + 960*t**235 + 968*t**236 + 976*t**237 + 984*t**238 + 992*t**239 + 1001*t**240 + 1008*t**241 + 1017*t**242 + 1025*t**243 + 1033*t**244 + 1042*t**245 + 1050*t**246 + 1058*t**247 + 1067*t**248 + 1075*t**249 + 1084*t**250 + 1092*t**251 + 1101*t**252 + 1109*t**253 + 1118*t**254 + 1127*t**255 + 1135*t**256 + 1144*t**257 + 1153*t**258 + 1161*t**259 + 1171*t**260 + 1179*t**261 + 1188*t**262 + 1197*t**263 + 1206*t**264 + 1215*t**265 + 1224*t**266 + 1233*t**267 + 1242*t**268 + 1251*t**269 + 1261*t**270 + 1269*t**271 + 1279*t**272 + 1288*t**273 + 1297*t**274 + 1307*t**275 + 1316*t**276 + 1325*t**277 + 1335*t**278 + 1344*t**279 + 1354*t**280 + 1363*t**281 + 1373*t**282 + 1382*t**283 + 1392*t**284 + 1402*t**285 + 1411*t**286 + 1421*t**287 + 1431*t**288 + 1440*t**289 + 1451*t**290 + 1460*t**291 + 1470*t**292 + 1480*t**293 + 1490*t**294 + 1500*t**295 + 1510*t**296 + 1520*t**297 + 1530*t**298 + 1540*t**299 + 1551*t**300 + 1560*t**301 + 1571*t**302 + 1581*t**303 + 1591*t**304 + 1602*t**305 + 1612*t**306 + 1622*t**307 + 1633*t**308 + 1643*t**309 + 1654*t**310 + 1664*t**311 + 1675*t**312 + 1685*t**313 + 1696*t**314 + 1707*t**315 + 1717*t**316 + 1728*t**317 + 1739*t**318 + 1749*t**319 + 1761*t**320 + 1771*t**321 + 1782*t**322 + 1793*t**323 + 1804*t**324 + 1815*t**325 + 1826*t**326 + 1837*t**327 + 1848*t**328 + 1859*t**329 + 1871*t**330 + 1881*t**331 + 1893*t**332 + 1904*t**333 + 1915*t**334 + 1927*t**335 + 1938*t**336 + 1949*t**337 + 1961*t**338 + 1972*t**339 + 1984*t**340 + 1995*t**341 + 2007*t**342 + 2018*t**343 + 2030*t**344 + 2042*t**345 + 2053*t**346 + 2065*t**347 + 2077*t**348 + 2088*t**349 + 2101*t**350 + 2112*t**351 + 2124*t**352 + 2136*t**353 + 2148*t**354 + 2160*t**355 + 2172*t**356 + 2184*t**357 + 2196*t**358 + 2208*t**359 + 2221*t**360 + 2232*t**361 + 2245*t**362 + 2257*t**363 + 2269*t**364 + 2282*t**365 + 2294*t**366 + 2306*t**367 + 2319*t**368 + 2331*t**369 + 2344*t**370 + 2356*t**371 + 2369*t**372 + 2381*t**373 + 2394*t**374 + 2407*t**375 + 2419*t**376 + 2432*t**377 + 2445*t**378 + 2457*t**379 + 2471*t**380 + 2483*t**381 + 2496*t**382 + 2509*t**383 + 2522*t**384 + 2535*t**385 + 2548*t**386 + 2561*t**387 + 2574*t**388 + 2587*t**389 + 2601*t**390 + 2613*t**391 + 2627*t**392 + 2640*t**393 + 2653*t**394 + 2667*t**395 + 2680*t**396 + 2693*t**397 + 2707*t**398 + 2720*t**399 + 2734*t**400 + 2747*t**401 + 2761*t**402 + 2774*t**403 + 2788*t**404 + 2802*t**405 + 2815*t**406 + 2829*t**407 + 2843*t**408 + 2856*t**409 + 2871*t**410 + 2884*t**411 + 2898*t**412 + 2912*t**413 + 2926*t**414 + 2940*t**415 + 2954*t**416 + 2968*t**417 + 2982*t**418 + 2996*t**419 + 3011*t**420 + 3024*t**421 + 3039*t**422 + 3053*t**423 + 3067*t**424 + 3082*t**425 + 3096*t**426 + 3110*t**427 + 3125*t**428 + 3139*t**429 + 3154*t**430 + 3168*t**431 + 3183*t**432 + 3197*t**433 + 3212*t**434 + 3227*t**435 + 3241*t**436 + 3256*t**437 + 3271*t**438 + 3285*t**439 + 3301*t**440 + 3315*t**441 + 3330*t**442 + 3345*t**443 + 3360*t**444 + 3375*t**445 + 3390*t**446 + 3405*t**447 + 3420*t**448 + 3435*t**449 + 3451*t**450 + 3465*t**451 + 3481*t**452 + 3496*t**453 + 3511*t**454 + 3527*t**455 + 3542*t**456 + 3557*t**457 + 3573*t**458 + 3588*t**459 + 3604*t**460 + 3619*t**461 + 3635*t**462 + 3650*t**463 + 3666*t**464 + 3682*t**465 + 3697*t**466 + 3713*t**467 + 3729*t**468 + 3744*t**469 + 3761*t**470 + 3776*t**471 + 3792*t**472 + 3808*t**473 + 3824*t**474 + 3840*t**475 + 3856*t**476 + 3872*t**477 + 3888*t**478 + 3904*t**479 + 3921*t**480 + 3936*t**481 + 3953*t**482 + 3969*t**483 + 3985*t**484 + 4002*t**485 + 4018*t**486 + 4034*t**487 + 4051*t**488 + 4067*t**489 + 4084*t**490 + 4100*t**491 + 4117*t**492 + 4133*t**493 + 4150*t**494 + 4167*t**495 + 4183*t**496 + 4200*t**497 + 4217*t**498 + 4233*t**499 + 4251*t**500 + 4267*t**501 + 4284*t**502 + 4301*t**503 + 4318*t**504 + 4335*t**505 + 4352*t**506 + 4369*t**507 + 4386*t**508 + 4403*t**509 + 4421*t**510 + 4437*t**511 + 4455*t**512 + 4472*t**513 + 4489*t**514 + 4507*t**515 + 4524*t**516 + 4541*t**517 + 4559*t**518 + 4576*t**519 + 4594*t**520 + 4611*t**521 + 4629*t**522 + 4646*t**523 + 4664*t**524 + 4682*t**525 + 4699*t**526 + 4717*t**527 + 4735*t**528 + 4752*t**529 + 4771*t**530 + 4788*t**531 + 4806*t**532 + 4824*t**533 + 4842*t**534 + 4860*t**535 + 4878*t**536 + 4896*t**537 + 4914*t**538 + 4932*t**539 + 4951*t**540 + 4968*t**541 + 4987*t**542 + 5005*t**543 + 5023*t**544 + 5042*t**545 + 5060*t**546 + 5078*t**547 + 5097*t**548 + 5115*t**549 + 5134*t**550 + 5152*t**551 + 5171*t**552 + 5189*t**553 + 5208*t**554 + 5227*t**555 + 5245*t**556 + 5264*t**557 + 5283*t**558 + 5301*t**559 + 5321*t**560 + 5339*t**561 + 5358*t**562 + 5377*t**563 + 5396*t**564 + 5415*t**565 + 5434*t**566 + 5453*t**567 + 5472*t**568 + 5491*t**569 + 5511*t**570 + 5529*t**571 + 5549*t**572 + 5568*t**573 + 5587*t**574 + 5607*t**575 + 5626*t**576 + 5645*t**577 + 5665*t**578 + 5684*t**579 + 5704*t**580 + 5723*t**581 + 5743*t**582 + 5762*t**583 + 5782*t**584 + 5802*t**585 + 5821*t**586 + 5841*t**587 + 5861*t**588 + 5880*t**589 + 5901*t**590 + 5920*t**591 + 5940*t**592 + 5960*t**593 + 5980*t**594 + 6000*t**595 + 6020*t**596 + 6040*t**597 + 6060*t**598 + 6080*t**599 + 6101*t**600 + 6120*t**601 + 6141*t**602 + 6161*t**603 + 6181*t**604 + 6202*t**605 + 6222*t**606 + 6242*t**607 + 6263*t**608 + 6283*t**609 + 6304*t**610 + 6324*t**611 + 6345*t**612 + 6365*t**613 + 6386*t**614 + 6407*t**615 + 6427*t**616 + 6448*t**617 + 6469*t**618 + 6489*t**619 + 6511*t**620 + 6531*t**621 + 6552*t**622 + 6573*t**623 + 6594*t**624 + 6615*t**625 + 6636*t**626 + 6657*t**627 + 6678*t**628 + 6699*t**629 + 6721*t**630 + 6741*t**631 + 6763*t**632 + 6784*t**633 + 6805*t**634 + 6827*t**635 + 6848*t**636 + 6869*t**637 + 6891*t**638 + 6912*t**639 + 6934*t**640 + 6955*t**641 + 6977*t**642 + 6998*t**643 + 7020*t**644 + 7042*t**645 + 7063*t**646 + 7085*t**647 + 7107*t**648 + 7128*t**649 + 7151*t**650 + 7172*t**651 + 7194*t**652 + 7216*t**653 + 7238*t**654 + 7260*t**655 + 7282*t**656 + 7304*t**657 + 7326*t**658 + 7348*t**659 + 7371*t**660 + 7392*t**661 + 7415*t**662 + 7437*t**663 + 7459*t**664 + 7482*t**665 + 7504*t**666 + 7526*t**667 + 7549*t**668 + 7571*t**669 + 7594*t**670 + 7616*t**671 + 7639*t**672 + 7661*t**673 + 7684*t**674 + 7707*t**675 + 7729*t**676 + 7752*t**677 + 7775*t**678 + 7797*t**679 + 7821*t**680 + 7843*t**681 + 7866*t**682 + 7889*t**683 + 7912*t**684 + 7935*t**685 + 7958*t**686 + 7981*t**687 + 8004*t**688 + 8027*t**689 + 8051*t**690 + 8073*t**691 + 8097*t**692 + 8120*t**693 + 8143*t**694 + 8167*t**695 + 8190*t**696 + 8213*t**697 + 8237*t**698 + 8260*t**699 + 8284*t**700 + 8307*t**701 + 8331*t**702 + 8354*t**703 + 8378*t**704 + 8402*t**705 + 8425*t**706 + 8449*t**707 + 8473*t**708 + 8496*t**709 + 8521*t**710 + 8544*t**711 + 8568*t**712 + 8592*t**713 + 8616*t**714 + 8640*t**715 + 8664*t**716 + 8688*t**717 + 8712*t**718 + 8736*t**719 + 8761*t**720 + 8784*t**721 + 8809*t**722 + 8833*t**723 + 8857*t**724 + 8882*t**725 + 8906*t**726 + 8930*t**727 + 8955*t**728 + 8979*t**729 + 9004*t**730 + 9028*t**731 + 9053*t**732 + 9077*t**733 + 9102*t**734 + 9127*t**735 + 9151*t**736 + 9176*t**737 + 9201*t**738 + 9225*t**739 + 9251*t**740 + 9275*t**741 + 9300*t**742 + 9325*t**743 + 9350*t**744 + 9375*t**745 + 9400*t**746 + 9425*t**747 + 9450*t**748 + 9475*t**749 + 9501*t**750 + 9525*t**751 + 9551*t**752 + 9576*t**753 + 9601*t**754 + 9627*t**755 + 9652*t**756 + 9677*t**757 + 9703*t**758 + 9728*t**759 + 9754*t**760 + 9779*t**761 + 9805*t**762 + 9830*t**763 + 9856*t**764 + 9882*t**765 + 9907*t**766 + 9933*t**767 + 9959*t**768 + 9984*t**769 + 10011*t**770 + 10036*t**771 + 10062*t**772 + 10088*t**773 + 10114*t**774 + 10140*t**775 + 10166*t**776 + 10192*t**777 + 10218*t**778 + 10244*t**779 + 10271*t**780 + 10296*t**781 + 10323*t**782 + 10349*t**783 + 10375*t**784 + 10402*t**785 + 10428*t**786 + 10454*t**787 + 10481*t**788 + 10507*t**789 + 10534*t**790 + 10560*t**791 + 10587*t**792 + 10613*t**793 + 10640*t**794 + 10667*t**795 + 10693*t**796 + 10720*t**797 + 10747*t**798 + 10773*t**799 + 10801*t**800 + 10827*t**801 + 10854*t**802 + 10881*t**803 + 10908*t**804 + 10935*t**805 + 10962*t**806 + 10989*t**807 + 11016*t**808 + 11043*t**809 + 11071*t**810 + 11097*t**811 + 11125*t**812 + 11152*t**813 + 11179*t**814 + 11207*t**815 + 11234*t**816 + 11261*t**817 + 11289*t**818 + 11316*t**819 + 11344*t**820 + 11371*t**821 + 11399*t**822 + 11426*t**823 + 11454*t**824 + 11482*t**825 + 11509*t**826 + 11537*t**827 + 11565*t**828 + 11592*t**829 + 11621*t**830 + 11648*t**831 + 11676*t**832 + 11704*t**833 + 11732*t**834 + 11760*t**835 + 11788*t**836 + 11816*t**837 + 11844*t**838 + 11872*t**839 + 11901*t**840 + 11928*t**841 + 11957*t**842 + 11985*t**843 + 12013*t**844 + 12042*t**845 + 12070*t**846 + 12098*t**847 + 12127*t**848 + 12155*t**849 + 12184*t**850 + 12212*t**851 + 12241*t**852 + 12269*t**853 + 12298*t**854 + 12327*t**855 + 12355*t**856 + 12384*t**857 + 12413*t**858 + 12441*t**859 + 12471*t**860 + 12499*t**861 + 12528*t**862 + 12557*t**863 + 12586*t**864 + 12615*t**865 + 12644*t**866 + 12673*t**867 + 12702*t**868 + 12731*t**869 + 12761*t**870 + 12789*t**871 + 12819*t**872 + 12848*t**873 + 12877*t**874 + 12907*t**875 + 12936*t**876 + 12965*t**877 + 12995*t**878 + 13024*t**879 + 13054*t**880 + 13083*t**881 + 13113*t**882 + 13142*t**883 + 13172*t**884 + 13202*t**885 + 13231*t**886 + 13261*t**887 + 13291*t**888 + 13320*t**889 + 13351*t**890 + 13380*t**891 + 13410*t**892 + 13440*t**893 + 13470*t**894 + 13500*t**895 + 13530*t**896 + 13560*t**897 + 13590*t**898 + 13620*t**899 + 13651*t**900 + O(t**901)

Hence, there are $13651$ nonnegative integer solutions.

0
On

Since the generating function $$ f(z)=\frac{1}{(1-z^2)(1-z^3)(1-z^5)} $$ has a triple pole at $z=1$ and simple poles at $9$ points of $S^1$, we may decompose it as $$ f(z) = \frac{1}{30(1-z)^3}+\frac{7}{60(1-z)^2}+\sum_{k=1}^{8}\frac{R_k}{z-R_k} $$ and deduce that the coefficient of $z^n$ in $f(z)$, up to a bounded error term (bounded by $\sum_{k=1}^{8}|R_k|$) is given by $$ [z^n]\left[\frac{1}{30(1-z)^3}+\frac{7}{60(1-z)^2}\right]=\frac{(n+1)(n+9)}{60} $$ (this follows from stars and bars). By evaluating the RHS at $n=900$ we get a bit more than $13650$, and the number of representations of $900$ as $2a+3b+5c$ is actually $13651$. In order to have a simultaneous control of the magnitude and the error term we may prove first that $$ [x^n]\frac{1}{(1-x^2)(1-x^3)} = \frac{2n+5}{12}+3(-1)^n+\left\{\begin{array}{rcl}1&\text{if}&n\equiv 0\pmod{3}\\-1&\text{if}&n\equiv 1\pmod{3}\\0&\text{if}&n\equiv 2\pmod{3}\\\end{array}\right.$$ which equals $\left\lfloor\frac{n+4}{6}\right\rfloor$, increased by one if $n\equiv 0\pmod{6}$. It follows that the exact number of representations is given by

$$ 31+\sum_{k=0}^{180}\left\lfloor \frac{5k+4}{6}\right\rfloor = 13651. $$ The sum in the last line equals the number of lattice points in a trapezium. By Pick's theorem this is given by the area of the trapezoid and the number of lattice points on the line $y=\frac{5x+4}{6}$, for $x\in[0,180]$. This counting problem is analogous to the determination of $$|[4,904]\cap6\mathbb{Z}|=180.$$

0
On

Above equation shown below:

$2x+3y+5z=900 ------(1)$

Equation $(1)$ is equivalent to :

$ax+by+cz=n -----(2)$

Where, $(a,b,c,n)=(2,3,5,900)$

If, $(p,q,r)$ is a known solution to equation (2),

then another solution is given as:

$x=p-bt+ct$

$y=q+at-ct$

$z=r-at+bt$

Where, $'t'$ is a parameter.

Taking $'w'$ as the number of solutions to equation $(2)$

then, "J. Franel" has given a formula for $'w'$.

$w={n}[(a(p+1)+b(q+1)+c(r+1))/(2abc)]$

For, $(p,q,r)=(6,16,168)$ & $(a,b,c,n)=(2,3,5,900)$ we have :

$w=13650$

1
On

You can solve this problem by creating equals Ax = b. Where A - transition matrix by x and b. Let's consider this example. Introduce F(m, i) where F(m, 1) - count of solutions 2x = m, F(m, 2) - count of solutions 2x + 3y = m, F(m, 3) - count of solution 2x + 3y + 5z = m ...

The following equations are valid:

F(m, 1) = F(m - 2, 1)

F(m, 2) = F(m, 1) + F(m - 3, 2) = F(m - 2, 1) + F(m - 3, 2)

F(m, 3) = F(m, 2) + F(m - 5, 3) = F(m - 2, 1) + F(m - 3, 2) + F(m - 5, 3)

Vector b we can construct as [F(m, 1), F(m - 1, 1), F(m, 2), F(m - 1, 2), F(m - 2, 2), F(m, 3), F(m - 1, 3), F(m - 2, 3), F(m - 3, 3), F(m - 4, 3)].

Vector x we can construct as [F(m - 1, 1), F(m - 2, 1), F(m - 1, 2), F(m - 2, 2), F(m - 3, 2), F(m - 1, 3), F(m - 2, 3), F(m - 3, 3), F(m - 4, 3), F(m - 5, 3)].

Matrix A is easily constructed by x and b.

Start vector x is [F(0, 1), F(-1, 1), F(0, 2), F(-1, 2), F(-2, 2), F(0, 3), F(-1, 3), F(-2, 3), F(-3, 3), F(-4, 3)] and have value [1, 0, 1, 0, 0, 1, 0, 0, 0, 0]

And it's finish. We interested in F(900, 3). We need calculate A^900 * x and take appropriate b[5]. We can raise the matrix to a power by O(2 * lb(900) * 10^3)