Ostatnie twierdzenie Fermata „odrzucają” [zamknięte]


49

Napisz program w wybranym języku, który wydaje się skutecznie znajdować kontrprzykład na temat ostatniego twierdzenia Fermata . Oznacza to, że znalezienie liczby całkowite a , b , c > 0 n > 2, tak że n + b n = c n .

Oczywiście, nie można naprawdę zrobić, o ile nie jest to wada w dowodzie Andrew Wiles. Mam na myśli podróbkę , polegając na

  • całkowitą przepełnienie
  • błąd zaokrąglania zmiennoprzecinkowego
  • niezdefiniowane zachowanie
  • typy danych z nietypowymi definicjami dodawania, potęgowania lub równości
  • błędy kompilatora / interpretera
  • lub coś podobnego.

Państwo może trudno kod niektóre lub wszystkie zmienne a, b, c, lub n, lub poszukać dla nich robiąc pętle podoba for a = 1 to MAX.

To nie jest golf golfowy; konkurs polega na znalezieniu sprytnych i subtelnych rozwiązań.


tak naprawdę możesz mieć je jako wszystkie oprócz wykładnika, który musi wynosić 3 lub więcej. Więc 1 ^ 3 + 1 ^ 3 = 1 ^ 3 to takie proste.

2
@Siver: 1³ + 1³ = 2; 1³ = 1; 2 ≠ 1
dan04

Odpowiedzi:


57

jot

W rzeczywistości Fermat popełnił dość pomyłkę: w rzeczywistości jest źle dla dowolnego b, c lub n, jeśli a wynosi 1:

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

Może po prostu zasady pierwszeństwa Fermata nie były ściśle od prawej do lewej.


19
+1 Rzeczywiście ściśle od prawej do lewej. Tylko dla osób, które czytają od lewej do prawej; normalnym zapisem dla ostatniego byłoby1^(9 + (3^(9 = (42^9))))
patrz

1
Podstępnie, mój mózg miał się stopić, dopóki nie zobaczyłem komentarza @ TheRare
german_guy

3
Czy jest to zamierzona funkcja J? Tego rodzaju rzeczy naprawdę doprowadzałyby ludzi do szaleństwa.
qwr

2
@qwr W J cała ocena odbywa się od prawej do lewej, z pewnymi wyjątkami. Brzmi dziwnie, ale jest całkiem fajny.
patrz

1
@ dan04 Nie do końca prawdą. 1^i.5ocenia na 1 1 1 1 1.
1ıʇǝɥʇuʎs

36

TI-Basic

1782^12+1841^12=1922^12

Wyjście (prawda)

1


1
Tak często widziałem ten odcinek, nigdy tego nie zauważyłem. Dobry chwyt!
dom0

1
Ta odpowiedź działa tylko tak, jak napisano w przypadku TI-89 o smaku TI-Basic. W TI-84 + SE kod zawiera błąd składniowy, ponieważ ta wersja TI-Basic nie dopuszcza spacji. Ale odpowiedź nadal działa na starszym kalkulatorze, jeśli usuniesz spacje, pisząc 1782^12+1841^12=1922^12.
Rory O'Kane

1
+1 za korzystanie z TI-Basic, to był mój pierwszy język programowania :)
Kik

2
@TaneBrimhall To ironia, kalkulator nie
radzi

35

Jawa

Ten facet Fermata musiał spać. Dostaję setki rozwiązań równań. Po prostu przekonwertowałem moją formułę Excel na program 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));
    }
}

^Operator faktycznie oznacza XOR w Javie, w przeciwieństwie do potęgowania w typowy zwykły tekst


Czy jest jakaś szansa na wyjaśnienie, dlaczego to działa?
Vality

20
@Vality: ^w Javie jest Xor, a nie moc.
marinus

3
technicznie działa to na prawie wszystkich językach opartych na języku 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;
}

Kompilowany clang++ -O3 -o fermat fermat.cpp, testowany z 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

Znaleźliśmy a, b, c> 0, więc a 3 + b 3 = c 3 (działa to również dla n = 4, 5, 6, ...).

Drukowanie a, b i c może jednak okazać się nieco trudne ...


1
@ dan04: Ups, zapomniałem ++in clang++.
Ventero

2
Nawiasem mówiąc, nie jest to błąd kompilatora. Standard C (i C ++) pozwala tutaj cokolwiek zrobić, podobnie jak val.uprzepełnienie (byłoby inaczej, gdyby tak było uint32_t). Poza tym kod ten również używa unionw niewłaściwy sposób (zgodnie ze standardem nie można pisać w jednym polu, a czytać w drugim polu), ale jest to dozwolone przez wiele kompilatorów (zgodnie z ich dokumentacją).
Konrad Borowski

3
Przyczyną tego jest sekcja standardu C ++, która mówi: Pętla, która poza instrukcją for-init w przypadku instrukcji for, * nie wywołuje funkcji bibliotecznych we / wy, a * nie uzyskiwać dostęp lub modyfikować obiekty lotne i * nie wykonuje żadnych operacji synchronizacji (1.10) lub operacji atomowych (klauzula 29) można uznać za zakończone.
dan04

3
@ dan04 To dokładne sformułowanie zostało faktycznie usunięte ze standardu w późniejszym szkicu, patrz US 38 w open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3196.htm - ale oczywiście to tylko uogólnione. To jest powód, dla którego wydruk a,b,c(lub cokolwiek, w tym przypadku) fermat()sprawia, że ​​funkcja nigdy nie powróci.
Ventero

8
Argh, tak zamierzałem to zamieścić. Dla każdego, kto się mylić: John Regehr ma ładne wyjaśnienie tutaj .
Voo

13

Jawa

Wygląda na to, że twierdzenie dotyczy n = 3, ale znalazłem kontrprzykłady dla 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));
    }
}

Wynik:

true

Wyjaśnienie:

Nawet jeśli liczby wydają się małe, przepełniają się, gdy zostaną podniesione do 4. potęgi. W rzeczywistości 64 4 + 496 4 = 528 4 - 2 34 , ale 2 34 staje się 0, gdy ogranicza się do int (32 bity).


Czy możesz to wyjaśnić?
Anubian Noob

@AnubianNoob zrobione
aditsu

9

Pyton

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

Kto mówi, że c musi być większa niż i B ?


2
Drukuje Trueponieważ Math.pow zwraca liczb zmiennoprzecinkowych, a te nie mają wystarczająco dużo precyzji, aby uzyskać właściwą odpowiedź 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

To podejście znajduje wiele różnych rozwiązań. Na przykład:

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

Jak to działa

Pierwszy wiersz powinien zaczynać się od, ~aby zinterpretować dane wejściowe. Zamiast np. Liczby 3 zmienna Nzawiera ciąg znaków 3\n.
Podczas 2 3 ?obliczania 3 , 2 N ?wypycha indeks znaku o kodzie ASCII 2 do N(-1 dla nie znalezionego).
W ten sposób, 43 N ?i 82 N ?przeć -1i 51 N ?popycha 0(51 to kod ASCII charakter 3).
Ponieważ -1 + 0 = -1warunek jest spełniony i (43,51,82)jest „rozwiązaniem”.


4

do

No cóż, oczywiście, wy wszyscy znajdujecie kontrprzykłady, ciągle dostajecie przepełnienia liczb całkowitych. Plus, jesteś naprawdę powolny, powtarzając również na c. To znacznie lepszy sposób na zrobienie tego!

#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 może być świetny w tym zakresie, ale wciąż brakuje mu precyzji ...


4

do

Wszyscy nienawidzimy przepełnień liczb całkowitych, więc użyjemy małego wykładnika ni niektórych konwersji zmiennoprzecinkowych. Jednak twierdzenie to nadal nie istnieje 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");
}

Wynik:

Disproved for 2139095040, 2139095040, 2139095040, 42: yes

Disproved for 2139095040, 2139095040, 2139095040, 90: yes

W IEEE 754 liczba 2139095040 lub 0x7F800000 reprezentuje dodatnią nieskończoność w typach zmiennoprzecinkowych pojedynczej precyzji. Wszystkie pow(...)połączenia zwrócą + Infinity, a + Infinity równa się + Infinity. Łatwiejszym zadaniem byłoby obalenie twierdzenia Pitagorasa za pomocą 0x7F800001 (cichy NaN), który według normy nie jest sobie równy.


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 to magia, wiesz.

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

A także Wiles nie jest jednym.

JavaScript Numbernie jest wystarczająco duży.


2

T-SQL

Aby obalić twierdzenie tego faceta Fermata, musimy tylko znaleźć przeciwny przykład. Wygląda na to, że był bardzo leniwy i próbował tego tylko dla naprawdę małej permutacji. W rzeczywistości nawet nie próbował. Znalazłem licznik w zaledwie 0 <a, b, c <15 i 2 <e <15. Przepraszam, że jestem golfistą, więc odkopię ten kod później!

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)

Zwraca 1, co oznacza, że ​​znaleźliśmy przeciwny przykład!

Sztuczka polega na tym, że chociaż pierwszy e wygląda jak alias, w rzeczywistości jest to podstępny sposób zmiany typu danych e z int na zmiennoprzecinkowy równoważny podwójnemu. Gdy osiągnęliśmy 14, jesteśmy już poza precyzją liczby zmiennoprzecinkowej, więc możemy dodać do niej 1 i nadal nic nie stracimy. Minifikacja jest dobrym pretekstem do wyjaśnienia mojej z pozoru głupiej podwójnej deklaracji aliasu kolumny w rekt. Gdybym tego nie zrobił, przepełniłoby się na długo, zanim dotrzemy do 14 ^ 14.


1

JavaScript

Wygląda na to, że ten facet był na czymś w porządku. Na narkotyki, jeśli mnie pytasz. Biorąc pod uwagę ograniczenia, nie można znaleźć zestawu wartości, dla których twierdzenie jest prawdziwe.

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

alert(lhs === rhs);

Podobnie jak w Javie, ^operator jest bitowym operatorem XOR w JavaScript. Prawidłowym sposobem obliczenia potęgi liczby jest użycie Math.pow.


2
W przypadku Fermata wykładnik ( n) musi być >= 3.
rekursywny

Dobrze, kod wciąż działa :)
thomaux

0

Kolejny kontrprzykład 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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.