Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Write any natural number as sum of three triangular numbers

by ambrus (Abbot)
on Sep 25, 2011 at 11:00 UTC ( #927735=perlmeditation: 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.

Comment on Write any natural number as sum of three triangular numbers
Select or Download Code
Re: Write any natural number as sum of three triangular numbers
by CountZero (Bishop) on Sep 25, 2011 at 12:07 UTC
    I looked at it from the "other side": get all the variations with repetition of the set of triangular numbers less than 80. Then compute their sums. Store these sums in a an array (yes it will overwrite previous results, but we only need one solution for each number) and print the results for the numbers upto 80.
    use Modern::Perl; use Algorithm::Combinatorics qw /variations_with_repetition/; use List::Util qw /sum/; my @triangulars; push @triangulars, $_ * ( $_ + 1 ) / 2 for 0 .. 12; my $iterator = variations_with_repetition( \@triangulars, 3 ); my @results; $results[ sum @$_ ] = join ' + ', @$_ while $_ = $iterator->next; say "$_ = $results[$_]" for 0 .. 80;
    Output:
    0 = 0 + 0 + 0 1 = 1 + 0 + 0 2 = 1 + 1 + 0 3 = 3 + 0 + 0 4 = 3 + 1 + 0 5 = 3 + 1 + 1 6 = 6 + 0 + 0 7 = 6 + 1 + 0 8 = 6 + 1 + 1 9 = 6 + 3 + 0 10 = 10 + 0 + 0 11 = 10 + 1 + 0 12 = 10 + 1 + 1 13 = 10 + 3 + 0 14 = 10 + 3 + 1 15 = 15 + 0 + 0 16 = 15 + 1 + 0 17 = 15 + 1 + 1 18 = 15 + 3 + 0 19 = 15 + 3 + 1 20 = 10 + 10 + 0 21 = 21 + 0 + 0 22 = 21 + 1 + 0 23 = 21 + 1 + 1 24 = 21 + 3 + 0 25 = 21 + 3 + 1 26 = 15 + 10 + 1 27 = 21 + 6 + 0 28 = 28 + 0 + 0 29 = 28 + 1 + 0 30 = 28 + 1 + 1 31 = 28 + 3 + 0 32 = 28 + 3 + 1 33 = 21 + 6 + 6 34 = 28 + 6 + 0 35 = 28 + 6 + 1 36 = 36 + 0 + 0 37 = 36 + 1 + 0 38 = 36 + 1 + 1 39 = 36 + 3 + 0 40 = 36 + 3 + 1 41 = 28 + 10 + 3 42 = 36 + 6 + 0 43 = 36 + 6 + 1 44 = 28 + 15 + 1 45 = 45 + 0 + 0 46 = 45 + 1 + 0 47 = 45 + 1 + 1 48 = 45 + 3 + 0 49 = 45 + 3 + 1 50 = 28 + 21 + 1 51 = 45 + 6 + 0 52 = 45 + 6 + 1 53 = 28 + 15 + 10 54 = 45 + 6 + 3 55 = 55 + 0 + 0 56 = 55 + 1 + 0 57 = 55 + 1 + 1 58 = 55 + 3 + 0 59 = 55 + 3 + 1 60 = 45 + 15 + 0 61 = 55 + 6 + 0 62 = 55 + 6 + 1 63 = 45 + 15 + 3 64 = 55 + 6 + 3 65 = 55 + 10 + 0 66 = 66 + 0 + 0 67 = 66 + 1 + 0 68 = 66 + 1 + 1 69 = 66 + 3 + 0 70 = 66 + 3 + 1 71 = 55 + 15 + 1 72 = 66 + 6 + 0 73 = 66 + 6 + 1 74 = 45 + 28 + 1 75 = 66 + 6 + 3 76 = 66 + 10 + 0 77 = 66 + 10 + 1 78 = 78 + 0 + 0 79 = 78 + 1 + 0 80 = 78 + 1 + 1

    CountZero

    A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

Re: Write any natural number as sum of three triangular numbers
by JavaFan (Canon) on Sep 25, 2011 at 12:22 UTC
    This solution first finds all the sums of the triangle number pairs. To find solutions, it looks for each triangle number whether there's a pair that sums to the target:
    #!/usr/bin/perl use strict; use warnings; my $target = 80; my @triangles; my %sum; # # Find all triangle numbers less than the target # my $n = 0; { my $t = $n * $n++ / 2; last if $t > $target; push @triangles, $t; redo; } # # Find all sums of triangle numbers: # for (my $i = 0; $i < @triangles; $i++) { my $t1 = $triangles[$i]; for (my $j = $i; $j < @triangles; $j++) { my $t2 = $triangles[$j]; last if $t1 + $t2 > $target; $sum{$t1 + $t2} ||= [$t1, $t2]; } } # # Now for each number, try all triangle numbers and see if there's a s +um # NUMBER: for (my $number = 0; $number <= $target; $number++) { foreach my $triangle (@triangles) { next unless $sum{$number - $triangle}; printf "%d = %d + %d + %d\n", $number, $triangle, @{$sum{$number - $triangle}}; next NUMBER; } } __END__ 0 = 0 + 0 + 0 1 = 0 + 0 + 1 2 = 0 + 1 + 1 3 = 0 + 0 + 3 4 = 0 + 1 + 3 5 = 1 + 1 + 3 6 = 0 + 0 + 6 7 = 0 + 1 + 6 8 = 1 + 1 + 6 9 = 0 + 3 + 6 10 = 0 + 0 + 10 11 = 0 + 1 + 10 12 = 0 + 6 + 6 13 = 0 + 3 + 10 14 = 1 + 3 + 10 15 = 0 + 0 + 15 16 = 0 + 1 + 15 17 = 1 + 1 + 15 18 = 0 + 3 + 15 19 = 1 + 3 + 15 20 = 0 + 10 + 10 21 = 0 + 0 + 21 22 = 0 + 1 + 21 23 = 1 + 1 + 21 24 = 0 + 3 + 21 25 = 0 + 10 + 15 26 = 1 + 10 + 15 27 = 0 + 6 + 21 28 = 0 + 0 + 28 29 = 0 + 1 + 28 30 = 0 + 15 + 15 31 = 0 + 3 + 28 32 = 1 + 3 + 28 33 = 3 + 15 + 15 34 = 0 + 6 + 28 35 = 1 + 6 + 28 36 = 0 + 0 + 36 37 = 0 + 1 + 36 38 = 0 + 10 + 28 39 = 0 + 3 + 36 40 = 1 + 3 + 36 41 = 3 + 10 + 28 42 = 0 + 6 + 36 43 = 0 + 15 + 28 44 = 1 + 15 + 28 45 = 0 + 0 + 45 46 = 0 + 1 + 45 47 = 1 + 1 + 45 48 = 0 + 3 + 45 49 = 0 + 21 + 28 50 = 1 + 21 + 28 51 = 0 + 6 + 45 52 = 1 + 6 + 45 53 = 10 + 15 + 28 54 = 3 + 6 + 45 55 = 0 + 0 + 55 56 = 0 + 1 + 55 57 = 0 + 21 + 36 58 = 0 + 3 + 55 59 = 1 + 3 + 55 60 = 0 + 15 + 45 61 = 0 + 6 + 55 62 = 1 + 6 + 55 63 = 3 + 15 + 45 64 = 0 + 28 + 36 65 = 0 + 10 + 55 66 = 0 + 0 + 66 67 = 0 + 1 + 66 68 = 1 + 1 + 66 69 = 0 + 3 + 66 70 = 0 + 15 + 55 71 = 1 + 15 + 55 72 = 0 + 6 + 66 73 = 0 + 28 + 45 74 = 1 + 28 + 45 75 = 3 + 6 + 66 76 = 0 + 10 + 66 77 = 1 + 10 + 66 78 = 0 + 0 + 78 79 = 0 + 1 + 78 80 = 1 + 1 + 78
Re: Write any natural number as sum of three triangular numbers
by BrowserUk (Pope) on Sep 25, 2011 at 13:49 UTC

    #! perl -slw use strict; my @trinums = map $_ * ($_-1) /2, 1 .. 15; my %trinums; undef @trinums{ @trinums }; sub triSum { my $n = shift; for my $f ( 0 .. $#trinums ) { my $first = $trinums[ $f ]; for my $s ( 0 .. $first - 1, $first + 1 .. $#trinums ) { my $second = $trinums[ $s ]; my $third = $n - ( $first + $second ); return $first, $second, $third if exists $trinums{ $third +}; } } } print "$_ : ", join ' + ', triSum( $_ ) for 1 .. 80; __END__ c:\test>trinums 1 : 0 + 1 + 0 2 : 0 + 1 + 1 3 : 0 + 3 + 0 4 : 0 + 1 + 3 5 : 1 + 3 + 1 6 : 0 + 3 + 3 7 : 0 + 1 + 6 8 : 1 + 6 + 1 9 : 0 + 3 + 6 10 : 0 + 10 + 0 11 : 0 + 1 + 10 12 : 0 + 6 + 6 13 : 0 + 3 + 10 14 : 1 + 3 + 10 15 : 0 + 15 + 0 16 : 0 + 1 + 15 17 : 1 + 6 + 10 18 : 0 + 3 + 15 19 : 1 + 3 + 15 20 : 0 + 10 + 10 21 : 0 + 6 + 15 22 : 0 + 1 + 21 23 : 1 + 21 + 1 24 : 0 + 3 + 21 25 : 0 + 10 + 15 26 : 1 + 10 + 15 27 : 0 + 6 + 21 28 : 0 + 28 + 0 29 : 0 + 1 + 28 30 : 0 + 15 + 15 31 : 0 + 3 + 28 32 : 1 + 3 + 28 33 : 3 + 15 + 15 34 : 0 + 6 + 28 35 : 1 + 6 + 28 36 : 0 + 15 + 21 37 : 0 + 1 + 36 38 : 0 + 10 + 28 39 : 0 + 3 + 36 40 : 1 + 3 + 36 41 : 3 + 10 + 28 42 : 0 + 6 + 36 43 : 0 + 15 + 28 44 : 1 + 15 + 28 45 : 0 + 45 + 0 46 : 0 + 1 + 45 47 : 1 + 10 + 36 48 : 0 + 3 + 45 49 : 0 + 21 + 28 50 : 1 + 21 + 28 51 : 0 + 6 + 45 52 : 1 + 6 + 45 53 : 10 + 15 + 28 54 : 3 + 15 + 36 55 : 0 + 10 + 45 56 : 0 + 1 + 55 57 : 0 + 21 + 36 58 : 0 + 3 + 55 59 : 1 + 3 + 55 60 : 0 + 15 + 45 61 : 0 + 6 + 55 62 : 1 + 6 + 55 63 : 3 + 15 + 45 64 : 0 + 28 + 36 65 : 0 + 10 + 55 66 : 0 + 21 + 45 67 : 0 + 1 + 66 68 : 1 + 66 + 1 69 : 0 + 3 + 66 70 : 0 + 15 + 55 71 : 1 + 15 + 55 72 : 0 + 6 + 66 73 : 0 + 28 + 45 74 : 1 + 28 + 45 75 : 3 + 36 + 36 76 : 0 + 10 + 66 77 : 1 + 10 + 66 78 : 0 + 78 + 0 79 : 0 + 1 + 78 80 : 1 + 78 + 1

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Write any natural number as sum of three triangular numbers
by Limbic~Region (Chancellor) on Sep 25, 2011 at 16:32 UTC
Reaped: Re: Write any natural number as sum of three triangular numbers
by NodeReaper (Curate) on Sep 26, 2011 at 13:20 UTC
Reaped: Re: Write any natural number as sum of three triangular numbers
by NodeReaper (Curate) on Sep 28, 2011 at 12:54 UTC
Reaped: Re: Write any natural number as sum of three triangular numbers
by NodeReaper (Curate) on Sep 29, 2011 at 13:17 UTC
Reaped: Re: Write any natural number as sum of three triangular numbers
by NodeReaper (Curate) on Sep 30, 2011 at 13:16 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://927735]
Approved by ww
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (8)
As of 2014-10-22 12:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (117 votes), past polls