January 14, 2009

Solution Found!

I finally solved Pell's Equation, or at least my version of it. (A quick reminder: Pell's Equation is a polynomial equation of the form Nx^2+-1=y^2, one finds solutions for x and y with N given.)

My methodology was strange, but the solution works. I began by leaving the subject, and exploring something else I found interesting. I noticed that squaring numbers of the form a+b*Sqrt[n] gave other numbers of the same form, for different a and b. For example, (1+Sqrt(3))^2 = 4+2*Sqrt(3). These are similar to multiplying complex numbers- one ends up with a real part, often denoted Rp, and an imaginary part, or Ip. Here, I ended up with a whole part and a part multiplied by the square root of some whole number. (With complex numbers it is a whole number and a whole number multiplied by i.) I decided to look at different powers of 1+Sqrt(2), since it was the most simple combination I could think of, and see if there was a common trend among the coeffecients.

[1+Sqrt(2)]^1 = [1+Sqrt(2)]
[1+Sqrt(2)]^2 = 3+2*Sqrt(2)
[1+Sqrt(2)]^3 = 7+5*Sqrt(2)
[1+Sqrt(2)]^4 = 17+12*Sqrt(2)
[1+Sqrt(2)]^5 = 41+29*Sqrt(2)
[1+Sqrt(2)]^6 = 99+70*Sqrt(2)

Whadda ya know?! The coefficients of each expansion, y+x*Sqrt(2), are solutions to Pell's Equation when [1+Sqrt(2)] is raised to an even power! I haven't yet figured out a more compact way to write the solutions; I would use a binomial expansion, but it isn't that simple because there is one whole part and one whole times sqare root of 2 part, and these parts are sums of certain terms in the expansion. This formula works because of this relationship within Pell's Equation:

Nx^2+1=y^2

y^2-Nx^2=1

(y-x*Sqrt[N])(y+x*Sqrt[N]) = 1

{(y-x*Sqrt[N])^m}{(y+x*Sqrt[N])^m} = 1^m = 1

This says that if x and y satisfy Pell's Equation, then so do the coeffieicnts you get when you multiply out (y+x*Sqrt[N])^m, which is exactly what I've done, given an initial x and y.

Also, in an unusual double-header solution, I realized that the odd powers of [1+Sqrt(2)] yield solutions to another form of Pell's equation: 2x^2 - 1 = y^2. If you check the official definition of Pell's Equation on Mathworld.com, you will find that it is often considered as Nx^2 +/- 1 = y^2, for a given whole N. So, the solutions to the equation with -1 are the coefficients, y+x*Sqrt[2] of the expansion of [1+Sqrt(2)]^n for odd n >0.

If you check my last post on Pell's Equation, you may notice that I noted 3+2*Sqrt[2] as the common ratio between x's of consecutive solutions. I had found the ratio for other Pell's Equations as well- for N = 3, N=5, and so on: all the way through n = 27. (All were found by estimating the ratio from the solutions my computer found with a C++ program, and they do converge rapidly which made them easier to find.) They all work as the base ratio for the value of N in Pell's Equation; when you take the ratio to a power greater than zero, you find that the coefficients of the result are solutions to the respective Pell's Equation. For example, for N = 10, the ratio is 19+6*Sqrt[10]. The fourth solution to this equation, then, is given by

[19+6*Sqrt(10)]^4 = 1039681 + 328776 Sqrt[10]
x = 328776, y = 1039681

And we arrive at

10*(328776)^2 + 1 = 1039681^2

The unfortunate part is that I haven't found a uniform method of determining the base ratio for each value of N. They are oddly spaced, and I've found two strange trends. First, some of the ratios are squares of other quantities, a+b*Sqrt[N], indicating that these can be used to find the solutions to the -1 case of Pell's Equation by taking the odd powers of the square root of the calculated ratio. (For example, the ratio for N = 17 was 33+8*Sqrt[17], and it's square root is simply 4+Sqrt[17].) The second trend is that some of the ratio values for specific N's are the same as earlier ones. For example, the value for N=8 is 3+Sqrt[8] = 3+2*Sqrt[2], which is the same ratio for N=2. The same thing occurs for N=5 and N=20, N = 6 and N=24, and N = 8 and N=18. (At first I thought that N sometimes has the same ratio as that of 4N, and the first 3 fit that rule- however, the final one, N=8 and N=18, doesn't.) I'll have to look into this further to finish Pell's Equation off.

January 3, 2009

New Findings

I have cataloged all of the Richey Numbers between 1 and 1000, and have come to some new conclusions.

First, I noticed that given a solution, N = a^2 + b^2 = c^2 + d^2, 2N is also a solution, and with some intuition I realized that 2N = (a+b)^2 + (a-b)^2 = (c+d)^2 + (c-d)^2. The solution I worked with first was 65- I noticed that 130 was also a solution.

65 = 8^2 + 1^2 = 4^2 + 7^2
130 = 9^2 + 7^2 = 11^2 + 3^2

As you may notice, 9 is the sum of 8 and 1, 7 is the difference of 8 and 1, 11 is the sum of 7 and 4, and 3 is the difference of 7 and 4.

This result is easily proven.

N = a^2 + b^2
2N = (a+b)^2 + (a-b)^2
= a^2 + 2ab + b^2 + a^2 - 2ab + b^2
= 2a^2 + 2b^2
= 2N

The same also follows for the other part, c^2 + d^2.

The next thing I began experimenting with was the prime factorizations of Richey Numbers. I looked mainly at the numbers I thought to be "pure"; those that are not iterations of other Richey Numbers. For example- 130 is only 65*2, and the prime factorization gave that of 65 with a 2 in it as well. Other examples include any Richey Number multiplied by a square #, because of another property I discovered: Given a solution N = a^2 + b^2 = c^2 + d^2, (k^2)N = (ka)^2+(kb)^2 = (kc)^2 + (kd)^2, an easily verifiable result. Therefore, numbers like 200, 260 and 450 are reiterations: 50*4, 65*4, 50*9 respectively. This finding, coupled with the principle noted above, also led me to include Pythagorean triplets into my definition of Richey Numbers. (This basically means that I would allow a, b, c, or d to be zero, something I hadn't allowed before.) I realized that if a^2+b^2 = c^2 was also considered as a solution, that may explain the prime factorizations of some of the numbers I already came up with, such as 50 and 388. This is because their prime factorizations turned out to be 2*k^2, for some integer k- in these cases, 2*5^2 and 2*169^2 respectively. At first, I was puzzled as to how something like 25, whose components (3^2+4^2 = 5^2) include a zero (in terms of Richey Numbers) could lead to a legitimate Richey Number. I quickly realized that when multiplying 25 by 2 and using the rule I stated above, the sum of 5 and 0 and their difference are both 5- both non-zero numbers, thus yielding 50, a more recognizeable Richey Number.

This analysis left four different kinds of prime factorizations, and I list them here in order of frequency, most frequent to least (N is a given Richey Number):

1. N = 5*Pk, where Pk is some prime in a specific set of primes.
2. N = Pa*Pb, where Pa and Pb are primes of the same set as in 1.
3. N = Pk^2, where Pk is a given prime in the same set as in 1.
4. N = 5^x, given a whole x>1.

The "specific set of primes" I refer to here was found only by studying the prime factorizations. These pure Richey Numbers' prime factorizations used these primes only, and I believe that there is some general relationship all these primes share (though I haven't yet found it). Here's a list of the first few pure Richey Numbers, their prime factorizations, and the categories they fall into:

25 = 5^2 (4)
65 = 5*13 (1)
85 = 5*17 (1)
125 = 5^3 (4)
145 = 5*29 (1)
169 = 13^2 (3)
185 = 5*37 (1)
205 = 5*41 (1)
221 = 13*17 (2)
265 = 5*53 (1)
...
And the list of primes:

13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193,197...

I hope this will lead somewhere interesting, as this list of oddly spaced primes does seem, well, odd.