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

[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.

 

[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