49
votes
\$\begingroup\$

Write a program, in the language of your choice, that appears to successfully find a counterexample to Fermat's Last Theorem. That is, find integers a, b, c > 0 and n > 2 such that an + bn = cn.

Of course, you can't really do it, unless there's a flaw in Andrew Wiles' proof. I mean fake it, by relying on

  • integer overflow
  • floating-point rounding error
  • undefined behavior
  • data types with unusual definitions of addition, exponentiation, or equality
  • compiler/interpreter bugs
  • or something along those lines.

You may hard-code some or all of the variables a, b, c, or n, or search for them by doing loops like for a = 1 to MAX.

This isn't a code golf; it's a contest to find clever and subtle solutions.

\$\endgroup\$
2
  • \$\begingroup\$ actually, you can have ones as all of them besides the exponent, which has to be 3 or higher. So, 1^3+1^3=1^3 its that simple. \$\endgroup\$
    – user32277
    Oct 23, 2014 at 2:21
  • 2
    \$\begingroup\$ @Siver: 1³+1³=2; 1³=1; 2≠1 \$\endgroup\$
    – dan04
    Oct 23, 2014 at 3:52

13 Answers 13

57
votes
\$\begingroup\$

J

Actually, Fermat did make quite a blunder: It's actually wrong for any b, c or n if a is 1:

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

Maybe just maybe, Fermat's precedence rules weren't strictly right to left.

\$\endgroup\$
7
  • 19
    \$\begingroup\$ +1 Strictly right to left indeed. Just for people who read left to right; normal notation for the last one would be 1^(9 + (3^(9 = (42^9)))) \$\endgroup\$
    – seequ
    Jun 28, 2014 at 15:41
  • 1
    \$\begingroup\$ Sneaky, my brain was about to melt until I saw @TheRare's comment \$\endgroup\$
    – german_guy
    Jun 29, 2014 at 18:37
  • 3
    \$\begingroup\$ Is this an intended feature of J? This is the kind of thing that would really drive people insane. \$\endgroup\$
    – qwr
    Jun 30, 2014 at 6:20
  • 2
    \$\begingroup\$ @qwr In J, all evaluation is from right to left, with some exceptions. It sounds weird but is actually pretty neat. \$\endgroup\$
    – seequ
    Jun 30, 2014 at 7:09
  • 1
    \$\begingroup\$ @dan04 Not strictly speaking true. 1^i.5 evaluates to 1 1 1 1 1. \$\endgroup\$ Jul 1, 2014 at 20:20
36
votes
\$\begingroup\$

TI-Basic

1782^12+1841^12=1922^12

Output (true)

1
\$\endgroup\$
9
  • 8
    \$\begingroup\$ photos1.blogger.com/blogger/4608/663/1600/homer.fermat.jpg \$\endgroup\$
    – dan04
    Jun 28, 2014 at 15:44
  • 1
    \$\begingroup\$ I saw that episode so often, never noticed that. Nice catch! \$\endgroup\$
    – dom0
    Jun 29, 2014 at 14:57
  • 1
    \$\begingroup\$ This answer only works as written with TI-89-flavor TI-Basic. On a TI-84+ SE, the code has a syntax error, because that version of TI-Basic does not allow spaces. But the answer still works on an older calculator if you remove spaces, writing 1782^12+1841^12=1922^12. \$\endgroup\$ Jun 29, 2014 at 21:59
  • 1
    \$\begingroup\$ +1 for using TI-Basic, it was my first programming language :) \$\endgroup\$
    – Kik
    Jun 30, 2014 at 17:14
  • 2
    \$\begingroup\$ @ThaneBrimhall That's the irony, a calculator failing a simple math problem \$\endgroup\$
    – qwr
    Jul 1, 2014 at 22:57
35
votes
\$\begingroup\$

Java

This Fermat guy must have been sleeping. I get hundreds of solutions to the equations. I merely converted my Excel formula to a Java program.

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 actually means XOR in Java, as opposed to exponentiation in typical plain-text

\$\endgroup\$
3
  • \$\begingroup\$ Any chance on an elaboration on why this works? \$\endgroup\$
    – Vality
    Jun 28, 2014 at 18:21
  • 20
    \$\begingroup\$ @Vality: ^ in Java is xor, not power. \$\endgroup\$
    – marinus
    Jun 28, 2014 at 18:55
  • 3
    \$\begingroup\$ this technically works on almost any C-based languages \$\endgroup\$
    – phuclv
    Jun 30, 2014 at 11:50
19
votes
\$\begingroup\$

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;
}

Compiled with clang++ -O3 -o fermat fermat.cpp, tested with 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

We obviously found a, b, c > 0 so that a3 + b3 = c3 (this also works for n = 4, 5, 6, ...).

Printing a, b and c might prove a bit difficult though ...

\$\endgroup\$
10
  • 1
    \$\begingroup\$ @dan04: Oops, forgot the ++ in clang++. \$\endgroup\$
    – Ventero
    Jun 28, 2014 at 1:57
  • 2
    \$\begingroup\$ By the way, this is not a compiler bug. C (and C++) standard allows to do anything here, as val.u can overflow (it would be different if it would be uint32_t instead). Besides, this code also uses union in incorrect way (according to standard, you cannot write to one field, and read the other field), but this is allowed by many compilers (according to their documentation). \$\endgroup\$
    – 0..
    Jun 28, 2014 at 13:34
  • 3
    \$\begingroup\$ The reason this is allowed is a section of the C++ standard that says: A loop that, outside of the for-init-statement in the case of a for statement, * makes no calls to library I/O functions, and * does not access or modify volatile objects, and * performs no synchronization operations (1.10) or atomic operations (Clause 29) may be assumed by the implementation to terminate. \$\endgroup\$
    – dan04
    Jun 28, 2014 at 14:27
  • 3
    \$\begingroup\$ @dan04 That exact wording has actually been removed from the standard in a later draft, see US 38 in open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3196.htm - but of course, it's only been generalized. This is the reason why printing out a,b,c (or anything, for that matter) in fermat() makes the function never return. \$\endgroup\$
    – Ventero
    Jun 28, 2014 at 15:16
  • 8
    \$\begingroup\$ Argh I was so going to post that one. For anybody who's confused: John Regehr has a nice explanation here. \$\endgroup\$
    – Voo
    Jun 28, 2014 at 22:59
13
votes
\$\begingroup\$

Java

It looks like the theorem holds for n=3, but I found counterexamples for 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));
    }
}

Output:

true

Explanation:

Even if the numbers seem small, they overflow when raised to the 4th power. In reality, 644 + 4964 = 5284 - 234, but 234 becomes 0 when restricted to int (32 bits).

\$\endgroup\$
2
9
votes
\$\begingroup\$

Python

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

Who says that c must be greater than a and b?

\$\endgroup\$
1
  • 2
    \$\begingroup\$ It prints True because math.pow returns floating-point numbers, and these do not have enough precision to get the correct answer, False. \$\endgroup\$
    – kernigh
    Jun 30, 2014 at 23:58
5
votes
\$\begingroup\$

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

This approach finds a bunch of different solutions. For example:

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

How it works

The first line should start with a ~ to interpret the input. Instead of, e.g., the number 3 , variable N contains the string 3\n.
While 2 3 ? calculates 3, 2 N ? pushes the index of a character with ASCII code 2 in N (-1 for not found).
This way, 43 N ? and 82 N ? push -1 and 51 N ? pushes 0 (51 is the ASCII character code of 3).
Since -1 + 0 = -1, the condition is satisfied and (43,51,82) is a "solution".

\$\endgroup\$
4
votes
\$\begingroup\$

C

Well of course you folks are all finding counterexamples, you keep on getting integer overflows. Plus, you're being really slow by iterating on c as well. This is a much better way to do it!

#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 might be great on the range, but it's still a bit lacking in precision...

\$\endgroup\$
4
votes
\$\begingroup\$

C

We all hate integer overflows, so we'll use a small exponent n and some floating point conversions. But still the theorem would not hold for 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");
}

Output:

Disproved for 2139095040, 2139095040, 2139095040, 42: yes

Disproved for 2139095040, 2139095040, 2139095040, 90: yes

In IEEE 754, the number 2139095040, or 0x7F800000, represents positive infinity in single-precision floating point types. All pow(...) calls would return +Infinity, and +Infinity equals +Infinity. An easier task would be to disprove the Pythagorean theorem by using 0x7F800001 (Quiet NaN) which is not equal to itself according to the standard.

\$\endgroup\$
2
votes
\$\begingroup\$

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 is magic, you know.

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

And also Wiles ain't one.

Javascript Number is not big enough.

\$\endgroup\$
2
votes
\$\begingroup\$

T-SQL

To disprove this Fermat guy's theorem, we just need to find a counter example. It seems, he was super lazy, and only tried it for really small permutation. In fact, he wasn't even trying. I found a counter example in just 0 < a,b,c < 15 and 2 < e < 15. Sorry I'm a golfer at heart so I'll ungolf this code later!

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)

Returns 1, meaning we found a counter example!

The trick is that while the first e looks like an alias, it actually is a sneaky way of changing the data type of e from an int to a floating point type equivalent to a double. By the time we got to 14 we are beyond the precision of a floating point number so we can add 1 to it and we still don't lose anything. The minification is a nice excuse to explain away my seemingly silly double declaration of a column alias in the rcte. If I didn't do this it would overflow long before we got to 14^14.

\$\endgroup\$
1
vote
\$\begingroup\$

JavaScript

It appears this guy was onto something alright. Onto drugs if you ask me. Given the constraints, no set of values can be found for which the theorem holds true.

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

alert(lhs === rhs);

As in Java, the ^ operator is the bitwise XOR operator in JavaScript. The correct way to calculate the power of a number is to use Math.pow.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ For Fermat, the exponent(n) has to be >= 3. \$\endgroup\$
    – recursive
    Jun 30, 2014 at 16:05
  • \$\begingroup\$ Good point, the code still works though :) \$\endgroup\$
    – thomaux
    Jun 30, 2014 at 16:11
0
votes
\$\begingroup\$

Another BASIC counterexample

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.