Author 
Topic: Highway (to) 61 revisited (Read 6112 times) 

Mickey1
Junior Member
Gender:
Posts: 116


Highway (to) 61 revisited
« on: Jul 11^{th}, 2012, 4:55pm » 
Quote Modify

The following is a tour of classical number theory, visiting Fermat’s sumoftwosquares theorem , Pell’s equation, and Mersenne’s (mostly nonprime) numbers , but it ends with an attempt to calculate x and y for difficult combinations such as x261y2=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 sumoftwosquares 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(n2y2y2+1)= ny+sqrt((n21)y2+1). An integer solution must require that (n21)y2+1 is a square of an integer which I call z2. We have therefore z2(n21)y2=1 i.e. a case of Pell’s equation using the constant d= n21 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 n21=(n+1)(n1), except for n=2, yielding Pell’s constant d=3. My calculations consists simply of choosing n; then I calculate n21, and get the first Pell equation solution, with z=n and y=1. The nest solution I found by setting y=2n and z=2n21, which works for my special case d=n21. 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 nonprime Mersenne numbers . The noprimes 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 (2n21,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=n1. The 2xy+1 still comes back as integers since the sqrt appears twice in the formula for n. I believe the second solution (2n21,2n) is still OK. In my iterations I get alternating integers and nonintegers 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 11^{th}, 2012, 5:05pm by Mickey1 » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13640


Re: Highway (to) 61 revisited
« Reply #1 on: Jul 11^{th}, 2012, 10:51pm » 
Quote Modify

on Jul 11^{th}, 2012, 4:55pm, Mickey1 wrote:Tried to attach the calculations in excel but failed. 
 If it's because of the filetype, 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 11^{th}, 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 12^{th}, 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 12^{th}, 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 12^{th}, 2012, 2:47pm by Mickey1 » 
IP Logged 



Mickey1
Junior Member
Gender:
Posts: 116


Re: Highway (to) 61 revisited
« Reply #5 on: Jul 12^{th}, 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 17^{th}, 2012, 2:57pm » 
Quote Modify

A new approach to x261y2=1 (I use again x2 for x*x). I note that Pell’s equation x2Dy2=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=n21 is very simple [x=D, y=1]. The solution below that, for D= n22 ia also simple [x=n1,y=n] ( (n21)2(n22)n2 = n42n2+1 –(n42n2)=1. There is a similar pattern for D above n2 but I am concentrating on solutions for D below n2, and in particular n23, since these are the ones that contain D=8*83=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*103=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=n23. 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 n23, 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 x2397y2=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 [x2Dy2=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: 2818


Re: Highway (to) 61 revisited
« Reply #7 on: Jul 18^{th}, 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 18^{th}, 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 20^{th}, 2012, 2:37am » 
Quote Modify

I didn't have to work long on this problem to find that xxDyy=1 implies that xx1=Dyy and therefore (x+1)(x1)=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 x1 at least for primes D=nn3 (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 3^{rd}, 2012, 11:44am » 
Quote Modify

The following proof was kindly provided to me from prof Hendrik from the Netherlands. It proves that (assuming xxdyy=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 3^{rd}, 2012, 1:49pm » 
Quote Modify

Awesome, I love seeing some elementary number theory though I cannot do it.


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2818


Re: Highway (to) 61 revisited
« Reply #12 on: Oct 4^{th}, 2012, 4:41am » 
Quote Modify

on Oct 3^{rd}, 2012, 11:44am, Mickey1 wrote:The following proof was kindly provided to me from prof Hendrik from the Netherlands. It proves that (assuming xxdyy=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 xxdyy=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 xxDyy=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(D1) 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 nonprimes 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(D1) 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 28^{th}, 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 9^{th}, 2013, 7:10pm » 
Quote Modify

Let me summarize some of my notes on Pell’s equation xxDyy=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 nn2,nn1, 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)) nn2 nn1 nn1 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=nn3, 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 –(mm1)1*1=1 with m=(1 + n (3 + n)).


IP Logged 



