Seleccione n enteros positivos, de modo que para todas las combinaciones de pares, las sumas de cada par generen los primos más únicos. ¿Cómo lo resolverías?

Answer 1

Podemos establecer un límite superior a través de un argumento de paridad simple. No se pueden sumar dos números impares para obtener un primo, porque el resultado es par. Por lo tanto, para generar un primo, el par debe considerar un número impar y un número par. Dados los números pares E y los números impares NE en nuestro conjunto, el número de sumas impares es

[matemáticas] E (NE) = EN-E ^ 2 [/ matemáticas]

Esto se maximiza en [matemática] N-2E = 0 [/ matemática] o [matemática] E = N / 2. [/ Matemática] Por ejemplo, con [matemática] n = 20 [/ matemática] el número máximo de números primos aparecer no puede ser más que [matemáticas] 10 \ cdot 20 – 10 ^ 2 = 100 [/ matemáticas]. Nuestro límite superior es, por lo tanto, [matemáticas] (N) (N / 2) – (N / 2) ^ 2 = N ^ 2/2 – N ^ 2/4 = N ^ 2/4 [/ matemáticas].

¿Qué otras restricciones teóricas numéricas podemos encontrar? Un resultado estándar en las constelaciones primas es que si [math] p + a_1, p + a_2, p + a_3, \ ldots, p + a_k [/ math] son ​​primos, entonces no puede haber un número primo que divida el producto [ math] (n + a_1) (n + a_2) (n + a_3) \ ldots (n + a_k) [/ math] para todos [math] n [/ math]. De manera equivalente, para cualquier primo [matemático] p [/ matemático], el conjunto de restos [matemático] \ {a_i \ bmod p \} [/ matemático] debe omitir uno de los valores posibles. Consulte Constelaciones primarias admisibles (para [matemática] p> k [/ matemática], es obvio que faltará al menos una de las clases de congruencia ya que hay más residuos que números en nuestra constelación, por lo que la verificación se puede realizar mecánicamente un conjunto finito)

Se conjetura que siempre que una constelación principal es admisible, hay infinitos primos que coinciden con esa constelación. Entonces, si solo estamos interesados ​​en encontrar algún conjunto de n, en lugar del más pequeño posible, podemos elegir una constelación admisible que comience con [math] a_1 = 0 [/ math] y buscar sus ocurrencias, cada una de las cuales dará nosotros un número impar para agregar a nuestro conjunto. La constelación no necesita ser la más pequeña posible para [matemáticas] N / 2 [/ matemáticas], pero eso parece más elegante. ¡Desafortunadamente, este enfoque parece conducir a números impares muy grandes!

Por ejemplo, con la constelación 0 2 6 8 12 18 20 26 30 32, los valores iniciales son: 11, 33081664151, 83122625471, 294920291201, 573459229151, 663903555851, 688697679401, 730121110331, 1044815397161, y 108986918901. Esta es una solución para el caso N = 20, pero es mucho menos compacta que la proporcionada en el comentario anterior. Eso sugiere que realmente necesitamos hacer un mayor uso de nuestra flexibilidad al elegir los números pares. 🙂 Pero esta solución debería funcionar siempre que no nos importe buscar mucho tiempo y confiar en el estado de las conjeturas de la teoría de números no comprobadas.

¿Qué pasa si comenzamos desde el otro extremo? Podemos generar muchos números primos y luego ver qué constelaciones existen dentro de nuestra muestra. La búsqueda codiciosa bien podría dar resultados aceptables. Parece que este es el punto en el que se requiere cierta inteligencia algorítmica. El problema más cercano que se me ocurre es la intersección máxima de subconjuntos k, donde queremos encontrar exactamente k subconjuntos cuyo tamaño de intersección se maximice. (Pero en realidad no nos importa la maximización, solo nos preocupamos por satisfacer que el tamaño de la intersección sea al menos k). Consulte http://www.ic.unicamp.br/~eduard … donde se muestra que el problema completo es NP-duro y difícil de aproximar.

Nuestros conjuntos están realmente lejos de ser arbitrarios. Cada uno de los conjuntos de distancias es una versión desplazada de la anterior. No veo una forma lista de usar eso que no sea hacer que su construcción sea más eficiente.

Para cada distancia candidata [math] d [/ math] para nuestra constelación, construya un conjunto de números primos [math] p [/ math] donde [math] p + d [/ math] es primo. Luego, realice una búsqueda codiciosa de las distancias, utilizando la distancia que conserva el mayor conjunto de números primos que se cruzan. (Cualquier distancia que aparezca en menos de N / 2 subconjuntos se puede excluir inmediatamente.) Las soluciones candidatas deben verificarse para que todas las sumas sean distintas, pero si hay suficientes números primos en el conjunto, entonces podemos recortar algunos de ellos.

Si el conjunto inicial de primos es lo suficientemente grande, este método parece funcionar bastante bien y encontrar una solución de manera más o menos inmediata. Si los números primos no son lo suficientemente grandes, podemos quemar mucha CPU buscando infructuosamente. Puede tener sentido terminar la búsqueda con bastante rapidez y ajustar el conjunto inicial de números primos, en lugar de tratar de explorar el árbol más profundamente.

Para N = 20 (ceba hasta 10000) solo una pista de retroceso:

[0, 210, 330, 420, 990, 1200, 1890, 2520, 2730, 3060] [23, 127, 331, 499, 887, 1151, 1277, 2383, 2789, 3307]

(Los primos 3491 y 3593 también satisfacen esta constelación)

Para N = 22 (primos hasta 12000), sin retroceso:

[0, 30, 210, 780, 990, 1200, 2310, 4440, 5070, 5610, 6786] [233, 647, 1151, 1567, 2341, 2857, 4241, 8543, 8941, 9467, 10837]

Para N = 24 (primos hasta 100000), pirateé mi rutina de retroceso para rendirme antes en las hojas y encontré esto con solo unos pocos callejones sin salida:

[0, 204, 840, 2310, 3570, 4620, 5100, 5880, 7704, 8190, 9510, 13020] [457, 1229, 3253, 4219, 6217, 8297, 14827, 48337, 48799, 73379, 78989, 83987]

(No estoy contento con esa solución, idealmente comenzaríamos de nuevo con una primera opción diferente en caso de que fuera el problema, pero no lo suficiente como para dedicarle mucho tiempo. O introducir alguna aleatorización, o algo así).

N = 26: sin éxito, los primos hasta 200000 son demasiado grandes para mi implementación ineficiente de Python.