Task — Next palindrome number

You are given a positive integer $N. Write a script to find out the next palindromic number higher than $N.

Examples

Example 1
Input: $N = 1234
Output: 1331

Example 2
Input: $N = 999
Output: 1001

Analysis

This is - or isn't - easy.

It's easy if you do this:

$test = $N + 1;
$test ++ while $test ne reverse($test);

I think it's clear that that will produce the correct answer, but if $N is large it could take a long time.

So I looked for a more analytic, and faster, method, and I think I found one, but it's quite complicated.

Briefly - and see the code for more details - first establish whether $N has an even or odd number of digits. Divide it into 3 strings: $left, $middle and $right where $left and $right are the same length and $middle is the middle digit of an odd-length number or '' (a zero-length string) for an even-length one.

The first attempt is then

$left . $middle . reverse($left)

which will work roughly half the time - that is, when reverse($left) > $right. For example, it works for 123000 -> 123321 or 1234000 -> 1234321 but not for 123444 -> 123321.

Where it doesn't work for even-length $N, reverse($left) < $right and the answer is ($left + 1) . reverse($left + 1).

In the odd-length cases we need to:

• concatenate $left and $middle
• increment that
• split the result into a new $left and (one-digit) $middle
• and the answer is $left . $middle . reverse($left).

But even that doesn't work if $N is all 9s - such as 99, 999, 9999 etc. For those numbers the answer is

'1' . '0' x (length($N) - 1) . '1'

And lastly, for the single digit values of $N the answer is simply $N + 1, except for 9 where the answer is 11.

Finally, just to be sure my algorithm works, I have added the easy way (see above) as well, and checked that the two agree. For the thousands of random numbers I have checked, they do.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-05-24
use utf8;     # Week 114 - task 1 - Next palindrome number
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

next_palindrome_number(12345);
next_palindrome_number(12320);
next_palindrome_number(12321);
next_palindrome_number(123456);
next_palindrome_number(123999);
next_palindrome_number(1234320);
next_palindrome_number(9999);
next_palindrome_number(99999);

sub next_palindrome_number {
    
    my ($number, $length, $left, $middle, $right, $try, $verify, $left_middle);
    
    # initialise
    $number = $_[0];
    $length = length($number);
    
    # single digit
    if ($length == 1) {
        $try = $number == 9 ? 11 : $number + 1;
    } else {
    
        # divide up odd-length number
        if ($length & 1) {
            $left = substr($number, 0, int($length / 2));
            $middle = substr($number, ($length - 1) / 2, 1);
            $right = substr($number, ($length + 1) / 2, 99);
        
        # or even-length number
        } else {
            $left = substr($number, 0, $length / 2);
            $middle = '';
            $right = substr($number, ($length / 2), 99);
        }
        
        # try this
        $try = $left . $middle . reverse($left);

        # no good so increment left and try again
        if ($try <= $number) {
            unless (($left . $middle) =~ m|^9*$|) {
                
                # odd length
                if ($middle ne '') {
                    $left_middle = ($left . $middle) + 1;
                    ($left, $middle) = $left_middle =~ m|(.*)(.)|;
                    $try = $left . $middle . reverse($left);
                    
                # even length
                } else {
                    $try = ($left + 1) . reverse($left + 1);
                }
                
            # special case - all 9s
            } else {
                $try = '1' . '0' x ($length - 1) . '1';
            }
        }
    }
    
    # verify by incrementing
    $verify = $number + 1;
    $verify ++ while $verify ne reverse($verify);
    
    say qq[\nInput:  $number];
    say qq[Output: $try] . ($try == $verify ? '' : qq[ should be $verify]);
}

last updated 2026-03-31 — 30 lines of code

Output

Input:  12345
Output: 12421

Input:  12320
Output: 12321

Input:  12321
Output: 12421

Input:  123456
Output: 124421

Input:  123999
Output: 124421

Input:  1234320
Output: 1234321

Input:  9999
Output: 10001

Input:  99999
Output: 100001