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

Listening to the language

For a while now I've been focusing this blog on my open source project as I think more about it and try to understand what it is, where it is, and where it should go.

One thing that I realized recently while doing these considerations is that it makes sense to just ask a computer language things and Java lets you do that with the Reflections API and Class Viewer is using that to give you information.

So you're asking the Java language and shouldn't all the various computer languages let you do the same?

So, as a developer when I use Class Viewer I'm getting questions answered from the current Java version I'm using, coming direct from the language itself as it talks to me.

And I can ask questions like, if I go to the String class I can ask, if I know how to use the program, which methods take char?

That's my simple example that I like to use as the String class is so familiar. But you can ask so many more questions and just fiddling with things I've been amazed myself at how flexible it is, especially when you use the search field, which will give you inherited methods.

So why not just listen to the language? If you wish, Java will talk to you. And isn't that just really cool?


James Harris

Running Class Viewer

My open source application Class Viewer is meant for Java developers, who presumably want to get the best method to write the best code, so they should have certain skills with Java. And one debate I have had with myself is whether or not I should use a universal installer for downloads. But I think that is more than necessary, as I'll explain how I test download.

I usually download the zip file, but do download the tar-ball file at times to test as well, and unzip it. Then I just double-click on the ClassViewer.jar which will run on many systems as it is an executable jar. Things should be ok at this point as ClassViewerConfig.xml should have unpacked next to the app. The app will give you a little message if it cannot find it! I added the feature that it will also tell you where it is looking for the file.

And if the above works, you can just use it immediately, and I like to use the String class as my test case.

And that is what I do with my test download. It's that easy and that fast. Unpack and double-click on the ClassViewer.jar and try a class.

And the above is just for playing around and seeing that it works! If you use the Firefox browser you can do a search for methods and immediately go to the web to JavaDocs, as Class Viewer will call Firefox out of the box. So don't get surprised if that happens! It's totally normal.

There is where there is an adjustment for your browser, which I don't think is reason enough to bother with an installer. To change your browser, open ClassViewerConfig.xml, where I recommend a text editor, and go to the browser section where you will see Firefox, and change it to your browser! Save, and restart the program. Now it will use your browser.

But for the real work, you'll want a full classpath, and when I run it as described above I don't get one, so the primary way I run to get the full classpath is from the command line.

First you need to unpack the code from the Jar file.

That is done with: jar xf ClassViewer.jar

Then you just use the command: java com.jstevh.viewer.ClassViewer

Or some variant on that theme which of course Java developers, the intended audience would know.

Now the program will have the full classpath.

And that is how you get going immediately. I think an installer is more than necessary, where the one area where plenty of people may change things immediately is with the browser, so why not autodetect the browser? I'm not sure. Sometimes I don't remember why I don't do certain things. If there is any demand for that feature I'd see about adding it.

But going into ClassViewerConfig.xml is important anyway, as you will presumably wish to add more packages including your own. So learning how to do it early shouldn't hurt, and I just use a text editor. Open it up, make some quick changes, save it, and restart Class Viewer and back in business.

If you have any thoughts on the above or suggestions, please comment! Curious about whether others feel like I need to give a different experience for users who download Class Viewer for Java.


James Harris

updated: June 28 2014--changed from packagedirectory.xml to ClassViewerConfig.xml  __JSH

updated: May 20 2017--minor edits to improve visual clarity and emphasis  __JSH