He intentado resolverlo utilizando el teorema de Ramsey infinito, con una coloración basada en si la suma de dos vértices tiene un número par o impar de factores primos distintos. Esto me lleva a una recursión infinita. ¿Está bien? Al final de todo el tiempo habré terminado.
Respuestas
¿Demasiados anuncios?
Justin Walgran
Puntos
552
Por si sirve de algo, tal secuencia construida por un algoritmo codicioso comienza:
2, 4, 8, 10, 16, 18, 36, 199, 208, 1131, 1347, 3984, 5751, 7310, 27315, 129313, 134101, 169400, 589570
Es decir, empezamos con $A_1 = 2$ y luego cada $A_n$ es el menor número mayor que $A_{n-1}$ con $A_i + A_n$ que tiene un número par de factores primos distintos para cada $n \le 1$ . (Así, por ejemplo, $A_3 = 8$ porque $5+4, 6+2, 7+2$ tienen cada uno un número impar de factores primos distintos, pero $8+2$ y $8+4$ ambos tienen números pares).
Otra secuencia de este tipo, que empieza por 1, comienza
1, 5, 9, 13, 35, 39, 286, 290, 381, 385, 866, 4376
y uno que empieza por 3 comienza
3, 7, 11, 15, 33, 41, 47, 65, 101, 203, 4102, 6392, 8507, 18608.
A partir de estos parece que estas secuencias crecen aproximadamente de forma exponencial; es decir, $A_n \approx k^n$ para alguna constante $k$ . Esto tiene sentido. Dado que aproximadamente la mitad de los números enteros tienen un número par de factores primos distintos, una vez que se tiene $n$ números en una secuencia tal que debería tomar alrededor de $2^n$ intenta encontrar el siguiente.
Por supuesto, esto no es una prueba, pero al menos es un argumento de por qué deben existir tales secuencias. Y a juzgar por la irregularidad de las secuencias construidas con avaricia, un método avaricioso probablemente no es el mejor camino a seguir aquí, incluso si quieres construir explícitamente la secuencia.
Comience con $\{5n+1\}$ y construir un gráfico completo infinito, coloreando la arista entre $x$ y $y$ con la paridad del número de factores primos distintos de $x+y$ .
Por el teorema de Ramsey infinito, hay una camarilla infinita de un color.
Si eso corresponde a que el número de factores primos distintos es par, hemos terminado. En caso contrario, considera cada número multiplicado por $5$ . Como la suma de cualquier dos (original) no es divisible por $5$ después de multiplicar por $5$ tenemos que el número de factores primos distintos para cada suma debe ser par.
De hecho, supongo que hay un número infinito de conjuntos de este tipo, de manera que dos conjuntos cualesquiera tienen una intersección finita.
