Solving the Subset Problem: Finding the Count of Valid Sets from 1 to N

[SeventhSigma]

thank you for the explanation, it was very helpful!

 

[ClifDavis]

thank you for the explanation, it was very helpful!

Thanks, I never know when my explanations are adequate and when they are as clear as mud.

 

[ClifDavis]

Yay! It's Thursday. And of course other things have come up, but we'll see how it goes.

My original approach to this was a bit different than haruspex's clever approach to the problem where he works with C(n) and D(n). Instead I worked at building a recurrence formula for Count(n) directly. But in doing so at one point I needed a function we can call R4(n) which for n>4 was defined to be the number of subsets of Sn which totaled more than A(n)+A(n-1)+A(n-2)+A(n-3).
But I never needed to work out what the full formula for R4(n) was because I was able to use an algebraic trick to Compare Count(i) to Count(i-3) and make R4 disappear to give me the final recurrence formula.

But in the derivation I had to use R4(n-8) which meant that the validity of the final recurrence formula depended on n-8>4 or n>12. While I derived a algebraically simplified form of the general recurrence formula for Count(n) with various terms of Count(n)and a final correction of a multiple of a power of 2 and a constant, I also kept around the unsimplified form of the formula because starting with Count(4) and going up, I knew for which values of n the different parts of the formula would start kicking in, and so this made calculating Count(4) through Count(12) relatively easy without having to actually create the relevant subsets of Sn.

As I say, I think heruspex's approach with C(n) and D(n) is a lot cooler and it occurred to me to see if I could work out the recurrence formula for Count(n) directly from them. And it is possible. Unsurprisingly it produces the very same recurrence formula as my simplified form but now we only have to assume that n>7.

In other words we can give the 1st 7 values and the recurrence formula and we're in business. We still need powers of 2 and a constant though. This means that we can set up a 9 element vector starting with 7 consecutive values of Count(n) and the an appropriate power of 2 and finally a 1 and create a matrix M to transform it to one with the values of Count(n) shifted to the left and then a new value created from the recurrence relationship followed by the next power of 2 and of course the value 1.

We can of course precalculate M^7 to give us 7 new values at a time, and the use of a 9 element vector instead of an 11 element vector also represents a savings.

So at this point I would say that we're pretty well motivated to look at the general recurrence formula for Count(n).

 

[haruspex]

I've been working on convergent lines with you ClifD.
My 7-term recurrence formula is surely the same as yours. In homogeneous form, the coefficients for G(n-1) down to G(n-7) to generate G(n) are:
1, 0, +2, -1, -1, -1, +1.
But what about the inhomogeneous term (25*2^(n-7)-1)?
I claim that if we generate a sequence H(n) with suitable starting values H1 to H7 from the above relation all we need to do to get G(n) is add:
n + 5*(2^n)/9
The 7 starting values for H(n) are simply those needed to make G(1) to G(7) right; and it works!
H[1, 7] = -19/9 -38/9 -67/9 -98/9 -142/9 -203/9 -280/9
Applying the homogeneous recurrence relation for the next 7 gives:
H[8, 14] = -380/9 -517/9 -701/9 -934/9 -1247/9 -1675/9 -2225/9
Adding in n + 5*(2^n)/9 to each we get
G[1, 7] = 0 0 0 2 7 19 47
as arranged, and beyond that:
G[8, 14] = 108 236 501 1045 2149 4378 8869

The nice thing about having a homogeneous relation is that we can accelerate the matrix multiplication. The matrix is now constant, so we can form high powers of it quickly by squaring repeatedly (applying modulo 1E9 as we go). If you want a power of M other than a power of 2 then just form a product of selected generated powers along the way, according to the binary bit pattern of the target power.

For the purposes of taking the result modulo 1E9, note that 5/9 mod 1E9 is 444444445.
I'm sure something clever can be done with 2^n mod 1E9 (for n >= 9).

 

[ClifDavis]

The last time around, in order to develop the M matrix we've been using, I got rid of the Countnew function and expressed Count solely in terms of older values. But for what we are about to do, I want to drop back to a slightly more transparent version.

We have:
C(1)=0
C(2)=1
C(3)=3
C(n)= C(n-3)+D(n-3)+5(2^(n-3))-1 for n>3

D(1)=0
D(2)=0
D(3)=1
D(n)=C(n-1)+D(n-3) for n>3

Countnew(1)=0
Countnew(n)=C(n)-2^(n-1)+1 for n>1

Count(0)=0
Count(n)=Count(n-1)+Countnew(n) for n>0.

Functionally Countnew(n) is applying the overcount correction to C(n) and Count is accumulating the count of smaller subsets of Sn.

Now I want to start by calculating the general formula for C(n-3) and D(n-3).
For n-3>3, which is to say for n>6, we can just apply the formulas directly.

C(n)= C(n-3)+D(n-3)+5(2^(n-3))-1
C(n-3)= C(n-3-3)+D(n-3-3)+5(2^(n-3-3))-1
or more succinctly
(1) C(n-3)= C(n-6)+D(n-6)+5(2^(n-6))-1 for n>6

and for D(n-3) we take
D(n)=C(n-1)+D(n-3)
and substitute to get
D(n-3)=C(n-4)+D(n-6) for n>6.

But as we recall C(n)= C(n-3)+D(n-3)+5(2^(n-3))-1
and if we substitute in for the D(n-3) term we get
(2) C(n)= C(n-3)+C(n-4)+D(n-6)+5(2^(n-3))-1 for n>6

Now equation (2) gives us an equation for C(n) while equation (3) gives us an equation for C(n-3). The fact that both equations contain a single identical occurrence of the D function, D(n-6) motivates me to look at C(n)-C(n-3) by substituting from equations (1) and (2).

C(n)-C(n-3)=(C(n-3)+C(n-4)+D(n-6)+5(2^(n-3))-1)-( C(n-6)+D(n-6)+5(2^(n-6))-1)
C(n)-C(n-3)=C(n-3)+C(n-4)+D(n-6)+5(2^(n-3))-1-C(n-6)-D(n-6)-5(2^(n-6))+1

We reorganize to put like terms with like terms

C(n)-C(n-3)=C(n-3)+C(n-4)-C(n-6)+(D(n-6)-D(n-6))+5(2^(n-3))-5(2^(n-6)+(1-1)
or
C(n)-C(n-3)=C(n-3)+C(n-4)-C(n-6)+(0)+5(2^(n-3))-5(2^(n-6)+(0)
but 2^(n-3)=8(2^(n-6))
so 5(2^(n-3))-5(2^(n-6) = 40(2^(n-6))-5(2^(n-6))=35(2^(n-6)).
Substituting we get
C(n)-C(n-3)=C(n-3)+C(n-4)-C(n-6)+35(2^(n-6))
and adding C(n-3) to both sides
(3) C(n)=2C(n-3)+C(n-4)-C(n-6)+35(2^(n-6))
all under the condition that n>6.

The recurrence relationship in (3) will let us define C(n) without the use of D(anything) provided we are willing to start with the first 6 values of C(n).

Our definition of Countnew was
Countnew(1)=0
Countnew(n)=C(n)-2^(n-1)+1 for n>1

If n>6 then certainly n>1 and so we must have
Countnew(n)=C(n)-2^(n-1)+1 or conversely
C(n)=Countnew(n)+2^(n-1)-1 for n>1

Trying this out for some other values of n we have
C(n-3)=Countnew(n-3)+2^(n-4)-1 if n-3>1 or n>4.
C(n-4)=Countnew(n-4)+2^(n-5)-1 if n-4>1 or n>5
C(n-6)=Countnew(n-6)+2^(n-7)-1 if n-6>1 or n>7.

If n>7 each of these last three holds as does equation (3). And so we can substitute in (3)
C(n)=2C(n-3)+C(n-4)-C(n-6)+35(2^(n-6))
=2(Countnew(n-3)+2^(n-4)-1)+Countnew(n-4)+2^(n-5)-1
-(Countnew(n-6)+2^(n-7)-1)+35(2^(n-6))
Simplifying
C(n)=2Countnew(n-3)+Countnew(n-4)-Countnew(n-6)+(16+4-1+70)(2^n-7)+(-2-1+1)
C(n)=2Countnew(n-3)+Countnew(n-4)-Countnew(n-6)+89(2^n-7)-2
Now if n>7 then n>1 and we said Countnew(n)=C(n)-2^(n-1)+1. So
Countnew(n)=(2Countnew(n-3)+Countnew(n-4)-Countnew(n-6)+89(2^n-7)-2)- 2^(n-1)+1
which gives us
(4) Countnew(n)=2Countnew(n-3)+Countnew(n-4)-Countnew(n-6)+25(2^n-7)-1 for n>7

which gives us a recurrence formula purely in terms of Countnew.

The remaining step is obtaining a recurrence for Count.

For n>0 we had Count(n)=Count(n-1)+Countnew(n) which means
Countnew(n)=Count(n)-Count(n-1)
Since n>7 then it's clear n-3>0, n-4>0, and n-6>0 and so
Countnew(n-3)=Count(n-3)-Count(n-4)
Countnew(n-4)=Count(n-4)-Count(n-5)
Countnew(n-6)=Count(n-6)-Count(n-7)

We make these substitutions in (4) to get
Countnew(n)=2(Count(n-3)-Count(n-4))+Count(n-4)-Count(n-5)-(Count(n-6)-Count(n-7))+25(2^n-7)-1 for n>7.
Simplifying,
Countnew(n)=2Count(n-3)-Count(n-4)-Count(n-5)-Count(n-6)+Count(n-7)+25(2^n-7)-1 for n>7.
And now Count(n)=Count(n-1)+Countnew(n) with n>7>0 gives us
Count(n)=Count(n-1)+2Count(n-3)-Count(n-4)-Count(n-5)-Count(n-6)+Count(n-7)+25(2^n-7)-1 for n>7.

We have a pure recurrence relation for Count(n) to which we only need add the first 7 values of Count to have it defined.

We still have powers of two and a constant in our recurrence so this give rise to an initial 9 element vector and an update matrix. But I'm out of time now.

(haruspex - just saw your last message, no time to think about it now but will do so later)

(edited to remove a typo and a spurious 1st line)

 

[SeventhSigma]

Is there a general strategy to finding recurrence relationships? Or is it more of an art than science?

 

[ClifDavis]

Is there a general strategy to finding recurrence relationships? Or is it more of an art than science?

Yes, but I don't know what it is. :-|

There is an advanced study of recurrence relationships and solving difference equations in general. Some of which is then used in solving certain types of differential equations.

I think that haruspex may be more familiar with some of the general theory than I am.

 

[ClifDavis]

I've been working on convergent lines with you ClifD.
My 7-term recurrence formula is surely the same as yours. In homogeneous form, the coefficients for G(n-1) down to G(n-7) to generate G(n) are:
1, 0, +2, -1, -1, -1, +1.
But what about the inhomogeneous term (25*2^(n-7)-1)?
I claim that if we generate a sequence H(n) with suitable starting values H1 to H7 from the above relation all we need to do to get G(n) is add:
n + 5*(2^n)/9
The 7 starting values for H(n) are simply those needed to make G(1) to G(7) right; and it works!
H[1, 7] = -19/9 -38/9 -67/9 -98/9 -142/9 -203/9 -280/9
Applying the homogeneous recurrence relation for the next 7 gives:
H[8, 14] = -380/9 -517/9 -701/9 -934/9 -1247/9 -1675/9 -2225/9
Adding in n + 5*(2^n)/9 to each we get
G[1, 7] = 0 0 0 2 7 19 47
as arranged, and beyond that:
G[8, 14] = 108 236 501 1045 2149 4378 8869

The nice thing about having a homogeneous relation is that we can accelerate the matrix multiplication. The matrix is now constant, so we can form high powers of it quickly by squaring repeatedly (applying modulo 1E9 as we go). If you want a power of M other than a power of 2 then just form a product of selected generated powers along the way, according to the binary bit pattern of the target power.

For the purposes of taking the result modulo 1E9, note that 5/9 mod 1E9 is 444444445.
I'm sure something clever can be done with 2^n mod 1E9 (for n >= 9).

Dammit, I had a free hour and just tried to post a longish comparison of our two suggestions and then when I went to submit it claimed I wasn't logged in. though it let me answer SeventhSigma just before. And the post seems to be irretrievable. :-(

Very aggravating

And now I don't have a spare hour.

 

[ClifDavis]

I've been working on convergent lines with you ClifD.
My 7-term recurrence formula is surely the same as yours. In homogeneous form, the coefficients for G(n-1) down to G(n-7) to generate G(n) are:
1, 0, +2, -1, -1, -1, +1.
But what about the inhomogeneous term (25*2^(n-7)-1)?
I claim that if we generate a sequence H(n) with suitable starting values H1 to H7 from the above relation all we need to do to get G(n) is add:
n + 5*(2^n)/9
The 7 starting values for H(n) are simply those needed to make G(1) to G(7) right; and it works!
H[1, 7] = -19/9 -38/9 -67/9 -98/9 -142/9 -203/9 -280/9
Applying the homogeneous recurrence relation for the next 7 gives:
H[8, 14] = -380/9 -517/9 -701/9 -934/9 -1247/9 -1675/9 -2225/9
Adding in n + 5*(2^n)/9 to each we get
G[1, 7] = 0 0 0 2 7 19 47
as arranged, and beyond that:
G[8, 14] = 108 236 501 1045 2149 4378 8869

The nice thing about having a homogeneous relation is that we can accelerate the matrix multiplication. The matrix is now constant, so we can form high powers of it quickly by squaring repeatedly (applying modulo 1E9 as we go). If you want a power of M other than a power of 2 then just form a product of selected generated powers along the way, according to the binary bit pattern of the target power.

For the purposes of taking the result modulo 1E9, note that 5/9 mod 1E9 is 444444445.
I'm sure something clever can be done with 2^n mod 1E9 (for n >= 9).

Okay, try #2 and I'll try to be a bit shorter this time.

SeventhSigma, just in case it isn't clear, haruspex is looking at the family of functions that have the same recurrence formula as Count except that they are missing the final two terms 25*2^(n-7)-1. Based on some of that theory I mentioned, he has determined that there should be such a function H(n) so that H(n)=Count(n)-n-5/9(2^n) and
H(n)=H(n-1)+2H(n-3)-H(n-4)-H(n-5)-H(n-6)+H(n-7). He used the known first seven values of Count(n) to get the first seven values of H(n).

Cutting the exposition short this time, my approach sets up a 9 element vector, (0,0,0,2,7,19,47,2,1)^T and use powers of M^7 to update it, where

0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 = M
0 0 0 0 0 0 1 0 0
1 0 2 -1-1 -1 1 0 0
0 0 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0 1

is a 9x9 matrix and I think you can see where M comes from.

His procedure is more compact starting with the vector (-19/9,-38/9,-67/9,-98/9,-142/9,-203/9,-280/9)^T and using powers of M^7 to update it where now M is a 7x7 matrix

0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0 = M
0 0 0 0 0 1 0
0 0 0 0 0 0 1
1 0 2 -1-1 -1 1

Obviously his procedure should take only about half as long as mine all else being equal, though of course all is not perfectly equal, but close. His does require adding n + 5/9*(2^n) back on at the end, but still his approach retains a substantial advantage. My suggestion is simple to implement in mod(1000000000) or indeed mod(anything) as you just perform the multiplication and addition mod(1000000000). No other arithmetic is involved. If you are using his technique it's handy to know that 1/9=888888889(mod 1000000000) as
9*888888889=8000000001=1(mod 1000000000).

 

[SeventhSigma]

I do believe that works... really awesome. I feel like I've been exposed to some sort of mathematical wizardry here! thank you guys... I have much to learn

 

[haruspex]

Is there a general strategy to finding recurrence relationships? Or is it more of an art than science?

It's a bit of both. Let me summarise the steps I went through.
First, I simplified the problem to one I thought should be easier to handle while still retaining essential features: sum of subset >= max in set (A(N)). If the subset had A(N) you were done; if not, we could represent the target as >= A(N-1)+A(N-3). Or we could think of that as dropping A(N) from the set, so now we had a target of A(M)+A(M-2) out of the set {..., A(M)}, where M = N-1. Again, either we used A(M) or we didn't. Repeating this process produced a set of relationships between different variations of the problem, i.e. different targets based on different combinations of high order elements of the set.
So now I had a set of simultaneous equations, but in which the unknowns were snapshots out of entire sequences (C(n), D(n) etc.). It wasn't hard to get this down to the 2 you saw, C(n) and D(n), and then to find how to map from these to the desired G(n).
Having obtained a recurrence relation of the form:
G(n) = some linear combination of G(n-1)...G(n-k) + f(n)
the next step is to consider just the homogeneous piece, i.e. throw away the f(n).
The reason is that if you have any solution G of the full equation and a solution H of the homogeneous equation then G+H is also a solution of the full equation. So armed with all possible solutions of the homogeneous and one of the inhomogeneous you can get all solutions of the inhomogeneous.
To solve the homogeneous in normal arithmetic just assume G(n) = λⁿ for some unknown constant, λ. This produces a polynomial in λ. The general solution is then a linear combination of these different roots each raised to n. But this wouldn't work mod 1bn - the polynomial had no roots. So I could find nothing better than to represent the relation as a matrix, as ClifD had already done.
But there still remained the inhomogeneous part, f(n), which had the form a.2ⁿ + b. The trick here was to treat the two pieces separately.
For the +b, it looked like it should be linear. So I just wrote down G(n) = c.n, substituted in the full equation and found c.
For the a.2ⁿ, G(n) = m.2ⁿ was the obvious choice.
At this point it looked strange because m was a fraction, but I trusted it would all come out in the wash.
Finally, I needed to kick the H sequence off in such a way that
G(n) = H(n) + c.n + m.2ⁿ
matched the starting values of G. I puzzled over that for a while, but it's trivial! Just set H(n) = G(n) - c.n - m.2ⁿ for n = 1 to 7.

HTH

 

[haruspex]

Obviously his procedure should take only about half as long as mine all else being equal, though of course all is not perfectly equal, but close. His does require adding n + 5/9*(2^n) back on at the end, but still his approach retains a substantial advantage.

The main advantage is that M becomes constant. This allows enormous acceleration. To compute P = M^k only requires log(k) steps instead of k steps.
P = I; // identity matrix
while (k>0) {
if ((k&1) > 0) P *= M;
M *= M;
k >>= 1;
}

 

[ClifDavis]

The main advantage is that M becomes constant. This allows enormous acceleration. To compute P = M^k only requires log(k) steps instead of k steps.
P = I; // identity matrix
while (k>0) {
if ((k&1) > 0) P *= M;
M *= M;
k >>= 1;
}

Yep, though he seemed to be familiar that part of it okay up front and was fine with the idea as applied to A(k).

I appreciate the mini-tutorial on solving homogeneous recurrence relationships by the way. I've probably seen that at one point or another but have long since forgotten. Just remembered that it could be done, not how.

Clif