Search This Blog

Saturday 24 May 2014

Triangular numbers

Background

When I can't sleep, I do calculations in my head: always have done, always will.  I might try to get the cube root of 17, or the successive powers of three, or other number patterns, like sets of three primes in arithmetic progression.

This story has its beginnings with a boring plane trip when I was playing with the triangular numbers, 1, 3, 6, 10, 15, 21 . . . which are generated by 1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5, 1+2+3+4+5+6...

These are called triangular numbers because you can make them up into neat triangles like this:
                        *
              *        **                                                  
      *      **      ***
*    **    ***    ****
1    3     6         10  and so on                                                                                                                     
There are several really cute things about these numbers that were known, way back in the days of Diophantus, an Ancient Greek who liked playing with really big numbers. Every perfect square is the sum of two consecutive triangular numbers, as you can see if you plot the square numbers as asterisks or dots like the diagram above. With a bit of effort, you can use a similar method to prove that every odd perfect square is of the form 8T + 1, where T is a triangular number.

The original problem

It occurred to me that the 8th term in the series of the numbers in the series was 36, which is a perfect square, and then I wondered if there are any other numbers in the series which are perfect squares, and if so, how you could generate them. It was late at night, I mistakenly calculated the value of T(15) as 121 (it is actually 120), and so it looked worth trying, but I went to sleep before I found any more.

Next day, I realised my error, and since I suspected that there would not be many numbers fitting the pattern, I created a spreadsheet that would generate them, knowing that term number T in the series is given by

T(n) = n * (n + 1) / 2, which means that term 11, for example, is 11 * 12/2 = 66

The Spreadsheet


Diophantus would have killed for even a simple spreadsheet program. Here is my spreadsheet solution to test for numbers that fit:

A1 is the starting number of the terms to be explored (in the first run, that will be 1).

A2 =A1 + 1

B1 =(A1*A1+A1)/2

C1 =IF(SQRT(B1)=INT(SQRT(B1)),1,"")

B2 and C2 are filled down from B1 and C1, which has similar formulas. Column A is copied down from A2.

I then fill down columns A, B and C to row 50000, and insert the value 1 in cell A1 to test the first fifty thousand terms. To get the next 50,000 terms, I type 50001 in cell A1, and so one.

A "hit" is indicated by the value 1 appearing in column C in the same line as the hit.

I found it a nuisance searching for the hits, so I created 20 cells in column D to help me find them:

D1 =sum(c1:c2500)

D2 =sum(c2501:c5000)

and so on to D20 -- this told me roughly where the hits were.

Then to eyeball for ANY hits in a block (they get fewer and fewer) I created E1 =sum(d1:d20), then all I had to do was insert my starting values 50001, 100001, 150001 etc in A1 and trawl through the terms, zeroing in on a specific 2500 rows to search for the hit when one was indicated in cell E1 and column D. Once I learned to calculate the approximate value, I could jump almost to the correct row, but that calculation is jumping ahead of the story.

The Results

What I had now was a curious pattern, where the terms that were perfect squares went like this:

The Mysterious Constant

About this time, I started to see some patterns. I found that these term numbers appear to be in a geometric progression with the ratios of two successive term numbers converging. Leaving out the first couple of terms of the converging series, I found these ratios between the key numbers:

5.87755102040816, 5.83680555555556, 5.82986317668055, 5.82867346938776, 5.82846938954150, 5.82843437620146, 5.82842836889813, 5.82842733820888, 5.82842716137060, 5.82842713102994, 5.82842712582431 and 5.82842712536459

So I wrote to an email list with  a few number-players in it, drawing attention to the curious patterns that were emerging, and asking for help. I ended by noting that the ratios of the square roots of the successive terms that are perfect squares rapidly converge and stabilise on the value 5.828427124746190, which I thought might give a hint about the value being converged upon above!

It was not long after that Ben Morphett told me that my mystery number was explicable:

"Your number 5.828427124746190 is equal to (3 + 2.sqrt(2)), and is the solution to the quadratic x^2 - 6x + 1 = 0"

I still don't know why, but I suspect that this relationship is just a coincidence, because somebody else managed to explain a lot of it for me in a different way — but that may just prove that I haven't looked hard enough.

But before we get to that, though, I commented to the list that the square roots of the perfect squares I had generated appeared relatively uninteresting, but Bruce Harris saw otherwise. My factorisation missed the point, he suggested:

" . . . if instead you factorise them into just two factors, allowing the factors themselves to be composite numbers, an obvious pattern emerges:

1 = 1 * 1

6 = 2 * 3

35 = 5 * 7

204 = 12 * 17

1189 = 29 * 41

6930 = 70 * 99

In each line, the first of the two factors is the sum of the two factors in the previous line, and the second is this number plus the first of those two factors again. Thus in the fourth line, 29 = 17 + 12, 41 = 29 + 12; in the fifth line, 70 = 41 + 29, 99 = 70 + 29."

He is right in this. Here is a table which extends this — the rest you can do yourself.



So what is the story with that strange factor? Tony Morton explained it to us in full, but I will reveal less than all of his solution, to leave you room to do some discovering yourself. Before I go to that, a few points:

Some hints


A famous mathematician called Gauss once was given, as a young boy, the task of summing the numbers from 1 to 100. He realised that if he added the first and the last terms in the sum, he got a total of 101, and the same if he added the second and second-last, or the third and the third-last: in all, there would be 100/2 instances of 101, making the final result he needed 5050. In fact he had multiplied (n+1) by n/2. Remember that.

    288 may be 2*12*12, but it is also 2*9*16, while 9800 can be 2*70*70 OR 2*49*100. Remember that.

    Every triangular number can be expressed either in the form n/2 * (n+1) OR n * (n+1)/2. Remember that.

    Geometrical proofs are possible for many problems with triangular numbers. Remember that.

You are now equipped to construct a proof which explains why the patterns arise, but you may not be able to explain that factor of 5.828427124746190 from this. Then again, maybe I have missed something :-)

The Morton Solution


So here is part of Tony Morton's solution, enough to get you thinking, and which does explain that factor. I have changed the notation to make it consistent with what has already appeared here.

If we want to know the nth triangular number - the sum of the numbers 1 through n — then we can use the formula T(n) = n (n + 1) / 2.

But suppose we are given a triangular number and want to know which one it is, to calculate n given T. The above formula can be written as n^2 + n - 2T = 0 which we can solve to get

n = (sqrt(8T + 1) - 1) / 2.

So for example, given T = 36, I can apply this formula to deduce that it is the 8th triangular number. So far so good. But if we look at this formula more closely we see it implies that if T is any triangular number, then 8T + 1 is always a perfect square. More explicitly, we can rearrange to get

8T + 1 = (2n + 1)^2.

Now, we are interested specifically in those triangular numbers T which are also perfect squares themselves. If we set T = m^2 for some (undetermined) integer m, then

8m^2 + 1 = (2n + 1)^2.

There is accordingly a one-to-one correspondence between the triangular numbers that are squares and pairs of positive integers (n,m) that satisfy the above equation. That is, given any square triangular number we can find n and m, and given n and m solving the equation we can find the corresponding square triangular number. So the problem of finding square triangular numbers is equivalent to that of solving the above equation.

Now, if n is a positive integer then so is 2n + 1, and if m is a positive integer then so is 2m. So let x = 2n + 1 and y = 2m to obtain

2y^2 + 1 = x^2

or x^2 - 2y^2 = 1.

Any solution in positive integers (x,y) to this equation gives us a solution in positive integers (n,m) to the earlier equation provided x is odd and y is even. It turns out, however, that every solution (x, y) satisfies this property. To see this, note that x^2 has to be odd because it is the sum of an even number (2y^2) and an odd number (1). Since x^2 is odd, x must be odd. But the square of any odd number leaves a remainder 1 when divided by 4, because (2k + 1)^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1. In mathematical jargon, x^2 is 'congruent to 1 mod 4'. If y were also odd, then y^2 would be congruent to 1 mod 4, and x^2 = 2y^2 + 1 would be congruent to 3 mod 4; a contradiction. Thus x is odd and y is even.

The equation x^2 - 2y^2 = 1 is known as Pell's equation. We thus see that every solution to Pell's equation gives a square triangular number, and conversely every square triangular number is obtained from a solution to Pell's equation. Given (x,y) we can calculate the triangular number T and its index n as

T = (y / 2)^2, n = (x - 1) / 2.

How to solve Pell's equation? Well, it's fairly easy to find the smallest solution: x = 3, y = 2. This corresponds to the trivial case n = 1, T = 1, which is obviously a square. So we'd like to find some larger solutions. It turns out that we can generate larger solutions from the smallest solution by the following trick. Write

1 = x^2 - 2y^2 = (x + y sqrt(2)) (x - y sqrt(2))

and raise this to an arbitrary power k to obtain

1^k = 1 = (x + y sqrt(2))^k (x - y sqrt(2))^k.

Now, given integers x and y, (x + y sqrt(2))^k can be written in the form A + B sqrt(2), where A and B are integers, and similarly (x - y sqrt(2))^k = A - B sqrt(2) by symmetry. We therefore have

1 = (A + B sqrt(2)) (A - B sqrt(2)) = A^2 - 2B^2.

So the numbers A and B, obtained from the kth power of x + y sqrt(2), provide a new solution to Pell's equation. Setting k = 2, 3, 4, 5 and so on through all the positive integers thus generates an infinite number of solutions to Pell's equation, hence an infinite number of square triangular numbers.

Thus, using the smallest solution x = 3, y = 2 we get (using Q to represent sqrt(2))

(3 + 2Q)^2 = 17 + 12Q x = 17, y = 12, n = 8, T = 36

(3 + 2Q)^3 = 99 + 70Q x = 99, y = 70, n = 49, T = 1225

(3 + 2Q)^4 = 577 + 408Q x = 577, y = 408, n = 288, T = 41616

and so on. It turns out that the powers of 3 + 2 sqrt(2) generate _all_ the solutions to Pell's equation in this way. Because, if we have any solution (A,B), we can always find C and D such that

A + B sqrt(2) = (3 + 2 sqrt(2)) (C + D sqrt(2))

and C, D are both positive, with C smaller than A. (Proof left to the interested reader.) If C is larger than 3 we can repeat this process with (C,D), and continue until we arrive at the smallest solution (3,2) (which we must do because C is getting smaller at every step). We thus obtain A + B sqrt(2) as a product of factors 3 + 2 sqrt(2).

***********************

We will leave Tony's proof at that point, but you are well on the way to the full explanation.

Possible enquiries


What is left for the honest enquirer, the interested reader, aside from testing the effects described, or seeking a new proof? Quite a lot, actually!

For a start, you have a method that may be new: using a spreadsheet to identify the interesting cases, and you have a couple of incomplete solutions.

Wondering what else might be explored led me to look at what David Wells had to say on pentagonal numbers in his "Penguin Dictionary of Curious and Interesting Numbers".

As I suspected, my discovery was not new to mathematics: on page 93, Wells notes that "Some numbers are simultaneously square and triangular . . . they are found by using a fact already mentioned . . . the Pell equation: 8x^2 + 1 = y^2" He goes on to give a general formula:

1/32 ((17 + 12*SQRT(2))^n + (17 - 12*SQRT(2))^n - 2)

and he adds that if T(n) is a perfect square, so is T(4n(n+1)) and that there are 40 palindromic numbers below 10^7: 1, 3, 6, 55, 66, 171, 595, 666 and 3003 among them. T(2662) = 3544453, and T(1111) and T(111*111) are also palindromes.

For every triangular number T(n), there is an infinite number of other triangular numbers T(m), such that T(n)*T(m) is a perfect square.

Also (T(n+1))^2 - (T(n))^2 = (n+1)^3, so the sum of the first n cubes is the square of the nth triangular number.

And (T(n))^2 = T(n) + T(n+1)*T(– 1)

And 2 * T(n) * T(– 1) = T(n^2-1)

The sum of the reciprocals of the triangular numbers converges on 2

The triangular numbers 16 and 21 have triangular numbers as both their difference and their sum, and there are others.

The triangular number 6 is said to be the only example under 660 digits whose square is also a triangular number (that sounds like a challenge to find the next one!)

And by the way, 1189 = (204 * 6) - 35

Pentagonal numbers


Pentagonal numbers are generated like this:


The numbers in the series are 1, 5, 12, 22, 35, 51, 70 . . . and there is a general formula which generates the whole set. What is it?

(Interestingly, the first factor in the general formula for triangular, square, pentagonal, hexagonal, heptagonal, octagonal numbers and so on is always 1/2n, and the second factor shows a fascinating pattern, which I leave you to discover when you work out the other formulae, but here are the first few numbers in a few of the polygonal series.)

Polygonal numbers
Polygonal numbers are generated by drawing similar patterns but with more sides, as seen in the figure above. If you draw them correctly, this is what you will get:




    Aside from the trivial cases of 0 and 1, there is another number under 500 which is both triangular and pentagonal, and there is another one under 50,000: are there any others? Can a computer be set the task of looking for these?

    There are three numbers under 2 billion which are at once triangular, pentagonal and hexagonal.

    There is at least one number under 1000 which is both square and heptagonal: are there any others?

    The 49th triangular, square (obviously!) and heptagonal numbers are all perfect squares: is this a record? (Excluding the trivial answers 0 and 1, of course, I have found nothing greater than three so far, but I have found a case where the triangular, square and octagonal numbers are all perfect squares. Maybe I should have tried nonagonal numbers . . .)

    There is an obvious link between triangular numbers and hexagonal numbers. Do any other sets of polygonal numbers have a relationship like this?

    The triangular numbers appear in Pascal's triangle. Do any of the other sets appear there? Why or why not?

    Think up some others yourself by deducing the formula for a set.

No comments:

Post a Comment