If
ak=4, this is equivalent to a combination where
ak is replaced with 2 2s, as they have the same product and sum. So, WLOG, there must be an optimal combination with
ak<4∀k. Clearly if
ak=1, a combination where another number was instead increased by 1 would have a greater product, therefore
ak=1. Therefore
ak=2 or
3. If there are 3 or more terms which are 2, then a combination where there are 2 3s, instead of 3 of those 2s, there will be a greater product as
2+2+2=3+3 and
23<32. Therefore the optimal combination will have only 3s and 2s, and at most 2 2s.
Therefore, if
N=0(mod3),
P(N)=33N, if
N=1(mod3),
P(N)=4⋅33N−4 and if
N=2(mod3),
P(N)=2⋅33N−2