#!/usr/bin/perl
#
# Which natural numbers are sums of consecutive smaller natural numbers?
# (from pp. 50 of Mathematical Thinking: Problem-Solving and Proofs, 2E,
#  D'Angelo & West)
#
#  9 + 10 + 11 = 30
#       15 + 16 = 31
# 
# Matt Sparks, 20060929
#
use strict;

my %answers;

for my $a (2..100) {
    # we start at 2 because 2-1=1 is the first natural number

    # we calculate our answers like so:
    # ($a) + ($a - 1) is an answer
    # ($a) + ($a - 1) + ($a - 2) is an answer
    # etc; down to ($a) + ($a - 1) + ... + (1)

    my $sum = $a;
    for($b = $a-1; $b >= 1; $b--) {
        $sum += $b;
        $answers{$sum}++;
    }

    last if scalar(keys %answers) > 200;
}

print "Solutions:\n";
my $i;
for(sort {$a <=> $b} keys %answers) {
    $i++;
    printf("%5d ",$_);
    print "\n" if $i % 10 == 0;
}
print "\n";

my $max=(sort {$a <=> $b} keys %answers)[scalar(keys %answers)-1];
printf("Max: %d, Count: %d\n",$max,scalar(keys %answers));

print "\nNot solutions:\n";
$i=0;
for (1..$max) {
    next if $answers{$_};
    $i++;
    printf("%5d ",$_);
    print "\n" if $i % 10 == 0;
}
print "\n";