## Subset problem

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

 Quote by haruspex 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?

 Quote by SeventhSigma 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.
 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: http://www.physicsforums.com/showpos...2&postcount=55

 Quote by haruspex 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.

 Quote by 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: http://www.physicsforums.com/showpos...2&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.
 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
 Recognitions: Homework Help Science Advisor 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.
 Recognitions: Homework Help Science Advisor 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?
 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)

 Quote by 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
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)

 Quote by SeventhSigma 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.