Problema principal combinatoria

Question

Actualización

Como Barry Cipra se indicó en los comentarios, un mejor encuadre de la pregunta podría ser que estoy viendo las diferencias absolutas $|a−b|$ o totales $a+b$ $5$- suave números de $a$ $b$ la satisfacción de las condiciones de $a>b>1$, mcd$(a,b)=1$, e $30∣ab.$

Pregunta Original

Es cierto que $251$ no puede ser hecho a partir de la diferencia absoluta entre el (o total) $2$ coprime números compone de TODOS los factores primos $2,3,$ $5$ (con un mínimo exponente:$1$)?

$251, 431, 487, 499, 539, 541, 583, 593, 599, 617, 641, 713, 727, 731, 751, 761, 767, 781, 811, 823, 853, 857, 863, 877, 899, 901, 941, 943, 953, 961, 971, 983\puntos$

o, alternativamente,

$251,431,487,499,7^2\cdot 11,541,11\cdot 53,593,599,617,641,23\cdot 31,727,17\cdot 43,751,761,13\cdot 59,11\cdot 71,811,823,853,857,863,877,29\cdot 31,17\cdot 53,941,23\cdot 41,953,31^2,971,983\dots$

Me interesaría si cualquiera de estos números se pueden "caer" de la lista. He intentado combinatorally hasta exponente $70$ pero no he encontrado nada. Curiosamente, el mayor exponente utilizado en cualquier otro número $<1000$$11$.

La lista de números de coprime a $2,3$ $5$ comienza:

$$\begin{align} &| 3-2\cdot 5|&=&7 \\ &|3\cdot 5 -2^2|&=&11\\ & |3\cdot 5-2|&=&13 \\ &| 3-2^2\cdot 5|&=&17 \\ &|5-2^3\cdot 3|&=&19 \\ &|5^2-2^4\cdot 3|&=&23\\ &|3^2\cdot 5-2^4|&=&29 \\ &|5-2^2\cdot 3^2|&=&31 \\ &|3-2^3\cdot 5|&=&37\\ &|3^2\cdot 5-2^2|&=&41\\ &|5-2^4\cdot 3|&=&43 \\ &|3-2\cdot 5^2|&=&47 \\ &|3\cdot 5-2^6|&=&49\\ &|3^3-2^4\cdot 5|&=&53 \\ &|3\cdot 5^2-2^4|&=&59\\ &|3^4-2^2\cdot 5|&=&61 \\ &|5-2^3\cdot 3^2|&=&67\dots\\ \end{align}$$

con exponente $11$ ejemplo:

$$\begin{align} &|3^2\cdot 5^3-2^{11}|&=&923\\ \end{align}$$

$15$ siendo el más alto exponente en todas las combinaciones de exponente $70$:

$$\begin{align} &|3^8\cdot 5-2^{15}|&=&37\\ \end{align}$$

Tengo una sensación de que el problema puede estar relacionado con la McNugget de números, pero no estoy seguro. No puedo pensar en una razón por la que todos los números coprime a $2,3$ $5$ no puede ser generada de esta forma, y estaría muy interesado si alguien podría señalar por qué no debería ser el caso.

También me gustaría saber si esto es un $NP$-problema difícil, o si hay un enfoque más económico que agotar todas las combinaciones.

Nota

Dejando fuera cualquier cosa exponente $0$ es una restricción importante, ya que, si se ignora, la lista resultante se convierte en todos los números enteros, frente a todos los enteros coprime a $2,3$ $5.$

Answer 1

Se trata de un equipo-solución compatible que no proporcionan la comprensión de las reglas que describen por qué algunos números pueden y otros no puede ser expresado. Además, yo no comprobar los cálculos todavía (especialmente la exhaustiva parte), así que si alguien quiere verificar independientemente, mi huésped!

---

Observación 0: Hay sólo un número finito de posibilidades de representación de un número positivo como la suma de dos números positivos; por lo que estos pueden ser descartado por la búsqueda exhaustiva. Vamos a centrar sólo en la "diferencia".

Observación 1: Si tenemos $a-b=n$, también tenemos $a-b=n\pmod q$ para cualquier entero positivo $q$. Por lo tanto, con el fin de demostrar que el $n$ no puede ser expresado como la diferencia de dos números (de forma particular), es suficiente para mostrar que es imposible hacerlo con el modulo convenientemente elegido entero $q$.

Observación 2: Si se han corregido los enteros positivos $x$$q$, hay sólo un número finito de valores que $x^k\bmod q$ puede lograr para diferentes poderes positivos $k$. Si empezamos con $k=1$ y sigue aumentando, es suficiente para ir hasta que nos encontramos con algún valor que hemos visto ya; todos los siguientes se duplica.

Considere la posibilidad de $q=4095$. Tenemos:

• $2^{13}\equiv 2^1\pmod q$,
• $3^{14}\equiv 3^{2}\pmod q$ y
• $5^{13}\equiv 5^1\pmod q$

Por lo tanto, es suficiente para considerar $2^a$, $3^b$, $5^c$ (todos modulo $q$) con $1\leq a\leq 12$, $1\leq b\leq 13$ y $1\leq c\leq 12$ cuando la construcción de los valores posibles. Resulta que ninguna de las diferencias resulta ser congruente a $251$ modulo $q$; por lo que el número de $251$ no es expresable en la forma deseada.

En realidad, hemos descartado todos los números congruentes a $251$ modulo $4095$, no sólo a $251$ sí. El "testigo" $q=4095$ también funciona para otros números de la lista-por ejemplo, $731$ o $877$. Otros números en la lista podría necesitar otros testigos: por ejemplo, $487$ deben ser cubiertos por $q=6552$$431$$q=94535$.