[seqfan] Re: The Savannah Math

Mon Dec 30 20:28:04 CET 2019

Hello Ali,

You’re very welcome. I thought it was an interesting problem and I’m glad you liked the analysis.

Looking for an explicit formula: clearly the pattern is related to the triangular numbers (1, 3, 6, 10, 15 and so on): in the sequence of first differences 2, 4, 3, 5, 4, 4, 6, 5, 5, 5, 7, 6, 6, 6, 6, 8 ….  the values of a(i) make a jump wherever i-1 is a triangular number. The triangular numbers are given by t = s(s+1)/2, the inverse function is s = (sqrt(8t+1)-1)/2. A little bit of experimentation gives this formula: 

a(i) = 2*F(i-1) - F(i-2) + 2
where F(i) = floor((sqrt(8*i+1)-1)/2)

for the partial sum (the number of possibilities, allowing the empty set), I get:
a(0)=1, a(1) = 3;
for i > 1: a(i) = F(i-1) + 2*i + 1 + Sum_(j=1-> i) F(j-1)

And for the number of possibilities, excluding the empty set:
a(0)=1, a(1) = 3;
for i > 1: a(i) = F(i-1) + i + 1 + Sum_(j=1-> i) F(j-1)

I would be grateful if someone would check these. And yes, IMHO these sequences would be suitable for the OEIS.

Best regards,

Jan

Op 29 dec. 2019, om 21:01 heeft Ali Sada <pemd70 at yahoo.com> het volgende geschreven:
> 
> Dear Dr. Ritsema van Eck,
> 
> Thank you very much for your response. It is high praise coming from you, and I really appreciate it. 
> 
> Your analysis is beautiful. I really like the pattern you found (five, two fours, six, three fives, seven, four sixes, eight, ...). How would the partial sums sequence look as a direct function of n? 
> 
> Obviously, David was right and I was wrong. Including the empty sets gave us a unique sequence. I wonder if this is a suitable sequence for the OEIS. 
> 
> Happy New Year to everyone. I wish you, your families, and everyone you love a million years of happiness.
> 
> Best,
> 
> Ali
> 
> On Saturday, December 28, 2019, 12:59:41 PM EST, Jan Ritsema van Eck <j.ritsemavaneck at planet.nl> wrote:
> 
> 
> Nice problem Ali!
> 
> If I understand correctly, each week 4 things happen:
> 1) All hungry lions die
> 2) All fed lions become hungry lions
> 3) x hungry lions eat x zebras and become x fed lions, where x = min(nr of hungry lions, nr of zebras).
> 4) A new animal enters the savannah, and if possible, one zebra is eaten by one hungry lion which becomes a fed lion.
> 
> As David pointed out, the order in which these things happen does make a difference, but I think this order is consistent with the first terms of the sequence and with the examples Ali gave.
> 
> I also agree with David that I do not see any compelling reason to exclude the branches which follow from an empty set after step 1. In fact, the problem becomes a bit simpler if we include these branches: the case with one hungry lion is then directly followed by the same three possibilities as we had in the first week. Therefore, all possibilities in week x are also possibilities in week x+1, and we only to need to find how many new possibilities there are each week. So let’s first analyse the sequence if we allow the empty set, and then find out which possibilities are excluded if we do not allow the empty set.
> 
> First note that rule 4 means that there are never both zebra’s and hungry lions: zebra’s are eaten until either the number of zebra’s or the number of hungry lions is 0. Therefore we can map the possibilities in a two-dimensional graph, with the number of zebra’s on the positive side of the Y (or Z) axis and the number of hungry lions on the negative side of the same axis. I hope it makes sense to see a hungry lion as a “deficit” of one zebra. On the Z (or L) axis we put the total number of lions. If we are on or above the Z axis, all lions are fed. If we are below the Z axis, L+Z is the number of fed lions and -Z is the number of hungry lions.    
> 
> Now how can we find the possibilities that directly follow from a possibility L,Z? If Z is nonnegative, step 1 can be ignored as there are no hungry lions, and steps 2 and 3 result in L being subtracted from Z, so (L,Z) -> (L, Z-L). In step 4 the three possibilities are: a fed lion (L+1, Z-L), a hungry lion (L+1, Z-L-1) or a zebra (L, Z-L+1). If Z is negative, in steps 1 and 2 all hungry lions die and all fed lions become hungry lions (L, Z) -> (L+Z, -L-Z). Since there are no zebra’s we can ignore step 3 and in step 4 the three possibilities are: a fed lion (L+Z+1, -L-Z), a hungry lion (L+Z+1, -L-Z-1) or a zebra (L+Z, -L-Z+1).
> 
> Below, I made a table showing in which week each possibility first occurs during the first 12 weeks. So in the first week, we have (0,1) one zebra, (1,0) a fed lion, and (1, -1) a hungry lion. In the second week, we have (0,2) two zebra’s, (1, 1) a fed lion and a zebra, (2,-1) a fed lion and a hungry one, and (2, -2) two hungry lions, and so on. Of course the pattern continues in upwards direction: above each 12 is a 13 and so on.  
> 
> <PastedGraphic-1.png>
>  
> Note that each possibility in the first column has to new followers: one directly above and one directly to the right. (They also have a third follower, directly to the right and one column lower, but that is not a new possibility). Each possibility in the part of the second column with positive Z, has one new follower directly to the right and one row lower. Each possibility in the positive part of the third column has one new follower directly to the right and two rows lower, and so on. The possibilities on the Z=0 row always have two new followers. The possibilities in the part with negative Z have no new followers. 
> 
> The number of new possibilities in week 1 is 3, in week 2, 4, in week 3, 3 again, in week 4, 5. Without having a rigorous proof, a clear pattern emerges of the number of new possibilities each week:
> 3, 4, 3, 5, 4, 4, 6, 5, 5, 5, 7, 6, 6, 6, 6, 8, 7, 7, 7, 7, 7, 9, followed bij six 8’s, one 10, seven 9’s, one 11, eight 10’s and so on. Thus the total number of possibilities in each week is the partial sum of this:
> 3, 7, 10, 15, 19, 23, 29, 34, 39, 44, 51, 57, 63, 69, 75, 83, 90, 97, 104, 111, 118, 127 and so on.
> 
> Now this is the sequence if we allow the empty set. Which possibilities have to be excluded if we do not allow the empty set? 
> 
> First note that each possibility in the part of the second column (L=1) with nonnegative Z, has itself as a follower (the one lion becomes hungry, eats one zebra and e new zebra arrives). Therefore, once a possibility in this column has occurred, it will return each week. Since all possibilities in the columns further to the right directly or indirectly follow from the second column, these will also return each week after their first occurrence. The possibilities in the first column can not return: a positive number of zebra’s without a lion can only occur if the previous week there was one zebra less, and a new zebra arrived. The situation with only one zebra could follow from the empty set, which is not allowed. Also the possibility (1, -1) can not reoccur: a single hungry lion can only only follow from the empty set which is not allowed. These are the only possibilities that cannot reoccur. Therefore, in week 2 we have 2 possibilities that must be excluded, in week 3, 3 possibilities, in week 4, 4 and so on. 
> 
> Therefore the sequence as defined by Ali, excluding the empty set, is:
> 3, (7-2=) 5, (10-3=) 7, (14-4=) 11 (19-5=) 14, (23-6=) 17, (29-7=) 22, and so on:
> 
> 3, 5, 7, 11, 14, 17, 22, 26, 30, 34, 40, 45, 50, 55, 60, 67, 73, 79, 85, 91, 97, 105 and so on.
> 
> A happy new year to everyone!
> 
> Jan
> 
>  
> 
>> Op 21 dec. 2019, om 23:05 heeft Ali Sada via SeqFan <seqfan at list.seqfan.eu <mailto:seqfan at list.seqfan.eu>> het volgende geschreven:
>> 
>> Hi Everyone,
>> 
>> The setup below has no real meaning in zoology. It is just a math practice. The math system is based on the following assumptions:
>> a)    One hungry lion (H) eats one zebra (Z) to become a fed lion (F).
>> b)    In one week, a fed lion becomes hungry; a hungry lion dies; and zebras don’t change.
>> c)    Every week, a new unknown animal (either F, H, or Z) enters the area. 
>> 
>> Let’s count the distinct possibilities for each week:
>> 
>> 1.    In the first week, we have one unknown animal, so, have 3 possibilities: it could be either F, H, or Z.  So, a(1)=3
>> 
>> 2.    In the second week, the fed lion becomes a hungry lion, and the hungry lion dies. So, we have only two possibilities left (H or Z). When another unknown animal (F or H or Z) comes, we have the following combinations: 
>> F+H=FH
>> F+Z=FZ
>> H+H=2H
>> H+Z=F
>> Z+Z=2Z
>> We have 5 distinct possibilities; so a(2)=5
>> 
>> 3.    In the third week, the combinations of the second week change:
>> FH becomes H; FZ becomes F; 2H disappears; F becomes H; and 2Z remains 2Z.
>> So, we have only 3 distinct possibilities (F, H, and 2Z) 
>> When a new animal comes, the distinct possibilities become: (F, 2F, FH, FZ, F2Z, 2H, 3Z). 
>> So, a(3)=7. 
>> If we continue, we get a(4)=11, a(5)=14, a(6)=17, a(7)=22, etc.
>> 
>> I would really appreciate it if someone could help me find the terms of this sequence. Also, what’s the pattern here?
>> 
>> Best,
>> 
>> Ali
>> 
>> 
>> 
>> 
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/ <http://list.seqfan.eu/>
>> 
> 
> 
> <PastedGraphic-1.png>