Power of simpler math

I found one of the best mathematical results in human history which is a simpler way to reduce things called binary quadratic Diophantine equations. That is, equations that look like this general case:

c₁x² + c₂xy + c₃y² = c₄ + c₅x + c₆y

where x and y are the unknowns to be figured out. A simple example of such an equation is:

x² + 2xy + 3y² = 4 + 5x + 6y

where I've simply used,  c₁ = 1, c₂ = 2, c₃ = 3, c₄ = 4, c₅ = 5, c₆ = 6.

With my simple example above I can reduce to a simpler form using my own research to get:

(-4(x+y) + 10)² + 2s² = 166

Now you can solve for x+y and s, and it's easier to find that s = 9 works, and x+y = 2 or 3, and x = 4, y = -2 is a solution. To see me work through in more detail, click here.

Now you may say, so what? Well, turns out we can immediately use this thing to get a simple result previously unknown before I discovered it, which is one of the greatest math finds of all time, and we're going to use it for some simple math trivia and approximate the square root of 2 with it.

And I start with a simple equation:

u² + Dv² = F.

And with my general method to reduce binary quadratic Diophantine equation we can find that:

(u-Dv)² + D(u+v)² = F(D+1)

And I'm now going to let D = -2, F = 1, since we're going after the square root of 2, and to make the equation look like a more familiar one I'm going to shift variables with: u=x, v=y, so my original is now:

x² - 2y² = 1

And now I can crank through my result to get:

(x+2y)² - 2(x+y)² = -1

And it's iterative! So I can do it again and again:

(3x+4y)² - 2(2x + 3y)² = 1

Next is:

(7x + 10y)² - 2(5x + 7y)² = -1

And iterating one more time:

 (17x + 24y)² - 2(12x + 17y)² = 1

And the more astute of you may have noticed that x = 1, y = 0 is a solution to the original equation, so guess what? We've solved the original equation as well with JUST my research result. Using that on the last:

(17)² - 2(12)² = 1

And we can still iterate, but let's do it now with just the numbers.

So now for another iteration: x = 17, y = 12,

so: (3(17)+4(12))² - 2(2(17) + 3(12))² = -1

Which is: (99)² - 2(70)² = -1

And that gives the slightly more impressive approximation of 99/70 is about: 1.4142

And if you're bored you can just keep going! Where now x=99 and y=70. And it works out to infinity with ever more precise approximations to sqrt(2).

Next one is: x=577, y=408, and 577/408 is approximately 1.41421.

Why do these solutions approximate the positive square root of 2?

Because x² - 2y² = 1, is:

(x² - 1)/y² = 2, and you can just take the square root of both sides now:

sqrt(x² - 1)/y = sqrt(2), so the trick then is that approximately x/y = sqrt(2).

And x² - 2y² = 1 was used over a thousand years ago, and one of its uses was, yup, approximating square roots, and I wonder if I'd have been cheered if I showed some of the ancients my simple result above?

I've used my result with much bigger things though.


James Harris

Class Viewer troubleshooting advice

Update July 3 2014: There was a change to how javadocs are accessed in Java 8. The latest version of Class Viewer dated July 3, 2014 addresses this change with backward compatibility for earlier versions. If you are not getting javadocs to the method please upgrade to this latest version.

-----------------------

A great thing about writing applications in Java is how well they can move around the world, across platforms. And for the most part my Class Viewer application can be used on any platform with Java, but it does do some things that are platform dependent like call your web browser.

Configuring for your system is all in ClassViewerConfig.xml which is where the app goes to see how to do such things. And I just edit it with a text editor.

If you run into problems with my Class Viewer, my guess is you likely need to make a change there.

For the browser and text editor everything is conveniently at the top with the BrowserLoc and Editor sections.


<browserloc>C:\\Program Files\\Mozilla Firefox\\firefox.exe</browserloc> <editor>C:\\Program Files\\gedit\\bin\\gedit.exe</editor> <acceptslinenumber>Yes</acceptslinenumber> <parameter>+</parameter>
Which is what I have as default for systems with Microsoft's Windows.

And if what's there doesn't work then change it to something that does.

If you have a different browser you just change BrowserLoc, and same for your text editor.

If what you try doesn't work the app will put up an error message telling you what it tried.

I ran into a problem recently out of the blue where Windows wanted quotes before it would call gedit, and I have no clue why and don't care. I just added the quotes and it worked. So I had:


<editor>"C:\\Program Files\\gedit\\bin\\gedit.exe"</editor>The default for Linux users is:
<browserloc>firefox</browserloc> <editor>gedit</editor> <acceptslinenumber>Yes</acceptslinenumber> <parameter>+</parameter>
Where it's simpler, and thus easier to change to your own preferences.

But I'm just helping people with those operating systems use Class Viewer while anyone who can run Java just needs to put in what will run on theirs.

Most troubleshooting issues I've found go back to what is in your ClassViewerConfig.xml, or your classpath.

As usual with Java make sure you have the classpath you need to get to programs you want.

You can check your classpath in Class Viewer to know where it is looking.

Any others having problems not covered here? If so, please comment, and I'll try to address any other issues.


James Harris

Updated: Changed packagedirectory.xml to ClassViewerConfig.xml--June 28 2014  __JSH

Diophantine modular solution

So I have math results that I've had for YEARS and it has occurred to me that maybe some of them might be of interest on this blog. And here's one where I found something so simple it puzzles me if it's not known already.

Consider x² - Dy² = F with all integers. Turns out I found there is a very easy way to solve for x and y modularly.

Given x² - Dy² = F where all variables are non-zero integers, with a non-zero integer N for which a residue m exists where m² = D mod N, and with r, any residue modulo N for which Fr^-1 mod N exists then:

2x = r + Fr^-1 mod N

and

2my = r - Fr^-1 mod N

It is EASY to derive so you may see if you can figure it out. Or you can see it derived here.

That result gives solutions to x² - Dy² = F mod N.

This thing is so simple I find it hard to believe it's a new discovery. So I'm emphasizing that and also still looking for it elsewhere. I think it's simple and cool though, even if it's just another re-discovery.

I do wonder if you could use it with, say, factoring, but haven't noticed anything about which I'm sure. And I think part of me just kind of just wants it to be important, you know?

But then again, I don't know if you could do much with it either. So it's just this thing I have and wonder about once in a while.


James Harris

Hyperbolas and ellipses with one equation

Sometimes you don't discover something new in math. Actually, it's really hard to discover something new in math as people have been kind of busy, and I have a result I like which I rediscovered a few years back.

It is a way to get hyperbolas and ellipses with a single equation.

The equation is x² - Dy² = 1, in rationals, so to program it you need to use doubles:

y = -2t/(D - t²)

and

x = (D + t²)/(D - t²)

and you get hyperbolas with D greater than 0, and ellipses with D less than 0, and the circle when D=-1, giving the well-known circle parameterization:

With x² + y² = 1: y = 2t/(1 + t²) and x = (1 - t²)/(1 + t²)

So yeah, you can just draw an ellipse or a hyperbola by incrementing t, which gives you x and y. Easy.

I like easy.

When I came up with my own solution for x and y with a parameter, I was shocked to discover that I was so far off from the time of the initial discovery that Fermat himself knew the above.

And Pierre Fermat died in 1665. So he's been dead for over 340 years.

Turns out it's really hard to find something new in math. No big deal though. I also like rediscovering things too, as it's fun!

So you can use a single equation for hyperbolas and ellipses, just by shifting that thing D, and yup, if you remember your trigonometry--or is it algebra?--that means that D has to be connected to eccentricity. And if you're really smart, figure out the equation that connects them directly to prove your intelligence.

Now, derive the equations yourself. If some dude centuries ago could do it, why not you today?

I did it. It's not all that hard actually, and might be a fun exercise to test your limits with something easy.

See! Isn't math fun?


James Harris

Simple and fast prime number counter

One of my favorite discoveries is one of my most innovative. It counts prime numbers. Here is the algorithm version. It uses a much smaller list of primes to count a much bigger number.

With positive ints or longs--where p_j is the jth prime:

P(x,n) = x - 1 - sum for j=1 to n of {P(x/p_j,j-1) - (j-1)}

The P(x,n) function will count primes up to and including x, if n equals the count of primes up to sqrt(x), and if as you iterate you never let n be greater than the count of primes up to and including sqrt(x), if the function receives an n greater than that value it just needs to reset it to that count.

That is the fastest algorithm for counting primes for its size.

For say, the count of primes up to 100, if you tried P(100,10), the algorithm would reset n to n=4, so you'd have P(100,4), because there are 4 primes--2, 3, 5 and 7--up to sqrt(100).

Notice with just those 4 primes you count all primes up to 100.

P(100,4) = 100 - 1 - (P(50, 0) - 0) - (P(33,1) - 1) - (P(20,2) - 2) - (P(14,3) - 3)

Except P(14,3) needs a correction because the 3rd prime is 5 which squares to 25, so that is going too high as it's bigger than 14 and has to be reset to P(14,2). Then I have:

P(100,4) = 100 - 1 - 49 - 16 - 6 - 3 = 25

Those numbers are explained simply enough: there are 49 even composites, 16 odd composites with 3 as a factor, 6 composites with 5 as a factor but no smaller prime as a factor. And 3 that have 7 as a factor with no smaller prime, and I'll give those as it's just three numbers so easy to do and they are of course: 49, 77 and 91.

And you subtract 1 for 1 itself, where the principle is easy enough--subtract composites and 1 to get the count of primes.

Another example is P(10,2) = 10 - 1 - (P(5,0) - 0) - (P(3,1) - 1) = 10 - 1 - 4 - 1 = 4

Where of course the 4 primes are 2, 3, 5 and 7.

There are 4 even composites--4, 6, 8, 10--which are being counted by P(5,0) and one composite divisible by 3, which is NOT even, which is 9, and that count is given by P(3,1) - 1 = 1.

The algorithm is fairly easy to program.

So you need a list of primes up to sqrt(x), so the hardest thing is how you generate that list of primes, which is usually done using the Sieve of Eratosthenes, even for the currently established fastest prime counting algorithms known! But for something quick you can just enter a small list.

For example the first 10 primes are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

With that list using the algorithm you can count primes up to 29*29 = 841.

The P function also has to check to see that n is not greater than count of primes up to, and including sqrt(x), where a simple implementation is just brute force, find floor(sqrt(x)) and count primes, for instance for 840, floor(sqrt(840)) = 28, and you can just count up to see that n  = 9, as 23 is the last prime less than or equal to 28.

Notice at 529 = 23*23, you'd still have n = 9, as you go up to and including sqrt(x).

You can actually get clever here as n tries to go greater at a very specific place as you iterate, so you don't actually have to check the square root at each iteration, but am just showing the simplest route to implementation.

To see a recent rather long-winded explanation of how the algorithm is derived and to understand why it works you can click here. No advanced math in the derivation, as you just need to know what a prime is and what division is, as well as some basic algebra to follow it.

The basic idea of counting composites and subtracting 1 to count primes is centuries old.

What's new with my prime counting function is a slight tweak.

I just did one little extra thing that no one did before over those centuries, which makes it more concise, easier to explain, understand and, importantly, implement.

If you're mathematically adventurous you can have it call itself to remove needing to give it a list of any primes, but then it's a lot slower. Run timing tests if you wish to see how much slower. But that is just a lot more recursion, and you can do things to speed it back up, if you're bored.

I've had it for over ten years, so I no longer play with it. Had all my fun with it years ago.


James Harris