wu :: forums
« wu :: forums - Highway (to) 61 revisited »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 7:26pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Grimbal, SMQ, william wu, Icarus, Eigenray, towr, ThudnBlunder)
   Highway (to) 61 revisited
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Highway (to) 61 revisited  (Read 6573 times)
Mickey1
Junior Member
**





   


Gender: male
Posts: 116
Highway (to) 61 revisited  
« on: Jul 11th, 2012, 4:55pm »
Quote Quote Modify 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: male
Posts: 13730
Re: Highway (to) 61 revisited  
« Reply #1 on: Jul 11th, 2012, 10:51pm »
Quote Quote Modify 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: male
Posts: 116
Re: Highway (to) 61 revisited  
« Reply #2 on: Jul 11th, 2012, 11:58pm »
Quote Quote Modify Modify

Yes, at least that was the complaint from the system. I will try to zip it.
IP Logged
Mickey1
Junior Member
**





   


Gender: male
Posts: 116
Re: Highway (to) 61 revisited  
« Reply #3 on: Jul 12th, 2012, 12:18am »
Quote Quote Modify 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: male
Posts: 116
Re: Highway (to) 61 revisited   61.jpg
« Reply #4 on: Jul 12th, 2012, 12:23am »
Quote Quote Modify 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: male
Posts: 116
Re: Highway (to) 61 revisited  
« Reply #5 on: Jul 12th, 2012, 3:42am »
Quote Quote Modify 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: male
Posts: 116
Re: Highway (to) 61 revisited  
« Reply #6 on: Jul 17th, 2012, 2:57pm »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: Highway (to) 61 revisited  
« Reply #7 on: Jul 18th, 2012, 5:12am »
Quote Quote Modify 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: male
Posts: 116
Re: Highway (to) 61 revisited  
« Reply #8 on: Jul 18th, 2012, 7:23am »
Quote Quote Modify 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: male
Posts: 116
Re: Highway (to) 61 revisited  
« Reply #9 on: Jul 20th, 2012, 2:37am »
Quote Quote Modify 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: male
Posts: 116
Re: Highway (to) 61 revisited  
« Reply #10 on: Oct 3rd, 2012, 11:44am »
Quote Quote Modify 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 Quote Modify Modify

Awesome, I love seeing some elementary number theory though I cannot do it.
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: Highway (to) 61 revisited  
« Reply #12 on: Oct 4th, 2012, 4:41am »
Quote Quote Modify 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: male
Posts: 116
Re: Highway (to) 61 revisited   n_n1_n2.pdf
« Reply #13 on: Oct 28th, 2012, 3:31pm »
Quote Quote Modify Modify

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: male
Posts: 116
Re: Highway (to) 61 revisited  
« Reply #14 on: Oct 28th, 2012, 4:00pm »
Quote Quote Modify 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: male
Posts: 116
Re: Highway (to) 61 revisited  
« Reply #15 on: Jan 9th, 2013, 7:10pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board