OK, I think I've got something... I think this function will properly calculate Euclidian coordinates for each number you feed it. At least, it calculates the correct coordinates for the first 16 values, and it completely covers the test area, with no holes: if I make each calculated point black for my whole integer range, I get a completely black area, with no spots.

sub position {
    my($i) = @_;
    my $e = int sqrt (--$i);
    my $r = $i - $e*$e;
    if($e & 1) {  # $e is odd
        if($r <= $e) {
            $x = ($e+1)/2;
            $y = ($e-1)/2 - $r;
        } else {
            $x = ($e+1)/2 - ($r-$e);
            $y = -($e+1)/2;
        }
    } else { # $e is even
        if($r <= $e) {
            $x = -$e/2;
            $y = -$e/2 + $r;
        } else {
            $x = -$e/2 + ($r-$e);
            $y = $e/2;
        }
    }
    return ($x, $y);
}
[download]

Now, my idea was to combine this with GD, so you can place a pixel for each number you want marked. For example, this will mark all numbers divisible by 16. It is largely an adaption of the synopsis for GD.

You need, of course, to combine this with the above sub.

my $edge = 100;

use GD;
# create a new image
my $im = new GD::Image($edge+2, $edge+2);

my $white = $im->colorAllocate(255,255,255);
my $red = $im->colorAllocate(255,0,0);

# make the background transparent white
$im->transparent($white);

# This is mine :-)
# plot the points
my $edge_squared = $edge * $edge;
for (my $i = 1; $i <= $edge_squared; $i++) {
    if($i % 16 == 0) {
        my($x, $y) = position($i);
        $im->setPixel($edge/2+$x, $edge/2-$y, $red);
    }
}

# Save the image file
open PNG, ">result.png" or die "Can't write to file: $!";
# make sure we are writing to a binary stream
binmode PNG;

# Convert the image to PNG and save it
print PNG $im->png;
[download]

If eventually you still need to cut it up to print, you could use one of the graphics modules to split this image up into subimages.

Update: added introduction