Palindrome numbers

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.

    1. Choose a number
    2. If it’s a palindrome, then stop
    3. If not, reverse the number and add to the original number
    4. 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

2 thoughts on “Palindrome numbers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s