use strict;

for my $n (1..1000000) {
#for my $n (1000..1090) {
  my $candidate = palindrome($n);
  print "$n: $candidate\n";
};

use strict;

sub palindrome {
  my ($n) = @_;
  my $l = int ((length $n) / 2);
  
  $n =~ /^(\d{$l})(.?)(\d{$l})$/
    or return $n;

  my ($left,$middle,$right) = ($1,$2,$3);
  
  my @parts = map { ($left ? $left + $_ : "") . $middle . ($left ? rev
+erse $left + $_ : "") } (-1, 0, 1);
  
  for (@parts) {
    die "$n: $_ is no palindrome"
      if $_ ne reverse $_;
  };

  my $result = $parts[0];
  for (@parts) {
    $result = $_ if abs($n - $_) < abs($n - $result);
  };

  die "$n: $result is no palindrome"
    if $result ne reverse $result;

  return $result
};
[download]

Update: On thinking a bit longer about this, I think my hypothesis above is wrong, but my code is still right, as there is the case of C == 0, which I neglected to mention. My handling of the code below, still generates the good results though.

Feh. On further testing, my code already fails for 107, where the closest palindrome is 111 and not 101 as my code finds. Oh well :-(