Encontrar la milmillonésima número de la serie: $2, 3, 4, 6, 9, 13, 19, 28, 42, \ldots $?

Question

La serie se define como $$a_{n+1} = \lfloor\frac{3\cdot a_n}{2}\rfloor,\qquad a_0 = 2$$ Se puede ver como el número de animales a partir de un solo par si cualquier par de animales puede producir una sola cría.

El problema es que si el más sencillo programa de ordenador fue implementada (de la recurrencia de la relación en un bucle), parece no terminar de la vida de su creador... Cómo acercarse de una manera diferente?

EDIT: Este número es muy grande. Su aproximación en notación científica (digamos 10 primeros dígitos decimales, decimal y exponente) sería suficiente.

Answer 1

La serie relacionada con $$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$ es difícil de calcular de antemano.

Así que vamos a tomar la ruta directa. Definir las secuencias $a_k^+=\frac32a_k^+$, $a_k^-=\frac32a_k^--1$, donde la inicial el conjunto de valores de $a_m^+=a_m^-=a_m$ para algunos fijos punto de base $m$. Entonces es fácil demostrar que

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

Ahora tenemos la desigualdad $a_n^-\le a_n\le a_n^+$ porque $x-1\le\lfloor x\rfloor\le x$, por lo que esta directamente da límites en $a_n$$n=10^9$. Desde que desee alrededor de 10 dígitos de precisión, tenemos que escoger un $a_m\ge 2\cdot 10^{10}$: por ejemplo, $a_{58}=26510400994$. Entonces tenemos:

$$\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}$$

Por lo tanto el exponente de $a_{10^9}$$176091259$, y la parte fraccionaria es $10^{0.2658045137}\approx1.844185120$ (donde sólo los dígitos que están de acuerdo tanto los límites se muestran). Poniendo todo junto, tenemos

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

Repitiendo este proceso con mayor basepoints, puede confirmar el número de dígitos que desee. Aquí hay unos cuantos más correcto de dígitos:

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

Answer 2

Creo que algunos gráficos como estos pueden ser muy útiles...donde $$A061418(n) = a_{n+1} = \lfloor\frac{3\cdot a_n}{2}\rfloor,\qquad a_0 = 2$$

Usted puede ver fácilmente que la Logarithimc diagrama de dispersión parece crecer de manera lineal, por lo que si usted está alloking para una aproximación a la milmillonésima número de la secuencia que se puede iniciar desde el segundo gráfico. Con un poco de la casa de la interpolación lineal se puede conseguir que la $$\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

La computación por la fuerza bruta, tenemos que $a_{62}=134208905031$. Que ha $11$ cifras significativas. Ya que el error se multiplica por el mismo factor que la parte importante, si hacemos uso de este número y multiplicar por $\left(\frac32\right)^{999999937}$$\left(\frac32\right)^{999999938}$, obtenemos $$ a_{999999999}\doteq1.2294567472\times10^{176091259} $$ y $$ a_{1000000000}\doteq1.8441851208\times10^{176091259} $$ a $10$ lugares, dependiendo de lo que significa "mil millones".

Answer 4

La OEIS entrada para $2,3,4,6,9,13,19,28,42,\ldots$, ajustado de acuerdo con el OP del índice inicial, dice que

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

donde $K\approx1.0815136685898448773046339885995$, con más dígitos disponibles en un ligados a los de referencia. Si lo que quieres es una aproximación en la notación científica, a continuación, el techo de la función round-up puede ser ignorado.

Vamos a dejar que $n=10^9$. A continuación, Wolfram Alpha nos da

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

y así

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

con está de acuerdo con lo robjohn y otros que se encuentran, con un poco más dígitos. (I truncada un par de dígitos de la WA de salida, para permanecer en el lado seguro.)