Triangular primes: or, the dangers of non-rigorous proofs

Triangular primes: or, the dangers of non-rigorous proofs

  • Comments 7
Beware of bugs in the above code; I have only proved it correct, not tried it.
-- Donald Knuth

If you've bowled, you know the arrangement of the bowling pins forms a triangle.

http://blogs.msdn.com/photos/matthew_van_eerde/images/8601570/original.aspx

(Image courtesy of the International Pumpkin Federation.)

If you've played eight-ball, you know the arrangement of the fifteen billiard balls forms a triangle.

http://blogs.msdn.com/photos/matthew_van_eerde/images/8601581/original.aspx

Ten, fifteen... what other numbers form a triangle? The common arrangement of nine-ball and ninepins doesn't count because it's a diamond, not a triangle.

You can start with ten and add five balls to make a triangle of fifteen... then add six more to make a triangle of 21... then seven more to make a triangle of 28... and so on, with this sequence:

..., 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231...

Start looking for patterns.  What do you see?  Nothing jumps out right away.  Are there any primes?  Ones that end in 0, 2, 4, 6, or 8 are obviously even and therefore not primes... ones that end in 5 are divisible by 5 and therefore not primes... the remaining ones fall due to specific cases (21 = 3 x 7; 91 = 7 x 13; 153 = 3 x 3 x 17; 171 = 3 x 3 x 19; 231 = 3 x 7 x 11...)

In fact, gosh darn it, it seems like none of these numbers are prime, no matter how far we extend that "..." on the right!  Can this be a coincidence?

A few mental coruscations later I have an idea that it is not a coincidence... that triangular numbers, by there very nature, cannot be prime.  In fact I'm even willing to call it a "proof."  Here it is.

"Theorem": there are no triangular primes.

First we need to generate a formula for the triangular numbers.  Note that if you take an n x (n + 1) rectangle and draw a zig-zag line like so, you get two triangles.

 http://blogs.msdn.com/photos/matthew_van_eerde/images/8601535/original.aspx

Each of these triangles is composed of n diagonals, the shortest of which is 1, and the longest of which is n.  That is to say, each of the triangles is composed of tn squares.  So we know that the total number of squares in the rectangle is 2tn.

But we also know that the total number of squares is the base times the height, or n(n + 1).  This gives us 2tn = n(n + 1), or tn = n(n + 1)/2.

The next part of the "proof" breaks down into case analysis.  n can be odd (as in the diagram, where n is 5) or even.

Case where n is even:

n is an even positive number.  Therefore n/2 is a positive number (maybe odd, maybe even; doesn't matter.)  tn can be written as (n/2)(n + 1), and is therefore not prime, since it has at least four factors: 1, n/2, n + 1, and tn.

Case where n is odd:

n is an odd positive number.  Therefore n + 1 is an even positive number.  Therefore (n + 1)/2 is a positive number (maybe odd, maybe even; doesn't matter.)  tn can be written as (n)([n + 1]/2), and is therefore not prime, since it has at least four factors: 1, n, (n + 1)/2, and tn.

Note that the "proof" that tn is not prime inevitably concludes in a stronger result - that tn has at least four factors... not only is tn not prime, it can't even have as few as three factors.  (Some numbers with three factors: 4, 9, 25, 49...)

Exercise: what kind of numbers have exactly three factors?

A beautiful proof.  Perhaps the two cases can be elegantly folded together to normalize it a bit better.  That is not a serious problem.

There is a serious problem.

The proof of our result is doomed.

Why?

Because the result does not hold! There is a triangular prime.

Exercise: find a triangular prime.

After having recovered from the shocking revelation that, our beautiful proof to the contrary, a triangular prime is so rude as to exist, a little self-examination is in order.  What is wrong with the proof?  This... and not the existence of triangular primes... is the lesson to be learned: that beauty is not always truth.

The great tragedy of Science -- the slaying of a beautiful hypothesis by an ugly fact.
-- Thomas Huxley
Leave a Comment
  • Please add 4 and 2 and type the answer here:
  • Post
  • 3 is an obvious prime triangular number.

    You found >2 factors but didn't show that they were all different.

  • Joe:  the different factors is only the case with tn = 1, from what I see.

    There are two possible sets of factors for a given tn, so find the n where those factors are equal:

    n = (n + 1) / 2

    2 n = n + 1

    n = 1

    tn = 1 * (1 + 1) / 2 = 1

    Second case:

    n / 2 = n + 1

    n = 2 n + 2

    n = -2

    tn = -2 / 2 * (-2 + 1) = 1

    For tn = 3, n = 2.  My suspicion is that there are no such primes greater than 3 to be found, but I don't know that my proof is correct:

    To be prime the only factors can be 1 and tn.  Therefore at least one of the following has to be true:

    tn = n

    tn = n + 1

    tn = n / 2

    tn = (n + 1) / 2

    1:

    n * (n + 1) / 2 = n

    (n + 1) / 2 = 1

    n + 1 = 2

    n = 1

    2:

    n * (n + 1) / 2 = n + 1

    n / 2 = 1

    n = 2

    3:

    n * (n + 1) / 2 = n / 2

    n + 1 = 1

    n = 0

    4:

    n * (n + 1) / 2 = (n + 1) / 2

    n = 1

    Therefore tn primes should be limited to t0, t1, t2, or:

    tp = { 0, 1, 3 }

  • @Kfarmer,

    There is only one prime triangular number, 3.

    0 and 1 don't count as they are zeros and unities respectively.

  • That's you're interpretation (and, admittedly, Dr Math's interpretation), based on how precisely you define primes.  

    Frankly, I have yet to see One be proven non-prime by any other argument than "we define it as non-prime because we don't want to consider { 1^n } to be a factorization" which is fairly artificial.  I freely admit that I only look for such arguments once or twice a year, and then only briefly.  I have better empires to run.

    I will grant that Zero is hard to support.

    Either way, the proof seems to still hold.  The set of tn primes was still limited to that set: whether you consider the set to be a superset of the final answer or not is your problem.

  • (and before I get flamed for the uniqueness requirements for arithmetic, everybody should remind themselves that math really is just an offshoot of philosophy, which historically has been rife with disagreements)

    (and, seriously, are you really *that* bored?)

  • { t0 = 0, t1 = 1, t2 = 3 } is indeed the set of triangular numbers where the proof breaks down.

    For t0, the "four distinct factors" are 1, 0, 1, and 0;

    For t1, they are 1, 1, 1, and 1;

    For t2, they are 1, 1, 3, and 3.

    For n >= 3, the "four distinct factors" can be shown to /actually be distinct/ (actually, for primality, it suffices to show that the two internal factors are both at least 2) so the proof is correct from t3 on.

    The definition of primality I would like to use is "having exactly two factors."

    1 has a single factor, and is thus /even better than prime/ -- it's the multiplicative identity.

    0 has infinitely many factors but is in turn a factor only of itself, so it's another kind of thing altogether.

  • Your proof is not "non-rigorous", it simply contains a mistake.

    In the case where n is even, you fail to observe that the four factors may not be distinct. It is easy to see that the only case in which they aren't distinct is when n=2, and in this case t2=3 is prime.

    So you have proved that the only prime triangular number is t2.

    This is not a "non-result", you just have to make the one exception to your hypothesis.

    So the Huxley quote is completely inappropriate here.

Page 1 of 1 (7 items)