# Prove that the elements of the triangle sum have even numbers of divisors.

Consider the sum $$S = \sum_{k=1}^n k$$

As I was computing the first triangle number with over 500 divisors (Project Euler), I came across the hypothesis that most triangle numbers have an even number of divisors (if $n=8$, then $S = 36$ has $9$ divisors).

Example:

The number 3 has 2 divisors for triangle number 2
The number 6 has 4 divisors for triangle number 3
The number 10 has 4 divisors for triangle number 4
The number 15 has 4 divisors for triangle number 5
The number 21 has 4 divisors for triangle number 6
The number 28 has 6 divisors for triangle number 7
The number 36 has 9 divisors for triangle number 8 <--- only exception
The number 45 has 6 divisors for triangle number 9
The number 55 has 4 divisors for triangle number 10
The number 66 has 8 divisors for triangle number 11
The number 78 has 8 divisors for triangle number 12
The number 91 has 4 divisors for triangle number 13
The number 105 has 8 divisors for triangle number 14
The number 120 has 16 divisors for triangle number 15
The number 136 has 8 divisors for triangle number 16
The number 153 has 6 divisors for triangle number 17
The number 171 has 6 divisors for triangle number 18
The number 190 has 8 divisors for triangle number 19
The number 210 has 16 divisors for triangle number 20
The number 231 has 8 divisors for triangle number 21
The number 253 has 4 divisors for triangle number 22
The number 276 has 12 divisors for triangle number 23
The number 300 has 18 divisors for triangle number 24
The number 325 has 6 divisors for triangle number 25
The number 351 has 8 divisors for triangle number 26
The number 378 has 16 divisors for triangle number 27
The number 406 has 8 divisors for triangle number 28
The number 435 has 8 divisors for triangle number 29
The number 465 has 8 divisors for triangle number 30
The number 496 has 10 divisors for triangle number 31
The number 528 has 20 divisors for triangle number 32
The number 561 has 8 divisors for triangle number 33
The number 595 has 8 divisors for triangle number 34
The number 630 has 24 divisors for triangle number 35
The number 666 has 12 divisors for triangle number 36
The number 703 has 4 divisors for triangle number 37
The number 741 has 8 divisors for triangle number 38
The number 780 has 24 divisors for triangle number 39
The number 820 has 12 divisors for triangle number 40
The number 861 has 8 divisors for triangle number 41
The number 903 has 8 divisors for triangle number 42
The number 946 has 8 divisors for triangle number 43
The number 990 has 24 divisors for triangle number 44
The number 1035 has 12 divisors for triangle number 45


Which triangle numbers $S_n$ will have an odd number of divisors?

• $n=8,49,288,1681,9800,57121,332928$ all have an odd number of divisors for $S_n$. There are infinitely many. – Edward Jiang Dec 20 '14 at 21:41
• $d \mapsto n/d$ is a bijection with at most 1 fixed point so you're searching for solutions of $n(n-1)=2m^2$. – Myself Dec 20 '14 at 21:44

First, note that for any positive integer $S$, its factors come in pairs $(n, \frac{S}{n})$; if $n$ and $\frac{S}{n}$ are the same, then $S = n^2$, that is, $S$ is a square number and $n$ is its square root. So, a positive integer has an odd number of factors iff it is square, and hence we may rephrase the question as one about numbers that are both triangular and square, and there are infinitely many of these---

$$0, 1, 36, 1225, 41616, 1413721, 48024900, 1631432881, \ldots$$

---(this is OEIS A001108) as one can show by translating the problem into one about the classical Pell equation, which I see now Mark has done in his excellent solution.

• Number "15" has an even number (4) of factors. – Don Larynx Dec 20 '14 at 21:56
• Oops, wrong word of course, thanks, Don. – Travis Willse Dec 20 '14 at 21:59
• You might also want to edit your numbers, i.e. 8, 288, etc.. – Don Larynx Dec 20 '14 at 22:01
• Ah, cheers again, thanks, Don! – Travis Willse Dec 20 '14 at 22:03

Here is a way of making substantial progress.

Divisors come in pairs except when a number is square, so you are looking for triangle numbers which are also squares i.e. $$\frac {n(n+1)}2=m^2$$

Next multiply both sides by $8$ and add $1$ to obtain $$4n^2+4n+1=8m^2+1$$

If you then put $p=2n+1, q=2m$ this gives $$p^2-2q^2=1$$ where $p$ is odd and $q$ is even.

This is a well known equation (Pell's) and any solution (there are infinitely many) can be worked back to a solution to the original problem.

To expand on the comments made by others, if we start with $(p,q)$ then $(3p+4q,2p+3q)$ is another solution, and we have $(p,q)=(3,2)$ to start us off - or we could start with $(1,0)$.

Again if $(p,q)$ is a solution so is $(3p-4q, 3q-2p)$ and you can use this to show that there is only one sequence of solutions beginning with $(1,0)$

This all links with the fact that $p^2-2q^2=(p+q\sqrt 2)(p-q\sqrt 2)$ which is why the $\sqrt 2$ terms come in the comments.

• It's also interesting to mention that there are recursive formulae that yield all solutions starting from a few base cases namely if $p,q$ and $p',q'$ are solutions then more can be found by expanding $(p+\sqrt 2 q)(p'+\sqrt 2 q')$. – Myself Dec 20 '14 at 21:52
• The connection with Pell's equation offers a nice explanation for why the limiting ratio of successive square triangular numbers is $(1 + \sqrt{2})^2 = 3 + 2 \sqrt{2}$. – Travis Willse Dec 20 '14 at 21:58
• How is it possible for $q$ to be odd? – Don Larynx Dec 20 '14 at 22:04
• @DonLarynx TYPO - have corrected – Mark Bennet Dec 20 '14 at 22:05