"Desaprobar" El último teorema de Fermat [cerrado]

49

Escriba un programa, en el idioma que elija, que parece encontrar con éxito un contraejemplo del último teorema de Fermat . Es decir, encuentre números enteros a , b , c > 0 y n > 2 de modo que a n + b n = c n .

Por supuesto, no se puede realmente hacerlo, a menos que haya una falla en la prueba Andrew Wiles. Me refiero a fingir , confiando en

  • desbordamiento de enteros
  • error de redondeo de punto flotante
  • comportamiento indefinido
  • tipos de datos con definiciones inusuales de suma, exponenciación o igualdad
  • errores del compilador / intérprete
  • O algo por el estilo.

Usted puede difícil que el código algunas o todas las variables a, b, c, o n, o la búsqueda de ellos haciendo bucles como for a = 1 to MAX.

Este no es un código de golf; Es un concurso para encontrar soluciones inteligentes y sutiles.

dan04
fuente
en realidad, puede tener unos como todos ellos además del exponente, que debe ser 3 o superior. Entonces, 1 ^ 3 + 1 ^ 3 = 1 ^ 3 es así de simple.
2
@Siver: 1³ + 1³ = 2; 1³ = 1; 2 ≠ 1
dan04

Respuestas:

57

J

En realidad, Fermat cometió un gran error: en realidad está mal para cualquier b, c o n si a es 1:

   1^3 + 4^3 = 5^3
1
   1^4 + 5^4 = 11^4
1
   1^9 + 3^9 = 42^9
1

Tal vez solo tal vez, las reglas de precedencia de Fermat no eran estrictamente de derecha a izquierda.

jpjacobs
fuente
19
+1 Estrictamente de derecha a izquierda. Solo para personas que leen de izquierda a derecha; la notación normal para el último sería1^(9 + (3^(9 = (42^9))))
verqu
1
Disimulado, mi cerebro estaba a punto de derretirse hasta que vi el comentario de @ TheRare
german_guy
3
¿Es esta una característica prevista de J? Este es el tipo de cosa que realmente volvería loca a la gente.
qwr
2
@qwr En J, toda la evaluación es de derecha a izquierda, con algunas excepciones. Suena raro pero en realidad es bastante bueno.
seequ
1
@ dan04 No es estrictamente hablando cierto. 1^i.5evalúa a 1 1 1 1 1.
1ıʇǝɥʇuʎs
36

TI-Basic

1782^12+1841^12=1922^12

Salida (verdadero)

1
qwr
fuente
1
Vi ese episodio tan a menudo, nunca lo noté. ¡Buena atrapada!
dom0
1
Esta respuesta solo funciona como está escrita con TI-89-taste TI-Basic. En una TI-84 + SE, el código tiene un error de sintaxis, porque esa versión de TI-Basic no permite espacios. Pero la respuesta aún funciona en una calculadora más antigua si elimina espacios, escribiendo 1782^12+1841^12=1922^12.
Rory O'Kane
1
+1 por usar TI-Basic, fue mi primer lenguaje de programación :)
Kik
2
@ThaneBrimhall Esa es la ironía, una calculadora que falla un problema matemático simple
qwr
35

Java

Este chico Fermat debe haber estado durmiendo. Obtengo cientos de soluciones a las ecuaciones. Simplemente convertí mi fórmula de Excel a un programa Java.

public class FermatNoMore {
    public static void main(String[] args) {
        for (int n = 3; n < 6; n++)
            for (int a = 1; a < 1000; a++)
                for (int b = 1; b < 1000; b++)
                    for (int c = 1; c < 1000; c++)
                        if ((a ^ n + b ^ n) == (c ^ n))
                            System.out.println(String.format("%d^%d + %d^%d = %d^%d", a, n, b, n, c, n));
    }
}

El ^operador en realidad significa XOR en Java, en oposición a la exponenciación en texto plano típico

Erwin Bolwidt
fuente
¿Alguna posibilidad de una explicación de por qué esto funciona?
Vality
20
@Vality: ^en Java es xor, no poder.
marinus
3
esto técnicamente funciona en casi cualquier lenguaje basado en C
phuclv
19

C ++

#include <cstdlib>
#include <iostream>

unsigned long pow(int a, int p) {
  unsigned long ret = a;

  for (int i = 1; i < p; ++i)
    ret *= a;

  return ret;
}

bool fermat(int n) {
  // surely we can find a counterexample with 0 < a,b,c < 256;
  unsigned char a = 1, b = 1, c = 1;

  // don't give up until we've found a counterexample
  while (true) {
    if (pow(a, n) + pow(b, n) == pow(c, n)) {
      // found one!
      return true;
    }

    // make sure we iterate through all positive combinations of a,b,c
    if (!++a) {
      a = 1;
      if (!++b) {
        b = 1;
        if (!++c)
          c = 1;
      }
    }
  }

  return false;
}

int main(int argc, char** argv) {
  if (fermat(std::atoi(argv[1])))
   std::cout << "Found a counterexample to Fermat's Last Theorem" << std::endl;
}

Compilado con clang++ -O3 -o fermat fermat.cpp, probado con Ubuntu clang version 3.4.1-1~exp1 (branches/release_34) (based on LLVM 3.4.1):

./fermat 3
Found a counterexample to Fermat's Last Theorem

Obviamente encontramos a, b, c> 0 para que a 3 + b 3 = c 3 (esto también funciona para n = 4, 5, 6, ...).

Sin embargo, imprimir a, byc puede resultar un poco difícil ...

Ventero
fuente
1
@ dan04: Vaya, se olvidó de la ++en clang++.
Ventero
2
Por cierto, esto no es un error del compilador. El estándar C (y C ++) permite hacer cualquier cosa aquí, ya que val.upuede desbordarse (sería diferente si lo fuera uint32_t). Además, este código también se usa unionde manera incorrecta (según el estándar, no se puede escribir en un campo y leer el otro campo), pero muchos compiladores lo permiten (de acuerdo con su documentación).
Konrad Borowski
3
La razón por la que esto está permitido es una sección del estándar C ++ que dice: Un bucle que, fuera de la instrucción for-init en el caso de una instrucción for, * no realiza llamadas a las funciones de E / S de la biblioteca y * no accede o modifica objetos volátiles, y * no realiza operaciones de sincronización (1.10) u operaciones atómicas (Cláusula 29) que puede suponer que la implementación termina.
dan04
3
@ dan04 Esa redacción exacta se ha eliminado del estándar en un borrador posterior, consulte US 38 en open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3196.htm , pero, por supuesto, solo ha sido generalizado Esta es la razón por la cual imprimir a,b,c(o cualquier otra cosa) fermat()hace que la función nunca regrese.
Ventero
8
Argh, iba a publicar eso. Para cualquiera que esté confundido: John Regehr tiene una buena explicación aquí .
Voo
13

Java

Parece que el teorema se cumple para n = 3, pero encontré contraejemplos para n = 4:

public class Fermat {
    public static int p4(final int x) {
        return x * x * x * x;
    }

    public static void main(final String... args) {
        System.out.println(p4(64) + p4(496) == p4(528));
    }
}

Salida:

true

Explicación:

Incluso si los números parecen pequeños, se desbordan cuando se elevan a la cuarta potencia. En realidad, 64 4 + 496 4 = 528 4 - 2 34 , pero 2 34 se convierte en 0 cuando está restringido a int (32 bits).

aditsu
fuente
¿Puedes explicar esto?
Anubian Noob
@AnubianNoob hecho
aditsu
9

Pitón

import math
print math.pow(18014398509481984,3) + math.pow(1, 3) \
      == math.pow(18014398509481983,3)

¿Quién dice que c debe ser mayor que a y b ?

Petr Pudlák
fuente
2
Se imprime Trueporque los números de retornos Math.pow de punto flotante, y éstos no tienen la suficiente precisión para obtener la respuesta correcta, False.
kernigh
5

GolfScript

# Save the number read from STDIN in variable N and format for output.

:N"n="\+

{
  [{100rand)}3*] # Push an array of three randomly selected integers from 1 to 100.
  .{N?}/         # Compute x**N for each of the three x.
  +=!            # Check if the sum of the topmost two results equals the third.
}{;}while        # If it doesn't, discard the array and try again.

# Moar output formatting.

~]["a=""\nb=""\nc="""]]zip

Este enfoque encuentra un montón de soluciones diferentes. Por ejemplo:

$ golfscript fermat.gs <<< 3
n=3
a=43
b=51
c=82

Cómo funciona

La primera línea debe comenzar con a ~para interpretar la entrada. En lugar de, por ejemplo, el número 3, la variable Ncontiene la cadena 3\n.
Mientras 2 3 ?calcula 3 , 2 N ?empuja el índice de un personaje con el código ASCII 2 en N(-1 para no encontrado).
De esta manera, 43 N ?y 82 N ?empujar -1y 51 N ?empujones 0(51 es el código de caracteres ASCII de 3).
Desde entonces -1 + 0 = -1, la condición se cumple y (43,51,82)es una "solución".

Dennis
fuente
4

C

Bueno, por supuesto, todos ustedes están encontrando contraejemplos, siguen obteniendo desbordamientos de enteros. Además, estás siendo muy lento al iterar en c también. ¡Esta es una forma mucho mejor de hacerlo!

#include <stdio.h>
#include <math.h>

int main(void) {
  double a, b, c;
  for (a = 2; a < 1e100; a *= 2) {
    for (b = 2; b < 1e100; b *= 2) {
      c = pow(pow(a, 3) + pow(b, 3), 1.0/3);
      if (c == floor(c)) {
        printf("%f^3 + %f^3 == %f^3\n", a, b, c);
      }
    }
  }
  return 0;
}

double puede ser excelente en el rango, pero aún le falta un poco de precisión ...

mullido
fuente
4

C

Todos odiamos los desbordamientos de enteros, por lo que utilizaremos un pequeño exponente ny algunas conversiones de coma flotante. Pero aún así el teorema no sería válido a = b = c = 2139095040.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int a, b, c;
int n;

int disprove(int a, int b, int c, int n)
{
    // Integers are so prone to overflow, so we'll reinforce them with this innocent typecast.
    float safe_a = *((float *)&a);
    float safe_b = *((float *)&b);
    float safe_c = *((float *)&c);

    return pow(safe_a, n) + pow(safe_b, n) == pow(safe_c, n);
}

int main(void)
{
    srand(time(NULL));

    a = b = c = 2139095040;
    n = rand() % 100 + 3;

    printf("Disproved for %d, %d, %d, %d: %s\n", a, b, c, n, disprove(a, b, c, n) ? "yes" : "no");
}

Salida:

Disproved for 2139095040, 2139095040, 2139095040, 42: yes

Disproved for 2139095040, 2139095040, 2139095040, 90: yes

En IEEE 754, el número 2139095040, o 0x7F800000, representa infinito positivo en tipos de coma flotante de precisión simple. Todas las pow(...)llamadas devolverían + Infinito, y + Infinito es igual a + Infinito. Una tarea más fácil sería refutar el teorema de Pitágoras usando 0x7F800001 (Quiet NaN) que no es igual a sí mismo de acuerdo con el estándar.

Tripas Yuriy
fuente
2

Javascript

var a, b, c, MAX_ITER = 16;
var n = 42;
var total = 0, error = 0;

for(a = 1 ; a <= MAX_ITER ; a++) {
  for(b = 1 ; b <= MAX_ITER ; b++) {
    for(c = 1 ; c <= MAX_ITER ; c++) {
      total++;
      if(Math.pow(a, n) + Math.pow(b, n) == Math.pow(c, n)) {
        error++;
        console.log(a, b, c);
      }
    }
  }
}

console.log("After " + total + " calculations,");
console.log("I got " + error + " errors but Fermat ain't one.");

42 es magia, ya sabes.

> node 32696.js
After 2176 calculations,
I got 96 errors but Fermat ain't one.

Y también Wiles no es uno.

Javascript Numberno es lo suficientemente grande.

Bocadillo
fuente
2

T-SQL

Para refutar el teorema de este tipo de Fermat, solo necesitamos encontrar un contraejemplo. Parece que era súper perezoso, y solo lo intentó por una permutación realmente pequeña. De hecho, ni siquiera lo estaba intentando. Encontré un ejemplo de contador en solo 0 <a, b, c <15 y 2 <e <15. Lo siento, soy un jugador de golf en el fondo, ¡así que desligaré este código más tarde!

with T(e)as(select 1e union all select (e+1) from T where e<14)select isnull(max(1),0)FROM T a,T b,T c,T e where e.e>2 and power(a.e,e.e)+power(b.e,e.e)=power(c.e,e.e)

Devuelve 1, lo que significa que encontramos un contraejemplo.

El truco es que si bien la primera e parece un alias, en realidad es una forma disimulada de cambiar el tipo de datos de e de un tipo int a un tipo de coma flotante equivalente a un doble. Para cuando llegamos a 14, estamos más allá de la precisión de un número de coma flotante, por lo que podemos agregarle 1 y aún así no perdemos nada. La minificación es una buena excusa para explicar mi aparentemente doble declaración tonta de un alias de columna en el rcte. Si no lo hiciera, se desbordaría mucho antes de llegar a 14 ^ 14.

Michael B
fuente
1

JavaScript

Parece que este tipo estaba en algo bien. Sobre las drogas si me preguntas. Dadas las restricciones, no se puede encontrar un conjunto de valores para los cuales el teorema sea verdadero.

var a = 1,
    b = 1,
    c = 1,
    n = 3,
    lhs = (a^n + b^n),
    rhs = c^n;

alert(lhs === rhs);

Como en Java, el ^operador es el operador XOR bit a bit en JavaScript. La forma correcta de calcular la potencia de un número es usar Math.pow.

thomaux
fuente
2
Para Fermat, el exponente ( n) tiene que ser >= 3.
recursivo
Buen punto, el código aún funciona :)
thomaux
0

Otro contraejemplo BÁSICO

10 a = 858339
20 b = 2162359
30 c = 2162380
40 IF (a^10 + b^10) = c^10 THEN
50   PRINT "Fermat disproved!"
60 ENDIF
ossifrage aprensivo
fuente