Sí , podemos encontrar números como este. Lo realmente genial es que podemos hacer esto sin resolver el problema a mano utilizando un probador de teoremas automatizado.
Es una buena demostración para ver porque la mayoría de las personas no se dan cuenta de lo poderosos que pueden ser los probadores de teoremas modernos. Podemos manejar fácilmente todo tipo de problemas, incluso si incluyen cosas como enteros ilimitados , ¡como este!
Para este ejemplo, vamos a utilizar el solucionador SMT de Microsoft, Z3. Esto nos ahorrará bastante pensamiento, lo cual es genial porque pensar apesta :).
Primero, vamos a precisar la pregunta exacta que nos interesa. Una lectura de su pregunta es “¿hay alguna tupla de enteros positivos (a, b, x, y) de tal manera que a / = x, a / = y, b / = x y b / = y y entonces a ^ 2 + b ^ 2 = x ^ 2 + y ^ 2 tiene? ” En realidad, es muy fácil escribir un programa que verifique esto. Voy a usar una biblioteca de Haskell llamada Data.SBV para interactuar con Z3.
- ¿Podemos demostrar que si [matemática] m [/ matemática] y [matemática] n [/ matemática] son dos enteros positivos tales que [matemática] m [/ matemática] divide [matemática] n [/ matemática], entonces [matemática] F_m [/ math] divide [math] F_n [/ math]?
- ¿Cuántos enteros positivos menores que 1000 son infinitamente Euler?
- Some Airways ofrece tres tipos de boletos en sus vuelos de Boston a Nueva York. Los boletos de primera clase son 70, los boletos de segunda clase son 55 y los boletos de reserva son 39. Si 69 pasajeros pagan un total de 3274 por sus boletos en un vuelo en particular, ¿cuántos de cada tipo de boletos se vendieron?
- Supongamos que byc son enteros positivos de modo que las ecuaciones polinómicas [matemáticas] x ^ 2 + bx + c = 0 [/ matemáticas] y [matemáticas] x ^ 2 + bx-c = 0 [/ matemáticas] ambas tienen soluciones enteras. Determine la suma de todos los valores de [math] b \ leq50 [/ math] para los que existen polinomios de esta forma.
- ¿Por qué el producto de tres enteros consecutivos es divisible por 6?
Comenzaré escribiendo una útil función auxiliar que nos permite generar variables que se extiendan sobre enteros positivos. Queremos tanto ∀ como ∃, así que también parametrizaremos sobre el cuantificador:
nombre del cuantificador natural =
do n :: SInteger 0)
volver n
Esto solo asegura que n sea un número entero simbólico (eso es lo que significa “S” en SInteger) limitado a ser siempre positivo.
A continuación, vamos a preguntar si existen cuatro enteros con otras restricciones:
teorema = hacer un <- natural existe "a"
b <- natural existe "b"
x <- existe natural "x"
y <- natural existe "y"
restringir (a ./= x &&& a ./= y)
restringir (b ./= x &&& b ./= y)
restringir (a. <= b &&& x. <= y &&& a. <= x)
return (a ^ 2 + b ^ 2. == x ^ 2 + y ^ 2)
Este código solo introduce nuestras variables, asegura que sean distintas y verifica nuestra restricción de “suma de cuadrados”. Realmente, solo está reescribiendo nuestra pregunta original en una sintaxis un poco extraña. Los operadores son feos sobre todo porque las versiones bonitas ya están tomadas por la biblioteca estándar de Haskell.
Agregué la restricción adicional de que a ≤ b y x ≤ y para filtrar soluciones que son las mismas, excepto para intercambiar a con b o x con y. Esto será útil cuando queramos enumerar un montón de soluciones.
Ahora podemos pedirle a z3 que resuelva nuestras variables:
* Datos principales.SBV> teorema sat Satisfable Modelo: a = 16 :: SInteger b = 2 :: SInteger x = 8 :: SInteger y = 14 :: SInteger
Y ahí lo tiene: ¡un ejemplo que se ajusta a lo que estaba pidiendo! También podemos pedir cada tupla, y estaremos encantados de imprimirlas. Estoy bastante seguro de que hay un número infinito de estos, por lo que puede llevar un tiempo.]
* Datos principales.SBV> allSat teorema Solución # 1: a = 16 :: SInteger b = 2 :: SInteger x = 8 :: SInteger y = 14 :: SInteger Solución # 2: a = 1 :: SInteger b = 32 :: SInteger x = 8 :: SInteger y = 31 :: SInteger ...
Ahora, ¿qué tal una pregunta diferente? ¿Es posible encontrar tal x, y para todos los pares a, b? Solo podemos modificar nuestro código original:
teorema '= hacer un <- forall natural "a"
b <- para toda la vida "b"
x <- existe natural "x"
y <- natural existe "y"
restringir (a ./= x &&& a ./= y)
restringir (b ./= x &&& b ./= y)
restringir (a. <= b &&& x. <= y &&& a. <= x)
return (a ^ 2 + b ^ 2. == x ^ 2 + y ^ 2)
Ahora lo ejecutamos nuevamente:
* Datos principales.SBV> teorema sat ' Insatisfactorio
No. No podemos hacer esto para todos los pares de enteros positivos. Demasiado.
Si quieres jugar con esto tú mismo, puedes tomar mi código: Suma de cuadrados con Z3
También necesitará instalar SBV. Lea 24 Days of Hackage: sbv para una introducción a la biblioteca.
También podemos hacer un razonamiento más complicado. Por ejemplo, el artículo que Justin Rising enlazó tiene una lista elegante de sumas que se pueden escribir así. ¡Podemos generar esa misma lista nosotros mismos, reutilizando el theorem de arriba!
El truco es que podemos descomprimir un resultado en un contenedor de algún tipo. Aquí hay un práctico programa de ayuda que solo enumera las soluciones a este problema:
generateList = do result print $ a ^ 2 + b ^ 2
Desafortunadamente, esto sigue enumerando soluciones para siempre sin un orden apreciable. El orden en que se generan las soluciones depende del funcionamiento interno del solucionador, por lo que no podemos confiar realmente en él. Lo que realmente queremos es generar todas las soluciones de manera que a ^ 2 + b ^ 2 sea menor que algún límite.
De hecho, esta es una táctica que terminamos usando con bastante frecuencia al resolver problemas con solucionadores SMT. Al elegir un límite arbitrario y reducirlo, podemos obtener soluciones en el rango que deseamos o incluso optimizar una solución.
Primero, modificamos el theorem para tomar un límite:
upTo limit = do a <- natural existe "a"
b <- natural existe "b"
x <- existe natural "x"
y <- natural existe "y"
restringir $ a ./= x &&& a ./= y
restringir $ b ./= x &&& b ./= y
restringir $ a. <= b &&& x. <= y &&& a. <= x
restringir $ a ^ 2 + b ^ 2. == x ^ 2 + y ^ 2
devuelve $ a ^ 2 + b ^ 2. <= límite
Luego hacemos lo mismo para nuestra función auxiliar:
generateListUpTo limit =
hacer resultado <- allSat (hasta el límite)
dejemos sumSq [a, b] = a ^ 2 + b ^ 2
ls :: [Entero] = ordenar. map (sumSq. take 2) $ extractModels resultado
forM_ ls print
Finalmente, podemos ejecutar esto.
* Datos principales.SBV> generateListUpTo 205 50 sesenta y cinco 85 125 130 145 170 185 200 205
Oye, obtuvimos el mismo resultado que el documento vinculado sin hacer ningún cálculo real . Bastante cargada.
