Breaking Fermat (Part 2 of 3)
It turns out Fermat, and Wiles, were actually right. The
famous FLT:
“The equation X^N +
Y^N = Z^N has no trivial integer solutions for N > 2”
Indeed it is correct. I’ll talk about how Wiles got the
proof right in 1995 (and what kind of proof Fermat may have had) in part 3 of
this post. But if that’s the case, how come the equality 7965^32 + 9516^32 =
9517^32 then? Well it doesn’t as my friend Taras correctly observed. This
equality only holds for the first 10 digits of the result – that’s why when
looking at the results of the left and right parts separately on a hand-pocket
calculator, or on Bing or Google, you may be deceived to believe that this
result is true because these calculators truncate the results after the 9th
or the 10th digit. These are the so-called “Fake FLT Numbers”
(F-FLT-N). Let’s write a code in C# to find few F-FLT-N.
First some principles
that we’ll apply:
a)
We’ll be dealing with massive huge numbers,
numbers with up to 300 digits long. Must use BigInteger.
b)
We’ll find an F-FLT-N when the first 10 digits
of (a^n+b^n) equals the first 10 digits of (c^n)
c)
Some limits that we’ll try:
a.
The exponent can go up to 100 (N<=100)
b.
The numbers (a,b,c) can go up to 10,000 (a,b,c
<= 10,000)
Alright, this will be a brute-force solution, with just few
adjustments. First, notice the following: a very basic brute-force all up might
have some problems because you may end up with:
a)
3 <= n <= 100
a.
1 <= a <= 10,000
i.
1 <= b <= 10,000
1.
1 <= c <= 10,000
If you multiply them all together to find the time complexity you get this
number: O(F-FLT-N) = 100,000,000,000,000. Your code will certainly take several
months to finish running on a very fast machine. Hence some pruning will be
necessary. Here are few improvements that will reduce the time complexity of
your brute-force algorithm from intractable to tolerable:
a)
First of, build a big cache in memory. The
calculation BigInteger.Pow is very experience by itself (which just makes the 100,000,000,000,000
even worse). Build a cache with the first 30,000 results for each of the 100
exponents. That means an initial calculation of 3,000,000 BigInteger.Pow and
storing the results in memory. In fact double that space because I also want to
store the “string” version of the same numbers. That’s fine, memory is usually
cheap.
b)
Alright, now the big improvement to the time
complexity: we’re going to have the result (a^n+b^n), and we want to find the
closest c^n to it. Well we have the cache, and the cache is sorted. We can do a Binary Search to
find the closest c^n. c^n will never be equal to (a^n+b^n) (otherwise FLT would
be wrong), but you’ll find the closest element to it. Binary Search in this
case will take Log(10,000), which will get us around 10 (little less).
Let’s see what this gives us in terms of the time complexity
(also, notice that the b can start after the a):
a)
3 <= n <= 100
a.
1 <= a <= 10,000
i.
a+1 <= b <= 10,000
1.
c = 10
The
new O(F-FLT-N) = 50,000,000,000. There is an extra constant cost to compare up
to the first 10 digits of (a^n+b^n) and (c^n), but that shouldn’t add much
(that comparison on average will fail fairly quickly in the very first digits). A loop
thru 50 billion is no fun, takes a while but it will finish in several minutes (or few
hours). As I said it is still brute-force but in a matter of up to few hours,
you can find a number of fake counterproof to FLT, such as:
4368^30 + 5186^30 = 5187^30
8767^31 + 8819^31 = 8993^31
7965^32 + 9516^32 = 9517^32
7489^33 + 8872^33 = 8873^33
8032^34 + 8485^34 = 8521^34
8703^41 + 8988^41 = 9040^41
5322^42 + 5788^42 = 5792^42
4014^45 + 4204^45 = 4215^45
6602^47 + 7096^47 = 7101^47
9601^52 + 9829^52 = 9878^52
5510^55 + 5822^55 = 5827^55
8392^58 + 8981^58 = 8984^58
5207^69 + 5304^69 = 5323^69
9112^76 + 9712^76 = 9713^76
9181^78 + 9767^78 = 9768^78
3195^86 + 3201^86 = 3224^86
6390^86 + 6402^86 = 6448^86
9585^86 + 9603^86 = 9672^86
8908^93 + 9002^93 = 9033^93
8767^31 + 8819^31 = 8993^31
7965^32 + 9516^32 = 9517^32
7489^33 + 8872^33 = 8873^33
8032^34 + 8485^34 = 8521^34
8703^41 + 8988^41 = 9040^41
5322^42 + 5788^42 = 5792^42
4014^45 + 4204^45 = 4215^45
6602^47 + 7096^47 = 7101^47
9601^52 + 9829^52 = 9878^52
5510^55 + 5822^55 = 5827^55
8392^58 + 8981^58 = 8984^58
5207^69 + 5304^69 = 5323^69
9112^76 + 9712^76 = 9713^76
9181^78 + 9767^78 = 9768^78
3195^86 + 3201^86 = 3224^86
6390^86 + 6402^86 = 6448^86
9585^86 + 9603^86 = 9672^86
8908^93 + 9002^93 = 9033^93
Code is below, cheers, Marcelo.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;
namespace FermatLastTheorem
{
class Program
{
static void Main(string[] args)
{
FindFakeSolutionToFermatLastTheorem();
}
static void FindFakeSolutionToFermatLastTheorem()
{
int MAX_EXP = 100;
int MAX_INT = 10000;
Console.Write("Doing its magic...");
BigInteger[,] x = new BigInteger[MAX_EXP + 1, 3 * MAX_INT + 1];
string[,] xStr = new string[MAX_EXP + 1, 3 * MAX_INT + 1];
for (int exp = 3; exp <= MAX_EXP; exp++)
{
for (int i = 1; i <= 3 * MAX_INT; i++)
{
x[exp, i] = BigInteger.Pow(i, exp);
xStr[exp, i] = x[exp, i].ToString();
}
}
Console.WriteLine("Done!");
Console.WriteLine("Processing...");
for (int exp = 30; exp <= MAX_EXP; exp++)
{
for (int y = 100; y <= MAX_INT; y++)
{
for (int z = y + 1; z <= MAX_INT; z++)
{
BigInteger result = x[exp, y] + x[exp, z];
int fakeX = 0;
BigInteger nearestFermatResult = FindNearestResult(x, MAX_INT, exp, result, out fakeX);
if (fakeX != z && DoNumbersOverlap(result.ToString(), xStr[exp, fakeX]))
{
Console.WriteLine("{0}^{1} + {2}^{3} = {4}^{5}", y, exp, z, exp, fakeX, exp);
}
}
}
}
Console.WriteLine("Done!");
}
public static bool DoNumbersOverlap(string n1, string n2)
{
int MIN_OVERLAP = 10;
int countOverlap = 0;
int minLen = (int)Math.Min(n1.Length, n2.Length);
for (int i = 0; i < minLen; i++)
{
if (n1[i] != n2[i])
{
break;
}
countOverlap++;
}
return countOverlap >= MIN_OVERLAP;
}
public static BigInteger FindNearestResult(BigInteger[,] x,
int len,
int exp,
BigInteger result,
out int index)
{
int lowerIndex = 1;
int higherIndex = len;
while (lowerIndex < higherIndex)
{
int midIndex = (lowerIndex + higherIndex) / 2;
if (result > x[exp, midIndex])
{
lowerIndex = midIndex + 1;
}
else
{
higherIndex = midIndex - 1;
}
}
//At this point find the best match comparing lowerIndex, lowerIndex-1 and lowerIndex+1
index = lowerIndex;
BigInteger smallestGap = BigInteger.Abs(x[exp, lowerIndex] - result);
if (lowerIndex - 1 >= 0)
{
if (BigInteger.Abs(x[exp, lowerIndex - 1] - result) < smallestGap)
{
index = lowerIndex - 1;
smallestGap = BigInteger.Abs(x[exp, lowerIndex - 1] - result);
}
}
if (lowerIndex + 1 <= len)
{
if (BigInteger.Abs(x[exp, lowerIndex + 1] - result) < smallestGap)
{
index = lowerIndex + 1;
smallestGap = BigInteger.Abs(x[exp, lowerIndex + 1] - result);
}
}
return x[exp, index];
}
}
}
Thanks for yet another interesting article and a reminder about how powerful binary search is!
ReplyDeleteThis comment has been removed by the author.
ReplyDelete