|Perl: the Markov chain saw|
Write any natural number as sum of three triangular numbersby ambrus (Abbot)
|on Sep 25, 2011 at 11:00 UTC||Need Help??|
Gauss has proved that any natural number can be written as a sum of three triangular numbers. Write a program that outputs a decomposition of each natural number up to 80 in such a form, thus experimentally testing this theorem. You must output exactly one decomposition of each number. (Printing all solutions for each number would degenerate to a wall of text, and it would also make it hard to see whether any number is skipped.)
The triangular numbers are numbers of the form n(n-1)/2, where n is an integer. For example, the first few triangular numbers are 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78. Part of the output of the program could be
At this point, you are invited to stop reading and try to solve the problem alone.
This post will show three solutions. The first solution is very simple and naive. The second and third solutions add some complication to the previous solution, but at once make it better in the sense that it would be more efficient if you wanted to adapt it to find decompositions of numbers much greater than 80.
You might notice how all three solutions give different output, but each output is equally valid. For example, the first solution prints 70 = 0 + 15 + 55, the second prints 70 = 28 + 21 + 21, the third prints 70 = 66 + 3 + 1.
The solutions are translations of the baby-Python programs from the notebook info1-gy4 I wrote when teaching introduction to programming (fallback in case previous link is broken).
The second and third solutions are actually not covered by the course, but presented there as supplementary material. That shouldn't stop you from reading them, especially if you are not a beginner like most students on this course were.
The second solution stops searching once it's found a solution (the first solution keeps searching, it only does not print further solutions). Also, the second solution cuts down the search space by only searching for solutions where the terms are in decreasing order.
The third solution iterates on triangular numbers downwards instead of upwards. Instead of always starting down from 12*13/2, we compute an upper bound for each loop so that the triangular number can't be greater than the sum we want to reach with the previous triangular numbers subtracted. As a result, we don't even need to iterate on the third triangular number, so there's no loop on n3 here. All this usually lets us find a solution faster.
Incidentally, this meditation was spawned by the thread An exploration of higher-level-language approaches to the "First all-zero row in an NxN matrix" problem (goto Considered Harmful).
Update: put all the solutions in readmore.
Update: added link to theorem.