Reverse-Then-Add sequence

Pascal.md

Let's see what Wolfram Alpha has for us:

RTA is the sequence obtained from reversing the digits of a number n and adding the result to the original number. The 196-algorithm operates RTA iteratively until a palyndromic number is obtained.

Let's define alg196 then. We can take the definition above literally and get the following script:

alg196 :: Integer -> [Integer]
alg196 n = takeWhile palyndromic . rtaseq n

rtaseq will produce an infinite stream of numbers, but we only care about those up to the first that is palyndromic. Essentially we want to produce the sequence

rtaseq n = n : n2 : n3 : n4 : ...
  where n2 = n  + reverse n
        n3 = n2 + reverse n2
        n4 = n3 + reverse n3
        ...

We notice that each element of the list depends on the previous one. There are many ways to express that in Haskell, but one that really shines is via cyclic lists. If I were to define the list [1, 2, 3, 4, ...], I could say that it is the list that starts with 1 followed by the list itself where every element is added to 1.

plus1 = 1 : fmap (+1) plus1

In our case, we need to take each number, reverse it, and add it to itself. This can be expressed just as easily by summing pair-wise the elements of the list itself with the elements of the list "mirrored", i.e. where the digits have been reversed:

rtaseq n = ns where ns = n : zipWith (+) ns (fmap mirror ns)

The mirror function can be described in a two-step process: first get the digits, then reassemble them in reverse order.

mirror :: Integer -> Integer
mirror = undigits . digits

We can either choose to extract the digits from left-to-right and assemble from right-to-left, or the opposite. We choose the former. The digits are extracted by iteratively dividing by 10, populating the result with the remainders. Haskell provides a nice divMod function that does both in one fell swoop and returns a tuple (n, r) where r is the remainder.

It is a typical example of anamorphism, i.e. an unfold. So we'll use unfoldr for that.

digits :: Integer -> [Integer]
digits = unfoldr step
  where step 0 = Nothing
        step n = let (m, r) = n `divMod` 10 in Just (r, m)

Running digits on 1234 will indeed give you the list [4,3,2,1] in return. Next we turn to undigits, which goes in the opposition direction. It is an example of a catamorphism aka a fold.

undigits :: [Integer] -> Integer
undigits = foldl1' f
  where f m n = 10 * m + n

foldl1 assumes a non-empty list and foldl1' is useful when f is strict in its argument to avoid blowing up the stack. We'll cover this in a future session.

Running undigits on [4,3,2,1] will give you back 4321, which is exactly what we want.

We move on to palyndromic. We can use our digits function and prove that a number is palyndromic if its digits are the same in both orders:

palyndromic n = let ns = digits n in ns == reverse ns

Finally we turn to takeWhile. We could use the version available in the Prelude, but the sequence would exclude the first number that is palyndromic. So we must come up with our own implementation, which is trivial

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p [] = []
takeWhile p (x:xs) | p x       = x : takeWhile p xs
                   | otherwise = [x]

And we're done ✌️

An alternative definition

We could take the definition even more literally and iterate the RTA algorithm:

alg196 = takeWhile palyndromic . iterate rta

The expression iterate f x produces the list [x, f x, f (f x), f (f (f x)), ...], which is quite convenient. We just need a proper definition of rta n which is simply the number itself added to is own reverse:

rta n = n + mirror n