«Disprove», dernier théorème de Fermat [fermé]

49

Ecrivez un programme, dans la langue de votre choix, qui semble bien trouver un contre-exemple au dernier théorème de Fermat . Autrement dit, recherchez les entiers a , b , c > 0 et n > 2 tels que a n + b n = c n .

Bien sûr, vous ne pouvez pas vraiment le faire, à moins que la preuve d'Andrew Wiles ne comporte un défaut. Je veux dire faux , en s'appuyant sur

  • débordement d'entier
  • erreur d'arrondi en virgule flottante
  • comportement indéfini
  • types de données avec des définitions inhabituelles d'addition, d'exponentiation ou d'égalité
  • bogues du compilateur / interprète
  • Ou quelque chose de ce genre.

Vous pouvez coder en dur une partie ou toutes les variables a, b, cou n, ou les rechercher en faisant des boucles comme for a = 1 to MAX.

Ce n'est pas un code de golf; C'est un concours pour trouver des solutions intelligentes et subtiles.

dan04
la source
en fait, vous pouvez en avoir tous comme l’exposant, qui doit être égal à 3 ou plus. Donc, 1 ^ 3 + 1 ^ 3 = 1 ^ 3 c'est aussi simple que cela.
2
@Siver: 1³ + 1³ = 2; 1³ = 1; 2
août

Réponses:

57

J

En fait, Fermat a fait une gaffe: en réalité, il est faux pour tout b, c ou n si a est 1:

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

Peut-être juste peut-être que les règles de priorité de Fermat n'étaient pas strictement de droit à gauche.

jpjacobs
la source
19
+1 Strictement droite à gauche en effet. Juste pour les gens qui lisent de gauche à droite; la notation normale pour le dernier serait1^(9 + (3^(9 = (42^9))))
seequ
1
Sneaky, mon cerveau était sur le point de fondre jusqu'à ce que je voie le commentaire de
@RareRare
3
Est-ce une fonctionnalité prévue de J? C'est le genre de chose qui rendrait vraiment les gens fous.
qwr
2
@qwr En J, toutes les évaluations vont de droite à gauche, à quelques exceptions près. Cela semble bizarre mais c'est en fait assez chouette.
seequ
1
@ dan04 Ce n'est pas à proprement parler vrai. 1^i.5évalue à 1 1 1 1 1.
ɐɔıʇǝɥʇuʎs
36

TI-Basic

1782^12+1841^12=1922^12

Sortie (true)

1
qwr
la source
1
J'ai vu cet épisode si souvent, jamais remarqué. Belle prise!
Dom0
1
Cette réponse ne fonctionne que comme écrit avec TI-Basic TI-89. Sur une TI-84 + SE, le code comporte une erreur de syntaxe, car cette version de TI-Basic n'autorise pas les espaces. Mais la réponse fonctionne toujours sur une ancienne calculatrice si vous supprimez des espaces, en écrivant 1782^12+1841^12=1922^12.
Rory O'Kane
1
+1 pour l'utilisation de TI-Basic, c'était mon premier langage de programmation :)
Kik
2
@ThaneBrimhall C'est l'ironie, une calculatrice échouant à un problème de calcul simple
qwr
35

Java

Ce gars de Fermat devait dormir. Je reçois des centaines de solutions aux équations. J'ai simplement converti ma formule Excel en un programme 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));
    }
}

En ^réalité, l'opérateur désigne XOR en Java, par opposition à une exponentiation en texte brut typique

Erwin Bolwidt
la source
Toute chance sur une élaboration sur pourquoi cela fonctionne?
Vality
20
@Vality: ^en Java, c'est xor, pas le pouvoir.
marinus
3
cela fonctionne techniquement sur presque toutes les langues basées sur le langage 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;
}

Compilé avec clang++ -O3 -o fermat fermat.cpp, testé avec 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

Nous avons évidemment trouvé a, b, c> 0 de sorte que a 3 + b 3 = c 3 (cela fonctionne aussi pour n = 4, 5, 6, ...).

Imprimer un, b et c peut s'avérer un peu difficile cependant ...

Ventero
la source
1
@ dan04: Oops, oublièrent ++dans clang++.
Ventero
2
Au fait, ce n'est pas un bug du compilateur. Le standard C (et C ++) permet de faire n'importe quoi ici, tout comme le val.udébordement (ce serait différent si c'était le cas uint32_t). En outre, ce code utilise également unionde manière incorrecte (selon la norme, vous ne pouvez pas écrire dans un champ et lire l'autre), mais cela est autorisé par de nombreux compilateurs (selon leur documentation).
Konrad Borowski
3
Cela est autorisé par une section de la norme C ++ qui dit: Une boucle qui, en dehors de l'instruction for-init dans le cas d'une instruction for, * n'appelle pas les fonctions d'E / S de la bibliothèque et * ne le fait pas. accéder ou modifier des objets volatiles, et * n'effectue aucune opération de synchronisation (1.10), ni d'opération atomique (Clause 29) pouvant être supposée être terminée par la mise en œuvre.
dan04
3
@ dan04 Ce libellé exact a en fait été supprimé de la norme dans un projet ultérieur, voir US 38 dans open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3196.htm - bien sûr, il n'a été que généralisé. C'est la raison pour laquelle imprimer a,b,c(ou quoi que ce soit d'autre) fermat()fait en sorte que la fonction ne revienne jamais.
Ventero
8
Argh j'allais tellement poster celui-là. Pour ceux qui sont confus: John Regehr a une bonne explication ici .
Voo le
13

Java

Il semble que le théorème soit valable pour n = 3, mais j'ai trouvé des contre-exemples pour 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));
    }
}

Sortie:

true

Explication:

Même si les nombres semblent petits, ils débordent lorsqu'ils sont portés à la 4ème puissance. En réalité, 64 4 + 496 4 = 528 4 - 2 34 , mais 2 34 devient 0 lorsqu'il est limité à int (32 bits).

Aditsu
la source
Pouvez-vous expliquer cela?
Anubian Noob
@AnubianNoob fait
Aditsu
9

Python

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

Qui a dit que c devait être supérieur à a et b ?

Petr Pudlák
la source
2
Il s’imprime Truecar math.pow renvoie des nombres à virgule flottante, qui n’ont pas une précision suffisante pour obtenir la réponse correcte 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

Cette approche trouve un tas de solutions différentes. Par exemple:

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

Comment ça fonctionne

La première ligne doit commencer par un ~pour interpréter l'entrée. Au lieu de, par exemple, le nombre 3, la variable Ncontient la chaîne 3\n.
Alors que 2 3 ?calcule 3 , 2 N ?pousse l'index d'un caractère avec le code ASCII 2 dans N(-1 pour introuvable).
De cette façon, 43 N ?et 82 N ?appuyez -1et 51 N ?continue 0(51 est le code de caractère ASCII de 3).
Depuis -1 + 0 = -1, la condition est remplie et (43,51,82)constitue une "solution".

Dennis
la source
4

C

Bien sûr, vous trouvez tous des contre-exemples, vous continuez à avoir des débordements d’entiers. De plus, vous êtes vraiment lent en itérant sur c aussi. C'est une bien meilleure façon de le faire!

#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 C'est peut-être bien sur la gamme, mais ça manque encore un peu de précision ...

duveteux
la source
4

C

Nous détestons tous les débordements d’entiers, nous allons donc utiliser un petit exposant net quelques conversions en virgule flottante. Mais le théorème ne serait toujours pas valable 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");
}

Sortie:

Disproved for 2139095040, 2139095040, 2139095040, 42: yes

Disproved for 2139095040, 2139095040, 2139095040, 90: yes

Dans IEEE 754, le nombre 2139095040, ou 0x7F800000, représente l'infini positif dans les types à virgule flottante simple précision. Tous les pow(...)appels renverraient + Infinity, et + Infinity sera égal à + Infinity. Une tâche plus facile consisterait à réfuter le théorème de Pythagore en utilisant 0x7F800001 (Quiet NaN) qui n'est pas égal à lui-même selon la norme.

Yuriy Guts
la source
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 est magique, vous savez.

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

Et aussi Wiles n'en est pas un.

Javascript Numbern'est pas assez grand.

Casse-croûte
la source
2

T-SQL

Pour réfuter le théorème de ce type Fermat, il suffit de trouver un contre-exemple. Il semble qu'il était super paresseux et ne l'a essayé que pour une très petite permutation. En fait, il n'essayait même pas. J'ai trouvé un exemple en 0 <a, b, c <15 et 2 <e <15. Désolé, je suis un golfeur de cœur, je code donc plus tard ce code!

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)

Renvoie 1, ce qui signifie que nous avons trouvé un contre-exemple!

Le truc, c'est que, bien que le premier e ressemble à un alias, il s'agit en réalité d'un moyen sournois de changer le type de données de e d'un int à un type à virgule flottante équivalent à un double. Au moment où nous sommes arrivés à 14, nous avons dépassé la précision d'un nombre à virgule flottante, nous pouvons donc ajouter 1 et nous ne perdons toujours rien. La minification est une bonne excuse pour expliquer ma double déclaration apparemment stupide d’un alias de colonne dans le rôle. Si je ne le faisais pas, il déborderait longtemps avant que nous ayons 14-14 ans.

Michael B
la source
1

JavaScript

Il semble que ce gars était sur quelque chose de bien. Sur la drogue si vous me demandez. Compte tenu des contraintes, aucun ensemble de valeurs ne peut être trouvé pour lequel le théorème est vrai.

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

alert(lhs === rhs);

Comme en Java, l' ^opérateur est l'opérateur bit à bit XOR en JavaScript. La méthode correcte pour calculer la puissance d'un nombre consiste à utiliser Math.pow.

thomaux
la source
2
Pour Fermat, l'exposant ( n) doit être >= 3.
récursive
Bon point, le code fonctionne toujours :)
thomaux
0

Un autre contre-exemple BASIC

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 délirant
la source