You can really see the audience perk up at a title like that.
About a week ago, I was at a family party where my cousin posed this question to me:
Given any positive integer m, find the smallest palindrome that is greater than or equal to m.
I scribbled around on a random index card for a while and thought I’d figured it out. I knew that with something this sneaky it would be smarter to spend some effort proving the algorithm correct before building anything, but I’ve been itching to write some Scheme for a while now and so I just dove right in. The solution involved persistent deques and some other cuteness that was much fun to implement.
And of course it didn’t work.
So, I went back to the drawing board and, after a couple of false starts, I had the algorithm and the proof written up within a half-hour or so. Calling this a ‘pearl’ is sort of a stretch, because I don’t think the answer is that elegant, but this is definitely a puzzle with one of those ‘pearly’ feelings to it, so I classified it as such.
The solution, in a nutshell, takes an integer with n digits, and creates a new integer p such that the first n/2 digits of p are the same as in m, and the last n/2 digits are
the first n/2 digits in m in reverse order. This works as long as the new integer p is greater than n: If it isn’t, you have to add one to the integer produced by the first half of the digits in m before reversing and appending it to produce p.
What I’ve described only works if n is even. There’s a bit of extra weirdness you have to tackle if n is odd, but it’s not that bad. Life also becomes more complicated if you demand the smallest palindrome that is strictly greater than n, instead of greater than or equal to. But only marginally so 
The code for my solution is here: next-palindrome.scm, digitized-integer.scm.
The persistent deque that I implemented but never used is here: deque.scm. I got the gist of how to implement it from Chris Okasaki’s Purely Functional Data Structures, which I’m reading in parallel with The Structure and Interpretation of Computer Programs.
This is the first nontrivial Scheme program I’ve ever written, as far as I can remember. It’s probably all hacked up, and I know that it’s grossly inefficient in parts. I was more concerned with writing a comprehensible program than a fast one.
(I know we did some Scheming in one of my undergraduate courses, but I think I was sufficiently demoralized at the time that I ended up skipping most of the relevant assignment.)
I’m using PLT Scheme with Dr. Scheme as my environment, because I need to level up a bit more before I can take on emacs. Also, I’m using the “Advanced Student” level of the language in Dr. Scheme, and I have no idea how this stacks up against “real” versions of Scheme.
One comment I’d like to make as a result of this experience: I understand now why many functional languages (like OCaml and Haskell) have builtin pattern-matching facilities. When your data structures are immutable, you’re necessarily going to write a lot of code to build new instances of them from old instances, which is exactly what pattern matching does for you. I often caught myself wishing for the ability to rip apart and reassemble my deques when writing deque.scm, instead of having to write procedures to glue everything together. I’ve been told that it’s not much of a stretch to implement such things using macros in Lisp and Scheme, but I’m not quite there yet.
For completeness, I’m going to present the algorithm a bit more formally and prove that it works for the even case here. So, if you’ve somehow managed to make it this far, I imagine that this is where you’ll definitely check out 
First, some notation. In the discussion that follows, I use the ‘.’ operator to mean concatenation of digits. So, 123 . 456 is the number 123 456. The _ denotes a subscript. The _rev subscript indicates the operation of reversing digits, so 123_rev is 321. A bold zero ( 0 ) indicates a sequences of n/2 zeroes. So, if m = 1234, then 12 . 0 is 1200.
Let m = d_n . d_(n-1) … d_1 be an n-digit number where n is even.
Let l = d_n . d_(n-1) … d_(n/2), and let r = d_(n/2 + 1) … d_1.
Claim:
(a) If (l . l_rev) >= m, then (l . l_rev) is the smallest palindrome that is greater than or equal to m.
(b) If (l . l_rev) < m, then ( (l + 1) . (l + 1)_rev) is the smallest palindrome that is greater than or equal to m.
Proof:
(a)
We have (l . l_rev) >= m.
This implies that (l . l_rev) >= (l . r), which implies that l_rev >= r. Any palindrome between (l . l_rev) and m would have to be of the form p = l . x, where r < x < l_rev, where x = l_rev (to satisfy the palindrome constraint). Obviously, the only such x is l_rev itself.
OK, that was pretty weak, but hopefully you get the gist.
(b)
We have (l . l_rev) < m.
p = ( (l + 1) . (l + 1)_rev) is certainly > m.
We show that there are no palindromes between m and p, and so p must be the next greatest palindrome.
We consider two cases:
(i) Is there a palindrome between m and ( (l + 1) . 0)? Such a palindrome would have l as the first n/2 digits. Thus, the resulting palindrome would be (l . l_rev), which we have already seen is < m.
(ii) Is there a palindrome between ( (l + 1) . 0) and p? No, because such a palindrome would have (l + 1) as the first n/2 digits, and the only palindrome that can be formed as such will be p itself.
OK, so that was likely more verbose than it needed to be, but so it goes. As I said before, the case where m has an odd number of digits is a bit stickier, but only involves one more check. See the program itself for details.