“Membantah” Teorema Terakhir Fermat [ditutup]

49

Tulis sebuah program, dalam bahasa pilihan Anda, yang tampaknya berhasil menemukan contoh tandingan untuk Teorema Terakhir Fermat . Yaitu, temukan bilangan bulat a , b , c > 0 dan n > 2 sedemikian rupa sehingga n + b n = c n .

Tentu saja, Anda tidak bisa benar - benar melakukannya, kecuali ada kekurangan dalam bukti Andrew Wiles. Maksudku berpura - pura , dengan mengandalkan

  • integer overflow
  • kesalahan pembulatan floating-point
  • perilaku yang tidak terdefinisi
  • tipe data dengan definisi penambahan, eksponensial, atau kesetaraan yang tidak biasa
  • bug kompiler / juru bahasa
  • atau sesuatu di sepanjang garis itu.

Anda mungkin sulit-kode beberapa atau semua variabel a, b, c, atau n, atau mencari mereka dengan melakukan loop seperti for a = 1 to MAX.

Ini bukan kode golf; ini adalah kontes untuk menemukan solusi yang cerdas dan halus.

dan04
sumber
sebenarnya, Anda dapat memiliki yang semuanya selain eksponen, yang harus 3 atau lebih tinggi. Jadi, 1 ^ 3 + 1 ^ 3 = 1 ^ 3 itu sesederhana itu.
2
@Siver: 1³ + 1³ = 2; 1³ = 1; 2 ≠ 1
dan04

Jawaban:

57

J

Sebenarnya, Fermat memang membuat kesalahan besar: Sebenarnya salah untuk b, c atau n jika a adalah 1:

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

Mungkin hanya mungkin, aturan diutamakan Fermat tidak sepenuhnya benar ke kiri.

jpjacobs
sumber
19
+1 Benar-benar kanan ke kiri. Hanya untuk orang yang membaca dari kiri ke kanan; notasi normal untuk yang terakhir adalah1^(9 + (3^(9 = (42^9))))
seequ
1
Sneaky, otakku akan meleleh sampai aku melihat komentar @ TheRare
german_guy
3
Apakah ini fitur yang dimaksudkan dari J? Ini adalah hal yang benar-benar akan membuat orang gila.
qwr
2
@ qwr Di J, semua evaluasi dari kanan ke kiri, dengan beberapa pengecualian. Kedengarannya aneh tapi sebenarnya cukup rapi.
seequ
1
@ dan04 Tidak sepenuhnya benar. 1^i.5mengevaluasi ke 1 1 1 1 1.
ɐɔıʇǝɥʇuʎs
36

TI-Basic

1782^12+1841^12=1922^12

Output (benar)

1
qwr
sumber
1
Saya sering melihat episode itu, tidak pernah memperhatikannya. Tangkapan bagus!
dom0
1
Jawaban ini hanya berfungsi seperti yang ditulis dengan TI-89-flavor TI-Basic. Pada TI-84 + SE, kode tersebut memiliki kesalahan sintaksis, karena versi TI-Basic tidak mengizinkan spasi. Tetapi jawabannya tetap bekerja pada kalkulator yang lebih tua jika Anda menghapus spasi, menulis 1782^12+1841^12=1922^12.
Rory O'Kane
1
+1 untuk menggunakan TI-Basic, itu adalah bahasa pemrograman pertama saya :)
Kik
2
@ThaneBrimhall Itulah ironi, kalkulator yang gagal soal matematika sederhana
qwr
35

Jawa

Cowok Fermat ini pasti sedang tidur. Saya mendapatkan ratusan solusi untuk persamaan. Saya hanya mengkonversi rumus Excel saya ke 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));
    }
}

The ^Operator sebenarnya berarti XOR di Jawa, sebagai lawan eksponensial dalam plain-text yang khas

Erwin Bolwidt
sumber
Apakah ada peluang untuk menjelaskan mengapa ini berhasil?
Vality
20
@ Vality: ^di Java adalah xor, bukan power.
marinus
3
ini secara teknis bekerja pada hampir semua bahasa berbasis 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;
}

Dikompilasi dengan clang++ -O3 -o fermat fermat.cpp, diuji dengan 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

Kami jelas menemukan a, b, c> 0 sehingga a 3 + b 3 = c 3 (ini juga berfungsi untuk n = 4, 5, 6, ...).

Mencetak a, b dan c mungkin agak sulit ...

Ventero
sumber
1
@ dan04: Ups, lupakan ++in clang++.
Ventero
2
Omong-omong, ini bukan bug kompiler. C (dan C ++) standar memungkinkan untuk melakukan apa pun di sini, seperti val.udapat meluap (akan berbeda jika itu akan menjadi uint32_tgantinya). Selain itu, kode ini juga menggunakan unioncara yang tidak benar (menurut standar, Anda tidak dapat menulis ke satu bidang, dan membaca bidang lainnya), tetapi ini diizinkan oleh banyak kompiler (sesuai dengan dokumentasinya).
Konrad Borowski
3
Alasan ini diperbolehkan adalah bagian dari standar C ++ yang mengatakan: Loop yang, di luar pernyataan-init dalam kasus pernyataan for, * tidak membuat panggilan ke fungsi I / O pustaka, dan * tidak mengakses atau memodifikasi objek yang mudah menguap, dan * tidak melakukan operasi sinkronisasi (1.10) atau operasi atom (Ayat 29) dapat diasumsikan oleh implementasi untuk diakhiri.
dan04
3
@ dan04 Kata-kata yang tepat itu sebenarnya telah dihapus dari standar dalam konsep selanjutnya, lihat US 38 di open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3196.htm - tapi tentu saja, hanya saja digeneralisasi. Ini adalah alasan mengapa mencetak a,b,c(atau apa pun, dalam hal ini) fermat()membuat fungsi tidak pernah kembali.
Ventero
8
Argh aku jadi akan memposting yang itu. Bagi siapa pun yang bingung: John Regehr memiliki penjelasan yang bagus di sini .
Voo
13

Jawa

Sepertinya teorema berlaku untuk n = 3, tetapi saya menemukan contoh tandingan untuk 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));
    }
}

Keluaran:

true

Penjelasan:

Bahkan jika angkanya tampak kecil, mereka meluap ketika dinaikkan ke kekuatan ke-4. Pada kenyataannya, 64 4 + 496 4 = 528 4 - 2 34 , tetapi 2 34 menjadi 0 ketika dibatasi ke int (32 bit).

aditsu
sumber
Bisakah Anda menjelaskan ini?
Anubian Noob
@AnubianNoob selesai
aditsu
9

Python

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

Siapa bilang c harus lebih besar dari a dan b ?

Petr Pudlák
sumber
2
Ini mencetak Truekarena math.pow mengembalikan angka floating-point, dan ini tidak memiliki cukup presisi untuk mendapatkan jawaban yang benar 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

Pendekatan ini menemukan banyak solusi yang berbeda. Sebagai contoh:

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

Bagaimana itu bekerja

Baris pertama harus dimulai dengan a ~untuk menginterpretasikan input. Alih-alih, misalnya, angka 3, variabel Nberisi string 3\n.
Saat 2 3 ?menghitung 3 , 2 N ?tekan indeks karakter dengan kode ASCII 2 dalam N(-1 untuk tidak ditemukan).
Dengan cara ini, 43 N ?dan 82 N ?mendorong -1dan 51 N ?mendorong 0(51 adalah kode karakter ASCII 3).
Karena -1 + 0 = -1, kondisinya puas dan (43,51,82)merupakan "solusi".

Dennis
sumber
4

C

Yah tentu saja kalian semua menemukan contoh tandingan, Anda terus mendapatkan bilangan bulat bilangan bulat. Plus, Anda menjadi sangat lambat dengan mengulangi c juga. Ini adalah cara yang jauh lebih baik untuk melakukannya!

#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 mungkin bagus di kisaran, tapi masih sedikit kurang presisi ...

halus
sumber
4

C

Kita semua membenci bilangan bulat bilangan bulat, jadi kami akan menggunakan eksponen kecil ndan beberapa konversi floating point. Tetapi teorema tetap tidak cocok 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");
}

Keluaran:

Disproved for 2139095040, 2139095040, 2139095040, 42: yes

Disproved for 2139095040, 2139095040, 2139095040, 90: yes

Dalam IEEE 754, angka 2139095040, atau 0x7F800000, mewakili tak terhingga positif dalam tipe floating point presisi tunggal. Semua pow(...)panggilan akan mengembalikan + Infinity, dan + Infinity sama dengan + Infinity. Tugas yang lebih mudah adalah menyangkal teorema Pythagoras dengan menggunakan 0x7F800001 (Quiet NaN) yang tidak sama dengan dirinya sendiri sesuai dengan standar.

Nyali Yuriy
sumber
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 adalah sihir, Anda tahu.

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

Dan juga Wiles bukan satu.

Javascript Numbertidak cukup besar.

Camilan
sumber
2

T-SQL

Untuk membantah teorema orang Fermat ini, kita hanya perlu menemukan contoh balasan. Sepertinya, dia sangat malas, dan hanya mencobanya untuk permutasi yang sangat kecil. Bahkan, dia bahkan tidak berusaha. Saya menemukan contoh balasan hanya dalam 0 <a, b, c <15 dan 2 <e <15. Maaf, saya pegolf, jadi saya akan ungolf kode ini nanti!

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)

Mengembalikan 1, artinya kami menemukan contoh balasan!

Kuncinya adalah bahwa sementara e pertama terlihat seperti alias, itu sebenarnya adalah cara licik untuk mengubah tipe data e dari int ke tipe floating point yang setara dengan ganda. Pada saat kita mencapai 14, kita berada di luar ketepatan angka floating point sehingga kita dapat menambahkan 1 ke dalamnya dan kita masih tidak kehilangan apa pun. Minifikasi ini adalah alasan yang bagus untuk menjelaskan deklarasi ganda saya yang kelihatannya konyol dari alias kolom di rcte. Jika saya tidak melakukan ini, itu akan meluap jauh sebelum kita mencapai 14 ^ 14.

Michael B
sumber
1

JavaScript

Tampaknya orang ini ke sesuatu yang baik-baik saja. Ke narkoba jika Anda bertanya kepada saya. Mengingat kendala, tidak ada set nilai yang dapat ditemukan yang mana teorema itu berlaku.

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

alert(lhs === rhs);

Seperti di Jawa, ^operator adalah operator XOR bitwise dalam JavaScript. Cara yang benar untuk menghitung kekuatan angka adalah dengan menggunakan Math.pow.

thomaux
sumber
2
Untuk Fermat, eksponen ( n) harus >= 3.
rekursif
Poin bagus, kodenya masih berfungsi :)
thomaux
0

Contoh tandingan BASIC lainnya

10 a = 858339
20 b = 2162359
30 c = 2162380
40 IF (a^10 + b^10) = c^10 THEN
50   PRINT "Fermat disproved!"
60 ENDIF
lubang keras melengking
sumber