Palindrome Reversal-Addition

Question

Palindrome Reversal-Addition

The process of Reversal-Addition is where a number is added to it's reverse until the number created is a palindrome. For example, if we start with 68, the process would be:

68 + 86 => 154 + 451 => 605 + 506 => 1111

As you can see, this took 3 additions to get to a palindromic number. If we were to start with 89, we would need 24 steps (which you can see the breakdown here).

The world record for the most steps taken before a palindrome is reached is 261, which occurs for the number 1186060307891929990, producing a number larger than 10¹¹⁸. However, there have been quite a few numbers which we have not been able to get a palindrome. These are called Lychrel numbers.

Since we are working in base 10, we can really only call them candidates, because there exists no proof that these numbers never reach a palindrome. For example, the smallest base-10 Lychrel candidate is 196, and has gone through well over a billion iterations. If the palindrome does exist, it is much larger than 10^108.77. As comparison, if that many 1s was inscribed on atoms, we would need 2.26772×10^588843575 universes worth of atoms to write it out, assuming it exists.

Your Task

Create a program or function that takes an integer input and returns or prints the number of steps required to reach a palindrome. You will not be required to deal with Lychrel candidates (i.e. Your program, when given a Lychrel candidate, is allowed to either throw an error or run forever).

Test Cases:

                  f(0) => 0
                 f(11) => 0
                 f(89) => 24
                f(286) => 23
          f(196196871) => 45
         f(1005499526) => 109
f(1186060307891929990) => 261

Rules

1. No standard loopholes.

Bonuses

1. If you print out each addition step, formatted n + rev(n) = m, you may multiply your score by 0.75. The sums should print out before the number of steps.
2. If your code can detect if a number is a Lychrel candidate, you may multiply your score by 0.85. In this case it is sufficient to assume anything that takes more than 261 iterations is a Lychrel candidate. Either return nothing, or anything that is not a number that can be mistaken for a correct answer (etc: any string or a number not in the range 0-261). Any error does not count as valid output (ex. maximum recursion depth exceeded) and can not be used in the detection.
3. If you complete both bonuses, multiply by 0.6.

This is code-golf, so least number of bytes wins.

---

This code snippet shows an example solution in Python 3 with both bonuses.

def do(n,c=0,s=''):
  m = str(n)
  o = m[::-1]
  if c > 261:
    return "Lychrel candidate"
  if m == o:
    print(s)
    return c
  else:
    d = int(m)+int(o)
    s+="%s + %s = %s"%(m,o,str(d))
    return do(d,c+1,s)

Answer 1

Pyth, 12 bytes

f_I`~+Qs_`Q0

Try it online: Demonstration or Test harness

This uses a quite new feature (only 17 hours old).

Explanation

               implicit: Q = input number
f          0   repeat the following expression until it 
               evaluates to true and return the number of steps
         `Q       convert Q to string
        _         reverse the digits
       s          convert to int
     +Q           add Q
    ~             assign the result to Q
                  (this returns the old value of Q)
   `              convert the old value of Q to a string
 _I               and check if it's invariant under the operation reverse

edit:

Changed the code a little bit. The old version was

fqKs_`Q~+QK0

Same byte count, but the new one is way cooler.

Answer 2

Python, 51

def f(n):r=int(str(n)[::-1]);return n-r and-~f(n+r)

For Python 2, backticks can't replace str() because of the L attached to long literals.

Here's an alternate version with score 64 * 0.85 = 54.4:

def f(n,c=262):r=int(str(n)[::-1]);return c*(n-r)and-~f(n+r,c-1)

And an alternate version for Python 3 with score 88 * 0.6 = 52.8:

def f(n,c=262):r=int(str(n)[::-1]);return c*(n-r)and-~f(n+r,print(n,'+',r,'=',n+r)or~-c)

Answer 3

CJam, 23 22 20.4 bytes

ri{__sW%i+}261*]{s_W%=}#

The code is 24 bytes long and prints -1 for Lychrel candidates.

Try it online.

How it works

ri                       e# Read an integer from STDIN.
  {       }261*          e# Do the following 261 times:
   __                    e#   Push two copies of the integer on the stack.
     sW%i                e#   Cast to string, reverse and cast back to integer.
         +               e#   Add the copy and the reversed copy of the integer.
               ]         e# Wrap all 262 results in an array.
                {     }# e# Push the index of the first element such that:
                 s       e#   The string representation equals...
                  _W%=   e#   the reversed string representation.

If {}# is successful, the index is also the number of steps. If, on the other hand, the array does not contain a palindrome, {}# will push -1.

Answer 4

Java, 200*0.6 = 120

import java.math.*;int f(BigInteger a){int s=-1;for(String b,c;(b=a+"").equals(c=new StringBuffer(b).reverse()+"")!=s++<999;)System.out.println(b+" + "+c+" = "+(a=a.add(new BigInteger(c))));return s;}

This is a simple loop that does just what it says on the box, but with some golf added. Returns 1000 for Lychrel candidates to get the detection bonus. Turns out I was able to print for not too many characters (for Java at least) and snag that bonus as well. The best I could do without bonus code was 156, so it was well worth it.

With some line breaks:

import java.math.*;
int f(BigInteger a){
    int s=-1;
    for(String b,c;(b=a+"").equals(c=new StringBuffer(b).reverse()+"")!=s++<999;)
        System.out.println(b+" + "+c+" = "+(a=a.add(new BigInteger(c))));
    return s;
}

---

Old Answer: 171*0.85 = 145.35 bytes

import java.math.*;int f(BigInteger a){int s=-1;for(String b,c;(b=a+"").equals(c=new StringBuffer(b).reverse()+"")!=s++<262;)a=a.add(new BigInteger(c));return s>261?-1:s;}

---

Answer 5

Ruby, (80+2)*0.6 =~ 49.2

With flags -nl, run

p (0..261).find{$_[b=$_.reverse]||puts($_+' + '+b+' = '+$_="#{$_.to_i+b.to_i}")}

Output looks like

 $ ruby -nl lychrel.rb 
89
89 + 98 = 187
187 + 781 = 968
968 + 869 = 1837
1837 + 7381 = 9218
9218 + 8129 = 17347
17347 + 74371 = 91718
91718 + 81719 = 173437
173437 + 734371 = 907808
907808 + 808709 = 1716517
1716517 + 7156171 = 8872688
8872688 + 8862788 = 17735476
17735476 + 67453771 = 85189247
85189247 + 74298158 = 159487405
159487405 + 504784951 = 664272356
664272356 + 653272466 = 1317544822
1317544822 + 2284457131 = 3602001953
3602001953 + 3591002063 = 7193004016
7193004016 + 6104003917 = 13297007933
13297007933 + 33970079231 = 47267087164
47267087164 + 46178076274 = 93445163438
93445163438 + 83436154439 = 176881317877
176881317877 + 778713188671 = 955594506548
955594506548 + 845605495559 = 1801200002107
1801200002107 + 7012000021081 = 8813200023188
24

If given 196, it prints the first 261 addition steps and then nil.

Nothing too tricky here. We check whether $_ (which is initialized to the input) contains its reverse, which is only possible if they're equal since they're the same size. If it is, we print the step number and exit, otherwise, we display and execute the addition step, storing the new value in $_ (I unfortunately can't just eval the string I'm displaying because it interprets a reversed number with a trailing 0 as an octal literal). puts returns a falsey value so the loop continues.

Answer 6

CJam, 24 bytes

0q{__W%#}{_W%~\~+s\)\}w;

Test it here.

Explanation

0q     e# Push a zero (the counter) and read input.
{      e# While this block leaves something truthy on the stack...
  __   e#   Make two copies of the current number (as a string).
  W%   e#   Reverse the second copy.
  #    e#   Check that they are not equal.
}{     e# ... run this block.
  _W%  e#   Make a copy of the current number and reverse it.
  ~\~  e#   Evaluate both N and its reverse.
  +s   e#   Add them and turn the sum into a string.
  \)\  e#   Pull up the counter, increment it, and push it back down again.
}w
;      e# Discard the palindrome to leave the counter on the stack.

For more information about why # can be used to check string inequality, see this tip.

Answer 7

Pyth - 19 bytes

Uses while loop and a counter. There is probably a smaller algorithm than this, but this is pretty short.

Wnz_z=z`+szs_z=hZ;Z

Try it online here.

Answer 8

Julia, 129 120 bytes * 0.6 = 72

i->(i=big(i);n=0;d=digits;while d(i)!=reverse(d(i))&&n<262 t=BigInt(join(d(i)));println(i," + ",t," = ",i+=t);n+=1end;n)

This creates an unnamed function which takes an integer as input and returns an integer, meanwhile printing each step. Lychrel candidates have a return value of 262. To call this, give it a name, e.g. f=i->....

Note that omitting code relating only to the bonuses, this solution would be 84 bytes.

Ungolfed + explanation:

function f(i)
    # Convert the input to a big integer
    i = big(i)

    # Initialize a step counter to 0
    n = 0

    # While the number is not a palindrome and we haven't exceeded 261 steps...
    while digits(i) != reverse(digits(i)) && n < 262

        # Get the reverse of the integer
        # Note that we aren't using reverse(); this is because digits()
        # returns an array of the digits in reverse order.
        t = BigInt(join(digits(i)))

        # Print the step and increment i
        println(i, " + ", t, " = ", i += t)

        # Count the step
        n += 1
    end

    # Return the number of steps or 262 for Lychrel candidates
    n
end

Examples:

julia> f(286)
286 + 682 = 968
968 + 869 = 1837
1837 + 7381 = 9218
9218 + 8129 = 17347
17347 + 74371 = 91718
91718 + 81719 = 173437
173437 + 734371 = 907808
907808 + 808709 = 1716517
1716517 + 7156171 = 8872688
8872688 + 8862788 = 17735476
17735476 + 67453771 = 85189247
85189247 + 74298158 = 159487405
159487405 + 504784951 = 664272356
664272356 + 653272466 = 1317544822
1317544822 + 2284457131 = 3602001953
3602001953 + 3591002063 = 7193004016
7193004016 + 6104003917 = 13297007933
13297007933 + 33970079231 = 47267087164
47267087164 + 46178076274 = 93445163438
93445163438 + 83436154439 = 176881317877
176881317877 + 778713188671 = 955594506548
955594506548 + 845605495559 = 1801200002107
1801200002107 + 7012000021081 = 8813200023188
23

julia> f(1186060307891929990)
(steps omitted)
261

julia> f(196)
(steps omitted)
262

julia> f(11)
0

Saved 2 bytes thanks to Geobits!

Answer 9

K, 25 bytes

#1_{~x~|x}{$. x,"+",|x}\$

Not very elegant. The overall form ({monad 1}{monad 2}\x) is K's equivalent of a general "while" loop, where the first monad is the halting condition and the second is an iteratively applied function to the argument x. The first monad ({~x~|x}) is the negation of the classic "is x a palindrome" phrase. The second monad concatenates together a string representing x plus the reverse of x, evaluates it and then casts the result back into a string with $.

A sample run showing intermediate results:

  {~x~|x}{$. x,"+",|x}\$68
("68"
 "154"
 "605"
 "1111")

Doing formatted output as requested for the bonus would be very clumsy and add a significant amount of code.

Answer 10

CJam, 23 bytes

Wl{\)\__W%_@#\i@i+s\}g;

Still only a few days into CJam, so I'm fairly happy to be at least in the same range as some of the pros. :) I did use Martin's string comparison trick that he also posted in the CJam hints. I also peeked at Dennis' solution to figure out how to reverse a string.

Explanation:

W    Initialize counter, will keep this at bottom of stack.
     Start counting at -1 because the counter will be incremented in the
     last pass through the loop, when the palindrome is detected.
l    Get input.
{    Start block of while loop.
\)\  Increment counter. Need to swap before/after because it's one below top of stack.
__   Copy current value twice. Need 3 copies in total:
       * one for reversal
       * one for comparison
       * one for addition with reverse
W%   Reverse value.
_    Copy the reverse value once because we need 2 copies:
       * one for comparison
       * one for addition with original value
@    Rotate one copy of original value to top.
#    Test for non-equality with reverse, using Martin's trick.
\i   Swap reverse value to top, and convert it to int.
@i   Rotate remaining copy of original value to top, and convert it to int.
+s   Add the values, and convert result to string.
\    Swap, so that comparison result is at top of stack for while loop test.
}g   End of while loop.
;    Current value sits at top of stack. Pop it, leaving only counter.

Test it online

Answer 11

Haskell, 66 53 bytes

r=reverse.show
f x|show x==r x=0|1<2=1+f(x+read(r x))

Usage example:

*Main> map f [0,11,89,286,196196871,1005499526,1186060307891929990]
[0,0,24,23,45,109,261]

Answer 12

Clojure, 94 bytes

(fn[x](#(let[r(bigint(apply str(reverse(str %1))))] (if(= %1 r)%2(recur(+ %1 r)(inc %2))))x 0))

This is my first attempt to code golf, so please tell me if I'm doing anything wrong.

With some spaces:

(fn [x]
(#(let [r (bigint (apply str (reverse (str %1))))]
  (if (= %1 r) %2 (recur (+ %1 r) (inc %2)))) x 0))

Simple recursion of the inner function. It takes two arguments, the integer %1 and an index %2. If %1 is a palindrome, the index gets returned. Otherwise, the function calls itself with the sum and the incremented index. The outer function initializes the index with zero.

A sample:

repl=> ((fn[x](#(let[r(bigint(apply str(reverse(str %1))))](if(= %1 r)%2(recur(+ %1 r)(inc %2))))x 0)) 1186060307891929990)
261

Answer 13

Boost.Build, 304 bytes

Not really a language. Still cool.

import sequence ;
import regex ;
rule r ( n ) {
m = "([0-9]?)" ;
return [ sequence.join [ sequence.reverse [ regex.match "$(m)$(m)$(m)$(m)$(m)$(m)$(m)$(m)$(m)" : $(n) ] ] : "" ] ;
}
rule x ( n ) {
i = 0 ;
while $(n) != [ r $(n) ] {
n = [ CALC $(n) + [ r $(n) ] ] ;
i = [ CALC $(i) + 1 ] ;
}
echo $(i) ;
}

Pretty straightforward, other than the elaborate regex-based hack I used to reverse the string.

Answer 14

Ruby, 44

f=->n{n==(r=n.to_s.reverse.to_i)?0:f[n+r]+1}

Needs Ruby 1.9 or higher for -> lambda syntax.