Finding the billionth number in the series: $2, 3, 4, 6, 9, 13, 19, 28, 42, \ldots $?

Question

Series is defined as $$a_{n+1} = \lfloor\frac{3\cdot a_n}{2}\rfloor,\qquad a_0 = 2$$ It can be viewed as the number of animals starting from a single pair if any pair of animals can produce a single offspring.

The problem is if the most straightforward computer program was implemented (recurrence relation in a loop), it seems it would not finish for the lifetime of its creator... How to approach this differently?

EDIT: This number is very large. Its approximation in scientific notation (let's say first 10 decimal digits, and decimal exponent) would be sufficient.

Answer 1

The related series $$x_n=\lceil\frac32x_{n-1}\rceil,\ x_0=1$$ is studied at MathWorld. Since for all integers $n$, $\lceil\frac32n\rceil=\lfloor\frac32(n+1)\rfloor-1$, we can rewrite this as $x_n+1=\lfloor\frac32(x_{n-1}+1)\rfloor$, and $x_0+1=2$; thus we have $a_n=x_n+1$ for all $n$. That page (links to a paper that) derives that there exists a real number $K$ such that for all $n$, $$x_n=\lceil K(3/2)^n\rceil,$$ which tells us that the sequence very nearly follows the expected power law, although the accumulated roundoff error $K$ is hard to calculate in advance.

So let's take the direct route. Define the sequences $a_{k+1}^+=\frac32a_k^+$, $a_{k+1}^-=\frac32a_k^--1$, where the initial values set $a_m^+=a_m^-=a_m$ for some fixed basepoint $m$. Then it is easy to show that

$$a_n^+=\Big(\!\frac32\!\Big)^{n-m}a_m;\qquad a_n^-=\Big(\!\frac32\!\Big)^{n-m}(a_m-2)+2.$$

Now we have the inequality $a_n^-\le a_n\le a_n^+$ because $x-1\le\lfloor x\rfloor\le x$, so this directly gives bounds on $a_n$ for $n=10^9$. Since you want around 10 digits of accuracy, we need to pick an $a_m\ge 2\cdot 10^{10}$: for example, $a_{58}=26510400994$. Then we have:

$$\log_{10}(a_m-2)\le\log_{10}a_n-(n-m)\log_{10}(3/2)\le\log_{10}a_m$$ $$\log_{10}26510400992\le\log_{10}a_{10^9}-(10^9-58)\log_{10}(3/2)\le\log_{10}26510400994$$ $$176091259.2658045137\underline{02}\le\log_{10}a_{10^9}\le176091259.2658045137\underline{34}$$

Thus the exponent of $a_{10^9}$ is $176091259$, and the fractional part is $10^{0.2658045137}\approx1.844185120$ (where only the digits that agree for both bounds are shown). Putting it all together, we have

$$a_{10^9}=1.844185120\dots\times10^{176091259}.$$

By repeating this process with bigger basepoints, you can confirm as many digits as you want. Here's a few more correct digits:

$$a_{10^9}=1.844185120759922192245258053300812265366889206992486395592885\times10^{176091259}.$$

Answer 2

I think some graphs like these ones can be very helpful...where $$A061418(n) = a_{n+1} = \Big\lfloor\frac{3\cdot a_n}{2}\Big\rfloor,\qquad a_0 = 2$$

You can easily see that the Logarithimc scatterplot seems to grow linearly, so if you're alloking for an approximation of the billionth number of the sequence you can start from the second graph. With a bit of homemade linear interpolation you get that $$\log(a_n) \approx n\cdot 0,6\overline{1} = n \frac{11}{18} \Rightarrow \\ a_n\approx e^{n \frac{11}{18}}$$

Answer 3

Computing by brute force, we get that $a_{62}=134208905031$. That has $11$ significant figures. Since the error is multiplied by the same factor as the significant part, if we use this number and multiply by $\left(\frac32\right)^{999999937}$ and $\left(\frac32\right)^{999999938}$, we get $$ a_{999999999}\doteq1.2294567472\times10^{176091259} $$ and $$ a_{1000000000}\doteq1.8441851208\times10^{176091259} $$ to $10$ places, depending on which you mean by "billionth".

Answer 4

The OEIS entry for $2,3,4,6,9,13,19,28,42,\ldots$, adjusted to agree with the OP's starting index, says that

$$a_n=\lceil K(3/2)^{n+1}\rceil$$

where $K\approx1.0815136685898448773046339885995$, with more digits available at a linked-to reference. If all you want is an approximation in scientific notation, then the ceiling function round-up can be ignored.

Let's let $n=10^9$. Then Wolfram Alpha gives us

$$\left({3\over2}\right)^{n+1}\approx 1.70518891653445589648412113069806868 × 10^{176091259}$$

and thus

$$a_n\approx1.8441851207599221922452580533 × 10^{176091259}$$

with agrees with what robjohn and others found, with a few more digits. (I truncated a few digits from the WA output, to stay on the safe side.)