Exponential growth of cow populations in Minecraft

Question

Minecraft is a computer game where you can do many things, including farming cows.

When fed wheat, cows in Minecraft breed with each other in pairs and produce one baby per pair. After about $20$ minutes, the baby/babies grow and can breed with each other and their parents. There are no genders in Minecraft, nor any issues with cows breeding with their offspring: all fully grown cows are identical.

So what is the total number of cows after n 'breedings'?

Starting with $2$ cows, the total number of cows goes like this:

$$2, 3, 4, 6, 9, 13, 19, 28, 42, 63, 94,$$ and so on.

Let $n$ be the number of times the cows have bred. The number of new cows (difference between two consecutive of the above numbers) equals $$\frac{n - n\%2}2,$$ where $\%$ means modulus.

So what is the total number of cows for any given $n$? I know it is a sum of some sort, but what is it?

Answer 1

This is OEISA061418, interestingly the "example" is about Minecraft. The given solution for the $n$th term is

$$ a(n) = \lceil K*(3/2)^n \rceil $$

where $K=1.0815136685\dots$ and $K=(2/3) K(3)$ where the decimal expansion of $K(3)$ is here.

For clarification as to how this formula is used, suppose you want to know how many cows you have after the $10$th breeding cycle. First,

$$ K*(3/2)^n = (1.0815136685)*(3/2)^{10} \approx 62.3655 $$

Now we have to take the ceiling of this number, which just means rounding it up to the nearest integer. Therefore,

$$ a(10) = \lceil K*(3/2)^n \rceil = \lceil 62.3655 \rceil = 63 $$

which agrees with the sequence. Note that for very large $n$, you may need to use a more exact value of $K$ (which is why I posted that second link.)

Answer 2

To restate what you've written: at each stage, if $N$ is the number of cows before breeding, then the number of additional cows is $\lfloor N/2 \rfloor$ (see the floor function defined here).

As a recurrence relation, we can state the following:

Let $N(k)$ be the number of cows after $k$ stages of breeding. Then $N$ satisfies the recurrence relation $$ N(k+1) = N(k) + \lfloor N(k)/2 \rfloor $$ With $N(0) = 2$. I'm not sure if there's a neat non-recursive expression for $N$ as a function of $k$, but at the very least this is a start.

Answer 3

What you are looking for is the solution to the recurrence: $$T(1) = 2$$ $$T(n) = T(n-1) + \left\lfloor \frac{T(n-1)}{2} \right\rfloor$$ Indeed this function grows as an exponential, since it behaves asymptotically like $$T(n) \approx 2 \left( \frac{3}{2} \right)^{n - 1}$$ Since $T(n)$ is always an integer, we can rewrite the recurrence as $$T(n) = \left\lfloor \frac{3}{2} T(n-1) \right \rfloor$$ This gives an efficient way to compute $T(n)$ iteratively. I'm not sure there is a useful closed form.

Answer 4

I know this may be useless at this point, but it doesn't take too much space ...

So this reflects more or less the same example of fibonacci (promiscuous bunnies) but with married cows or something alike, so after the first breeding there's two cows (one couple) and after the next breeding that couple will give birth another cow, then there will be 3 cows but still one couple since the younger (recently added) cow doesn't belong to any couple.

The next breeding there will be 4 cows as expected and then we get 2 couples, so the next breeding those couples of cows will give birth other 2 cows (a new full couple). And then with 6 (4 + 2) cows we get 3 cows (9 cows in total). And so on:

9 + 4 = 13, 13 + 6 = 19, 19 + 9 = 28, . . .

Greetings, MasterGeek.

Edit: Sorry, there are two cows BEFORE the first breeding, since you need at least one couple.