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

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


Comments

  1. TarasApril 30, 2016 at 11:22 AM

    Thanks for yet another interesting article and a reminder about how powerful binary search is!

    ReplyDelete
  2. RoninAugust 28, 2016 at 11:37 AM

    This comment has been removed by the author.

    ReplyDelete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more

The Power Sum, a recursive problem by HackerRank

-
Image
Another one by HackerRank:  https://www.hackerrank.com/challenges/the-power-sum : Find the number of ways that a given integer,  , can be expressed as the sum of the   power of unique, natural numbers. Input Format The first line contains an integer  .  The second line contains an integer  . Constraints Output Format Output a single integer, the answer to the problem explained above. Sample Input 0 10 2 Sample Output 0 1 Explanation 0 If   and  , we need to find the number of ways that   can be represented as the sum of squares of unique numbers. This is the only way in which   can be expressed as the sum of unique squares. Sample Input 1 100 2 Sample Output 1 3 Explanation 1 Sample Input 2 100 3 Sample Output 2 1 Explanation 2  can be expressed as the sum of the cubes of  .  . There is no other way to express   as th
Read more