wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Highway (to) 61 revisited 
        
(Message started by: Mickey1 on Jul 11^th, 2012, 4:55pm)

Title: Highway (to) 61 revisited
Post by Mickey1 on Jul 11^th, 2012, 4:55pm

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.

Title: Re: Highway (to) 61 revisited
Post by towr on Jul 11^th, 2012, 10:51pm

on 07/11/12 at 16:55:23, 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.

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Jul 11^th, 2012, 11:58pm

Yes, at least that was the complaint from the system. I will try to zip it.

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Jul 12^th, 2012, 12:18am

I tried again - this time the answer was "could not uplode file 61.zip" so something is not working for me.

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Jul 12^th, 2012, 12:23am

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 .

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Jul 12^th, 2012, 3:42am

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.

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Jul 17^th, 2012, 2:57pm

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

Title: Re: Highway (to) 61 revisited
Post by rmsgrey on Jul 18^th, 2012, 5:12am

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?"

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Jul 18^th, 2012, 7:23am

Very good

I will do that if I get any comments. So far it is mostly me talking to myself.

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Jul 20^th, 2012, 2:37am

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.

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Oct 3^rd, 2012, 11:44am

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

Title: Re: Highway (to) 61 revisited
Post by peoplepower on Oct 3^rd, 2012, 1:49pm

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

Title: Re: Highway (to) 61 revisited
Post by rmsgrey on Oct 4^th, 2012, 4:41am

on 10/03/12 at 11:44:19, Mickey1 wrote:

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.

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Oct 28^th, 2012, 3:31pm

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

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Oct 28^th, 2012, 4:00pm

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

Title: Re: Highway (to) 61 revisited
Post by Mickey1 on Jan 9^th, 2013, 7:10pm

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