S.O.S. Mathematics CyberBoard

Folks this is the first time I am posting on this forum so please forgive any deviation from the application of forum policy.

I am trying to program a mathematical model in VBA but am not quite sure how to arrive at some of the stages.

The Model
I have to determine a set of numbers {n} with "An", a set of coefficients, that can be stochastic but adhere to the following constraints:

{n} can only belong to the following set:
=> n = {1, 2, 3, ... 8}

and An is the set of whole numbers
=> An = 0, 1, 2, 3, 4, ...

Target Constraint 1 = Eh
Target Constraint 2 = Pd

Find a possible combination of the Sum of Products where:

=> sum(An x n) = Eh & sum(An) = Pd

such that entropy is maximized. I.E. select the combination with maximum count of non-zero coefficients.

=> count(An) = MAXIMUM-POSSIBLE

Most solvers I have attempted use numerical techniques (e.g. Simplex method) but I need to find a way to solve it analytically.

Any suggestions?

I'll give examples in subsquent posts

Example Computation 1:

Eh = 128
Pd = 18

sum(An x n) = 128
sum(An) = 18

Take empty {Bn} as the set to optimize and arrive at the "ideal" set {An}

Eh = 128 (Power of 2? Yes)

Iteration 1
Eh = 64 + 64 = (8 x 8) + (8 x 8)
=> Bn = {8, 8}, n = {8}, sum(Bn) = 8, count(Bn) = 2
Comment: sum(Bn) < Pd - Keep Going

Iteration 2
Eh = 64 + 32 + 32 = (8 x 8) + (8 x 4) + (8 x 4)
=> Bn = {8, 4, 4}, sum(Bn) = 16, count(Bn) = 3
Comment: sum(Bn) < Pd & sum(An) increased => Keep Going

Iteration 3
Eh = 64 + 32 + 32 = (8 x 8) + (8 x 4) + (4 x 4) + (4 x 4)
=> Bn = {8, 4, 4, 4}, sum(Bn) = 20, count(Bn) = 4
Comment: sum(Bn) > Pd & sum(Bn) increased => Try Changing "n" for smallest divisible Product

Iteration 4
Eh = 64 + 32 + 16 + 16 = (8 x 8) + (4 x 4) + (4 x 4) + (2 x 8)
=> Bn = An = {8, 4, 4, 2}, n = {8, 4, 4, 8}, sum(Bn) = 18, count(Bn) = 5
Comment: sum(Bn) = Pd [STOP]


Example Computation 2:

Eh = 135
Pd = 21

sum(An x n) = 135
sum(An) = 21

Take empty {Bn} as the set to optimize and arrive at the "ideal" set {An}

Eh = 135 (Power of 2? No)

Get R + 2^Q = 135 => r = 7 & Q = 7 => Eh = 7 + 128

Iteration 1
Eh = 7 + 128 = (1 x 7) + (8 x 8) + (8 x 8)
=> Bn = {7, 8, 8}, sum(Bn) = 23, count(Bn) = 3
Comment: sum(Bn) > Pd, sum(Bn) = 23 > Pd, count(Bn) = 3

Iteration 2
Eh = (1 x 7) + (8 x 8) + (4 x 8) + (4 x 8)
=> Bn = {7, 8, 4, 4}, sum(Bn) = 23 > Pd, count(Bn) = 4

Iteration 3
Eh = 7 + 128 = (1 x 7) + (8 x 8) + (4 x 8) + (2 x 8) + (2 x 8)
=> Bn = {7, 8, 4, 2, 2}, sum(Bn) = 23 > Pd, count(Bn) = 5

Iteration 4
Eh = (1 x 7) + (4 x 8) + (2 x 8) + (2 x 8) + (4 x 8) + (2 x 8) + (2 x 8)
=> Bn = {7, 4, 2, 2, 4, 2, 2}, sum(Bn) = 23 > Pd, count(Bn) = 7 => sum doesn't change - try breaking up non divisible number

Iteration 5
Eh = (1 x 4) + (1 x 3) + (4 x 8) + (2 x 8) + (2 x 8) + (4 x 8) + (2 x 8) + (2 x 8)
=> Bn = {1, 1, 4, 2, 2, 4, 2, 2}, sum(Bn) = 18 < Pd, count(Bn) = 8 => Oops, try switching the factors starting with smaller one

Iteration 6
Eh = (1 x 4) + (3 x 1) + (4 x 8) + (2 x 8) + (2 x 8) + (4 x 8) + (2 x 8) + (2 x 8)
=> Bn = {1, 3, 4, 2, 2, 4, 2, 2}, sum(Bn) = 20 < Pd, count(Bn) = 8 => Oops, go back and try switching the other factor instead

Iteration 7
Eh = (4 x 1) + (1 x 3) + (4 x 8) + (2 x 8) + (2 x 8) + (4 x 8) + (2 x 8) + (2 x 8)
=> Bn = An = {4, 1, 4, 2, 2, 4, 2, 2}, n = {1, 3, 8, 8, 8, 8, 8, 8} sum(Bn) = 21 = Pd, count(Bn) = 8
GOT IT!!!

What have you tried so far, analytically?

I have an analytical method that may work. Do you have any knowledge of generating functions?

I sure don't.. .and for methods, no I have not tried anything other than going through the two examples I put on the forum.

The idea is that you define a recurrence relation. You'll learn about these if you're a computer science major, if you haven't already. Wikipedia talks about them here.

A good place to learn about how to set up the generating functions is Herbert Wilf's Generatingfunctionology, which is available for free download here.

Unfortunately, they can be a little complicated, especially for something like this, and could take a lot of time to learn/master. You may want to just consider going with computing the material as you have been, since it gets exceedingly complex to try to obtain a formula. Unless someone knows of an easier method...