Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) 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

50 = 28 + 1 + 21 51 = 0 + 15 + 36 52 = 21 + 3 + 28 53 = 10 + 28 + 15 54 = 6 + 3 + 45

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.

sub triang_decompose_1 { my($goal, $found, $n0, $n1, $n2); for $goal (0 .. 80) { $found = 0; for $n0 (0 .. 12) { for $n1 (0 .. 12) { for $n2 (0 .. 12) { if ($goal == $n0*($n0+1)/2 + $n1*($n1+1)/2 + $n2*( +$n2+1)/2 && !$found) { say $goal, " = ", $n0*($n0+1)/2, " + ", $n1*($ +n1+1)/2, " + ", $n2*($n2+1)/2; $found = 1; } } } } } }

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.

sub triang_decompose_2 { my($goal, $found, $n0, $n1, $n2); for $goal (0 .. 80) { $found = 0; $n0 = 0; while (!$found && $n0*($n0+1)/2 <= $goal) { $n1 = 0; while (!$found && $n1 <= $n0) { $n2 = 0; while (!$found && $n2 <= $n1) { if ($goal == $n0*($n0+1)/2 + $n1*($n1+1)/2 + $n2*( +$n2+1)/2 && !$found) { say $goal, " = ", $n0*($n0+1)/2, " + ", $n1*($ +n1+1)/2, " + ", $n2*($n2+1)/2; $found = 1; } $n2++; } $n1++; } $n0++; } if (!$found) { say $goal, " has no decomposition."; } } }

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.

sub triang_decompose_3 { my($goal, $found, $n0, $n1, $n2, $rem2, $rem1); for $goal (0 .. 80) { $found = 0; $n0 = int(sqrt(2*$goal+1) - 1/2); while (!$found && 0 <= $n0) { $rem2 = $goal - $n0*($n0+1)/2; $n1 = floor(sqrt(2*$rem2+1) - 1/2); while (!$found && 0 <= $n1) { $rem1 = $rem2 - $n1*($n1+1)/2; $n2 = floor(sqrt(2*$rem1+1) - 1/2); if ($rem1 == $n2*($n2+1)/2) { say $goal, " = ", $n0*($n0+1)/2, " + ", $n1*($n1+1 +)/2, " + ", $n2*($n2+1)/2; $found = 1; } $n1--; } $n0--; } if (!$found) { say $goal, " has no decomposition."; } } }

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.

Update: Limbic~Region points out in this reply that this question has been asked here nine years ago: Triangle Numbers and Triangle Numbers Revisited.


In reply to Write any natural number as sum of three triangular numbers by ambrus

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others browsing the Monastery: (3)
As of 2024-03-29 15:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found