Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Siver Oct 23 at 2:21
1  
@Siver: 1³+1³=2; 1³=1; 2≠1 –  dan04 Oct 23 at 3:52

14 Answers 14

up vote 57 down vote accepted

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.

share|improve this answer
19  
+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)))) –  Sieg Jun 28 at 15:41
1  
Sneaky, my brain was about to melt until I saw @TheRare's comment –  german_guy Jun 29 at 18:37
3  
Is this an intended feature of J? This is the kind of thing that would really drive people insane. –  qwr Jun 30 at 6:20
2  
@qwr In J, all evaluation is from right to left, with some exceptions. It sounds weird but is actually pretty neat. –  Sieg Jun 30 at 7:09
1  
@dan04 Not strictly speaking true. 1^i.5 evaluates to 1 1 1 1 1. –  ɐɔıʇǝɥʇuʎs Jul 1 at 20:20

TI-Basic

1782^12+1841^12=1922^12

Output (true)

1
share|improve this answer
16  
+1 for the Simpsons reference –  dan04 Jun 28 at 1:36
8  
1  
I saw that episode so often, never noticed that. Nice catch! –  dom0 Jun 29 at 14:57
1  
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. –  Rory O'Kane Jun 29 at 21:59
2  
@ThaneBrimhall That's the irony, a calculator failing a simple math problem –  qwr Jul 1 at 22:57

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

share|improve this answer
    
Any chance on an elaboration on why this works? –  Vality Jun 28 at 18:21
19  
@Vality: ^ in Java is xor, not power. –  marinus Jun 28 at 18:55
3  
this technically works on almost any C-based languages –  Lưu Vĩnh Phúc Jun 30 at 11:50

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 ...

share|improve this answer
1  
@dan04: Oops, forgot the ++ in clang++. –  Ventero Jun 28 at 1:57
2  
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). –  xfix Jun 28 at 13:34
3  
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. –  dan04 Jun 28 at 14:27
3  
@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. –  Ventero Jun 28 at 15:16
8  
Argh I was so going to post that one. For anybody who's confused: John Regehr has a nice explanation here. –  Voo Jun 28 at 22:59

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).

share|improve this answer
    
Can you explain this? –  Anubian Noob Jun 29 at 23:01
    
@AnubianNoob done –  aditsu Jun 30 at 6:47

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?

share|improve this answer
2  
It prints True because math.pow returns floating-point numbers, and these do not have enough precision to get the correct answer, False. –  kernigh Jun 30 at 23:58

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".

share|improve this answer

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...

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Mulit-Language

For all who had mis-typed like this

int an=a^n;
int bn=b^n;
int cn=c^n;
if(an+bn=cn)
{
[...]
}
share|improve this answer
    
In what C-syntax-family language does an+bn=cn even compile? –  fluffy Jul 1 at 1:37
    
I think you meant cn=an+bn. –  dan04 Jul 1 at 2:42
    
In javascript you can run an + (bn = cn), but not the way it is in the answer, without parentheses. –  Chris Hayes Jul 1 at 6:58

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.

share|improve this answer
2  
For Fermat, the exponent(n) has to be >= 3. –  recursive Jun 30 at 16:05
    
Good point, the code still works though :) –  Anzeo Jun 30 at 16:11

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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