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

[Mandlebra]

Ah are correct, I misread. Good thread though with a nice topic

 

[SeventhSigma]

I don't understand how this lambda equation was arrived at or how you solve it. Where does the k term come from? Are all lambdas the same since we're looking at the same equation here (λ^3 +/- λ - 1 = 0)? Trying to piece it together but I am not sure what I'm doing.

 

[haruspex]

The lambdas are roots of a 6th order polynomial, so there are in principle 6 of them.
The polynomial is (λ^3 + λ - 1)(λ^3 - λ - 1), so the roots are those of the two cubics (λ^3 + λ - 1) and (λ^3 - λ - 1). Each has one real root and a complex pair.
The importance of these numbers is that if C(n) is a solution of the recurrence relation then C(n) + λ^n is also, but only for these 6 values of λ. This means that we can generate all possible solutions for C(n) by starting with anyone solution and adding combinations of terms like λ^n. Then we plug in the boundary conditions (the first few values) to find the right combination of these terms.
The real roots are 0.6823.., 1.3247.. The complex roots are -.3412+/-i*1.1615, -.6624+/-i*0.5623.
I'm not sure how the cancellation of the imaginary parts will happen. I'm going to assume that it happens separately within each pair, i.e. the imaginary parts of λ^n will cancel with the contribution from its conjugate root. This means the coefficients will be the same for both members of the pair. That gets us down to only 4 terms to worry about.
The easiest way to extract the real components is to write the complex roots in r.e^iθ form. Then the real part of λ^n is r^n.cos(n*θ).
The table of lambda powers therefore starts:
n 1 2 4 5
0 1 1 1 1
1 1.32 1.32 0.68 0.68
2 1.75 1.44 0.47 -0.88
3 2.32 1.07 0.32 -2.44
4 3.08 -0.15 0.22 -1.73
5 4.08 -2.61 0.15 2.07
6 5.4 -6.6 0.1 5.97
7 7.16 -12.09 0.07 4.39
8 9.48 -18.35 0.05 -4.85
9 12.56 -23.59 0.03 -14.58
10 16.64 -24.5 0.02 -11.1
It remains to find four constant coefficients to multiply each column by, and one more additive constant. Adding up those 5 terms for each row, plus ((2^n)-1))*5/9 + n, should then give the required answers. We need to use the known values for G(1) to G(5) to find these. So that's an exercise is simultaneous linear equations with 5 unknowns. (As I mentioned, the additive constant can actually be calculated from the four coefficients and the lambdas, so we can reduce it to four unknowns.)
I can have a go at that later if you like.

 

[SeventhSigma]

Would this method be workable for solutions where n>10^18, modulo 1 billion? I ask because I am wondering how precise the roots would need to be?

 

[ClifDavis]

Fwiw, I had a go at this simpler problem:
Sn = {A(1), .. , A(n)}, where the A(n) satisfy the recurrence relation A(n) = A(n-1) + A(n-3), etc.
How many subsets of Sn sum to A(n) exactly?

The value of the question isn't in obtaining the actual value of of the number of such subsets of Sn, but rather in the fact that in order to do so, you have to be able to characterize the subsets that Sn counts and it's what you have to do to accomplish that which gives you the tools to answer the original question.

I can't even solve that yet. The problem is that some such subsets cannot be obtained by repeated application of the recurrence relation to break down the target sum. E.g. A(1)+A(2) = A(3).

And you put your finger on the significant question. Can all such subsets be obtained by repeated application of the recurrence relation? And as you correctly point out, the answer is no, as a(1)+a(2)=a(3) which certainly cannot be obtained by repeated application of the recurrence relation. Nor is this a lone exception. For example a(1)+a(2)+a(5)=a(6) cannot be obtained by repeated use of a(n)=a(n-1)+a(n-3). But we can go a(6)=a(6-1)+a(6-3)=a(5)+a(3)=a(5)+a(2)+a(1).

So this leads to a new question. Can all such subsets be obtained by repeated application of the recurrence relation combined with the possible substitution of a(1)+a(2) for a(3)?

In order to answer the question we need 4 facts.

(1) The a(i) are positive. Or another words if n>0 then a(n)>0.

(2) The a(i) are increasing, a(1)<a(2)<a(3)<a(4)<... Or in other words if n>1 then a(n-1)<a(n).

(3) For n>0, the sum of the first n values, a(1)+...+a(n) is less than a(n+3).

[[If n=1, the expression on the left is intended to have only one term as a(n) is a(1). I would use summation notation to be clearer, but have no appropriate tool to do that.
Notice that this third item can also be stated as:
For n>3, the sum of the first n-3 values, a(1)+...+a(n-3) < a(n).]]

(4) for n>0, a(1)+...+a(n) <a(n+1)+a(n+2)

[[or for n>2 a(1)+...+a(n-2)<a(n-1)+a(n)]]

 

[ClifDavis]

The a(n) are positive, ie. For n>0, a(n)>0.

Our definition of the a function is:
a(1)=1
a(2)=2
a(3)=3
and for n>3, a(n)=a(n-1)+a(n-3).

Notice that a(0) and a(-1) etc. are not defined. We might be able to use the recurrence relationship to define them, but we don't. There is also the assumption that n is an integer. We don't define a(1.5).

Suppose the a(n) are not all positive. If for some integer we have a zero or negative result, ie. a value of a(n) which is not positive, then since they are integers, there is a smallest value, let's call it k, for which a(k)>0 is not true.

Now k is not 1 or 2 or 3 as
a(1)=1>0
a(2)=2>0
a(3)=3>0
and so k>3.

But this means a(k)=a(k-1)+a(k-3).

Since k>3 then k-1>3-1=2>0 (or k-1>0 ) and k-3>3-3=0 (k-3>0). So a(k-1) and a(k-3) are defined. But since -1<0 k-1<k. And likewise k-3<k. Now k was the smallest integer for which a(k)>0 is false so we know that a(k-1)>0 and a(k-3)>0. But this means that a(k-1)+a(k-3)>0+0=0. But from the recurrence relationship a(k) is a(k-1)+a(k-1), and so a(k)>0 contrary to our assumption. And this means that a(k) is not the smallest value of k that isn't positive, and so there is no smallest integer k such that a(k) is not positive and so there aren't any. Which is to say they are all positive.

 

[ClifDavis]

The a(i) are increasing, if n>1 then a(n-1)<a(n).

Well for n=2 then 1<2 or a(1)<a(2 or a(2-1)<a(2) or a(n-1)<a(n) is true for n=2.
For n=3 we know 2<3 so a(2)<a(3) or a(3-1)<a(3) or a(n-1)<a(n) for n=3.

Assume there is an integer n>1 for which a(n-1)<a(n) is not true. Let i be the smallest such that i>1 but a(n-1)<a(n) is false.
We have already seen that i is not 2 or 3 because it would be true for them. So i>3. This means that i-1>2>0 and i-3>0. Which means a(i-1) and a(i-3) are defined and a(i-1)>0 and a(i)-3>0. Or as I prefer, 0<a(i-3). So a(i-1)+0<a(i-1)+a(i-3). But a(i-1)+0=a(i-1) and as we all know since i>3, a(i-1)+a(i-3)=a(i), which gives us a(i-1)<a(i), contrary to our assumption. So there no such smallest i, which means there is no such n and the a(i) are strictly increasing.

 

[ClifDavis]

For n>0, the sum of the first n values of a(i) is less than a(n+3).

I like to state it that way, though when I use it, its usually in the form, if n>3 then the sum of the first n-3 values of a(i) is less than a(n).

For n=1 the first 1 values of a(i) is a(1) and it's sum is a(1)=1. a(1+3)=a(4)=4. It's certainly the case that 1<4, and so it's true for n=1.

Let's assume that it's true for some integer k>0, ie. the sum of the first k values of a(k) is less than a(k+3). Or as I prefer to write it, a(1)+...+a(k)<a(k+3). Since k>0 then k+1 >0 and so a(k+1) is defined and we can add it to both sides of our inequality to get a(1)+...+a(k)+a(k+1)<a(k+3)+a(k+1). Since k>0, k+4>4>3, and so from our recurrence relationship we know that a(k+3)+a(k+1)=a(k+4).
And so we have the sum of the first k+1 values of a(i), a(1)+...+a(k+1)<a(k+3)+a(k+1)=a(k+3+1).

So we know it's true for k=1 and if its true for k, then it's true for k+1, so by induction it's true for all integer k>0 or if you prefer, for all integer n>0.

 

[ClifDavis]

For n>0, a(1)+...+a(n) <a(n+1)+a(n+2). For n=1 this is true as a(1)< a(1+1)+a(1+2) or another words 1<2+3. This is another case where a(1)+...+a(n) is intended to show one term when n=1. I apologize for not using summation notation and can see that I'm going to have to learn MathXML.

For n>1 then n+2>3 and so a(1)+...+a(n-1)<a(a+2). But since the a(i) are strictly increasing, a(n)<a(n+1). All of which means a(1)+...+a(n-1)+a(n)<a(n+1). And so it's true for all n>0,

 

[ClifDavis]

Let Sn={a(1),...,a(n)} for any n>0. How do we characterize the subsets of Sn that add up to a(n)? Can we get a subset of Sn for any n, such that the elements of the subset add up to a(n) but the elements cannot be derived from the recurrence relationship and a(3)=a(2)+a(1) [substituting a(2)+a(1) for a(3)]?

Let i be the smallest integer such that Si has a subset where all the elements of the subset add up to a(n) but the set is not {a(n)} and cannot be derived from {a(n)} by repeated application of the recurrence relationship [that for n>3, a(n-3)+a(n-1)=a(n)] and the fact that a(1)+a(2)=a(3). Then i<6.

Assume that i>5 and i is the smallest integer so that there is a subset S'i of Si such that the elements of S'i add up to a(n), but S'i is not {a(n)} and cannot be derived from {a(n)} with repeated applications of the recurrence relationship and a(1)+a(2)=a(3).

(1) It is not the case that a(n) is an element of S'i.
If a(n) were an element then either a(n) is the only element and S'i={a(n)} contrary to assumption or there are other elements a(r1),...,a(rj), but each of the elements of Si is positive and so a(r1)+...+a(r2) >0 and adding a(n) to both sides of the inequality give us a(r1)+...a(rj)+a(n)>a(n) contrary to the assumption that the elements add up to a(n).

(2) At least one of a(i-1) and a(i-2) is an element of S'i.
Since i>5 then a(i-1) and a(i-2) exist. Assume that neither a(i-1) nor a(i-2) is in S'i. But since a(i) is not in S'i, we see that all the elements of S'i are in S(i-3). (S(i-3) exists since i>5>3.) But even if all the elements of S(i-3) were added up, a(1)+...+a(i-3), since i>3 a(1)+...+a(i-3)<a(i) and so as the elements of S(i-3) are all positive, the elements of S'i cannot add up to a(i). Therefor at least one of a(i-1) or a(i-2) is an element of S'i.

(3) a(i-1) and a(i-2) are not both elements of S'i.
Since i>5, i>3 and so a(i)=a(i-1)+a(i-3). Since i>3, i-2>1 and so a(i-3)<a(i-2). Or the same thing, a(i-2)>a(i-3). Adding a(i-1) to both sides give us a(i-1)+a(i-2)>a(i-1)+a(i-3)=a(i). Since a(i-1) and a(i-2) add up to more than a(i) and all elements of S'i must be positive, if both a(i-1) and a(i-2) were elements of S'i then the sum of its elements must be more than a(i) contrary to assumption. Therefor a(i-1) and a(i-2) are not both elements of S'i.

(4) S'i is not {a(i-3),a(i-1)}.
While this would add up to a(i), it can be derived from {a(i)} with a single application of the recurrence relationship, contrary to assumption.

(5) a(i-1) is not in S'i.
Assume a(i-1) is in S'i and a(i-2) is not. Then as a(i-1)<a(i), it must be the case that there are other elements of S'i, a(r1),...,a(rj) such that a(r1)+...+a(rj)+a(i-1)=a(i). But a(i)=a(i-1)+a(i-3) so a(r1)+...+a(rj)+a(i-1)=a(i-1)+a(i-3) and subtracting a(i-1) from both sides,a(r1)+...+a(rj)=a(i-3). Since neither a(i-2) nor a(i) are in S'i , they're also not in {a(r1),...,a(rj)} and so {a(r1),...,a(rj)} is a subset of S(i-3)={a(1),...,a(i-3)}. Notably it's a subset of S(i-3) whose elements sum to a(i-3). Furthermore {a(r1),...,a(rj)} cannot be derived from {a(i-3)} by the use of the recurrence relationship and the substitution of a(2)+a(1) for a(3), since if it could then {a(r1),...,a(rj),a(i-1)} could be derived in the same way from {a(i-3),a(i-1)}. But S'i={a(r1),...,a(rj),a(i-1)} and {a(i-3),a(i-1)} can be derived from {a(i)} using the recurrence relationship, and so S'i could be derived from {a(i)} contrary to our definition of S'i. So, i-3<i and S(i-3) has a subset {a(r1),...,a(rj)} which cannot be derived from {a(i-3)} using the recurrence relation and possibly substituting a(2)+a(1) for a(3). But this contradicts our assumption that i is the smallest integer with that property, so if we are to preserve that assumption we must conclude that in fact a(i-1) is not in S'i.

(6) a(i-2) is in S'i.
This is straightforward. By (2) a(i-1) or a(i-2) is in S'i. By (5), a(i-1) is not in S'i. And so a(i-2) is in S'i.

(7) {a(i-4),a(i-3),a(i-2)} is not S'i.
Since i>5 a(i-4),a(i-3),and a(i-2) all exist and {a(i-4),a(i-3),a(i-2)} is a subset of Si. It's elements do add up to a(i) [see the derivation that follows immediately]. However from {a(i)} we can derive {a(i-3),a(i-1)} by applying the recurrence relationship to a(i), and then by applying it to a(i-1), we get {a(i-4),a(i-3),a(i-2)} and since it is derivable from {a(i)} it cannot be S'i.

(8) Both a(i-4) and a(i-3) cannot be in S'i.
By (6), a(i-2) is in S'i. If a(i-3) and a(i-4) are as well then either there are no additional elements in S'i which contradicts (7) or there are and since they are positive, the elements of S'i will add up to more than a(i-4)+a(i-3)+a(i-2) = a(i), contrary to the definition of S'i.

(9) a(i-4) and a(i-3) cannot both be absent from S'i.
At this point we know from (1) that a(i) cannot be in S'i. We know from (5) that a(i-1) cannot be in S'i. We know from (6) that a(i-2) is in S'(i). Assume that a(i-4) and a(i-3) are both absent from S'i. Since S'i is a subset of Si the the largest value that S'i could sum to under our assumptions is a(1)+...a(i-5)+a(i-2). But i>5 and so i-3>2 and so a(1)+...a(i-5)<a(i-4)+a(i-3). Adding a(i-2) to both sides we see that a(1)+...a(i-5)+a(i-2)<a(i-4)+a(i-3)+a(i-2)=a(i) and the elements of S'i cannot add up to a(i). But this violates our definition of S'i and so either a(i-4) or a(i-3) must be an element of S'i.

(10) a(i-4) is not an element of S'i.
Assume a(i-4) is in S'i and a(i-3) is not. Then it must be the case that there are other elements of S'i, a(r1),...,a(rj) such that a(r1)+...+a(rj)+a(i-4)+a(i-2)=a(i). But a(i)=a(i-4)+a(i-3)+a(i-2) so a(r1)+...+a(rj)+a(i-4)+a(i-2)=a(i-4)+a(i-3)+a(i-2) or subtracting a(i-4)+a(i-2) from both sides,a(r1)+...+a(rj)=a(i-3). Since neither a(i-2) nor a(i) are in S'i , their also not in {a(r1),...,a(rj)} and so {a(r1),...,a(rj)} is a subset of S(i-3). Once again it's a subset of S(i-3) whose elements sum to a(i-3). Furthermore {a(r1),...,a(rj)} cannot be derived from {a(i-3)} by the use of the recurrence relationship (and/or a(3)=a(2)+a(1)) since if it could then {a(r1),...,a(rj),a(i-1)} could be derived in the same way from {a(i-3),a(i-1)}. But S'i={a(r1),...,a(rj),a(i-1)} and {a(i-3),a(i-1)} can be derived from {a(i)} using the recurrence relationship, and so S'i could be derived from {a(i)} contrary to our definition of S'i. So, i-3<i and S(i-3) has a subset {a(r1),...,a(rj)} which cannot be derived from {a(i-3)} using the recurrence relation and a(3)=a(2)+a(1). But this contradicts our assumption that i is the smallest integer with that property, so if we are to preserve that assumption we must conclude that in fact a(i-4) is not in S'i.

(11) The big contradiction. a(i-3) cannot be an element of S'i either.
Assume a(i-3) is in S'i and a(i-4) is not. Then as we also know a(i-2) is in S'i and a(i-1) and a(i) are not, there must be other elements of S'I, a(r1),...,a(rj) such that a(r1)+...+a(rj)+a(i-3)+a(i-2)=a(i). But a(i)=a(i-4)+a(i-3)+a(i-2) so a(r1)+...+a(rj)+a(i-3)+a(i-2)=a(i-4)+a(i-3)+a(i-2). This time we subtract a(i-3)+a(i-2) from both sides to obtain a(r1)+...+a(rj)=a(i-4). The elements on the left side of the equation all came from S'i and since they were not a(i-3) or a(i-2) and could not be a(i-1) and a(i) because those elements weren't in S'i then {a(r1),...,a(rj)} is a subset of S(i-4) which has elements that add to a(i-4). {a(r1),...,a(rj)} cannot be derived from {a(i-4)} by the use of the recurrence relationship and the substitution of a(1)+a(2) for a(3) since if it could then S'i={a(r1),...a(rj),a(i-3),a(i-2)} could be similarly derived from {a(i-4),a(i-3),a(i-2)} which can be derived from {a(i-3),a(i-1)} by the recurrence relationship and can in turn be derived from {a(i)} by the same relationship. This would violate our definition of S'i and so no such derivation of {a(r1),...,a(rj)} is possible. But now since i-4<i, we have a violation of our assumption that i is the smallest such value and so our assumption that a(i-3) is in S'i must be wrong.

(12) The big finish.
We assumed that i was the smallest integer for which there was a subset, S'i of Si, such that the elements of S'i added up to a(i) but S'i was distinct from {a(i)} and could not be derived from {a(i)} using some combination of the recurrence relationship a(n-3)+a(n-1)=a(n) for n>3 and a(3)=a(1)+a(2) and that i>5.
We deduced that:
(8) a(i-4) and a(i-3) cannot both be in S'i.
(9) Either a(i-4) or a(i-3) must be an element of S'i.
(10) a(i-4) is not an element of S'i.
(11) a(i-3) is not an element of S'i.
Our only possible conclusion? If such an i exists then it is not the case that i>5 and so i<6.

 

[ClifDavis]

We want to characterize the subsets of Sn that add up to a(n). One possible useful way of characterizing them is as the subsets that can be derived from {a(n)} by the recurrence relationship used in defining a, (for n>3, a(n)=a(n-1)+a(n-3) and the substitution of a(1)+a(2) for a(3) based on the fact that a(1)+a(2)=a(3).

Is this characterization correct. Or is there some value of n with a subset of Sn we will designate as S'n whose elements add to a(n) but cannot be derived from {a(n)} in that way. If there is any such integer n, then there is a smallest such integer i. We have shown that if such an i exists then i<6.

By the examination of those possible subsets, no such i exists.

The examination is left as an exercise for the reader. :-D
No, really.

Well okay, not really. We can run through the possible combinations looking for surprises fairly quickly. The five values we have to worry about are a(1),a(2),a(3),a(4),a(5) which happen to be 1,2,3,4,6.
1+2=3 or a(1)+a(2)=a(3). This would be the big surprise if we were depending totally on the recurrence relationship, but we're not.
1+3=4 or a(1)+a(3)=a(4) which comes directly from the recurrence applied to a(4).
1+4=5 which isn't in S1, S2, S3, S4 or S5.
1+6=7 which isn't in our Si's
2+3=5 which isn't in our Si's
2+4=6 or a(2)+a(4)=a(5) which comes from the recurrence applied to a(5).
2+6=8 which isn't in our Si's
and the rest of the pairs aren't in our Si's
1+2+3=6 or a(1)+a(2)+a(3)=a(5) which comes from applying the recurrence twice, once to a(5) and then to a(4).
And all the other possibilities give us totals not in our Si's.

So no surprises and there is no such smallest i with the property Si contains a subset distinct from {a(i)} that adds to a(i) but the subset cannot be derived from {a(i)} using the recurrence relationship and a(3)=a(2)+a(1).

But since there is no smallest value i for which it is true, it is also not true for any integer n. In short we have successfully categorized the subsets of Sn that add up to a(n) and so we can use haruspex's type of approach to count the number of subsets of Sn which total a(n).

But doing so is of minimal help in solving the problem we're interested in. What is very useful and the reason for suggesting looking at this problem first is that it has forced us to develop the machinery that we need to tackle the actual problem.

 

[ClifDavis]

I took a look at haruspex's latest solution. Looking at C(n) and D(n) is much more clever and compact that what I did. I like it.

But I have two comments. The first is that for the actual problem C(n) overcounts the new subsets whose totals exceed A(n) we are actually interested in. We are not actually interested in the subsets where A(n) is added in, rather we want those without A(n) whose total exceeds A(n) and then we will toss A(n) to be the largest element. This is not a problem because we can leave the definition of C(n) alone and then subtract 2^(n-1)-1 back off. The other thing is that what we want all the values not just the newest ones, but as haruspex pointed out sometime back this is easy to get around. We just carry forward the older results.

We have the function Count(n) that give the answer we're looking for. We have Countnew(n) that gives the new subsets from increasing n by 1.

Then for n>1, Count(n)=Count(n-1)+Countnew(n).
And to start it off we will say Count(1)=0.

For Countnew we have Countnew(n)=C(n)-2^(n-1)+1 for n>1 and Countnew(1)=0.


And now for the second comment. The derivation of the relationships from the initial definition of what C(n) and D(n) means is wonderful. But those relationships only work once n has a sufficient size. Does C(2)= 2^(2-1)-1+2^(2-3)+C(-1)+D(-1) = 2-1+1/2 + C(-1) + D(-1) = 1.5+undefined stuff? I'm pretty sure that the 1.5 isn't very relevant to the logic you used to obtain the relationship.

Instead we need definitions for C(1), C(2), C(3) and maybe more before n gets big enough for the full relationship to kick in. Similarly for D(n). But in finding the solutions on the bottom you assumed that the relationships were true everywhere which is not the case and is why it gives you C(2)=4*7/9 = 3 1/9 instead of C(2)= 1, the number of subsets of S2 with a total over a(2)=2.

Notice that Countnew(2)=C(2)-2(n-1)+1=1-2+1=0.
Count(2)=Count(1)+Countnew(2)=0+0=0 which is correct.

Now what I did was work out the recurrence relation for Count(n) directly but it's ugly looking and I wind up having to assume that n>12, so I have to give 12 values of Count before the full relationship kicks in. On the other hand, the process of developing the recurrence relationship makes coming up with the 12 values fairly easy. But I'm now out of time and it will be Thursday before I can start typing on this again. :-(

Clif

 

[ClifDavis]

SeventhSigma, Sorry, I forgot to point out that this is not quite the problem as you stated it, but that it should be mappable to it fairly easily.
First, if you exclude the use in the sum of the top term in the set, that just subtracts 2^(n-1)-1 possibilities. That gets us to the version ClifDavis considered. (I probably could have got straight to that by modifying the argument a little. You might care to try that.) Now you have to sum the counts for n = 1 to N to get the solution to the correct version.

And there were some messages I missed reading. I see you already pointed this out. Well, I was going to go to bed, but who needs sleep?

 

[ClifDavis]

I guess I am just not understanding how generating functions work here because I am trying to solve this for a very large n with modulus, and I worry that using roots will result at in decimal values that will lack precision (assuming that I even figure out how that approach works)

Okay. If you are trying to solve this for a very large n with modulus m then a single recursively defined function is the way to go. The reason is that you can then set up your recurrence relationship as a matrix operation and take powers of the matrix mod m fairly easily.

Let's do it with the A(n) recurrence relationship as an example.

We start with our initial values as a vector (A(1),A(2),A(3)) and then set up a matrix M which when we multiply by to get the next three values (A(4),A(5),A(6)) and that in general if we have any successive 3 values (A(i),A(i+1),A(i+2)) multiplication by M will give us a vector with the next three values (A(i+3),A(i+4),A(i+5)). The recurrence relationship is captured by the following 3x3 matrix.

1 1 1

0 1 1 = M

1 1 2


Perform the matrix multiplication of the vector (1 2 3) by the Matrix and you will see that you get (4,6,9).

Where did this matrix come from? Well you will notice that multiplication by the first column of M performs the recurrence formula directly by adding the first and third term of the vector. The next row add the previous term as given by the previous column vector to two terms before which is given by a column vector with 1 in the second term and 0 elsewhere and the sum is the 2nd column vector of M. The last column vector of M is derived by taking the column vector of the previous term and adding a column vector with zeros except for the 3rd entry, giving us the last column of M. In other words M is derived from the recurrence formula in a fairly straightforward way.

Now suppose we are interested in A(100). We start with (A(1),A(2),A(3)) in our vector and after k multiplication by M obtain (A(3k+1),A(3k+2),A(3k+3)). Since 100 is 3*33+1, we want the first element of the vector after 33 multiplications by M. But I am not going to multiply by M 33 times. Instead I am going to multiply the Matrix M by itself to get M^2. Multiplying a vector times M^2 gives the same result as multiplying by M twice. I multiply M^2 by itself to get M^4, and multiply that by itself to get M^8. Then I get M^16 and then M^32. So to find the result I want I multiply (1 2 3) by M^32 and then that vector one more time by M to give the same result as multiplying by M 33 times.

Or actually I would really multiply by M to start with and then again by M^32 after calculating it, using the binary representation of 33 = 100001 to guide me when to multiply the vector as I calculate the ever larger powers of M. In general to take M to a k power will take me log(k) matrix multiplication and a worst case of log(k) vector multiplications, where we are taking the log base 2.

Unfortunately the numbers get very large very quickly when dealing with large n and hence with large k. But if we are doing all our matrix arithmetic mod m, then it really isn't a problem.

 

[SeventhSigma]

I know that finding the modular exponentiation of a matrix can find solutions to recurrences, but in this case I was not sure how to do it when there were multiple, interlaced recurrences involved, since c(n) and d(n) meld into each other and g(n) relies on c(n). It didn't seem as simple as just raising a singular matrix to higher powers, taking the modulus each step.

The recurrences I refer to: https://www.physicsforums.com/showpost.php?p=3922972&postcount=55

 

[ClifDavis]

OK, here's my attempt at the actual problem. Methods and results largely the same.

Let C(n) be the number of subsets of Sn that sum to more than A(n).
Let D(n) be the number of subsets of Sn that sum to more than A(n)+A(n-1).

Starting with a summation target of A(n)+1 (or higher):
1. Suppose we use A(n). We now only have to use one other, i.e. any of 2^(n-1)-1 subsets. OTOH,
2. if we don't use A(n) we know we must use either A(n-1) or A(n-2) or both.
2a. If we use both then we can use any combination of A(1) to A(n-3), 2^(n-3) subsets.
2b. If we use A(n-1) but not A(n-2) then we have a remaining target of A(n)+1-A(n-1) = A(n-3)+1, for which there are C(n-3) possibilities.
2c. If we use neither A(n) nor A(n-1) then we have a target of A(n)+1 = A(n-2)+A(n-3)+A(n-4)+1. We must use A(n-2). That leaves a target of A(n-3)+A(n-4)+1, for which there are D(n-3) possibilities.
Putting this together:
C(n) = 2^(n-1)-1 + 2^(n-3) + C(n-3) + D(n-3)

Similarly, with D(n), we can use A(n), leaving a target of A(n-1)+1; or not use A(n), leaving a target of A(n)+1 = A(n-2) + A(n-3) + A(n-4) + 1.
D(n) = C(n-1) + D(n-3)

Okay, I have now convinced myself that your general equations for C(n) and D(n) work for n>3.

I prefer to express C(n)= C(n-3)+D(n-3)+5(2^(n-3))-1 but that's a matter of taste.

So 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(1)=0
Count(n)=Count(n-1)+Countnew(n) for n>1

Now that I look at it, the definition of Countnew could be incorporated directly into Count and Countnew could go away. Additionally it would make better sense if Countnew was defined by old values and not current values.

Okay, kill the previous definition of Countnew and Count and we will redefine Count as
Count(1) = 0
Count(2) = 0
Count(3) = 0.
Count(n)=Count(n-1)+C(n-3)+D(n-3)+2^(n-3)

Ok let's give it a try and construct a table and then maybe see if we can construct a suitable matrix version.

n 2^(n-3) C(n) D(n) Count(n)
1 0.25 0

Arg. Falling asleep at the keyboard. Time to quit. Back Thursday.

 

[ClifDavis]

I know that finding the modular exponentiation of a matrix can find solutions to recurrences, but in this case I was not sure how to do it when there were multiple, interlaced recurrences involved, since c(n) and d(n) meld into each other and g(n) relies on c(n). It didn't seem as simple as just raising a singular matrix to higher powers, taking the modulus each step.

The recurrences I refer to: https://www.physicsforums.com/showpost.php?p=3922972&postcount=55

Well I may go back and give the derivation of just Count as a single recurrence, but now I think on it a single vector should be able to to show all the different values, and the Matrix update them all.

But I really have to get some sleep before it's time to get up.
Sorry.

 

[ClifDavis]

As I was going to bed, it hit me that the matrix doesn't have to update 3 values at once. The big savings is in being able to take the powers of the Matrix and skipping all the internal multiplications.

We start with an original vector of

(0,0,0,0,1,3,0,0,1,2,1) where the first element of our vector is count(1). To find count(n) we multiply by M^(n-1) and take the first element of our vector.

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

I'm 3/4 asleep and won't swear I didn't make a mistake.

At any point the vector should be (count(i).count(i+1),count(i+2),c(i),c(i+1),c(i+2),d(i),d(i+1),d(i+2),2^i,1) and our initial vector is for i=1.

- Clif

 

[haruspex]

You mean, to the nearest billion?
All the roots of absolute value less than 1 will become completely irrelevant, leaving only the 1.3247 root. So once we have the coefficient for that it will be straightforward. But I think it would be a good idea to extract all the coefficients so that the correctness of the formula can be demonstrated for n up to 10.

 

[haruspex]

SeventhSigma, please clarify before I go any further: do you only want these values for large N modulo 1 billion (which would seem an odd thing to want to know), or did you mean want an answer to the nearest billion?

 

[SeventhSigma]

What I mean is that I am trying to find the last 9 digits (and so this is the same as the result modulo 1 billion) of g(large N). It is easy to see that the result explodes into huge numbers very quickly (even in your Excel output you can drag it all down and watch the last column erupt)

 

[SeventhSigma]

As I was going to bed, it hit me that the matrix doesn't have to update 3 values at once. The big savings is in being able to take the powers of the Matrix and skipping all the internal multiplications.

We start with an original vector of

(0,0,0,0,1,3,0,0,1,2,1) where the first element of our vector is count(1). To find count(n) we multiply by M^(n-1) and take the first element of our vector.

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

I'm 3/4 asleep and won't swear I didn't make a mistake.

At any point the vector should be (count(i).count(i+1),count(i+2),c(i),c(i+1),c(i+2),d(i),d(i+1),d(i+2),2^i,1) and our initial vector is for i=1.

- Clif

Just pointing out that this didn't seem to work either, testing it for N=10 the resulting vector is (0, 0, 0, 10, 13, 5, 12, 21, 10, 7424, -41) using a program I wrote a while back to find final vector = initial vector*(matrix^power) modulo m. Wondering how you go about making such a matrix/vector (I tried doing this approach from the very beginning)

 

[ClifDavis]

Just pointing out that this didn't seem to work either, testing it for N=10 the resulting vector is (0, 0, 0, 10, 13, 5, 12, 21, 10, 7424, -41) using a program I wrote a while back to find final vector = initial vector*(matrix^power) modulo m. Wondering how you go about making such a matrix/vector (I tried doing this approach from the very beginning)

I believe you have a problem in your matrix multiplication routine then. Each time the vector is multiplied by M the 10th (next to last) element should double and 7424 is not a power of 2.

When I have more than a few seconds we can go over where M comes from.

Check your matrix multiplication.

 

[SeventhSigma]

I've used my matrix multiplication procedure many other times and it hasn't failed yet, but it is still possible that something is wrong on my end. I too noticed that 7424 was not a power of 2 but this may be because I am multiplying the vector by M, so perhaps 7424 is 2^1 * some other value = 7424.

When I output the matrix after raising it to power 10-1=9, I get

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
4, 7, 8, 1, 3, 1, 0, 3, 4, 0, 0,
3, 4, 7, 0, 1, 3, 1, 0, 3, 0, 0,
6, 7, 8, 3, 1, 1, 3, 4, 1, 0, 0,
7, 11, 12, 3, 4, 1, 1, 6, 5, 0, 0,
4, 7, 11, 0, 3, 4, 1, 1, 6, 0, 0,
4, 4, 7, 1, 0, 3, 3, 1, 1, 0, 0,
242, 515, 1066, 385, 785, 1575, 210, 435, 890, 512, 0,
-8, -14, -21, -4, -7, -8, -4, -7, -11, 0, 1

I do see 2^9 = 512 in there. Does this match you?

My procedure would then take that matrix and multiply it by (0,0,0,0,1,3,0,0,1,2,1) as a column

I just tried inputting the matrix above and the vector in the site http://www.bluebit.gr/matrix-calculator/multiply.aspx
http://i.imgur.com/sPtLd.jpg
Please let me know if I've misunderstood you

 

[haruspex]

Okay, I have now convinced myself that your general equations for C(n) and D(n) work for n>3.

The recurrence relation gave the right numbers all the way to n=10 (as far as I went). See post #53 and SeventhSigma's earlier post mentioning 501.

 

[haruspex]

What I mean is that I am trying to find the last 9 digits (and so this is the same as the result modulo 1 billion) of g(large N). It is easy to see that the result explodes into huge numbers very quickly (even in your Excel output you can drag it all down and watch the last column erupt)

OK. In that case, the polynomials should be solved modulo 1 billion. I'll havde a go at that.

 

[ClifDavis]

I've used my matrix multiplication procedure many other times and it hasn't failed yet, but it is still possible that something is wrong on my end. I too noticed that 7424 was not a power of 2 but this may be because I am multiplying the vector by M, so perhaps 7424 is 2^1 * some other value = 7424.

When I output the matrix after raising it to power 10-1=9, I get

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
4, 7, 8, 1, 3, 1, 0, 3, 4, 0, 0,
3, 4, 7, 0, 1, 3, 1, 0, 3, 0, 0,
6, 7, 8, 3, 1, 1, 3, 4, 1, 0, 0,
7, 11, 12, 3, 4, 1, 1, 6, 5, 0, 0,
4, 7, 11, 0, 3, 4, 1, 1, 6, 0, 0,
4, 4, 7, 1, 0, 3, 3, 1, 1, 0, 0,
242, 515, 1066, 385, 785, 1575, 210, 435, 890, 512, 0,
-8, -14, -21, -4, -7, -8, -4, -7, -11, 0, 1

I do see 2^9 = 512 in there. Does this match you?

My procedure would then take that matrix and multiply it by (0,0,0,0,1,3,0,0,1,2,1) as a column

I just tried inputting the matrix above and the vector in the site http://www.bluebit.gr/matrix-calculator/multiply.aspx
http://i.imgur.com/sPtLd.jpg
Please let me know if I've misunderstood you

You multiplied the matrix times the transpose of the row vector? Okay, that's the problem then. I wrote the vector and matrix intending to multiply the row vector times the matrix, not the matrix times a column vector. If you are going to transpose the row vector into a column vector and put it on the right then you need to use the transpose of M as well.

So yeah, if you do that then the 512 will be multiplied by 2 and added to a bunch of zeros giving you 1024 which is what I expected to see.

 

[SeventhSigma]

I think I understand better now, but how does one go about creating M in the first place? How do you know what values are 0, 1, etc?

 

[haruspex]

OK. In that case, the polynomials should be solved modulo 1 billion. I'll have a go at that.

Hmmm.. the polynomials have no roots modulo 1 billion, not even complex ones. Don't know what this implies. Thinking...

 

[ClifDavis]

I think I understand better now, but how does one go about creating M in the first place? How do you know what values are 0, 1, etc?

I'm going to assume now that you are using the transpose of M and multiplying by a column vector. To write a column vector as a row vector I'm going to use the ^T to indicate transpose as in vectors V and V^T

We want to use the functions defined by:

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

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

That last one, you will note, looks pretty similar to the formula for C(n) except that we are subtracting back off the 2^(n-1)-1 that it overcounts and adding in the old value of count.

We want to write M so that it changes the vector
(count(i),count(i+1),count(i+2),c(i),c(i+1),c(i+2) ,d(i),d(i+1),d(i+2),2^(i+1),1)^T
to
(count(i+1),count(i+2),count(i+3),c(i+1),c(i+2),c(i+3) ,d(i+1),d(i+2),d(i+3),2^(i+2),1)^T

Since we have 3 values of the c,d, and count functions we can safely assume that i+3>3.

When we do the matrix multiplication with the old column vector, the first value of the new column vector will be the result of multiplying (dot-product) the first row of M by the old vector. We want the result to be count(i+1). count(i+1) is in the second position of the old vector. So to get that value, we can have the first row of M be the vector
(0,1,0,0,0,0,0,0,0,0,0). When we multiply it by the old vector we get 0*count(i)+1*count(i+1)+0*count(i+2)+0*c(i)+0*c(i+1)+0*c(i+2)+0*d(i)+0*d(i+1)+
0*d(i+2)+0*2^i+0*1=count(i+1) which is exactly what we wanted.

If you look back at what I gave you as M, but which is now M^T you will see (0,1,0,0,0,0,0,0,0,0,0)^T is exactly the first column.

The second row of M is what gets multiplied by the old column vector to give the second element of the new column vector. We want the second element of the new vector to be count(i+3). The third element of the old vector is count(i+3). I trust it will be no surprise to say that we write the second row of M as
(0,0,1,0,0,0,0,0,0,0,0).

The third row of M is a little trickier. We want Count(i+4) there. But there is no count(i+4) entry in the old vector. But we want our multiplication to produce it. We have the relationship Count(n)=Count(n-1)+C(n-3)+D(n-3)+2^(n-3) for n>3. Back four paragraphs we noted that we could safely assume i+4>3 and so we use the equation with n=i+4. This gives us Count(i+4)=Count(i+4-1)+C(i+4-3)+D(i+4-3)+2^(i+4-3)
=count(i+3)+c(i+1)+d(i+1)+2^(i+1).

Now in the old column vector, count(i+3) is in the 3rd place, c(i+1) is the 4th element, d(i+1) is the seventh element and 2^(i+1) is the next to last element. So we write the third row of M as (0,0,1,1,0,0,1,0,0,1,0) with 1's in the 3rd,4th,7th and next to last positions and 0 elsewhere.

The next two rows of M will be to shuffle the old values of c(i+2) and c(i+3) into their new positions. And then our sixth row of M will implement the formula for c(i+4), c(i+4)= c(i+1)+d(i+1)+5(2^(i+1))-1

The new wrinkle is that we don't have an entry for 5*2^(i+1) or -1 but we do have an entry for 2^(i+1) in the 10th position and 1 in the 11th. And so we echo the formula in the sixth row of M as (0,0,0,1,0,0,1,0,0,5,-1) and note that the multiplication of 2^(i+1) and 1 is accomplished by placing 5 in the 10th position and -1 in the 11th.

Similarly the next three rows of M will update the d values. This leaves two rows. The first has the responsibility of updating the power of 2 by doubling it, which we accomplish by
(0,0,0,0,0,0,0,0,0,2,0).

And finally we take note of the last row and last element. Sticking an extra value of 1 at the end of your vectors is an old trick to allow additions of constant by matrix multiplication. It's a good trick, but to preserve those constant 1's at the end of your vectors we need a last row of M which does just that. (0,0,0,0,0,0,0,0,0,0,1).

And that's our M, an exact implementation of our recursive definitions.

Can we be more efficient. Why yes. Our vectors have three successive values of the the C, D, and Count functions. The simplest and most productive change is to precompute M^3 and use it to update three values of Count at a time as we did with our matrix for obtaining A(n).

But we can also cut down from a 11x11 matrix to a 9x9 matrix and calculate the values 7 at a time.

More later.