Considering a behavior

One of the things that helped me a lot recently was a result of mine with a famous equation, where finally I could look at something that seemed to explain a lot for me. So for background information for those interested in my research and issues around it, I want to talk about this result as objectively as possible. So deliberately I'll try to stay away from emotion, and focus on the facts.

The famous equation is x² - Dy² = 1, which according to various web sources has been known for over a thousand years. Typically integer solutions for x and y, given positive integer D, are discussed in regard to it, for instance: 3² - 2(2)² = 1

However, the size relative to D of the smallest set of positive non-zero integers which will give a solution, which is called the fundamental solution, can vary extensively.

Current accepted number theory about the equation x² - Dy² = 1  cannot explain the size in general of the fundamental solution.

My own research proves that D is key, and if D is a prime or two times a prime, then solutions will be the largest, with exceptions, when D-1, D+1, D-2, or D+2 is a square, as x is forced to equal 1 or -1 mod D, especially if D-1 has small prime factors, and if 4 is also factor they will be even bigger still.

That is, x-1 or x+1 must have D as a factor, if D is a prime or twice a prime, which forces a larger solution unless D-1, D+1, D-2 or D+2 is a square. And when a larger solution is forced, if D-1 has small prime factors, solutions will be even larger. And then if 4 is also a factor they are the largest.

For example there is a large fundamental solution at D = 61.

The smallest positive non-zero x and y that will work are x = 1766319049 and y = 226153980.

1766319049² - 61(226153980)² = 1

Currently accepted number theory cannot tell you why that solution is so large, as my research is to my knowledge not yet accepted.

Here notice that x = -1 mod 61, as: 1766319049 + 1 = (28956050)(61)

From my research it follows that the solution is so large because x = -1 mod 61, D-1, D+1, D+2, and D-2 are not square, while D-1 = 60, which has the first three primes as factors, as 4(3)5) = 60, and because 4 is a factor as well.

So I can explain why D=61 is so large and my explanation is backed by a mathematical proof which has been public on this blog since September 2011.

Also I directly contacted various mathematicians last year, giving them the rules. Usually I went to some effort to find number theorists so that the people contacted would presumably have an interest in this result.

Also one of the mathematicians I knew of from searches on the equation commonly called "Pell's Equation" by mathematicians as he had a book listed on Amazon.

Contacts were successful to some extent in that I got emailed replies from several mathematicians at first, but later, no additional emails garnered replies.

To my knowledge there has been no acknowledgement of this result by established mathematicians.

The equation is very famous and presumably is taught yearly in number theory courses.

As far as I know, mathematicians do not explain the size of the fundamental solutions at all.

Remarkably you can find papers on the subject, however, for instance:

"ON THE SIZE OF THE FUNDAMENTAL SOLUTION OF PELL
EQUATION" by ETIENNE FOUVRY.

It is a 29 page paper and I looked through it trying to find an example with an actual D. There was none. I also scanned through looking for an explanation for the fundamental solution size. I saw none, but I'm not a mathematician.

Another reference to a paper where I could only see the abstract:

"The size of the fundamental solutions of consecutive Pell equations" by Michael J. Jacobson and Hugh C. Williams

There the abstract indicates, well I'll just quote part of it:

"...We also provide some heuristic reasoning which suggests that there exists an infinitude of values of D for which $\rho(D) \gg \sqrt{D} \log \log D / \log D$, and that this is the best possible result under the Extended Riemann Hypothesis. Finally, we present some numerical evidence in support of this heuristic."

I could present more examples but I think those two are indicative.

Looking over what I can see on the web, modern mathematicians cannot explain the size of the fundamental solution to the equation x² - Dy² = 1.

But also, now a year since I informed some of them, they have yet to acknowledge the solution.

That is the behavior under consideration in this post for background.


James Harris

Hidden help?

One of the reasons I like noting I'm not a mathematician is routinely I make dumb mistakes with the math, and oddly enough I've been corrected often through the years by math people. I say "math people" to include those who may not be actual mathematicians, versus trying to figure out who is, and who is not.

And recently I had an erroneous argument which I thought proved that x² - 34y² = -1 had no integer solutions using some recent math finds of mine. That was pointed out to me in a comment to a post which I've yanked. It was a solid comment, very helpful, and now it's gone and I'm worrying to myself, shouldn't I acknowledge the person some kind of way?

Now it has been an issue for years to what extent I should give credit for any such help, and what happened is that for a long time I was arguing with people who were mostly insulting. And the way I see it, if someone is calling you names or insulting your intelligence, while they point out an error, why bother giving them any credit?

So I fell out of the habit.

So here's a post to acknowledge LOTS of help through the years from critics! People who for whatever reason pointed out when I made mistakes. And with my techniques, which involve brainstorming--i.e. often I JUMP to a huge conclusion very quickly as I throw up ideas--that has been often.

Erroneous argument is YANKED, and I'm puzzling as usual how I had some stupid math mistakes. But often it's easy enough to explain--you really WANT to believe something that is just not true. And your mind tells you what you wish to hear.

Thankfully someone pointed out my error, and thanks! And even thanks to all the others through the years, even the ones who were insulting, as you not only helped me, you saved me time from not needing to worry about acknowledging you.

Oh yeah, making mistakes SUCKS!!! I hate it, because then you have to clean up the mess. Here thankfully someone helped me early before I went too far with a mistake as I was getting ready to really get excited with what I thought was a pivotal result.


James Harris

Disruptive mathematics?

A recent discovery of mine is a modular solution for x² - Dy² = F.

With a non-zero integer N for which a residue m exists where--m² = D mod N, and 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 too. I use (x+my)(x-my) = F mod N, where m² = D mod N.

But the reduced form of what is called a binary quadratic Diophantine equation is supposedly well studied by mathematicians (I'm not a mathematician) but I haven't seen this simple solution. That's scary.

It's so easy I still puzzle myself about why it took me so long to notice it, but it has implications in some important areas where I hesitate to mention bigger ones, but for instance xy = T is a binary quadratic Diophantine equation.

That is, integer factorization is covered in this area, and can be considered to be simply solving a binary quadratic Diophantine equation. But the supposed difficulty of integer factorization for certain very large numbers is a reason for using it in web encryption. And, for instance, if you go to a site with "https" your computer sends something called a public key, which is worthless as a security system if someone could just quickly factor it.

I've now put a hold on research of mine which I worry might lead to a general way to solve binary quadratic Diophantine equations, and note that I'm not sure I could have achieved it. But mathematicians aren't acknowledging my results! It'd be irresponsible of me to continue further in such a situation.

Most people may not realize that mathematicians see their field as free from disruptions from sweeping changes. Unlike people in just about every other discipline out there they see mathematics as an ever growing mountain of research, where their job is to build on what was done before--not overturn it.

To give an example the way I see it, as I got an undergraduate degree in physics, imagine if a group of people said that human transportation was by horse and buggy, and all we could do is build better and better horse drawn carriages? What if you drove a car by them and they just refused to acknowledge it existed?

And airplanes? Are you kidding? They'd probably laugh and tell you if vehicles ever fly, it will be if horses can first.

That to me is like this situation.

NO one else thinks like mathematicians.

For most people society is advancing, which means that some old ideas get overturned as better ways of doing things are found. But mathematicians pride themselves on the belief that no such thing happens in their field, and they refuse to acknowledge information that shows otherwise.

The breakdown of their worldview, however, in this area could have shattering repercussions for the world. While I am not saying my ideas definitely lead to a general way to solve binary quadratic Diophantine equations, there is enough done already for sensible people to have concerns.

But mathematicians are confident in their worldview and they don't approach these equations in this way!

If they turn out to be wrong, imagine, the news headlines blaring about a sudden collapse of the system used for encryption. Major companies around the world scrambling for some way to figure out how to continue doing business. Big tech giants find their continued existence questioned by pundits. And that's just on the corporate view without considering the country security issues. Or issues of personal security for most people.

And what would mathematicians say?

I suspect they'd be befuddled. Maybe even pathetic at that point. Insistent that these kinds of things just don't happen in their field.

And no one would care then.

I'm not interested in having anything to do with a new financial crisis that could take the world by surprise, but my not continuing research in this area doesn't mean someone else isn't.

But in my experience, I can assure you that mathematicians will calmly inform you that there is no point in worrying at all.


James Harris

Concepts in binary quadratic Diophantine equations

While I am NOT a mathematician I have found myself playing around with intriguing ideas around what are called binary quadratic Diophantine equations and thought it would be a good idea to explain the basics as I know them.

First off binary quadratic Diophantine equations are when you look for integer solutions to equations like:

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

Here x and y are the unknowns to be figured out. An 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.

Such equations are also called binary quadratic forms, and in general can be reduced to a more basic binary quadratic form, like:

u² - Dv² = C

Here the letters used don't matter, of course, and in this case u and v represent the unknowns.

With my simple example above that reduction to the simpler form using my own research gives:

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

So to fit into the form above:

u = -4(x+y) + 10 and v = s, while D = -2, and C = 166.

The reason to reduce to a simpler form is to aid in finding solutions. And in this case I can find the answers rather simply.

Subtracting 2s² from both sides the equation above is:

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

Running through possible odd s's I notice that s=9 works to give -4(x+y) + 10 = 2 or -2, so x+y = 2, or x+y = 3. And x = 4, y = -2, or x = 5, y = -2 work.

The letters do not matter so the general form can also be written as x² - Dy² = F.

That form has a modular solution for x and y.

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 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 derived here.

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

If modular arithmetic is unfamiliar to you, I have my own short introduction.

And that covers enough of the basic concepts of binary quadratic Diophantine equations to help in understanding my posts on the subject.


James Harris

Surprising modular discovery progression

After years with my own mathematical results I was surprised to come across something which to me is bizarrely simple for the 21st century, as how can this approach be new? But I haven't found it elsewhere yet, while I keep looking. And I'll put it up in a bit, and then walk down the progression from it to a general modular solution.

So I found out recently that a certain well-known equation could be solved modularly:

A modular solution to x² - Dy² = 1 is:

2x = r + r^-1 mod D-1 and 2y = r -  r^-1 mod D-1

Proof:

x² - Dy² = 1 mod D-1, and D mod D-1 = 1, so:

x² - y² = 1 mod D-1

Which is: (x+y)(x-y) = 1 mod D-1, and letting r be any residue with an inverse modulo D-1:

x+y = r mod D-1 and x-y = r^-1 mod D-1, so:

2x = r + r^-1 mod D-1 and 2y = r -  r^-1 mod D-1

Proof complete.

That one is easy and short so I decided to use more of a traditional format. Math people can get really weird about how you present things. It's their way, or...well it's just THEIR way. And they get years of training at colleges and universities for a particular format. I didn't get that training in their format. I was a physics student. But I digress.

Next step is to generalize beyond modulo D-1.

Given n such that: n² = D mod p, where p is a prime number, and r, any residue modulo p:

2x = r + r^-1 mod p and 2y = n^-1(r - r^-1) mod p

gives solutions for x² - Dy² = 1 mod p.

And THAT can be generalized to modulo N.

But this approach can be taken still further to something even more general.

With x² - Dy² = F where all variables are non-zero integers:

Given a non-zero integer N for which a residue m exists where--m² = D mod N, and 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

Which of course gives you the original result, with F = 1 and N = D-1.

Or the modulo p result with F = 1, N = p.

Of course the simple reality I'm exploiting is that in modular arithmetic a non-zero D is always a square!

Proof: Let N = D - m², or N = m² - D, for any non-zero integer m, then D is a quadratic residue modulo N.

To me it is a very surprising progression, with simple solutions which can actually solve these equations explicitly if x and y exist less than N, though I'm not suggesting it as a practical technique in these forms.

Why such a simple, basic modular arithmetic concept is not part of what I'm seeing on math websites about these equations is a puzzle to me.


James Harris

More detail on weird construction

Here I want to explain a good bit more about a weird mathematical construction.

That construction is as follows.

The start is very importantly in the complex plane:

7(175x² - 15x + 2) = (5a₁(x) + 7)(5a₂(x)+ 7)

where the a's are roots of

a² - (7x-1)a + (49x² - 14x) = 0

At this point there is just quadratic construction and the information that the a's are kind of bizarre in that they are roots of a quadratic! Not something you see every day I think, but also VERY IMPORTANT that at this point you're in the complex plane. There is a good reason for that being true which comes up soon.

And now normalize the functions, that is, have functions that equal 0, when x=0.

Looking at x=0, gives

a² + a = 0, so a₁(0) = 0, or -1, and a₂(0) = -1, or 0.

So I can let a₁(0) = 0, and then introduce a new function b₂(x), where:

b₂(x) = a₂(x) + 1, so a₂(x) = b₂(x) - 1, and making that substitution:

7(175x² - 15x + 2) = (5a₁(x) + 7)(5b₂(x)+ 2)

where now a₁(0) = b₂(0) = 0.

So with normalized functions I have:

7(175x² - 15x + 2) = (5a₁(x) + 7)(5b₂(x)+ 2)

And a lot of the idea here is that it's starting to look clear from what we can see on the complex plane how the 7 distributed, where it looks easy.

So now I have easily that the 7 multiplied in a trivial way--which makes sense as I made up this example, why would I make it too hard?

So now it looks like we need one more functional substitution which is:

a₁(x) = 7b₁(x)

Which gives me:

7(175x² - 15x + 2) = (5(7)b₁(x) + 7)(5b₂(x)+ 2)

And I can divide off the trivial factor of 7 to find:

175x² - 15x + 2 = (5b₁(x) + 1)(5b₂(x)+ 2)

And in the complex plane, we're done!

Easy.

So at this point I've removed an extraneous factor of 7 in a fairly straightforward way, using basic algebraic techniques, but I need a LOT more, which is what's coming up, where I'm moving from the field of complex numbers as I need a factor result.

But I don't exactly state it upfront which may seem sneaky. I'll explain why in a bit.

But um, we have this result now that one of the a's results by multiplying one of the b's by 7, and the a's are roots of:

a² - (7x-1)a + (49x² - 14x) = 0

But now if we want to play with our result, say with x=1, we find that the a's are: 3+sqrt(-26) and 3-sqrt(-26), and in fact if you try:

7(175(1)² - 15(1) + 2) = (5(3+sqrt(-26))  +  7)(5(3-sqrt(-26))  +  7)

You'll see it is correct! That math worked!

But it implies that one of the a's has 7 as a factor. But established number theory says neither of the a's have 7 as a factor?

And I've made a seemingly HUGE leap! In the complex plane factors are meaningless, so why make this sudden claim about 3+sqrt(-26)?

So what did I do wrong?

Turns out, I didn't do anything wrong. I simply forced you to rely on the field of complex numbers telling you what happened at the top level, so you can figure out what happens if you go to a ring where factors are meaningful in a way that they aren't in the field.

So let's look at a seeming counter-example to this approach!

Consider:

a² - (x-1)a + (49x² - 14x) = 0

Here I've removed a 7 so that I can force a case where we can seemingly see the 7 split up into square roots, as at x=1, I have: a²  + 35 = 0

Then the a's are sqrt(-35) and -sqrt(-35), and clearly sqrt(7) is a factor, not 7.

But what about the complex plane? The complex plane encompasses lesser rings, right?

But in the complex plane with my earlier example:

7(175x² - 15x + 2) = (5a₁(x) + 7)(5b₂(x)+ 2)

with normalized functions, requiring that the 7 distributed in only one way, and yup, the mathematical linchpin here is the distributive property!

Quite simply there is no way for sqrt(7) to have distributed, as then you'd see something like:

7(175x² - 15x + 2) = (5a₁(x) + sqrt(7))(5b₂(x)+ 2sqrt(7))

And notice, it's basic math at this point. If the 7 split up into squares then they'd multiply through, and you'd actually see them in the construction.

So how do we maintain mathematical consistency at this point? Or is it time to throw away algebra?

Answer is, easy, as look at:

175x² - 15x + 2 = (5b₁(x) + 1)(5b₂(x)+ 2)

Here I don't see a 7 at all. And I've used the assumption:

a₁(x) = 7b₁(x)

So if we extrapolate from here to something that results from removing the 7, if we say the first of the a's is sqrt(-35) we'd have a solution for one of the b's of:

b₁(1) = sqrt(-35)/7 = sqrt(-5)/sqrt(7)

So a 1/sqrt(7) forced its way into the picture.

And note that the above is not direct from my original construction but would follow if I made one with a key 7 removed, as I'm talking about what happens if you try to force a factor of 7 to move around, when the field of complex numbers tells you it can't. The math simply shifts, as it IS consistent. It has no choice.

The field of complex numbers says how the 7 distributed which includes all lesser rings. If you have an example where that appears to not be true, then you are wrong, as the field of complex numbers is right!

Here is a giant area and it's critical to hammer home the point that the field of complex numbers tells you how the 7 distributed and it MUST be correct. From there certain things logically follow--or you lose something called mathematical consistency.

That is, otherwise I've demonstrated that human mathematics falls apart here.

(I actually considered that carefully for some time. Whether our mathematics is consistent or not is actually a really big deal.)

The construction is built using special techniques designed to make it valid in what I call the ring of objects which I figured out to handle this problem.

So now it's time to focus on how I built my construction!!!

It's suddenly of HUMONGOUS importance, as the field of complex numbers will only allow one thing, but we broke my construction by just removing a 7, which forced 1/sqrt(7) to be included in whatever ring or field, or where are we now?

Traditionally to talk about factors with non-rationals I'd be using the ring of algebraic integers.

However, it turns out in that ring you can prove that neither of the a's can have 7 as a factor!!!

Here things get a little more complicated as if you don't remember your number theory or never had much of it--like I hadn't as I was a physics student--you might wish to see that proof. And I have to say, go look for it.

For the math people who are up on their number theory though, it's a standard result which is well established, and they can see my conundrum: I'd proven a factor result using the complex plane by the distributive property, which MUST include lesser rings, only to find that the ring of algebraic integers didn't wish to agree, with the field of complex numbers!!!

And I thought about it, and thought about, and thought about it some more and came up with the ring of objects which doesn't have the problem. In the ring of objects 7 is indeed a factor of 3+sqrt(-26).

One thing that emerges though is that you cannot see the 7, as it's permanently entangled, because the square root cannot be resolved.

Like imagine you couldn't resolve sqrt(9), how would you know with the following?

It's kind of like 10 + sqrt(9) has 7 as a factor for one of its two solutions.

If you think 10 + sqrt(9) is 13, you're wrong, as it's 13 or 7 because sqrt(9) = 3 or -3.

For the truly curious and mathematically sophisticated, you may now wonder how the ring of algebraic integers pulls off the trick of not allowing 7 to be a factor. Turns out I puzzled that one out years ago, where the answer is, it wraps it up in unit factors, which are units in the ring of objects but NOT in the ring of algebraic integers!

Tricky, but not really. Unit factors CAN move in the field of complex numbers with the original example, with ease, without being forced to show themselves in the same way as the 7 is forced.

What's wild is that these are not unit factors within the ring of algebraic integers, but must be in the ring of objects.

And notice I rely heavily on the result from the field of complex numbers because there is where you can see what actually happens with the 7.

And the weird thing for those who'd like to try and start from the ring of algebraic integers is, it won't allow you to see the result. In fact, it won't even let you divide the 7 off, blocking entirely the final result:

175x² - 15x + 2 = (5b₁(x) + 1)(5b₂(x)+ 2)

with normalized functions.

So could this have been figured out before? Well, read through all of the above and it's easy to see why it's hard to figure out. The ring of algebraic integers works you can say, to hide the correct result. Only by use of the field of complex numbers and belief in the distributive property was I able to tease out the correct answer, and then needed to figure out a ring which worked ok!

Whew! That was actually quite a bit of work. Had never figured out my own ring before, but I had no choice.


James Harris

Some weird math

My most unsettling mathematical result is also one of the hardest to explain even though I can use only simple algebra. Thing is, I constructed this balancing act, where I forced a function to reveal more, by doing things a little stranger than others had tried.

In the complex plane, here's the wacky construction:

7(175x² - 15x + 2) = (5a₁(x) + 7)(5a₂(x)+ 7)

where the a's are roots of

a² - (7x-1)a + (49x² - 14x) = 0

And now normalize the functions, that is, have functions that equal 0, when x=0.

Looking at x=0, gives

a² + a = 0, so a₁(0) = 0, or -1, and a₂(0) = -1, or 0.

So I can let a₁(0) = 0, and then introduce a new function b₂(x), where:

b₂(x) = a₂(x) + 1, so a₂(x) = b₂(x) - 1, and making that substitution:

7(175x² - 15x + 2) = (5a₁(x) + 7)(5b₂(x)+ 2)

where now a₁(0) = b₂(0) = 0.

So now I have easily that the 7 multiplied in a trivial way--which makes sense as I made up this example, why would I make it too hard?

So now it looks like we need one more functional substitution which is:

a₁(x) = 7b₁(x)

Which gives me:

7(175x² - 15x + 2) = (5(7)b₁(x) + 7)(5b₂(x)+ 2)

And I can divide off the trivial factor of 7 to find:

175x² - 15x + 2 = (5b₁(x) + 1)(5b₂(x)+ 2)

And in the complex plane, we're done!

Easy.

But um, we have this result now that one of the a's results by multiplying one of the b's by 7, and the a's are roots of:

a² - (7x-1)a + (49x² - 14x) = 0

But now if we want to play with our result, say with x=1, we find that the a's are: 3+sqrt(-26) and 3-sqrt(-26), and in fact if you try:

7(175(1)² - 15(1) + 2) = (5(3+sqrt(-26))  +  7)(5(3-sqrt(-26))  +  7)

You'll see it is correct! That math worked!

But it implies that one of the a's has 7 as a factor. But established number theory says neither of the a's have 7 as a factor?

So what did I do wrong?

The construction is built using special techniques designed to make it valid in what I call the ring of objects which I figured out to handle this problem.

In the ring of objects then--as I figured it out BECAUSE of this problem--there is no problem at all. It says that 7 is indeed a factor.

It's kind of like 10 + sqrt(9) has 7 as a factor for one of its two solutions.

If you think 10 + sqrt(9) is 13, you're wrong, as it's 13 or 7 because sqrt(9) = 3 or -3.


James Harris

Differential equation and prime counting

A bit over a decade ago in the summer of 2002 I found a difference equation which can be constrained to count prime numbers. The derivation is remarkably simple requiring only very elementary techniques, but weirdly enough leads to this difference equation which in turn leads to a partial differential equation.

My pivotal idea was to count composites at each prime excluding counts from smaller primes. And that seemingly small shift leads to dramatic mathematical consequences.

The count at each composite is given by:

ΔS(x,p_j) = [x/p_j] - 1 - (j-1) - S(x/p_j, p_j-1)

That is the count of composites for a particular prime excluding composites that are products of lesser primes.

First it gets a count of integers with a prime as a factor, subtracts 1 for the prime itself, and then subtracts the count of primes less than it. And finally it subtracts the count of composites multiplied times that prime.

Here's an example:

ΔS(16,3) = [16/3] - 1 - 1 - S(16/3,2) = 5 - 1 - 1 - 1 = 2

There are 5 numbers with 3 as a factor below 16, but you subtract 1 for 3, then 1 for 2, to handle 2(3), and then 1 more for the count of composites times 3, where that is for 12.

The two composites with 3 as smallest prime factor below 16, of course are: 9 and 15

The S function is just a complete count of composites, so it is a sum of ΔS functions, where of course, if you have the complete count of composites you can count primes.

The form of the ΔS function leads to a very compact prime counting function.

I call the prime counting function P:

P(x,p_j) = [x] - S(x,p_j) - 1

which allows me to simplify ΔS(x, p_j) to

ΔS(x,p_j) = P(x/p_j,p_j-1) - (j-1)

where again p_j has to be less than or equal to sqrt(x).

And I can make things a little simpler with the P function by not writing the prime itself but just using its indice, so then P(x,j) is equivalent to P(x,p_j).

And the entire thing is:

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

where if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

That is quite compact!

So much from a simple shift in an idea, where excluding counts of composites with smaller primes as factors yields a surprisingly efficient result.

Actually using it to count primes is very straightforward, for instance to count the primes up to 100, you need primes up to sqrt(100) = 10, which is 4 primes. And those primes of course are 2, 3, 5, and 7.

And the prime count is given by:

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

So 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.

(It's fascinating to me that the symbols "S" and "ΔS" disappear at this point though the sum is the S function and the ΔS is what is being summed so they are still there.)

And for a comparison to other techniques you can look up "prime counting function" on the web.

However, we're going to push forward as there is a difference equation yet to be found, which remarkably enough is lurking within that form!

Notice that P(x,p_j) is the full count of primes up to and including x, if p_j is greater than or equal to the last prime less than sqrt(x), so I can remove all mention of primes with the following

ΔS(x,y) = (P(x/y,y-1) - P(y-1, sqrt(y-1)))(P(y, sqrt(y)) - P(y-1, sqrt(y-1)))

as if y is not prime then

P(y, sqrt(y)) - P(y-1, sqrt(y-1)) = 0

with the constraint that if y>sqrt(x), then P(x,y) = P(x,sqrt(x)) to keep the correct count.

And of course now I finally have my difference equation.

Notice here that sqrt(x) is the integer square root, so it means to find the largest integer less than or equal to sqrt(x), for instance, the integer square root of 10 is 3.

I also now have

P(x,y) = [x] - S(x,y) - 1

as I can remove mention of primes themselves!

Here's the new function then with all mention of primes removed:

P(x,y) = [x] - 1 - sum for j=2 to y of {(P([x/j],j-1) - P(j-1, sqrt(j-1)))(P(j, sqrt(j)) - P(j-1, sqrt(j-1)))}

where if y>sqrt(x), then P(x,y) = P(x,sqrt(x)).

Not as efficient a way to actually count, but in this fully mathematized form we can see a reason for a connection between the count of primes and non-discrete functions that intrigued notables from Euler, to Chebyshev, Gauss, and of course Riemann along with others.

From the difference equation in that summation I can get to a partial differential equation:

P'_y(x,y) = -(P(x/y,y) - P(y, sqrt(y))) P'(y, sqrt(y))

And our connection between the count of prime numbers and a differential form is complete.

One of the coolest things to me that jumps out is the x/y within it. With the integration x would be constant, and of course 1/y integrates as the logarithm, but it's still a bit of a reach I think as x/ln x is one of the known approximations to the prime count. And I'm just really out of my area of math comfort at this point.

There is more to guess here though, as notice above I ended up with a reset if y is greater than sqrt(x), which comes in from the original ΔS function and how it counts composites:

ΔS(x,p_j) = [x/p_j] - 1 - (j-1) - S(x/p_j, p_j-1)

You only need primes up to or equal to the sqrt(x) or the count is off! For instance, [100/11] = 9 numbers with 11 as a factor, but all composites have already been counted, so it screws everything up if you keep going.

But if you integrate the partial differential that rule is not in sight. That would add more ΔS values. Continuing on with additional ΔS values with the discrete equations decreases the size of P(x,y) as you're subtracting more. So one more guess is that the integration would tend to be below the prime count.

And that is what's seen with what we can assume are approximations, with x/ln x, for instance 100/ln 100 equals approximately 21.71, which lags behind the prime count of 25. And 1000/ln 1000 is approximately 144.76 which lags behind the count of primes up to 1000, which is 168. Guessing then it would never catch it.

But now there is the possibility of a direct answer to one of the more intriguing mathematical questions ever presented. Evaluating that partial differential equation could answer quite a few questions and again I admit it is out of my league to move well there.

While I did take numerical methods for my physics degree it was over two decades ago, and besides there are some serious experts in this area all over the world who could do the best job. I just wish I could get some help here, as I will admit I'm a bit curious!


James Harris

Composite counting functions and prime counter

One of my ideas from over a decade ago was a way to count prime numbers by counting composites in a slightly different way than was done before. Here I'll focus on the composite counting functions I used.

The two main composite counting functions I used I called S and dS, where I probably was thinking about "sum" as S is the sum of composites.

The main workhorse is the dS function though which is where I had to do the most work in figuring out its form:

dS(x,p_j) = [x/p_j] - 1 - (j-1) - S(x/p_j, p_j-1)

where S(x/p_j, p_j-1) is the count of composites that multiply times p_j to give a product less than or equal to x, where notice that p_j must be less than or equal to sqrt(x) or the composite count given by [x/p_j] - 1 will not be correct.

So the dS function is the count of composites for a particular prime excluding composites that are products of lesser primes. So it gets a count of integers with a prime as a factor, subtracts 1 for the prime itself, and then subtracts the count of primes less than it. And finally it subtracts the count of composites multiplied times that prime. Whew!

Here's an example:

dS(16,3) = [16/3] - 1 - 1 - S(16/3,2) = 5 - 1 - 1 - 1 = 2

There are 5 numbers with 3 as a factor below 16, but you subtract 1 for 3, then 1 for 2, to handle 2(3), and then 1 more for the count of composites times 3, where that is for 12.

Here S(16/3,2) = S(5,2) = 1, because 2(2)(3) is the only composite case where 3 is multiplied times a composite up to 16. I don't typically write the floor() inside the S function as I consider it redundant.

The dS function only wanted composites divisible by 3, but not by a lesser prime, so it tossed off the evens, meaning 6 and 12 were not counted! So no need to correct the count.

Now let's do dS(16,2) as a second example:

dS(16,2) = [16/2] - 1 - 0 - S(16/2,1)  = 8 -1 - 0 - 0 = 7

Which is where 6 and 12 get counted along with the other evens. And notice if S(x,1) you can't have any composites made up of smaller primes as 2 is the smallest prime, so S(x,1) = 0.

And that's it. The S function then is just a complete count of composites, where of course, if you have the complete count of composites you can count primes.

So with my examples I can now count primes up to 16:

16 - 1 - dS(16,2) - dS(16,3)  = 16 - 1 - 7 - 2 = 6

What's weird though is that the simple shift of making dS a function that counts for each prime excluding counts of lesser primes leads to a very compact mathematical form for a prime counting function itself.

I call the prime counting function P for obvious reason:

P(x,p_j) = [x] - S(x,p_j) - 1

which allows me to simplify dS(x, p_j) to

dS(x,p_j) = P(x/p_j,p_j-1) - (j-1)

where again p_j has to be less than or equal to sqrt(x).

But notice that P(x,p_j) is the full count of primes up to and including x, if p_j is greater than or equal to the last prime less than sqrt(x), so I can remove all mention of primes with the following

dS(x,y) = (P(x/y,y-1) - P(y-1, sqrt(y-1)))(P(y, sqrt(y)) - P(y-1, sqrt(y-1)))

as if y is not prime then

P(y, sqrt(y)) - P(y-1, sqrt(y-1)) = 0

with the constraint that if y>sqrt(x), then P(x,y) = P(x,sqrt(x)) to keep the correct count.

And of course now I have a difference equation.

One thing of interest then is that the P function acts as a boolean switch, telling the dS function when y is prime.

For instance 6 is not prime and the count of primes up to 6 is 3, which is the same as the count up to 5, which is the third prime, so the switch will give 0 for y = 6.

Notice here that sqrt(x) is the integer square root, so it means to find the largest integer less than or equal to sqrt(x), for instance, the integer square root of 10 is 3.

I also now have

P(x,y) = [x] - S(x,y) - 1

as I can remove mention of primes themselves! So while I started with a focus on primes, determining at each prime, thanks to my boolean switch I can now remove all mention of them.

Now the count of composites for each prime less than or equal to the square root of x when added together just gives the full count of composites, so I have that the S function equals the sum of the dS functions for each prime less than or equal to sqrt(x), where I define S(x,1) = 0, and my prime counting function is complete.

Here's the entire thing.

P(x,y) = [x] - 1 - sum for j=2 to y of {(P([x/j],j-1) - P(j-1, sqrt(j-1)))(P(j, sqrt(j)) - P(j-1, sqrt(j-1)))}

where if y>sqrt(x), then P(x,y) = P(x,sqrt(x)).

It's actually prettier with the summation sign. But Blogger doesn't make that easy for me to do, so I've just used the format above, which is of course correct, just not as pretty looking.


James Harris

My approach to counting primes

I like emphasizing that I'm NOT a mathematician as it keeps things simple, while noting my background is in physics, as yes, I did get a lot of mathematical training. But it was mostly in the complex field, and worrying maybe about differential equations, NOT Diophantine equations. Not much call for number theory in the sciences.

But college was over two decades ago, and I'm not even a physicist as I only got my undergraduate degree in physics, but still like challenges, so I found myself doing number theory out of intellectual curiosity.

Which means I've learned most of the number theory I know, late. Which can help explain how I came up with my own way to count prime numbers.

You see for a dedicated math student, who knew a lot of number theory, it'd probably be something they learned early, where counting primes actually involves very easy concepts! So if you can do division and know what a prime number is you should be able to follow along.

For instance, consider the primes up to 16. To count those, what if you go to composites instead? Like 8 of those numbers are even: 2, 4, 6, 8, 10, 12, 14 ,16

And 5 of them are divisible by three: 3, 6, 9, 12, 15

And notice that 16/2 = 8, and 16/3 = 5 1/3, and we don't need that 1/3 to count composites! So we can just throw it away with something called the floor() function, and floor(16/3) = 5. Because typing "floor" a lot can get tedious, another way to do it is to use brackets, so [16/3] = 5.

But we've counted the primes too!

So the even composites up to 16 are really: 8 - 1 = 7. And similarly the composites divisible by 3 are 4, as we need to subtract one for the prime itself in each case.

But notice we have 6 and 12 in both lists! So there is a double-count so we need to subtract 2 back out to correct for counting them twice.

So if we say 7 evens + 4 divisible by three - 2 evens divisible by three, we get: 9 composites

And those 9 composites are: 4, 6, 8, 9, 10, 12, 14, 15, 16

And there is one more number to handle which is 1, itself, as it's not considered prime, and we can now count primes as 16 - 9 - 1 = 6.

And the six primes are: 2, 3, 5, 7, 11, 13

Notice we only needed 2 and 3 to count the primes with this technique, as the first composite that does not have 2 or 3 as a factor is 25. As it is 5(5) and that gives a rule that you only need the primes up to the integer square root. So you only need 2, 3, 5 and 7 using the technique above to count primes up to 100, but also up to 120, as 121 = 11(11) is the start of needing the next prime.

And all of the above was discovered centuries ago, and is the way humanity approached counting primes. Others built on the basic technique figuring out ways to make it faster, as the above gets tedious when you're adding and subtracting for all the corrections. And over time mathematicians built very fast ways to count prime numbers.

And I knew none of the above back in the summer of 2002, when I started thinking about counting primes.

So I came up with my own way.

Hold on to your seats. All of the above is what was known to humanity for centuries.

Now you'll learn my way.

I'm drawing heavily on my post from June 2005 on this blog, as it turns out I don't explain it a lot, unlike many of my other results, and I'm glad I did explain it at least once! Or I might have forgotten how I did it. Turns out I got really bored counting primes, but I digress.

Here we go.

My start is a simple idea: consider a function that gives the count of composites for a particular prime that have that prime as a factor, but no lesser primes as factors.

Why did I start with a function? I don't know, maybe it was my physics background sneaking through.

For instance, up to 16, for 3 that function would give a count of 2, as 9 and 15 are the composites that have 3 as a factor and no lesser primes, while 6 and 12 would be excluded as they have 2 as a factor, and 2 is less than 3.

Now call that function dS(x,p_j) where x is where you're counting up to, and p_j is the j_th prime, so my earlier result is dS(16,3) = 2.

(Us physics guys like cool looking functions.)

Now generalizing a bit, to get the count of composites that have p_j as a factor up to and including some x, it's now time to use that floor() function, which again means to throw away the remainder, as I generalize a bit:

floor(x/p_j) - 1

where from now on, I'll use [x] = floor(x), so I have

[x/p_j] - 1

for the count of composites with p_j as a factor.

And notice that's the idea from before, so it still emerges, where we want the count of composites for a particular prime.

From that count I need to subtract the number of primes less than p_j, which is j-1, so I have:

[x/p_j] - 1 - (j-1).

The reason is that for each of those smaller primes I know I'm multiplying times p_j.

For instance, for 16 and 3, j = 2, as 3 is the second prime, and j-1 = 1, where that composite is 6, as 2(3) is the one composite.

Now I need the count of composites up to and including x that have primes less than p_j as a factor, which is another function.

That is, I now need a function that is the count of composites up to and including some x for all primes less than p_j, and I'll call it S(x,p_j-1), as the count of composites up to and including x that have primes less than p_j as factors.

Here's where things are a little tricky as I now have my full dS(x,p_j) function as

dS(x,p_j) = [x/p_j] - 1 - (j-1) - S(x/p_j, p_j-1)

where S(x/p_j, p_j-1) is the count of composites that multiply times p_j to give a product less than or equal to x, where notice that p_j must be less than or equal to sqrt(x) or the composite count given by [x/p_j] - 1 will not be correct.

So sticking in numbers, you have:

dS(16,3) = [16/3] - 1 - 1 - S(16/3,2) = 5 - 2 - 1 = 2

And again those two composites are 9 and 15. So yeah! Our functions worked!

And should I have used the floor() function inside S? Looks ok to me--study the definition of S to see why--and actually one trick is to just declare everything to be natural numbers so it's understood without using floor() all over the place.

The dS function only wanted composites divisible by 3, but not by a lesser prime, so it tossed off the evens, meaning 6 and 12 were not counted! So no need to correct.

Now let's do dS(16,2).

dS(16,2) = [16/2] - 1 - 0 - S(16/2,1)  = 8 -1 - 0 - 0 = 7

Which is where 6 and 12 get counted along with the other evens. And notice if S(x,1) you can't have any composites made up of smaller primes as 2 is the smallest prime, so S(x,1) = 0.

And now I can count primes up to 16:

16 - 1 - dS(16,2) - dS(16,3)  = 16 - 1 - 7 - 2 = 6

Which of course is the same answer as before, as the prime count can't change. And remember 1 is being subtracted for the number 1, which is not a prime number. Then the evens are subtracted which is dS(16,2) followed by composites divisible by 3, which are NOT even, which is dS(16,3).

My approach simply removes the correction piece because 6 and 12 are not double-counted.

Ok, it's time to get more mathematical.

Now I know that in general the count of primes up to and including x is equal to x minus the count of composites minus 1, and that gives an idea for one more function, which I'll call P(x,p_j), where

P(x,p_j) = [x] - S(x,p_j) - 1

which allows me to simplify dS(x, p_j) to

dS(x,p_j) = P(x/p_j,p_j-1) - (j-1)

where again p_j has to be less than or equal to sqrt(x).

But notice that P(x,p_j) is the full count of primes up to and including x, if p_j is greater than or equal to the last prime less than sqrt(x), so I can remove all mention of primes with the following

dS(x,y) = (P(x/y,y-1) - P(y-1, sqrt(y-1)))(P(y, sqrt(y)) - P(y-1, sqrt(y-1)))

as if y is not prime then

P(y, sqrt(y)) - P(y-1, sqrt(y-1)) = 0

with the constraint that if y>sqrt(x), then P(x,y) = P(x,sqrt(x)) to keep the correct count.

That is, if a number y is NOT prime then the prime count will not move. For instance 6 is not prime and the count of primes up to 6 is 3, which is the same as the count up to 5, which is the third prime. So our clever function can call itself to see if a number is prime or not!

And don't worry, we didn't wander away from integers! That sqrt(x) here is the integer square root, so it means to find the largest integer less than or equal to sqrt(x), for instance, the integer square root of 10 is 3.

It's still number theory, and integers rule.

I also now have

P(x,y) = [x] - S(x,y) - 1

and notice that dS(x,y) is the count of composites that have y as a factor that do not have primes less than y as a factor, which means that if y is composite dS(x,y) = 0, which is how I can remove mention of specific primes.

Now the count of composites for each prime less than or equal to the square root of x when added together just gives the full count of composites, so I have that the S function equals the sum of the dS functions for each prime less than or equal to sqrt(x), where I define S(x,1) = 0, and my prime counting function is complete.

Here's the entire thing.

P(x,y) = [x] - 1 - sum for j=2 to y of {(P([x/j],j-1) - P(j-1, sqrt(j-1)))(P(j, sqrt(j)) - P(j-1, sqrt(j-1)))}

where if y>sqrt(x), then P(x,y) = P(x,sqrt(x)).

And notice, no need to mention primes at all! And I have my own way to count prime numbers.

And I guess there is no way I'd have figured that thing out if I'd been taught the traditional way first.

Turns out you can connect it back to the approaches used traditionally by mathematicians only with a form where you DO keep in primes, which looks simpler.

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

where if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

Which is really nice and compact. I do like it.

And that form is faster if you actually program it. The original fully mathematicized form keeps figuring out numbers are prime, as it recurses to itself to determine primeness. That takes a lot of unnecessary computing time.

And if you followed through all of the above, good for you! I'll admit that it's easier for me to rely mostly on the copy and paste from my original post and trust that I got it right, as, um, did I mention counting primes is boring to me now? It's been years since I sat down and thought through this derivation again.

Oh yeah, so there is a differential form as well, so I did get to use calculus, and as a physics guy that was just way cool too. But then you're getting away from exactness, as using it requires approximate methods for the numerical integration.

If you're bored, you can figure out the partial differential equation that follows from the fully mathematicized form, or just find it on my blog as I have it in several places. Seemed like a big deal to me a long time ago.

But now I've had this information for over a decade. So it's just I guess familiar now.

I guess it is kind of cool though, as I refresh on how things work for this post.


James Harris

Very useful little math result

One of my favorite math discoveries is a surprisingly simple result which I've used for years where a lot of recent posts are I think a culmination of years of following down paths that flowed from this one thing.

Oh yeah, it's worth mentioning again that I am NOT a mathematician. And I have no intentions of ever being one, while I have training in physics with a 4 year degree, but then with that little training I'm not a physicist either. But it's intriguing to me that while I have a lot of math in my background, it was mostly in the field of complex numbers. And with physics you end up doing a lot of approximations.

And I don't really like approximating.

I love exactness, and to me playing with integers is relaxing where at the end I can look at exact answers as you're looking at integers.

Like getting back to this extremely useful result.

It turns out that if you have:

u² + Dv² = F

then it must be true that

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

And it's easy to get to actual integers, as let F = 1, u=x, v=y, and D = -2.

Then just plug those values in and let if fly:

1. x² - 2y² = 1

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

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

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

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

and you can keep going out to infinity, but I'll stop with 4 iterations.

Notice now you can use the simple case of x=1 and y = 0:

1. 1² = 1

2. (1)² - 2(1)² = -1

3. (3)² - 2(2)² = 1

4. (7)² - 2(5)² = -1

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

And you have answers. The solidity of exactness is so comforting. Perfection.

You can actually verify the result by just multiplying out and simplifying:

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

Which is kind of fun, and if you do it, you'll find it just reduces back to the original:

u² + Dv² = F

The cool thing is that I figured it out using my general method to reduce binary quadratic Diophantine equations on that original.

Where that was about curiosity as the reduction method allows you to reduce any binary quadratic Diophantine equation to that simpler form, so I wondered to myself, so what happens with the simpler form if I use the same process on it?

It just kind of gives a variation on itself, as the math really had nowhere else to go.

The next one in the series is easy enough: (3(17)+4(12))² - 2(2(17) + 3(12))² = 1

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

And that gives an approximation the square root of 2, as 99/70 is about: 1.4142

And if you're bored you can just keep going! Next one is: x=577, y=408, and 577/408 is approximately 1.41421.

But I don't like approximations and just throw that in there because it seems I should.

Now I've only touched the surface as you can also figure out a connection between discrete ellipses and hyperbolas. But keep going, as you can also use it to figure out the reason behind the size of the fundamental solution for something mathematicians like to call Pell's Equation.

But keep going, and the research path can lead you to a general modular solution for binary quadratic Diophantine equations in the reduced form.

For me it was years of chasing down those paths which was very satisfying, with exact answers in so many places. Nothing like the certainty of integers, which is why for my hobby I much prefer these types of intellectual exercises to physics problems, where approximate might be the best answer.


James Harris

Generalizing modular solution

The equation x² - Dy² = F where all variables are non-zero integers can be solved modularly.

Find a non-zero integer N for which a residue m exists where: m² = D mod N, and r, any residue modulo N for which Fr^-1 mod N exists then:

2x = r + Fr^-1 mod N and 2y = m^-1(r - Fr^-1) mod N

if m does not share prime factors with N, otherwise: 2my = r - Fr^-1 mod N.


Proving the above one simply relies on D being a quadratic residue modulo some N, so if D = m² mod N you can factor the original as:

(x + my)(x - my) = F mod N

And then let x + my = r mod N, and x - my = Fr^-1 mod N, and then you can just add to solve for x and subtract to solve for y.

I like to leave the 2 on the left hand side because it's simpler than handling cases where its modular inverse exists or does not.

Not doing so with m means I have to mention a special case and maybe I should do the same?

And I'm going to go now to the famous x² - 61y² = 1, and use an r that I found in a previous post, using the published explicit solution.

There I picked N = 1766352723, and m = 42028, as 42028² = 61 mod 1766352723.

And m^-1 = 28957291 mod 1766352723.

And I found r = 55435303, which means that r^-1 = 1710850072 mod 1766352723.

Then

2x = 55435303 + 1710850072 mod 1766352723 = 1766285375 mod 1766352723

2y = (28957291)(55435303 - 1710850072) mod 1766352723 = 452307960 mod 1766352723

And 2^-1 = 883176362 mod 1766352723, so I get finally:

x = (883176362)(1766285375) mod 1766352723 = 1766319049

y = (883176362)(452307960) mod 1766352723 = 226153980

Which are the exact solutions as:

1766319049² - (61)226153980² = 1

Where I knew that as I used that solution to find r, but it's fun looking at the numbers going in the other direction with a famous case. It's also just kind of fun using big numbers even though the math does not care.

And that was with F=1, but the generalization doesn't care and will handle F, a non-zero integer.

It's interesting to me that the original equation can look like it doesn't factor if D is not a square, but of course it always does in modular arithmetic, so getting a modular solution is easy.


James Harris

Playing with modular solution

Great thing with number theory is playing with numbers, and I love watching them follow cool rules.

So, here's a post playing with one of my results that solves x² - Dy² = 1 modularly.

Given n such that: n² = D mod p, where p is a prime number, and r, any residue modulo p:

2x = r + r^-1 mod p and 2y = n^-1(r - r^-1) mod p

gives solutions for x² - Dy² = 1 mod p.

Two equations that follow from the result--or which can be used to derive it--are:

r = x + ny mod p and r^-1 = x - ny mod p

But I wish to play wider than p, a prime number, so will jump to mod N, where N is a natural number, which is easy to prove, but means you now have to add the restriction on n and r that their modular inverse exists! So now I have:

2x = r + r^-1 mod N and 2y = n^-1(r - r^-1) mod N

And I'm going to go now to a famous solution to x² - Dy² = 1.

With D=61, the smallest positive nonzero integer x and y set that will work is:

x = 1766319049, y = 226153980

That solution was made famous by Fermat using the D=61 case as a challenge problem! Hundreds of years ago. Here I'll use it with my equations for r and its modular inverse now modulo N, with 'm' instead of 'n' so there is no confusion with letters:

r = x + my mod N

and

r^-1 = x - my mod N

I'm going to try something, which is to find r and its inverse by using x and y from the D=61 solution, so I need m and N, where m² = 61 mod N. I want N greater than x so will go looking at x+4:

1766319049 + 4 = 1766319053, and its integer square root is: 42027

And I'll add one more and use 42028² - 61, which is: 1766352723.

So N = 1766352723, and m = 42028.

Now I can plug in my numbers:

r = 1766319049 + (42028)(226153980) mod 1766352723

and

r^-1 = 1766319049 - (42028)(226153980) mod 1766352723

Which gives me:

r = 55435303 mod 1766352723; and r^-1 = 1710850072  mod 1766352723

So why bother? Well it just gave me a modular inverse--if the equations are correct!

And, yup, you can use your pc calculator--which I just did--and verify:

(55435303)(1710850072) = 1 + (53693405)(1766352723) = 1 mod 1766352723

What's kind of funny to me is that first while typing this post I did several things wrong, and did that check and didn't get 1, so there is this feeling of mini-panic. And I'll wonder briefly if my math theory is wrong, but then remind myself, nope, it's derived. So I realize I made a mistake somewhere. And of course I did.

Math is perfect. It's us people who make mistakes.

Want to see more? You can check out the derivation of the mod p result here. New to modular arithmetic? Then you might like my light introduction to modular arithmetic.

So what's the use of the result? I can't think of a practical use! But it's just fun playing with numbers to me, and it shows the correctness of the equation for others with a famous solution.

There is that comfort for me, I'll admit too. At times I just run numbers with my research just to get that feeling of satisfaction when everything works, perfectly.


James Harris

Prime Counting 10 Year Anniversary

So I should acknowledge an intriguing milestone as it has been 10 years since I found a way to count prime numbers using, for the first time known, a difference equation:

With natural numbers

P(x,y) = x - 1 - sum for j=2 to y of {(P([x/j],j-1) - P(j-1, sqrt(j-1)))(P(j, sqrt(j)) - P(j-1, sqrt(j-1)))}

where if y>sqrt(x), then P(x,y) = P(x,sqrt(x)).

Because it is a difference equation you do not need to tell the equation any prime numbers.

To count primes up to 100, for example, you'd calculate P(100,10), which gives 25.

For me it was always fascinating as I found the original form working at the computer.

It was such a fascinating feeling August of 2002, ten years ago, when that computer screen filled up with prime numbers, found as the full count took place. It finds the primes up to the square root, so if you're counting to 100, it finds 2, 3, 5 and 7. If you're counting primes up to 10000, it finds primes up to 100 as it counts. So cool.

It does have a sieve form, where you give it those primes instead of letting the math find them, which is what can be made faster as in iterating through to count with the fully mathematicized form, it's doing some calculations over and over again. The sieve form helps stop that repetition so it's faster:

Still with natural numbers where p_j is the j_th prime:

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

where if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

Because you're using natural numbers, no fractions or decimals, so those are just dropped. So 10/3 is 3 with just natural numbers, the sqrt() is the integer square root, for instance sqrt(10) = 3, as that's floor(sqrt(10)), and it's automatically positive because natural numbers are only the positive integers greater than 0.

But if you're not looking for something faster to count primes, it's more interesting to probe the difference equation further, and follow it through to a differential equation!

Continuous function:

In the complex plane

P'_y(x,y) = -(P(x/y,y) - P(y, sqrt(y))) P'(y, sqrt(y))

is the partial differential equation that follows from the difference equation.


James Harris

Derivations are fun

Finding math derivations is something I enjoy doing, where I like finding multiple ones for the same thing as it helps understanding, and is an enjoyable exercise for me. So here is a post deriving a result I've already derived.

Given n such that: n² = D mod p, where p is a prime number, and r, any residue modulo p:

2x = r + r^-1 mod p and 2y = n^-1(r - r^-1) mod p

gives solutions for x² - Dy² = 1 mod p.

Here I'll give a different derivation by considering two modular equations:

r = x + ny mod p

and

r^-1 = x - ny mod p

Since r(r^-1) = 1 mod p, I can just multiply and get:

r(r^-1) = 1 = x² - n²y² mod p

Which is: x² - n²y² = 1 mod p

And introduce D, such that: D = n² mod p, and I have: x² - Dy² = 1 mod p

Solving for x and y then is just a matter of adding and subtracting and simplifying with my original equations. Adding to solve for x and subtracting to solve for y, to get finally:

2x = r + r^-1 mod p, and 2y = n^-1(r - r^-1) mod p

Here I like leaving the 2 on the left side as I think it is a little bit cleaner. And looking modulo p, means I don't have to worry if the modular inverse exists. Note, I don't consider 0 to be a residue.

This result will solve the original equation explicitly and non-trivially if you have p greater than x and y, and you happen to pick the right residue! Or just run through them all till you find it. So it's not like it's practical. But I like it.

Oh yeah, it will solve explicitly non-trivially as long as D is not a perfect square, because if D is a perfect square then you have (x-ny)(x+ny) = 1, which has only x=1 or -1, y = 0 as an integer solution.

Re-deriving results over and over again is maybe one of those things that others might not understand, but I think it's fun, and it's something that keeps the mind active for a bit before moving on to other things.


James Harris

My math comfort

For years I've realized I find comfort in the solidity of mathematics and turn to it when the world seems screwy, or I'm under a lot of pressure. Then I kind of reflexively find myself musing on some result and I feel better, as math can give you that certainty that can be missing in an often arbitrary world.

And recently I've found myself turning often to the equation x² - Dy² = 1. I've found quite a few things about it, and lots of results about it that I enjoy. Here I'll talk about one of the latest.

Back in June of this year I noticed a way to solve for x and y mod p, where p is a prime for which D is a quadratic residue, so there exists n such that: n² = D mod p

Then where r is any residue modulo p:

2x = r + r^-1 mod p and 2y = n^-1(r - r^-1) mod p

Which gives solutions for x² - Dy² = 1 mod p.

So you don't necessarily get an explicit answer to the original equation, but you can use any prime p you want as long as D is a quadratic residue. You can easily move to composite N versus prime p, but I find it simpler to just focus on primes for just playing around, so for instance I know the modular inverse will exist.

And you can find p as big as you want.

Now let's plug in some numbers! For me with number theory it's so cool when you watch the numbers follow the rules. Perfectly. They do it with absolute perfection.

Here I'll use D=23, and I just checked and it's a quadratic residue of 101, which I picked arbitrarily. So let p=101. Then n = 15 is a solution, as 15² = 23 mod 101.

And I need its modular inverse and 15^-1 = 27 mod 101.

And I can use whatever residue I want for r, where I note I don't consider 0 a residue, and 1 would be boring I'm sure, and 2 might be ok, but I'll just use r = 3, because that might be more interesting.

And I need its modular inverse and 3^-1 = 34 mod 101.

So now I can solve for x and y:

2x = 3 + 34 = 37 mod 101, and 2y = 27(3 - 34) = 27(-31) = 27(70) = 72 mod 101.

And now I need the modular inverse of 2, and 2^-1 = 51 mod 101.

So:

x =51(37) = 69 mod 101, and y = 51(72) = 36 mod 101

So do they work? They HAVE to work, as it's math! But let's plug them in and check:

69² - 23(36)² = -25047 = 1 - 248(101) = 1 mod 101

So they work! But of course they do, it's math.

But you don't get an explicit solution for x and y, and I'm curious about what r would give it to you.

I looked up the explicit solution even though it's easy to figure it out, and it is:

x = 24, and y = 5, as 24² - 23(5)² = 1

From my derivation I have that r = x + ny mod 101, so: 24 + 15(5) = 99.

So guess I should have worked down from 101 instead of up!

The interested reader can run through with r = 99 and see that it all works.

And for me that is relaxing! It is just really cool seeing the numbers do as expected. And they follow rules that I found! Is it really practical? What do I care. I like the perfection and keeping my mind occupied.

For years when the world stresses me, I've had my math to rely on. It's a comfort like no other, and its perfection is a great shelter.


James Harris

Quadratic residue gaps

In an earlier post I went through the equations covering spacing of quadratic residues:

If integer solutions for x² - Dy² = F exist, it must be true that:

2ky = z - Fz^-1 mod D-k²

(z-ky)² = k²y² + F mod D-k²

Where x = z-ky or x = -(z-ky), and z is any residue for which the modular inverse exists. Here there is the additional requirement that 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k² is a square.

Now I'll consider the related subject of gaps between quadratic residues. And I'll start with k=1:

2y = z - Fz^-1 mod D-1

(z-k)² = y² + F mod D-1

The possibility of a gap is determined by the value of F, but these equations must exist! Where for x and y to have integer solutions, we have that F must be a quadratic residue modulo D, from x² - Dy² = F.

To get perspective on the number theory mechanism and how the gaps are different from the spacing consider the quadratic residues of 19:

1, 4, 5, 6, 7, 9, 11, 16, 17

And notice that 4 is one away from 5, but 2 away from 6, while 7 is two away from 9, with a gap of 2.

For the control equations with k=1 we'd need D=20 with F=2, which is: x² - 20y² = 2

And there are no integer solutions for x and y, and notice that 20 doesn't have 2 as a quadratic residue.

The quadratic residues for 20 are: 1, 4, 5, 9, 16

But let k = 2, then D=23, and still with F = 2, the control equations are:

4y = z - 2z^-1 mod 19

(z-2y)² = 4y² + 2 mod 19

And now consider the quadratic residues of 23, which are:

1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18

And 2 is there as needed to allow the gap of 2 with 19, but notice it doesn't mean there actually is such a gap! We know there is one because we looked but the equations are actually simply allowing a spacing of 2, where we could see two examples with the quadratic residues of 19.

Looking over the quadratic residues for 19, I'm more interested now in what is not allowed as a spacing, and it looks like only 17, for obvious reasons, which is boring but not surprising with quadratic residues of primes.

And by observation I see that 5 is the widest gap between the quadratic residues of 19, and at this point I'm not sure why, so it's something to ponder. But things should be much more interesting with composites, where there should be potential for bigger gaps, as there are fewer quadratic residues.

For instance for 16 the quadratic residues are: 1, 4, 9

So spacings appear to be 3, 5 and 8, but gaps are only 3 and 5.

Looking at the control equations, starting with k=1, so I'd have x² - 17y² = F, then:

2y = z - Fz^-1 mod 16

(z-y)² = k²y² + F mod 16

And it's easy to see how a lot of possibles are blocked which is that the modular inverse won't exist for any even z's. But what does that have to do with F? Not much I guess.

Looking at quadratic residues of 17 they are:

1, 2, 4, 8, 9, 13, 15, 16

And 3 and 5 don't even make the list, so F = 3 or 5 mod 16 isn't allowed. So F may not even be able to equal a spacing that you can see from the actual quadratic residues. Interesting.

Oh, forgot the additional requirement: 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k² is a square.

These things can get convoluted and you have to keep up with all the rules! Maybe should have looked at 21 or 32 instead. Maybe later.

So not much progress here. But putting up things to ponder.

At this point I'm not sure how you find the gaps then! Spacing doesn't tell you that a gap exists as explained above, so it's an open problem on which I might ponder for a while. Cool!


James Harris

Quadratic residue modular solution

So I've started playing around with trivial modular solutions to x² - Dy² = 1 as I'm bored and it's easy to do. Earlier I noted that:

x² - Dy² = 1 mod D-1, is solved modularly by:

2x = r + r^-1 mod D-1 and 2y = r - r^-1 mod D-1

Now I've thought up another easy one using some prime p for which D is a quadratic residue, so there exists n, such that:

n² = D mod p

Then I have (x + ny)(x - ny) = 1 mod p.

And with x + ny = r mod p, and x - ny = r^-1 mod p, then

2x = r + r^-1 mod p and 2y = n^-1(r - r^-1) mod p

Giving yet another way to solve for x and y modularly.

And, of course, as it's a modular solution it is for:

 x² - Dy² = 1 mod p

So you don't necessarily get an explicit answer to the original equation.

Of course you can generalize easily enough modulo some natural number N for which D is a quadratic residue, and continue even further to solve modularly for the equation:

x² - Dy² = F

Where F is some natural number.

If "mod" is unfamiliar to you, I made up a small primer covering modular arithmetic that you may find useful.


James Harris

Tautological spaces and calculus

So back December 1999 out of desperation I came up with using identities to help analyze mathematical equations, where after some thought I first focused on the identity:

x+y+vz = x+y+vz

where I made it part of modular arithmetic very simply:

x+y+vz = 0(mod x+y+vz)

which is equivalent, and I decided to call mod x+y+vz a tautological space, as it represents a region where that is true, and I liked the sound of it. I've also considered logic and mathematics, so it was easy enough for me to meld them a bit with that term.

And I can do things with tautological spaces like I came up with a more refined and general way to reduce binary quadratic Diophantine equations, among other things.

And I've advanced tautological spaces methodology. The general form is actually:

a₁^h + a₂^h + v₁a₃^h +...+v_n-2a_n^h = 0(mod a₁^h + a₂^h +v₁a₃^h +...+v_n-2a_n^h )

where h is what I call the hyperdimension and n is what I'll now call the tautological freedom.

So with my first tautological space you have a hyperdimension of 1 and a tautological freedom of 1, which means three variables, which are x, y and z.

The generalization to the full form is needed for more dimensions than x, y and z, as well as for the calculus as I'd started pondering how to bring it in with my idea, which I realized required that you have at least two degrees of tautological freedom. That is, n=4 or greater is required for the calculus.

For instance if you differentiate against the tautological space itself, you do a partial differentiation, for example with h = 1 and n = 4, you have:

a₁ + a₂ + v₁a₃ + v₂a₄ = 0(mod a₁ + a₂ +v₁a₃ +v₂a₄)

And one way to differentiate is:

a₃ + a₄dv₂/dv₁ = 0(mod a₃ + a₄dv₂/dv₁)

That's curious. I'll call it a tautological differentiated space or a tautological D-space, or a TDS.

What's interesting is, you do not in general differentiate from within the tautological space, so you'd differentiate a conditional outside of it, as when you differentiate inside the tautological space you lose variables!

The problem is that differentiation is one thing that must impact the modulus, and it's only possible to do it against the v's as otherwise it's trivial.

And I don't know the utility of that expression, but will keep it up.

But there is another way to introduce the calculus in a possibly more useful way, since the a's are so free, as consider the following tautological space:

x + y + v₁y_x' + v₂z = 0(mod x + y + v₁y_x' + v₂z)

which allows you to introduce a conditional with differentials, as I can just use as many of the a's as needed, and you can use partial differentials or full differentials as the a's do not care.

The general principle is that the shape of the tautological space is driven by the conditional.

There are an infinity of tautological spaces. You simply pick from that infinity to suit your needs.

Pulling from the Absolute.

Because it's an identity it MUST be true, and I do wonder what great things can now be done.

Excellent, so you CAN use the calculus, and my generalization was needed for that effort, where now I see where differentials can be added in a way that makes more sense to me.

And I haven't even reached for integration yet.

That's enough of that effort. Thinking at foundation level is just SO hard.

Makes you really hungry too, but that's a benefit, as food tastes so much better.


James Harris

Cubic Diophantine computations

So yesterday I found myself wondering what would happen if I extended my idea of looking modulo D-1 to a cubic Diophantine, which is just about curiosity! Here, I'll do a post with some computations.

To recap, I found that given x³ - Dy³ = 1, I could solve for y with:

3(2y+r)²  = 4r^-1 - r²  mod D-1

where x = y+r mod D-1, and r is a residue which has a modular inverse modulo D-1.

So I'll arbitrarily use a situation where I have a solution, which is D=26, as x=3, y=1 works.

Then:  3(2y+r)²  = 4r^-1 - r²  mod 25, and I'll try r=1, so (2y+1)²  = 1 mod 25.

Which gives 2y + 1 = 1 or -1 mod 25. So y = 0 or -1 mod 25, which works trivially.

Moving to r=2.

3(2y+2)²  = 4(13) - (2)²  mod 25 = 23 mod 25, so (2y+2)²  = 16 mod 25.

Which gives two solutions. One is 2y + 2 = 4 mod 25, so y = 1 mod 25.

For the other 2y = -4 mod 25, so y = 22 mod 25, then x = 24 mod 25.

And (24)³ - 26(22)³ = -263024 = 1 - (10521)(25) = 1 mod 25 as required.


James Harris

Considering a cubic Diophantine

It is intriguing to me to consider now a cubic Diophantine with the approach of considering it modulo D-1.

Given x³ - Dy³ = 1 I'll try to find modular solutions for x and y modulo D-1:

x³ - Dy³ = 1 mod D-1, and D mod D-1 = 1, so:

x³ - y³ = 1 mod D-1

Which is: (x-y)(x² + xy + y²) = 1 mod D-1, and letting r be any residue with an inverse modulo D-1:

x-y = r mod D-1 and x² + xy + y² = r^-1 mod D-1, so, x = y+r mod D-1, allowing me to substitute:

(y+r)² + (y+r)y + y² = r^-1 mod D-1

and expanding out gives:

y² + 2yr + r² + y² + ry + y² = r^-1 mod D-1, so:

3y² + 3yr + r²  -  r^-1 = 0 mod D-1, and I'll use fractions--though it can be done without them--to make things easier for me and complete the square:

y² + yr + r² /4 -  r² /4+( r²  -  r^-1 )/3 = 0 mod D-1, which is: (y+r/2)²  = -(r² - 4r^-1)/12  mod D-1, so:

3(2y+r)²  = 4r^-1 - r²  mod D-1

And I think it is kind of ugly. But I'd think you could get answers with it, but just have to be able to find a quadratic residue, if it exists.

Just a curiosity. I'll put this up and maybe come back later to check my derivation and try it with some numbers.

I don't know of a practical use for this result, but it seemed like a fun thing to just extend a bit, and see what I got.


James Harris

Deriving x and y modular solution

Given x² - Dy² = 1 it is trivial to find modular solutions for x and y modulo D-1:

x² - Dy² = 1 mod D-1, and D mod D-1 = 1, so:

x² - y² = 1 mod D-1

Which is: (x+y)(x-y) = 1 mod D-1, and letting r be any residue with an inverse modulo D-1:

x+y = r mod D-1 and x-y = r^-1 mod D-1, so:

2x = r + r^-1 mod D-1 and 2y = r -  r^-1 mod D-1

I like leaving the 2 on the left hand side rather than use its modular inverse, which may not exist, or write a fraction on the right hand side.

That is easy to generalize mod D - k², as well as with x² - Dy² = F.

x² - Dy² = F mod D-k², and D mod D-k²  =  k², if k² is less than D so:

x² - k²y² = F mod D-k² where now r₁(r₂) = F mod D-k², so:

x+ky = r₁ mod D-k²  and x-ky = r₂ mod D-k², and you have:

2x = r₁ + r₂ mod D-k²  and

2ky = r₁ -  r₂ mod D-k²

Here if the modular inverse of r₁ modulo D-k² exists I can substitute out r₂ by using r₂ = Fr₁^-1 mod D-k² and have:

2x =  r₁ + Fr₁^-1 mod D-k²  and

2ky = r₁ - Fr₁^-1 mod D-k²

Derivation complete.

And I've derived the solution for y before, using a substitution x = z-y, but I think the above is a little cleaner looking and more direct. But it's not as applicable as it requires that k² is less than D, unless that requirement is actually there with my prior results, where I just didn't see it. Puzzling over that detail though it makes sense as otherwise you could just make k really huge and pull out explicit solutions that way?

Regardless, I like finding multiple ways to do derivations and think this approach is elegant, and looks prettier while also being very easy.


James Harris

Shifting to math is fun perspective

I like playing with numbers, and figuring things out about them. And admitting that to myself helps a lot, and I think this blog has plenty of interesting things for people who like to play with numbers and I've put up some introductory information including a page introducing modular arithmetic to help people get quickly to things that work.

It's better I think to shift to math is fun. And I have so many math ideas where you can just play with numbers and see things for yourself.

Like counting quadratic residue pairs! I didn't even know what a quadratic residue pair was until recently, because of a discovery.

Quadratic residues are the squares of modular arithmetic, like with x² = r mod N, r is the quadratic residue.

Here are the quadratic residues for 29:

1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28

Some are explicitly squares, like 4, 9 and 16, while others are not as you flip over when you get past 29, so for instance 6² = 36 = 7 mod 29.

And some of the quadratic residues follow each other, like 4 and 5 and 5 and 6, and math people call those quadratic residue pairs and I figured out a way to count them. There was a way known before, but I found my own way, which I like better.

The end equations have to be the same, of course.

And if p is prime, and p mod 4 = 1, the count is (p-5)/4, which for 29 is 6.

And here are the pairs with participating numbers in bold. Note that 4,5 is a pair, as is 5,6, so they count as two.

1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28

Go with what people can prove. If you like playing with numbers there are lots of things on this blog, where I explain and derive. I'm not a mathematician though, and am not trained in writing things in some peculiar format, so I have my own style. Proof is rigorous though.

And besides the numbers speak more eloquently. There can be such a thrill in watching numbers follow these beautiful mathematical rules. Math IS fun.

All of the above is the confident, act like I really know what I'm doing kind of thing, but at the end, yeah, it is about the numbers. If your math is right, the numbers behave by stated rules. And for some, the precision and beauty of numbers IS all that's really important when it comes to discussing useful mathematics.


James Harris

Simplifying number theory

Surprisingly to me, I have found my ability to simplify certain areas of number theory to be the best path to confidence in my ideas, and importantly in discrete mathematics I found a way to reduce Diophantine equations like:

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

which is called a binary quadratic Diophantine as x and y are the unknowns, to a general form like:

u² - Dv² = C

where u and v are the new unknowns and in solving them you find x and y with the original equation.

It's a simplification of number theory as the traditional ways to reduce involve three different ways depending on the values of the c's, while I found there is one way available.

I used a mathematical tool I call tautological spaces for that discovery, which also gave me a very useful relation on the simplified form, where I'll go back to x and y for the unknowns:

The equation x² - Dy² = F

requires that

(x+Dy)² - D(x+y)² = -F(D-1).

Remarkably that alone allowed me to connect equations when F=1, with Pythagorean Triples when D-1 is a square, which was the first indication for me, of the importance of D-1, where since then I've been able to explain the size of fundamental solutions, with factors of D-1 being part of it.

That covers research mostly completed in 2008. I've updated some of it recently, for better exposition.

These results were I believed intriguing and they helped my confidence as I could just play with actual numbers and watch them behave as the equations required. But I still was looking for social validation from mathematical society.

Recently I found that I could do even more with the simplified form and solve for y modularly:

Instead of x² - Dy² = F, let x = z-ky or x = -(z-ky), so:

(z-ky)² - Dy² = F.

Then it can be shown that if integer solutions for x² - Dy² = F exist, it must be true that:

2ky = z - Fz^-1 mod D-k²

(z-ky)² = k²y² + F mod D-k²

Here there is the additional requirement that 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k² is a square.

And now it was REALLY cool watching numbers behave as expected including quadratic residues where their spacing now made mathematical sense as being governed by those equations.


James Harris