Author |
Topic: Highway (to) 61 revisited (Read 6611 times) |
|
Mickey1
Junior Member
Gender: 
Posts: 116
|
 |
Highway (to) 61 revisited
« on: Jul 11th, 2012, 4:55pm » |
 Quote  Modify
|
The following is a tour of classical number theory, visiting Fermat’s sum-of-two-squares theorem , Pell’s equation, and Mersenne’s (mostly non-prime) numbers , but it ends with an attempt to calculate x and y for difficult combinations such as x2-61y2=1 in a simple way (I apologize for my notation and my continued use of it).
Looking at so called 4n+1 primes and Fermat’s theorem about sum-of-two-squares
x2+y2 =4n+1=p (prime) you have perhaps noted, as I have, that in many cases x and y, and indeed xy, is a divisor of 4n. To study those cases, I rewrite the equation
x2+y2 =2nxy+1, and since either x or y must be even, I believe this is a general case (i.e. we don’t need to have the number 4 appearing in the equation).
I solve this for x for which I get
X=ny+-sqrt(n2y2-y2+1)= ny+-sqrt((n2-1)y2+1). An integer solution must require that
(n2-1)y2+1 is a square of an integer which I call z2.
We have therefore z2-(n2-1)y2=1 i.e. a case of Pell’s equation using the constant d= n2-1
I continued to look at the solutions to this type of Pell’s equation and the numbers it rendered for p.
(Let me first note that n=1 gives x=y+-1 and that the corresponding sum of 2 squares x2 + (x+1)2 =p is a relatively prime rich sequence.)
I note also that since the nth power of 2 -1 is a Mersenne number the method offers a way of obtaining primes (and some other nonprime sums x2+y2) of these numbers. Most of the Mersenne numbers are composite since n2-1=(n+1)(n-1), except for n=2, yielding Pell’s constant d=3.
My calculations consists simply of choosing n; then I calculate n2-1, and get the first Pell equation solution, with z=n and y=1. The nest solution I found by setting y=2n and z=2n2-1, which works for my special case d=n2-1. I now have 2 sets of z and y and i continue with Brahmaguptas iterations where the new set x and y are conbinations of the old and of n (my strange power notation forbids me to explain because x2 could then mean both x*x and the second x solution but it is available on Wikipedia – P’s equation – it is fairly obvious. The other 2 ways are one using sqrt(d) and chain divisions are difficult or not explained well).
It occurs to me that this prime (3) seems to generate more primes when I recreate the number 2nxy+1 than the non-prime Mersenne numbers . The no-primes are numbers which have two alternative sums of 2 squares such as 65=64+1=49+16. (These are numbers such as (a2+1)(b2+1)/4 for both a and b odd). The primes generated above give very poor statistics, because of the limited precision in excel. For some reason Pari does not allow me to create files so I can only perform simple tasks with Pari.
But we must haste to my last approach. The insight that my second solution (2n2-1,2n) is always available gives me a method for calculation in a closed form (if that is the right term).
I now proceed to do something partly odd or illegal: I simply enter n=sqrt(n) instead of n. This gives me d=n-1. The 2xy+1 still comes back as integers since the sqrt appears twice in the formula for n. I believe the second solution (2n2-1,2n) is still OK. In my iterations I get alternating integers and non-integers for x and y.
I now insert sqrt(62) to receive d=61 and I hoped to get integers for both x and y when the “right” numbers came up (1 766 319 049 and 226 153 980 for z and y respectively). However in my 5th solution i.e. my third Brahmagupta iteration I get the numbers z= 1 830 972 097 and y= 234 431 954,54
Surprisingly these numbers are close to the real ones and they are off both by exactly the same amount, only 3,660 %. Is this a coincidence or is it a reflection of my limited precision?
Tried to attach the calculations in excel but failed.
|
| « Last Edit: Jul 11th, 2012, 5:05pm by Mickey1 » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Highway (to) 61 revisited
« Reply #1 on: Jul 11th, 2012, 10:51pm » |
Quote Modify
|
on Jul 11th, 2012, 4:55pm, Mickey1 wrote:| Tried to attach the calculations in excel but failed. |
|
If it's because of the file-type, you can try zipping the excel sheet.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Highway (to) 61 revisited
« Reply #2 on: Jul 11th, 2012, 11:58pm » |
Quote Modify
|
Yes, at least that was the complaint from the system. I will try to zip it.
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Highway (to) 61 revisited
« Reply #3 on: Jul 12th, 2012, 12:18am » |
Quote Modify
|
I tried again - this time the answer was "could not uplode file 61.zip" so something is not working for me.
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Highway (to) 61 revisited  61.jpg
« Reply #4 on: Jul 12th, 2012, 12:23am » |
Quote Modify
|
I tried again - this time the answer was "could not uplode file 61.zip" so something is not working for me.
Another try of a - less useful - screen print. An error: Z=n is wrong, but I have a bad connection so I don't dare to try more.
I have tried in vain one more to uplode my excel file.
Anyone interested might contact me through email, or perhaps through a suggested 3rd party file storage .
|
| « Last Edit: Jul 12th, 2012, 2:47pm by Mickey1 » |
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Highway (to) 61 revisited
« Reply #5 on: Jul 12th, 2012, 3:42am » |
Quote Modify
|
I note the my ratio of z/y is the same as those of Pell's numbers to 9 significant digits.
Perhaps this could still be a coincident considering that any attempt of an answer for z/y would be close to sqrt(n+1/y), and very close for high numbers.
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Highway (to) 61 revisited
« Reply #6 on: Jul 17th, 2012, 2:57pm » |
Quote Modify
|
A new approach to x2-61y2=1 (I use again x2 for x*x).
I note that Pell’s equation x2-Dy2=1 appear to arrange itself in a cyclic manner from D= n2 (n*n) to D=(n+1)2 or just below n2 since there are no solutions for D=n2.
The (first) solution just below n being a square, i.e for D=n2-1 is very simple [x=D, y=1].
The solution below that, for D= n2-2 ia also simple [x=n-1,y=n] ( (n2-1)2-(n2-2)n2 = n4-2n2+1 –(n4-2n2)=1. There is a similar pattern for D above n2 but I am concentrating on solutions for D below n2, and in particular n2-3, since these are the ones that contain D=8*8-3=61, where the first solution with a very large x and y, [x= 1 766 319 049, y= 226 153 980].
This is not the only solution with large numbers , D=10*10-3=97 is another [x=62 809 633, y=6 377 352]. I realize there seems to be other cyclic patterns but for now I am concentrating on the D=n2-3.
I have not solved anything yet but I have noted a particular pattern which I haven’t seen anywhere on the usual links. It doesn’t really prove much and I realize I may be a few thousand years late, but I still propose the following conjecture which I believe is true up to D=397:
When D is
1) >3,
2) of the form n2-3, and
3) a prime number
then
x+1 contains a set of factors which
a)
includes D and
b)
includes one or more factors from y twice, i.e. in a squared form.
For instance: x and y are the solution of x2-397y2=1 [x=838 721 786 045 180 184 649, y= 42 094 239 791 738 438 433 660].
X+1 has the factors 2, 5^2, 17^2, 37^2, 173^2, 397, 1889^2, and
y the factors 2^2, 3^3, 5, 17, 37, 173, 383, 1 889, 990 151, of which 5 appear as squares in x.
If you find a few cases where such a relations hold you could always be the victim of relations that holds for small numbers, but the seeing these relatively high factors of y appearing squared in x+1 (761 for D=61, 569 for D=97) is convincing enough for me to go further (the idea is to use this for a simplification, leading to other equations with much lower numbers, taking some of the magic out of D=61 for example). (I apologize for possible errors which I unfortunately make all the time – otherwise I might have been looking for a career as a mathematician).
By the way, the conjecture above leads to two riddles:
1 Take two natural numbers, a and b, <n (or two numbers a<A and b<B), what is the probability that a has one (or more) factor(s) f which appears twice as a factor in b, who also contains a given factor D.
2 given the fact that people have looked at x in [x2-Dy2=1] what is the (subjective) probability that someone looked at x+1 as I have done?
Regarding 2, I note that almost anything I have looked at, have been thought about before (and turns out to be trivial once it is explained).
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Highway (to) 61 revisited
« Reply #7 on: Jul 18th, 2012, 5:12am » |
Quote Modify
|
As a notational note, I find xx and yy easier to read than x2 and y2.
In general, writing something in a way that's likely to confuse your readers simply because it's easier to type encourages the question "why should I spend time and effort reading it when you didn't put much effort into writing it?"
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Highway (to) 61 revisited
« Reply #8 on: Jul 18th, 2012, 7:23am » |
Quote Modify
|
Very good
I will do that if I get any comments. So far it is mostly me talking to myself.
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Highway (to) 61 revisited
« Reply #9 on: Jul 20th, 2012, 2:37am » |
Quote Modify
|
I didn't have to work long on this problem to find that
xx-Dyy=1 implies that
xx-1=Dyy and therefore (x+1)(x-1)=Dyy
so that x+1 must have at least some factor f of y and therefore also ff of yy.
What remains of my discovery is that D seems to be a factor of x+1 and not of x-1 at least for primes D=nn-3 (n=4, 8, 10,14, and 20) as far as I can see.
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Highway (to) 61 revisited
« Reply #10 on: Oct 3rd, 2012, 11:44am » |
Quote Modify
|
The following proof was kindly provided to me from prof Hendrik from the Netherlands. It proves that (assuming xx-dyy=1) for all primes d, x=-1 (mod d).
"I first note that x is odd, since if x is even then y is
odd, but now xx = 0 mod 4 and dyy + 1 = 2 mod 4, so that
xx and dyy + 1 cannot be equal.
So x is odd, and y must be even, say y = 2z. The two
positive integers w = (x - 1)/2 and w + 1 = (x + 1)/2 are
clearly coprime, and their product is d times a square. For
d prime, this can only happen if one of them is a square, say
uu, and the other is d times a square, say dvv. If w + 1
is the one that is a square, then we get uu = w + 1 = dvv + 1.
However, one has 0 < u < x, so this contradicts that x, y
is the LEAST positive solution to the Pell equation. Hence it
must be the other way around: w = uu, w + 1 = dvv, so that
x + 1 = 2(w + 1) is indeed divisible by d."
|
|
IP Logged |
|
|
|
peoplepower
Junior Member
Posts: 63
|
|
Re: Highway (to) 61 revisited
« Reply #11 on: Oct 3rd, 2012, 1:49pm » |
Quote Modify
|
Awesome, I love seeing some elementary number theory though I cannot do it.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Highway (to) 61 revisited
« Reply #12 on: Oct 4th, 2012, 4:41am » |
Quote Modify
|
on Oct 3rd, 2012, 11:44am, Mickey1 wrote:The following proof was kindly provided to me from prof Hendrik from the Netherlands. It proves that (assuming xx-dyy=1) for all primes d, x=-1 (mod d).
"I first note that x is odd, since if x is even then y is
odd, but now xx = 0 mod 4 and dyy + 1 = 2 mod 4, so that
xx and dyy + 1 cannot be equal." |
|
dyy+1=2 (mod 4) iff d=1 (mod 4)
For example: x=10, y=3, d=11 satisfies xx-dyy=1 and x=-1 (mod d)
I'd have to spend more time than I have if I were to figure out whether you've simply left out a constraint from earlier, or overlooked a class of solutions.
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
Let x(D) be a solution to Pell’s equation xx-Dyy=1 (x,y and D natural
numbers).
it seems few people are concerned with x as a function of D. Here is a conjecture along the lines toward such an understanding, or perhaps rather pattern recognition.
If D is a prime = n(n+1)(n+2)+1 then
• x(D) is increasing with D
• x(D-1) is unusually low and x(D) is unusually high (NB the notorious
case of D=61 is included), and
• n is approximately proportional the logarithm of x(D), see table
below and attached
I realize there are a very limited No of cases presented, related to
my own limitation of tools. I simply counted the digits from Wolfram
Alpha's solutions. (Inclusion of non-primes would disturb the
picture.)
Observe that the 3 degree of the polynomial for D rules out a simple
general polynomial representation of x, since the polynomial
representing xx would have an odd degree.
1st row: n 2nd row: No of digits in x(D=n(n+1)(n+2)+1) 3rd row: No of digits in x(D-1)
1 1 1
3 10 2
5 12 2
6 19 2
9 29 3
10 46 3
13 51 3
14 86 4
18 133 5
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Highway (to) 61 revisited
« Reply #14 on: Oct 28th, 2012, 4:00pm » |
Quote Modify
|
I forgot to correct an error in my earlier post
The source of my help from the Netherland was Prof Hendrik Lenstra, I only mentioned his first name earlier. By the way, Prof Lenstra has two brothers in the same field (mathematics).
Another error was that that I omitted the fact that the proof was for 4n+1 primes. Here is the full text
You are right: if d = nn - 3 is a
prime number, or more generally if d is a prime number that is
1 mod 4, then the least positive solution x, y to the Pell
equation xx = dyy + 1 satisfies x = -1 mod d. To prove this,
I first note that x is odd, since if x is even then y is
odd, but now xx = 0 mod 4 and dyy + 1 = 2 mod 4, so that
xx and dyy + 1 cannot be equal.
So x is odd, and y must be even, say y = 2z. The two
positive integers w = (x - 1)/2 and w + 1 = (x + 1)/2 are
clearly coprime, and their product is d times a square. For
d prime, this can only happen if one of them is a square, say
uu, and the other is d times a square, say dvv. If w + 1
is the one that is a square, then we get uu = w + 1 = dvv + 1.
However, one has 0 < u < x, so this contradicts that x, y
is the LEAST positive solution to the Pell equation. Hence it
must be the other way around: w = uu, w + 1 = dvv, so that
x + 1 = 2(w + 1) is indeed divisible by d.
I should mention that this is a known theorem! I just gave the proof for your convenience.
With my best regards,
Hendrik Lenstra
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Highway (to) 61 revisited
« Reply #15 on: Jan 9th, 2013, 7:10pm » |
Quote Modify
|
Let me summarize some of my notes on Pell’s equation xx-Dyy=1 and my Don Quixote quest of understanding x and y versus D (or perhaps it is closer to the Monty Python search for the Holy Grail). Nevertheless I think is is important and nobody else seems to care about this. "If you don’t see a pattern, don’t feel bad; neither do I", Prof. John Robertson, Solving the generalized Pell equation xx - Dyy=N, 2004.
The table below shows that x and y can be expressed in very simple polynomial in n for D from 2 to 18, with the exception of D=13. D is either nn for which there is no solution or nn-2,nn-1, nn+1 or nn+2. D=12 is a special case with D=3*4 so that x=(3+4) and y = 2 or more generally: x=(n+(n+1)), D=n*(n+1) and y=2.
D(n) X(D(n))
nn-2 nn-1
nn-1 n
nn no solution
nn+1 2nn+1
n+2 nn+1
These rules take us past D=4, 9 and 16 up to D=18.
The remaining puzzle D=13 belongs to a series where D is a prime and D=nn-3, with D=61 and 97 in the same family, all with large values of x.
Another family of primes with large values of x is given by D=n(n+1)(n+2)+1 when D is a prime and with very modest values for D=n(n+1)(n+2). Observe that D=61 also belongs to this category 61=3*4*5+1 (and prime).
A math professor I asked about this (same John Robertson as above) claimed, without demonstration, that there are cases where D=n(n+1)(n+2)+1 yield lower solutions for x(D) than D=n(n+1)(n+2). I assume these would be for high numbers of n. For most primes D=n(n+1)(n+2)+1, x(D) is very high, and n=34 (D= 321) corresponds to x > 1E+300 (which I assume is the upper limit of the professor’s representation, he did all the calculations). He also falsified my theory that x(D) would be a positive function of D. It appears that x(D) for n=21 is lower than for n=20.
I still feel it is safe to say that for many primes D=n(n+1)(n+2)+1 x(D) is very high. D for n= 34 and the next 24 primes correspond to x>1E+300 for all but 5. D itself ranges from the more modest numbers 42841 to 1560781 (D=115*116*117+1).
Observe also that y(D)=1 when D is the product of 4 consecutive numbers, since n(n+1)(n+2)(n+3) +1 is always a square, D= (1 + n (3 + n))^2, and therefore
D= m*m -1, so that x=m and y=1 and the equation becomes mm –(mm-1)1*1=1 with m=(1 + n (3 + n)).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print