From: Spamless@nil.nil Subject: Re: Q: When is sqrt(x*(x+1)/2) an integer? Newsgroups: sci.math Date: 8 Jun 98 13:38:20 GMT In sci.math singlis@my-dejanews.com wrote: > Any ideas about how I determine when y=sqrt(x*(x+1)/2) is an integer? > Computationally I get: > (1,1) (6,8) (35,49) (204 288)... Assuming you want x and y to be positive integers, you want x(x+1)/2 (the generic triangular number) to be y^2 (a generic square number). So, when are triangular numbers square? Square numbers that are triangular ---------------------------------- Pell's Equation: (not solved by Pell, but he wrote a text describing it) ------------------------------------------------------------------------ x^2 - D*y^2 = 1 We want positive integral solutions to this where D is square free (that is, cannot be divided by 4, 9, 16, 25, etc.) The trick to solving this is to note that there is a SMALLEST solution (if one has two solutions, (x1, y1) and (x2, y2) and x1V THEN REM check PRINT "ERROR": END ELSE REM print m, n and the number which is the m'th triangular, REM n'th square number. PRINT USING "#### #### #########";M,N,U ENDIF A = 3*M + 4*N + 1: B = 3*N + 2*M + 1: M=A: N=B LOOP END -- End of QBasic Programme -- However, to handle more digits than QBasic can handle, one may want to use the UBasic programme (UBasic can handle numbers of thousands of digits) below: -- UBasic Programme -- 10 M=1:N=1 20 *More 30 V=N*N:U=M*(M+1)/2 40 print "m=";M:print "n=";N:print "val=";V 50 if U=V then print "values check out" 60 A=3*M+4*N+1:B=3*N+2*M+1:M=A:N=B 70 print 80 if U<10^73 then *More -- End of UBasic Programme -- Results ------- QBasic programme (numbers rather limited in size): m n Number ---- ---- -------- 1 1 1 8 6 36 49 35 1225 288 204 41616 1681 1189 1413721 9800 6930 48024900 etc. etc. etc. The numbers at the right are both triangular and square. They are m(m+1)/2 (the m'th triangular number: m in the first column) and n^2 (the n'th square number: n in the second column). -=-=- UBasic programme (I have removed the "values check out" lines): The following lists m and n one one line and then the common value of m(m+1)/2 and n^2 (the number which is the m'th triangular and n'th square number). m= 1 n= 1 val= 1 m= 8 n= 6 val= 36 m= 49 n= 35 val= 1225 m= 288 n= 204 val= 41616 m= 1681 n= 1189 val= 1413721 m= 9800 n= 6930 val= 48024900 m= 57121 n= 40391 val= 1631432881 m= 332928 n= 235416 val= 55420693056 m= 1940449 n= 1372105 val= 1882672131025 m= 11309768 n= 7997214 val= 63955431761796 m= 65918161 n= 46611179 val= 2172602007770041 m= 384199200 n= 271669860 val= 73804512832419600 m= 2239277041 n= 1583407981 val= 2507180834294496361 m= 13051463048 n= 9228778026 val= 85170343853180456676 m= 76069501249 n= 53789260175 val= 2893284510173841030625 m= 443365544448 n= 313506783024 val= 98286503002057414584576 m= 2584123765441 n= 1827251437969 val= 3338847817559778254844961 m= 15061377048200 n= 10650001844790 val= 113422539294030403250144100 m= 87784138523761 n= 62072759630771 val= 3853027488179473932250054441 m= 511643454094368 n= 361786555939836 val= 130889512058808083293251706896 m= 2982076586042449 n= 2108646576008245 val= 4446390382511295358038307980025 m= 17380816062160328 n= 12290092900109634 val= 151046383493325234090009219613956 m= 101302819786919521 n= 71631910824649559 val= 5131130648390546663702275158894481 m= 590436102659356800 n= 417501372047787720 val= 174307395661785261331787346182798400 m= 3441313796169221281 n= 2433376321462076761 val= 5921320321852308338617067495056251121 m= 20057446674355970888 n= 14182756556724672846 val= 201150583547316698251648507485729739716 m= 116903366249966604049 n= 82663163018885960315 val= 6833198520286915432217432187019754899225 m= 681362750825443653408 n= 481796221556591089044 val= 232127599106207807997141045851185936833936 m= 3971273138702695316401 n= 2808114166320660573949 val= 7885505171090778556470578126753302097454601 m= 23146276081390728245000 n= 16366888776367372354650 val= 267875048217980263112002515263761085376622500 m= 134906383349641674153601 n= 95393218491883573553951 val= 9099866134240238167251614940841123600707710401 m= 786292024016459316676608 n= 555992422174934068969056 val= 309127573515950117423442905473334441338685531136 m= 4582845760749114225906049 n= 3240561314557720840260385 val= 10501237633408063754229807171152529881914600348225 m= 26710782540478226038759688 n= 18887375465171390972593254 val= 356732951962358217526390000913712681543757726308516 m= 155681849482120242006652081 n= 110083691476470624995299139 val= 12118419129086771332143030223895078642605848094141321 m= 907380314352243226001152800 n= 641614773393652358999201580 val= 411669517436987867075336637611518961167055077474496400 m= 5288600036631339114000264721 n= 3739604948885443528999910341 val= 13984645173728500709229302648567749601037266786038736281 m= 30824219905435791458000435528 n= 21796014919919008815000260466 val= 475066266389332036246720953413691967474100015647842537156 m= 179656719395983409634002348449 n= 127036484570628609361001652455 val= 16138268412063560731679283113416959144518363265240607527025 m= 1047116096470464666346013655168 n= 740422892503852647351009654264 val= 548226059743771732840848904902762918946150251002532813381696 m= 6103039859426804588442079582561 n= 4315500870452487274745056273129 val= 18623547762876175355857183483580522285024590170820875047450641 m= 35571123060090362864306463840200 n= 25152582330211071001119327984510 val= 632652397878046190366303389536834994771889915556907218799940100 m= 207323698501115372597396703458641 n= 146599993110813938731970911633931 val= 21491557980090694297098458060768809299959232538764024564150512761 m= 1208371067946601872720073756911648 n= 854447376334672561390706141819076 val= 730080318925205559910981270676602681203842016402419927962317493776 --------------------------------------------------------------------------- The end ============================================================================== From: Spamless@nil.nil Subject: Re: Q: When is sqrt(x*(x+1)/2) an integer? Newsgroups: sci.math Date: 11 Jun 98 01:03:33 GMT (I obviously have MUCH, too MUCH time on my hands!) Pell's Equation: (not solved by Pell, but he wrote a text describing it) ------------------------------------------------------------------------ x^2 - D*y^2 = 1 We want positive integral solutions to this where D is a positive integer which is not a perfect square. The trick to solving this is to note that there is a SMALLEST solution (if one has two solutions, (x1, y1) and (x2, y2) and x10) This field has an isomorphism given by conjugation, say CONJ with: CONJ(x+y*SQRT(D)) := x-y*SQRT(D) (and CONJ(u+v)=CONJ(u)+CONJ(v), CONJ(u*v)=CONJ(u)*CONJ(v) where u,v are of the form rational+rational*SQRT(D)) In particular, CONJ([x+y*SQRT(D)]^j)=[x-y*SQRT(D)]^j. -=-=- Second, a few facts about rational approximations ------------------------------------------------- Suppose t is a (positive) real number. Consider approximating this by a rational number with denominator n (a positive integer), say by taking m as the smallest (positive) integer with m>=nt (so [m/n]>=t>[(m-1)/n]). In general, the error between t and the rational approximation m/n is between 0 and 1/n ([1/n]>([m/n]-t)>=0). Not too good. Now, pick some positive integer N and let n range from N to 2N (N+1 values -- N+0, N+1, N+2,..., N+N). For each n in this range, we pick m (so m/n is an approximation to t with denominator n and m/n>=t). Consider the error, ([m/n]-t). It is non-negative and smaller than 1/n, so it is either in the interval between: 0/(N*n) and 1/(N*n) or 1/(N*n) and 2/(N*n) or 2/(N*n) and 3/(N*n) or ... (N-1)/(N*n) and N/(N*n)=1/n There are N such intervals, but we have N+1 possible values for n (from N to 2N), so by the Pigeon Hole principle, some one of those intervals must contain two of the terms [m/n]-t. Call two of the m,n values which are in one interval m,n and m',n'. Consider: m-nt is between 0 and 1 as is m'-n't, but they are BOTH in the same interval from (K-1)/N to K/N. Consider the difference (m-m')-(n-n')t. It is the difference between these two values, but they are no further apart than 1/N. Let m"=m-m', n"=n-n'. We have: |m"-n"*t|<=1/N or |(m"/n")-t|<=1/(Nn") But how big can n" be? It is the difference between two numbers between N and 2N so its largest value is 2N-N=N (n"<=N) and so we have: Given a real number t and positive integer N, there exists integers m",n" with |m"/n"-t|<=1/(Nn")<=1/(n")^2. Note that now the error between m"/n" and t is no longer on the order of 1/n" but is on the order of 1/(n")^2 (heck... let me drop the " and call the numbers m,n with |m/n-t|<=1/(Nn)<=1/n^2). This is not true for arbitrary denominators (n) (for which the best error is about 1/n), but SOME denominators always give a better approximation. Now, suppose t is IRRATIONAL. Pick an |m/n-t|<=1/n^2. Now pick N with 1/N<|m/n-t| (we can do this as m/n-t is non zero since t is irrational!). Now pick another m',n' with |m'/n'-t|<=1/(Nn')<=1/(n')^2. Can m'/n' be the same as m/n? No, because it is closer to t than is m/n (|m'/n'-t|<=(1/Nn')<1/N<|m/n-t|). Now pick N' with 1/N'<|m'/n'-t| and m",n" with |m"/n"-t|<=1/(N'n")<=1/(n")^2. m"/n" is another, different, rational number. In this way we can get an infinite sequence of rational numbers, m_j/n_j with |m_j/n_j-t|<=1/(n_j)^2 and from this we can choose a subsequence (if necessary) with n_j increasing. [NOTE: if t is rational, say t=p/q, UNLESS m/n EQUALS t, |m/n-p/q|=|(mq-np)/(nq)|>=(1/q)/n so that in general we can not have different rational numbers approximating a RATIONAL number faster than 1/denominator... of course we CAN take, for example, in approximating 1/2, the approximations 2/4, 10/20, 1000/2000, etc. which have error of zero in the approximation, but these are not different rational numbers] -=-=- Now consider the above applied to SQRT(D) ----------------------------------------- If D is a positive integer which is not a square, SQRT(D) is irrational, so we have an infinite sequence of rational numbers m_j/n_j with n_j increasing without bound and |(m/n)-SQRT(D)|<=1/n^2 for every one of the rational numbers m/n in the sequence. Consider (m/n)+SQRT(D)<=|(m/n)-SQRT(D)|+2*SQRT(D)<=2*SQRT(D)+1/n^2 Thus, |m/n-SQRT(D)|*|m/n+SQRT(D)|<=(1/n^2)(2*SQRT(D)+1/n^2) or, since n>=1, and multiplying out: |(m/n)^2-D|<=(2*SQRT(D)+1)/n^2 or (multiply by n^2): |m^2-D*n^2| <= (2*SQRT(D)+1) So, we now have an infinite set of number pairs, (m,n) (positive integers) with |m^2-D*n^2|<=(2*SQRT(D)+1)=some_finite_number. Well, if we have infinitely many pairs, and for them all the values of |m^2-D*n^2| are in some finite set, there is some infinite subset (some subsequence of the m_j,n_j) where all the values of m^2-D*n^2 are the same, and call this value k. -=-=- We now have an infinite sequence of pairs (m,n) (positive integers) with n increasing without bound and m^2-D*n^2=k (some number k). For these pairs, write down the remainders of m and n modulo k. These may be, for example: (1,3), (3,2), ... (first pair has m=1 mod k and n=3 mod k, etc.). There are finitely many pairs (k^2 different pairs) so there is ANOTHER subsequence of this sequence of (m,n)'s (infinitely many terms) all of which have the SAME values for the remainders of m and n modulo k. Thus: There exists an infinite sequence of pairs of positive integers, (m,n) with: m^2-D*n^2 = k and m=m' mod k n=n' mod k if (m,n) and (m',n') are two pairs in this set Let (a,b) be any pair in this set. For any other (of the infinitely many) pairs (m,n) consider: (m+n*SQRT(D))/(a+b*SQRT(D)) = (ma-nbD)/k + [(an-mb)/k]*SQRT(D) (again, in rationalizing the denominator, a^2-D*b^2=k] But, m=a mod k and n=b mod k, so ma-nbD=a*a-b*b*D=a^2-D*b^2=k=0 mod k an-mb =a*b-a*b = 0 mod k Thus, both ma-nbD and an-bm are divisible by k, so: i:=(ma-nbD)/k and j:=(an-mb)/k are *integers* and: (m+n*SQRT(D))/(a+b*SQRT(D)) = i+j*SQRT(D) Now, multiply each side by its conjugate, on the left by: (m-n*SQRT(D))/(a-b*SQRT(D)) on the right by: i-j*SQRT(D) to get: (m^2-n^2*D)/(a^2-b^2*D) = i^2-j^2*D but the left hand side is just k/k=1. If i or j is not positive... well, take I=|i| and J=|j| to get: -=-=- --------------------------------------------------------- There are infinitely many positive integers I,J with: I^2 - J^2*D = 1 if D is a positive integer which is not a perfect square. --------------------------------------------------------- -=-=- At this point we know that there is always SOME (in fact, infinitely many) solution to the Pell equation. ALL the above work (with the Pigeon Hole principle; taking infinite subsets of infinite subsets, etc.) was done just to show that there IS some solution to I^2-D*J^2=1 (J>0). Once we have ONE such solution, say, (I,J), then M+N*SQRT(D)=(I+J*SQRT(D))^j is also a solution for any positive integer j -- just multiply each side by its conjugate to see this -- so one solution will show that there are infinitely many -- but we have to get one solution to start -- once we have that, we can proceed to find the general solution... but all that work above is JUST to show that there is SOME solution to Pell's equation. For positive integral solutions I,J with I^2-J^2*D=1, let me order them by saying one solution (I,J) is larger than another (I',J') if I>I' (this is equivalent to J>J' and equivalent to I+J*SQRT(D)>I'+J'*SQRT(D)) (for integral, not necessarily positive, solutions i^2-j^2*D=1, we can order the solutions by |i|+|j|*SQRT(D)) (since I^2-J^2*D=1=I'^2-J'^2*D, we have: I^2-I'^2 = D*(J^2-J'^2) so I is larger than I' just when J is larger than J' for non-negative I,I',J,J'). Let me use (a,b) for the SMALLEST POSITIVE solution to a^2-b^2*D=1 (in particular, it is the solution with the smallest POSITIVE value for b). Finally note that the positive solutions to m^2-D*n^2=1 (m,n both positive) are well ordered under the ordering we have chosen (any non-empty subset of the positive solutions contains a SMALLEST element since we just take one with the smallest value for the positive integer, n, and the positive integers do satisfy this well ordering property) (this is also clearly true for the solutions to m^2-D*n^2=r for arbitrary r, provided that such equation does have positive solutions). Now we are almost ready to get the formula for the general solution (the trick is to show that if (M,N) is a positive solution LARGER than the smallest positive solution, then m+n*SQRT(D)=(M+N*SQRT(D))/(a+b*SQRT(D)) is a positive solution smaller than (M,N)). -=-=-=-=-=-=-=-=-=-=-=-=- However, let's be more general and try to find the general solution to: m^2 - D*n^2 = r (m,n positive integers) First, note that there may be NO solutions! (e.g. consider m^2-3*n^2=2 where a solution would imply that m^2=2 mod 3, but this is impossible). This is why we spent the time to show that for r=1 there ARE solutions. First, let (a,b) be the smallest positive (a,b positive integers) solution to a^2-D*b^2=1. Suppose there IS some solution to m^2-D*n^2=r (m,n positive integers) (some fixed r). IF so there are infinitely many ([a+b*SQRT(D)]^j*[m+n*SQRT(D)]=M+N*SQRT(D) gives another solution, M,N for each non-negative integral j). Order the solutions to m^2-D*n^2=r (m,n positive integers) (if any) by the size of m+n*SQRT(D) (equivalently, just by m or n). Say a solution is LARGE if: SQRT(D+r/n^2) * SQRT(D+1/b^2) > D and SQRT(D+1/b^2) - SQRT(D+r/n^2) > 0 and SMALL otherwise. (for sufficiently large n, depending upon r, D and b, these equations are true, so there are but finitely many SMALL solutions) (note: For r>0, the first equation is automatically true and the second is simply that n^2>r*b^2. For r=1, large solutions to m^2-D*n^2=1 are simply ones with n>b, that is solutions larger than the smallest solution and there is just one SMALL solution, namely the smallest solution.) -=-=- CLAIM: IF m^2-D*n^2=r has any solutions and IF (m,n) is a large solution to m^2-D*n^2=r, then M+N*SQRT(D)=[m+n*SQRT(D)]/[a+b*SQRT(D)] is a smaller positive solution. Pf: As 1/[a+b*SQRT(D)]=a-b*SQRT(D) (since a^2-b^2*D=1), M,N are integers. We can write them as: M=ma-bnD=bn([m/n][a/b]-D) N=an-bm=bn(a/b - m/n) or: M=bn(SQRT(D+r/n^2)*SQRT(D+1/b^2)-D) N=bn(SQRT(D+1/b^2) - SQRT(D+r/n^2)) which are positive if (m,n) is a LARGE solution to m^2-D*n^2=r. Further, as a+b*SQRT(D)>1, M+N*SQRT(D) is smaller than m+n*SQRT(D) ((M,N) is a smaller solution than (m,n)). -=-=- Now, suppose m^2-D*n^2=r has some solutions. Then, there are finitely many SMALL solutions (just one for r=1, namely the SMALLEST solution, as we have seen) (since if n is sufficiently large, depending upon r and b, a term involved with the smallest solution to a^2-b^2*D=1, the solution is LARGE) THEN: -=-=-=-=-=- If M,N is any positive solution to M^2-D*N^2=r, there is a SMALL positive solution m^2-D*n^2=r and a non-negative integer j with M+N*SQRT(D)=(m+n*SQRT(D))*(a+b*SQRT(D))^j. Pf: By well ordering, if there is some solution to M^2-N^2*D=r which canNOT be written that way, then there is a smallest such solution. Call it (M,N). 1: (M,N) cannot itself be SMALL (for them with j=0, (M,N) would be expressible as claimed) or we would have a contradiction. 2: As (M,N) is not small, m+n*SQRT(D)=(M+N*SQRT(D))/(a+b*SQRT(D)) is a smaller positive solution. 2a: If (m,n) is small, then (M,N) can be expressed as claimed with j=1 (again a contradiction to (M,N) being the smallest positive solution that canNOT be so expressed). 2b: If (m,n) is large, then as (M,N) is the SMALLEST solution that canNOT be expressed as claimed and (m,n) is a smaller positive solution, there exists a SMALL solution, say, s^2-D*t^2=r and non-negative integer j with m+n*SQRT(D)=(s+t*SQRT(D))*(a+b*SQRT(D))^j. But then multiply by a+b*SQRT(D) to get: M+N*SQRT(D)=(s+t*SQRT(D))*(a+b*SQRT(D))^(j+1), again a contradiction to (M,N) not being able to be so expressed. Those are all the possibilities, so we get a contradiction to the existence of a smallest (and, by well ordering, any) positive solution to m^2-D*n^2=r which cannot be expressed as a small solution times a power of (a+b*SQRT(D)). -=-=-=-=-=- Thus... all solutions to m^2-D*n^2=r can be gotten as: FIRST find the smallest positive solution to a^2-D*b^2=1. Then find all the SMALL solutions to m^2-D*n^2=r. Take, for each small solution, all the solutions M+N*SQRT(D)=(m+n*SQRT(D))*(a+b*SQRT(D))^j (where (m,n) ranges through the small solutions and j is a non-negative integer). Those give all the solutions. NOTE, again, for general r there may be no solutions and for r=1 there IS a solution (which we proved after a lot of work with those infinite subsets of infinite subsets!). For r=1, the set of SMALL solutions is just {(a,b)} so -=-=-=-=-=- The general solution to m^2-D*n^2=1 is (a+b*SQRT(D))*(a+b*SQRT(D))^j where j>=0, that is, the general solution is: (a+b*SQRT(D))^j for j>=1 where (a,b) is the SMALLEST solution. -=-=-=-=-=- Well, that proves the formula for the general (in terms of the smallest) solution to the Pell equation. How to get the smallest solution to m^2-D*n^2=1? And for general r, how to find the SMALL solutions (if any) to m^2-D*n^2=r? For the Pell (r=1), we have (m/n)^2-D=1/n^2 (for the generalized Pell, we have (m/n)^2-D=r/n^2). For r=1, this means m/n is a DAMN GOOD approximation to SQRT(D). In fact, so good that it must be an approximant of the continued fraction expansion to SQRT(D). I will not prove that... but continued fraction expansions are the "best" rational approximations and, in fact, if an approximation is "good enough" (and for SQRT(D), a Pell approximation "is" this good) it *must* be an approximant of the continued fraction. This also holds for small r. However, if r is NOT small enough (so one cannot immediately claim that one only has to look among the continued fraction approximants to find possible solutions to m^2-D*n^2=r) finding solutions is more difficult. For the Pell equation, however (r=1), life is easy. One simply expands SQRT(D) in a continued fraction... right before the period (or twice the period if there is a solution to x^2-D*y^2=-1) the approximant will give a solution to m^2-D*n^2=1. This will be the smallest solution. From that, we have the general solution. In the case of Square Numbers that are Triangular, however, we have the Pell equation with D=8. In this case, one can find the smallest solution (a,b) to a^2-8*b^2=1 by inspection (a=3,b=1) and the general solution is then found with no more work. ============================================================================== From: Spamelss@nil.nil Subject: Re: Q: When is sqrt(x*(x+1)/2) an integer? Newsgroups: sci.math Date: 12 Jun 98 13:05:38 GMT In sci.math Spamless@nil.nil wrote: > Now, pick some positive integer N and let n range from N to 2N (N+1 > values -- N+0, N+1, N+2,..., N+N). For each n in this range, we pick m > (so m/n is an approximation to t with denominator n and m/n>=t). > Consider the error, ([m/n]-t). It is non-negative and smaller than 1/n, > so it is either in the interval between: > 0/(N*n) and 1/(N*n) or > 1/(N*n) and 2/(N*n) or > 2/(N*n) and 3/(N*n) or ... > (N-1)/(N*n) and N/(N*n)=1/n > There are N such intervals, but we have N+1 possible values for n (from > N to 2N), so by the Pigeon Hole principle, some one of those intervals > must contain two of the terms [m/n]-t. Call two of the m,n values which > are in one interval m,n and m',n'. Ooops... these intervals change as n changes. Rewrite as: m-nt is between 0 and 1 and so must be in one of the intervals: 0/N to 1/N 1/N to 2/N etc.