|No such thing as a small change|
Triangle Numbersby YuckFoo (Abbot)
|on Apr 24, 2002 at 17:31 UTC||Need Help??|
I read about triangle numbers in book by Clifford Pickover, I forget which one.
Triangle numbers are numbers of the form 0+1+2+3...n, or .5*n*(n+1). The first few t-nums are 0, 1, 3, 6, 10, 15, 21. These are numbers of items that can be arranged in a triangle, like bowling pins.
There are many interesting features of t-nums. Adding any two consectutive t-nums is a square number (6+10, 10+15), which makes sense when you think about it.
A notable t-num is the 36th t-num, 666. Of course 36 (6*6) is itself a t-num.
What I found most fascinating was the claim that any whole number can be written as the sum of three t-nums. I'm still trying to figure out why. In the meantime I wrote this program to check it out.
The program is a bit brutish. I keep an array of t-nums that I add to as needed. To find the three addends, I binary search for the largest t-num less or equal to the target. I initialize the three numbers to this value and iterate through all possibilities to find the answer. Any suggestions to optimize the search method?