Repetir la extracción de los valores de la media de no vacía de subconjuntos de un conjunto: $2,\,3,\,5,\,15,\,875,\,...$

Question

Considere el siguiente proceso iterativo. Vamos a empezar con un 2-element set $S_0=\{0,1\}$. En $n^{\text{th}}$ paso $(n\ge1)$ tomamos todos, no vacía de subconjuntos de a $S_{n-1}$, entonces para cada subconjunto calcular la media aritmética de sus elementos, y recoger los resultados en un nuevo conjunto $S_n$. Deje $a_n$ ser el tamaño de $S_n$. Tenga en cuenta que, debido a que algunos subconjuntos de a $S_{n-1}$ pueden tener idénticos los valores de la media, $a_n$ puede ser menor que el número de no vacía de subconjuntos de a $S_{n-1}$ (es decir, $2^{a_{n-1}}-1$).

Por ejemplo, en el $1^{\text{st}}$ paso tenemos los subconjuntos $\{\{0\},\,\{1\},\,\{0,1\}\}$, y sus medios son $\{0,\,1,\,1/2\}.$ $S_1=\{0,\,1,\,1/2\}$ $a_1=|S_1|=3.$

En el $2^{\text{nd}}$ paso tenemos los subconjuntos $\{\{0\},\,\{1\},\,\{1/2\},\,\{0,\,1\},\,\{0,\,1/2\},\,\{1,\,1/2\},\,\{0,\,1,\,1/2\}\},$ y sus medios son $\{0,\,1,\,1/2,\,1/2,\,1/4,\,3/4,\,1/2\}.$, por Lo que, después de eliminar los valores duplicados, obtenemos $S_2=\{0,\,1,\,1/2,\,1/4,\,3/4\}$ $a_2=|S_2|=5.$ Y así sucesivamente.

La secuencia de $\{a_n\}_{n=0}^\infty$ comienza: $2,\,3,\,5,\,15,\,875,\,...$

Al parecer, esta secuencia no está aún en OEIS, pero me lo presentó como un proyecto de A273525.

Un ataque de fuerza bruta aproximación algorítmica permite encontrar fácilmente sus elementos hasta el $a_4=875$, pero se vuelve computacionalmente inviable después de eso. Mi pregunta es:

¿Cuál es el valor de $a_5$?

Es fácil ver que $5\times10^5<a_5<2^{875}<10^{264}$ (el límite inferior $5\times10^5$ es, probablemente, muy débil, y se encontró de forma directa la enumeración de algunos subconjuntos de a $S_4$). Así que, en principio, este número puede ser escrito de forma explícita, si encontramos una manera más inteligente y rápida manera de calcular.

---

Actualización: Otra pregunta que me interesa es:

¿Cuál es el comportamiento asintótico de $\frac{a_n}{2^{a_{n-1}}}$$n\to\infty$?

Answer 1

No es una respuesta completa, pero algunas ideas:

El número de los distintos medios de $k$-elemento de subconjuntos de un $n$-elemento del conjunto es, al menos,$k(n-k)+1$. Por ejemplo, cuando se $k=3$$n=9$, los siguientes subconjuntos de todos los distintos medios: $\{x_1,x_2,x_3\}$, $\{x_1,x_2,x_4\}$, ..., $\{x_1,x_2,x_9\}$, $\{x_1,x_3,x_9\}$, ..., $\{x_1,x_8,x_9\}$, $\{x_2,x_8,x_9\}$, ..., $\{x_3,x_8,x_9\}$. La aplicación de este con $n=875$ $k=438$ ya da 191,407 distintos medios.

Podemos construir sobre esto, sin embargo. De los 875 significa contado por $a_4$, 52 de ellos tienen un factor de 13 años, en su denominador, mientras que el otro 823 no. Tomando $k=412$$n=823$, obtenemos 169,333 subconjuntos con medios distintos. Pero además, de los 52, hay numeradores correspondiente a cada valor distinto de cero residuos de la clase modulo 13. Por lo tanto, podemos tomar cada uno de los 169,333 subconjuntos y obtener 13 variantes con diferentes medios (el subconjunto de sí mismo, junto con el subconjunto con un único elemento que se anexa, que el elemento que tiene un denominador divisible entre 13 y un numerador de cada uno de los distinto de cero residuos clases modulo 13). Que da 2,201,329 significa que un poco de pensamiento verifica son distintos.

Uno podría experimentar con denominadores distintos de 13 (tal vez compuesto) para sacar el máximo partido a este argumento.

Por último, tenga en cuenta que la media de una $p$-elemento del subconjunto y la media de una $q$-elemento del subconjunto, si $p$ $q$ son relativamente primos, son muy propensos a ser distintos el uno del otro. (Ambos primos tendría que ser cancelados de sus denominadores de las sumas de los elementos de los subconjuntos.) Así que uno debe ser capaz de combinar varias colecciones de medios en este camino y mejorar el límite inferior. (Por supuesto, teniendo en $p$ $q$ cerca de $875/2$ parece el mejor lugar para explorar.)

(agrega más adelante) Como para el límite superior, vamos obligado el número de $k$-elemento significa por separado y en su mayoría se olvide acerca de si se podría coincidir. Obviamente hay 875 $1$-elemento significa. Para $2\le k\le 875$, hay, obviamente, en la mayoría de los $\binom{875}k$ $k$-elemento significa. Sin embargo, podemos obtener una cota superior de la siguiente manera: El mayor de los 875 elementos es $1$ del curso, y el mínimo común denominador de las 875 elementos es 17,297,280. Por lo tanto, cada uno de $k$-elemento media es un número racional entre el $0$ $1$ cuyo denominador se divide $17\text{,}297\text{,}280k$, y en la mayoría de las $17\text{,}297\text{,}280k-1$ de ellos (no recuento $0$ $1$ sí, los que ya están contabilizados por el $1$-elemento significa). Por lo tanto un límite superior para $a_5$ es $$ 875 + \sum_{k=2}^{875} \min\bigg\{ \binom{875}k, 17\text{,}297\text{,}280k-1 \bigg\} = 6\text{,}568\text{,}806\text{,}008\text{,}597. $$ Así que al menos sabemos que $a_5$ entre $2\times10^6$$7\times10^{12}$.