An + Bn = Cn
“It is impossible for a cube to be the sum of two cubes, a fourth power to be the sum of two fourth powers, or in general for any number that is a power greater than the second to be the sum of two like powers. I have discovered a truly marvelous demonstration of this proposition that this margin is too narrow to contain.”
Some work the crosswords. Some work on cars and motorcycles. Sometimes I write programs. Anyway, I got the urge to write a “quick” little program to plow thru Fermat’s A B C and n. Of course “quick” is a relative term in the realm of programming. And especially if you’re used to working on projects that take months, or even years, to complete. This Fermat program would be recreational. It would be my substitute for crosswords and Lumosity. And how hard could it be!? There are only 4 variables and the “what” to do is pretty much defined! All that remains is to implement the “how.” So I started Visual Studio and tried to open a new “Windows Forms” project for C++ (aka a “WinForms” project).
What do you mean, you can’t do it!? What’s that!? You can ONLY open an existing C++ project that you brought forward from a prior release of Visual Studio (VS)… but you can’t start a new one!!! Whose idea was that!!?? It turns out that somebody(s) at Microsoft thinks that C++ is dead and that C# and VB and F# (whatever that is) are what you should use. And to that end Microsoft will not support the creation of new C++ programs/projects that use a GUI (Forms) in Visual Studio (VS); at least not in the free/Express versions. They killed C++. You bastards! But all was not lost. Apparently I had run across this before and had a half-dozen earlier projects named “GenericWF1” thru “GenericWF6” from a few years ago that I must have created for just this problem (but which I had since forgotten about). These GenericWF# projects are the Windows GUI versions of “Hello World.” All they are is a C++ project with a single window with a single Button and without any code (except for what was generated by VS).
So I opened one of these 3 year old existing generic C++ projects in Visual Studion (VS) and it automagically converted it to the latest version of VS. The world made sense again. The Anti-C++ demons were defeated! In short order the first cut at the C++ Fermat program was running. A couple of days later I decided to convert it to C# (more for “recreation” than anything else). So I created a new C# WinForms project with the same simple controls as the C++ program and simply pasted the C++ code into the VS generated C# program. In just a few minutes the equivalent C# program was running. I mention this because it demonstrates that the differences between C# and C++ are minimal (at least for mundane (if not most) things). This raises the question of why Microsoft wants to eliminate C++ support in their flagship IDE (VS). I don’t get it. ‘Splain it to me Lucy!
But I digress… In any event, the rest of the “Fermat program” was done in C# (for convenience). It’s worth mentioning at this point that C++ is still a whole lot easier for doing many (if not most) “lower level” interfacing to Windows such as controlling the mouse cursor, interfacing to other Windows programs and features, Screen Scraping, using DLLs, and so on. There’s a whole raft of extremely useful functionality in Windows that is oh so much easier to use via C++. So why Microsoft wants to phase out C++ for the consumer (me) is a mystery… especially considering that the differences between the languages (C++ and C#) are minimal! Oh well. Time marches on.
So basically, this “Fermat program” (now in C#) lets you assign a range of values to A and B and to specify the exponent (n). It will then plow thru the combinations with astonishing brute force and list the values of A and B and C and n that meet the requirements of Fermat’s Last Theorem. Of course we already knew that values of n > 2 have no solutions but the idea was/is that maybe it would be instructive to go thru the process anyway.
At last we get to the more interesting part of the story (if that’s even possible)… Here’s the deal. Think about how you might write such a seemingly trivial program. The basic idea is very simple but, as they say, the devil is in the details…
An + Bn = Cn
Choose (assign) values for A (e.g. a range such as 1 to 10,000) and values for B (e.g. a range of 1 to 5,000). Then assign a value to n (the exponent). See the screen print at the end of this post. Then click on the GO button to see if there are any values of C such that
An + Bn = Cn
It turns out that there are considerations and techniques that are critical to accomplishing this task even for very “modest” values of A, B, and n. The techniques and considerations were NOT OBVIOUS to me in the beginning.
- An or Bn or Cn will go negative for long integer values > 264. I.e. variables can’t be made infinitely large. “long” integers in C# have a max value of 264 and even though it’s a pretty big number, with the speed of today’s computers it doesn’t take long (pun) to plow thru a lot of combinations.
- Initially, the program would spend large numbers of cycles evaluating combinations that could never satisfy the formula. So without getting into the details, a Binary Search technique was added to the code to be much more efficient at “skipping over” useless combinations. Binary Search, as you’ll probably remember, is usually taught in Programming 101. Anyway, the Binary Search technique initially used here was very basic but fairly effective at reducing cpu usage and making the programming run much faster. I did not spend a lot of time refining it. This was, after all, a recreational programming exercise where Better Is The Enemy of Good. Note, however, that I would soon discover that use of the Math.Pow() function could be leveraged as a hugely more efficient way to do the functional equivalent of the “binary search” (even though it’s nothing like a binary search under the covers). Details omitted here.
One interesting thing that came out of this exercise is yet a better appreciation of just how fast today’s PCs are. For example, my PC is a 4-core I5 with 8GB of memory running at 3.4 Ghz. It’s NOT state-of-the-art but it’s pretty fast and it was pretty cheap! I suspect that for this task the memory is not a significant factor but the 4 CPUs make a big difference! If I make use of all 4 CPUs then I observe (generally) anywhere from 300,000 to 1.2 million combinations of A B C and n tested per second! The rate of evaluating possible solutions depends on the ranges of A and B, and the value of n, with lower values being faster (for obvious reasons).
All hail Brute Force!! OPEN THE POD BAY DOORS!
We know that Fermat’s theorem has no solutions for n > 2. Because of this, testing the code becomes a little problematic. That is, just observing that a test run returns a “no solution” result doesn’t tell us much. Did the code operate correctly or did we get the correct answer for the wrong reason? Enter the Pythagorean Triple. I.e. when n==2 we do get solutions and we can desk-check their accuracy and completeness. The solutions for n== 2 are called Pythagorean Triples (time for a google). These are, of course, what we learned about in basic Geometry class for the Right Triangle solutions for A B and C where, of course, each is an integer. Anyway, in this way we can wring out the code almost 100 percent using just n == 2 and in theory at least there is no reason to suspect that the code would operate differently for values of n > 2 (but we are always suspicious and we keep a sharp eye out for such things). Because n==2 is the most interesting testing we do, and provides the only results we actually see, we start getting pretty familiar with these “triples.” We start noticing patterns in the distribution of results (i.e. in the distribution of Pythagorean Triples) and we start realizing (and even proving) things like the fact that there are an infinite number of such Triples, and that B can never be an integer multiple of A, and…. This eventually leads us to start googling “Pythagorean Triples.” For example:
There’s a mountain of information on Pythagorean Triples which we interestingly came to kind of by accident while putzing around with Fermat and C#. You never know what you’re going to get…
Finally, this “Fermat Program” would soon lead to the next, and more general, Sums Of Powers program (Think Euler’s Conjecture). Below is a screen shot from the Sums Of Powers program. More on that in other posts.
Click on it to view full size.
******************************** The End *****************************