A palindrome number is the same forward or backward e.g. 121, or 2442. All the integers between 0 and 9 are palindromes. The occurrence of palindrome numbers between 10 and 100 is straightforward and regular e.g. 11, 22, 33,…(you get the idea)

One obscure mathematical recreation is to make non-palindrome numbers palindromic through a process of reversing and adding.

- Choose a number
- If it’s a palindrome, then stop
- If not, reverse the number and add to the original number
- Go to step 2.

For example: 12 + 21 = 33

Most numbers become palindromes quite quickly but some take a while, for example, the numbers 89 and 98 take 24 iterations. No one has yet made 196 palindromic using this procedure despite years of reversing and adding. There are a couple of web sites that have way-more information about this than you’d probably care to know: 196 Palindrome Quest and p196. A number that cannot be made into a palindrome by the process of reversing and adding is referred to a Lychrel number.

# Palindrome calculations in R

We are not going to turn 196 into a palindrome using R, that problem is being tackled with highly optimised algorithms running on fast machines; however we can explore some of the lower slopes of the palindrome number mountain. We need functions to reverse a number and to test if it is a palindrome.

### Reversing a number

There are probably many ways to reverse a number. I started by using string manipulation as in the following code.

Reverse.numberAsString <- function(x){ # Reverse using string manipulation x.out <- as.character(x) # convert number to a character string x.out <- unlist(strsplit(x.out, '')) # break the string up into a vector x.out <- rev(x.out) # reverse it x.out <- paste(x.out, collapse='') # join it back together x.out <- as.numeric(x.out) # turn it back to a number return(x.out) }

Perhaps a better way is to use integer division with successive powers of 10.

Reverse.number <- function(x){ n <- trunc(log10(x)) # now many powers of 10 are we dealing with x.rem <- x # the remaining numbers to be reversed x.out <- 0 # stores the output for(i in n:0){ x.out <- x.out + (x.rem %/% 10^i)*10^(n-i) # multiply and add x.rem <- x.rem - (x.rem %/% 10^i)*10^i # multiply and substract } return(x.out) }

### Testing if a number is a palindrome

A number is a palindrome it is is equal to its reverse. It is handy to have a vectorized function which we can achieve using sapply.

is.Palindrome <- function(x){ x == sapply(x,Reverse.number) }

Now we can, for example, easily find all the palindromes between 1 and 200.

x <- 1:200 x[is.Palindrome(x)] 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 111 121 131 141 151 161 171 181 191

### Making numbers into palindromes

We can use our two functions to implement the reverse and add algorithm to turn a number into a palindrome. The Make.palindrome function below prints out the numbers at the intermediate steps and will stop if the number has too many significant digits to be represented accurately. With double-precision floating point numbers, the standard in R, we are limited to about 16 significant digits before rounding error will make these calculations inaccurate.

Make.palindrome <- function(x){ i <- 0 if(is.Palindrome(x)) return(x) while(!is.Palindrome(x) ){ i <- i + 1 x.rev <- Reverse.number(x) x <- x + x.rev cat(i,' ',format(x, digits=16),'\n') if(x>10^16) stop('the number is getting too big') } }

The function will make 89 into a palindrome as follows.

Make.palindrome(89) 1 187 2 968 3 1837 4 9218 5 17347 6 91718 7 173437 8 907808 9 1716517 10 8872688 11 17735476 12 85189247 13 159487405 14 664272356 15 1317544822 16 3602001953 17 7193004016 18 13297007933 19 47267087164 20 93445163438 21 176881317877 22 955594506548 23 1801200002107 24 8813200023188

### Beyond double-precision

For higher precision arithmetic we can use the gmp package which introduces the bigz class for large integers. I’ve re-written the Reverse.number and Make.palindrome functions to use this class and the associated arithmetical functions. The Make.palindrome function has also had some minor tweaking to make it run a bit faster.

library(gmp) Reverse.number.bigz <- function(x){ n <- trunc(log10(x)) x.rem <- x x.out <- as.bigz(0) for(i in n:0){ # use interger division to get the parts we need int.div <- divq.bigz(x.rem,pow.bigz(10,i)) x.out <- add.bigz(x.out,mul.bigz(int.div, pow.bigz(10,(n-i)))) x.rem <- sub.bigz(x.rem, mul.bigz(int.div, pow.bigz(10,i))) } return(x.out) } Make.palindrome.bigz <- function(x, max.iter=100){ i <- 0 # count iterations xin <- x x.rev <- Reverse.number.bigz(x) while(x != x.rev ){ i <- i + 1 x <- add.bigz(x, x.rev) x.rev <- Reverse.number.bigz(x) # cat(i,format(x),'\n') # remove comment to print every step if(i >=max.iter) stop('Reached max.iter') } return(list(input=xin, palindrome=x, iter=i)) }

### Most delayed palindrome

Another task in the palindrome quest is to find the most delayed palindrome. This is the number that takes the greatest number of reverse and add iterations to become palindromic. The record so far is the number 1,186,060,307,891,929,990 which resolves to a palindrome in 261 iterations. We can test that with our new functions.

x <- as.bigz("1186060307891929990") Make.palindrome.bigz(x, max.iter=300) $input Big Integer ('bigz') : [1] 1186060307891929990 $palindrome Big Integer ('bigz') : [1] 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 $iter [1] 261

# Links

- Palindromes at the Encyclopedia of Integer Sequences
- Palindromes at Wikipedia
- Le Monde Puzzle 818

ccapraniVery nice! Hadn’t heard of this problem before. A bit like calculating pi but more obscure.

thesciencegeekInteresting

The Science Geek

http://www.thesciencegeek.org