The reverse-then-add (RTA) sequence is a sequence obtained by adding a number to its reverse, and repeating the process on the result. For eg.,

$$ 5 + 5 = 10 \Rightarrow 10 + 01 = 11 \Rightarrow 11 + 11 = 22 \Rightarrow 22 + 22 = 44 \Rightarrow\text{ }... $$

Thus, 5's RTA sequence contains 10, 11, 22, 44, 88, 176, etc.

The RTA root of a number \$n\$ is the smallest number that is either equal to \$n\$ or gives raise to \$n\$ in its RTA sequence.

For eg., 44 is found in the RTA sequence of 5, 10, 11, 13, 22, 31, etc. Of these, 5 is the smallest, and hence RTAroot(44) = 5.

72 is not part of any number's RTA sequence, and so is considered its own RTA root.

Input is a positive integer in a range that your language can naturally handle.

Output is the RTA root of the given number, as defined above.

Test cases








Related OEIS: A067031. The output will be a number from this sequence.


19 Answers 19


Perl 6 Raku, 45 44 39 bytes


Try it online!


{                                   }  # Anonymous code block
 +(1...                            )     # Find the first integer
       {                          }      # Where
        $_∈                              # The input is an element of
           (              ...    )         # A sequence defined by
            $^b,                           # The first element is the number we're checking
                {$_+.flip}                 # Each element is the previous element plus its reverse
                             *>$_          # The last element is larger than the input
  • 5
    \$\begingroup\$ The Perl 6 ellipsis syntax gets more magical every time I come across it. That lambda-based sequence specification is such a neat idea! \$\endgroup\$
    – Sundar R
    Commented Aug 11, 2018 at 17:06
  • 1
    \$\begingroup\$ @sundar, that syntax was actually one of the main reasons why I came over to Perl 6. (and why, after some time, it became my most favorite language) \$\endgroup\$
    – Ramillies
    Commented Aug 12, 2018 at 14:11

Brachylog, 24 22 bytes

  • 2 bytes thanks to sundar noticing that I had a {{ and }}


                --  f(n):
                --      g(x):
 {              --          h(y):
  ~             --              get z where k(z) = y
   {            --              k(z):
    ℕ≤.         --                  z>=0 and z<=k(z) (constrain so it doesn't keep looking)
    &≜          --                  label input (avoiding infinite stuff)
      ↔;?+      --                  return z+reverse(z)
   }            --
    {           --                  
     |↰₁        --              return z and h(z) (as in returning either)
    }           --                  
  |             --          return h(x) or x (as in returning either)
 }              --
ᶠ               --      get all possible answers for g(n)
  ⌋             --      return smallest of them

sorry for the wonky explanation, this is the best i could come up with

Try it online!

  • 1
    \$\begingroup\$ The use of {|↰₁} there is simple but brilliant. Good work! \$\endgroup\$
    – Sundar R
    Commented Aug 11, 2018 at 16:40

Haskell, 59 57 bytes

-2 bytes thanks to user1472751 (using a second until instead of list-comprehension & head)!

f n=until((n==).until(>=n)((+)<*>read.reverse.show))(+1)1

Try it online!


This will evaluate to True for any RTA-root:

(n==) . until (n<=) ((+)<*>read.reverse.show)

The term (+)<*>read.reverse.show is a golfed version of

\r-> r + read (reverse $ show r)

which adds a number to itself reversed.

The function until repeatedly applies (+)<*>read.reverse.show until it exceeds our target.

Wrapping all of this in yet another until starting off with 1 and adding 1 with (+1) will find the first RTA-root.

If there is no proper RTA-root of n, we eventually get to n where until doesn't apply the function since n<=n.

  • 1
    \$\begingroup\$ You can save 2 bytes by using until for the outer loop as well: TIO \$\endgroup\$
    – colossus16
    Commented Aug 14, 2018 at 19:06

05AB1E, 7 bytes

Using the new version of 05AB1E (rewritten in Elixir).



Try it online!


L           # Create the list [1, ..., input]
 .Δ         # Iterate over each value and return the first value that returns a truthy value for:
   λ        #   Where the base case is the current value, compute the following sequence:
     Â+     #   Pop a(n - 1) and bifurcate (duplicate and reverse duplicate) and sum them up.
            #   This gives us: a(0) = value, a(n) = a(n - 1) + reversed(a(n - 1))
    j       #   A λ-generator with the 'j' flag, which pops a value (in this case the input)
            #   and check whether the value exists in the sequence. Since these sequences will be 
            #   infinitely long, this will only work strictly non-decreasing lists.
  • \$\begingroup\$ Wait.. j has a special meaning in a recursive environment? I only knew about the through and the λ itself within the recursive environment. Are there any more besides j? EDIT: Ah, I see something about £ as well in the source code. Where is it used for? \$\endgroup\$ Commented Feb 6, 2019 at 13:22
  • 1
    \$\begingroup\$ @KevinCruijssen Yes, these are flags used in the recursive environment. j essentially checks whether the input value is in the sequence. £ makes sure it returns the first n values of the sequence (same as λ<...>}¹£). \$\endgroup\$
    – Adnan
    Commented Feb 7, 2019 at 11:46

Jelly, 12 11 bytes


This is a full program. Run time is roughly quadratic; test cases \$999\$ and \$1111\$ time out on TIO.

Thanks to @JonathanAllan for golfing off 1 byte!

Try it online!

How it works

ṚḌ+ƊС€œi¹Ḣ  Main link. Argument: n

      €      Map the link to the left over [1, ..., n].
    С         For each k, call the link to the left n times. Return the array of k
               and the link's n return values.
   Ɗ           Combine the three links to the left into a monadic link. Argument: j
Ṛ                Promote j to its digit array and reverse it.
 Ḍ               Undecimal; convert the resulting digit array to integer.
  +              Add the result to j.
       œi¹   Find the first multindimensional index of n.
          Ḣ  Head; extract the first coordinate.

Ruby, 66 57 bytes

f=->n{(1..n).map{|m|m+(m.digits*'').to_i==n ?f[m]:n}.min}

Try it online!

Recursive function that repeatedly "undoes" the RTA operation until arriving at a number that can't be produced by it, then returns the minimum.

Instead of using filter, which is long, I instead simply map over the range from 1 to the number. For each m in this range, if m + rev(m) is the number, it calls the function recursively on m; otherwise, it returns n. This both removes the need for a filter and gives us a base case of f(n) = n for free.

Highlights include saving a byte with Integer#digits:


The last one would be a byte shorter, but sadly, Ruby parses numbers starting with 0 as octal.


Python 2, 70 bytes

f=lambda n,i=1,k=1:i*(k==n)or f(n,i+(k>n),[k+int(`k`[::-1]),i+1][k>n])

Try it online!


Pyth, 12 bytes


Check out a test suite!

Surprisingly fast and efficient. All the test cases ran at once take less than 2 seconds.

How it works

fqQ.W<HQ+s_` – Full program. Q is the variable that represents the input.
f            – Find the first positive integer T that satisfies a function.
   .W        – Functional while. This is an operator that takes two functions A(H)
               and B(Z) and while A(H) is truthy, H = B(Z). Initial value T.
     <HQ     – First function, A(H) – Condition: H is strictly less than Q.
        +s_` – Second function, B(Z) – Modifier.
         s_` – Reverse the string representation of Z and treat it as an integer.
        +    – Add it to Z.
             – It should be noted that .W, functional while, returns the ending
               value only. In other words ".W<HQ+s_`" can be interpreted as
               "Starting with T, while the current value is less than Q, add it
               to its reverse, and yield the final value after the loop ends".
 qQ          – Check if the result equals Q.

05AB1E, 13 bytes


Try it online!


L               # push range [1 ... input]
 ʒ         }    # filter, keep elements that are true under:
  IF   }        # input times do:
    D           # duplicate
     Â+         # add current number and its reverse
        )       # wrap in a list
         Iå     # check if input is in the list
            н   # get the first (smallest) one
  • \$\begingroup\$ Smart! I know my 21 bytes version was already way too long (which I've golfed to 16 with the same approach), but couldn't really figure out a way to do it shorter. Can't believe I haven't thought about using head after the filter.. I kept trying to use the loop index+1, or the global_counter.. >.> \$\endgroup\$ Commented Aug 12, 2018 at 14:40

JavaScript (ES6), 61 bytes


Try it online!


n =>                        // n = input
  (g = k =>                 // g() = recursive function taking k = current value
    k - n ?                 //   if k is not equal to n:
      g(                    //     do a recursive call:
        k > n ?             //       if k is greater than n:
          ++x               //         increment the RTA root x and restart from there
        :                   //       else (k is less than n):
          +[...k + '']      //         split k into a list of digit characters
          .reverse().join`` //         reverse, join and coerce it back to an integer
          + k               //         add k
      )                     //     end of recursive call
    :                       //   else (k = n):
      x                     //     success: return the RTA root
  )(x = 1)                  // initial call to g() with k = x = 1

05AB1E, 21 16 15 bytes


-1 byte thanks to @Emigna.

Try it online.


G               # Loop `N` in the range [1, input):
 ¼              #  Increase the global_counter by 1 first every iteration (0 by default)
 N              #  Push `N` to the stack as starting value for the inner-loop
  ¹F            #  Inner loop an input amount of times
    Â           #   Bifurcate (short for Duplicate & Reverse) the current value
                #    i.e. 10 → 10 and '01'
     +          #   Add them together
                #    i.e. 10 and '01' → 11
      Ð         #   Triplicate that value
                #   (one for the check below; one for the next iteration)
       ¹Qi      #   If it's equal to the input:
          ¾     #    Push the global_counter
           q    #    And terminate the program
                #    (after which the global_counter is implicitly printed to STDOUT)
]               # After all loops, if nothing was output yet:
 ¹              # Output the input
  • \$\begingroup\$ You don't need the print due to implicit printing. \$\endgroup\$
    – Emigna
    Commented Aug 13, 2018 at 7:27

Charcoal, 33 bytes


Try it online! Link is to verbose version of code. Explanation:


Input \$q\$.


Assign \$2q\$ to \$h\$ so that the loop starts.


Repeat while \$h>q\$:


push a dummy null string to \$u\$ thus increasing its length, and assign the resulting length to \$h\$;


repeat while \$h<q\$:


add the reverse of \$h\$ to \$h\$.


Print the final length of \$u\$ which is the desired root.


MATL, 17 bytes


Try it online!


`         % Do...while loop
  @       %   Push iteration index, k (starting at 1)
  G:"     %   Do as many times as the input
    tt    %     Duplicate twice
    VPU   %     To string, reverse, to number
    +     %     Add
  ]       %   End
  v       %   Concatenate all stack into a column vector. This vector contains
          %   a sufficient number of terms of k's RTA sequence
  G-      %   Subtract input. This is used as loop condition, which is falsy
          %   if some entry is zero, indicating that we have found the input
          %   in k's RTA sequence
}         % Finally (execute on loop exit)
  @       %   Push current k
          % End (implicit). Display (implicit)
  • 1
    \$\begingroup\$ Just as a side note, I used MATL to generate the test case outputs, using this 31 byte version: :!`tG=~yV2&PU*+tG>~*tXzG=A~]f1) Try it online! \$\endgroup\$
    – Sundar R
    Commented Aug 12, 2018 at 12:12

Java 8, 103 bytes

n->{for(int i=0,j;;)for(j=++i;j<=n;j+=n.valueOf(new StringBuffer(j+"").reverse()+""))if(n==j)return i;}

Try it online.


n->{                // Method with Integer as both parameter and return-type
  for(int i=0,j;;)  //  Infinite loop `i`, starting at 0
    for(j=++i;      //  Increase `i` by 1 first, and then set `j` to this new `i`
        j<=n        //  Inner loop as long as `j` is smaller than or equal to the input
        ;           //    After every iteration:
         j+=        //     Increase `j` by:
            n.valueOf(new StringBuffer(j+"").reverse()+""))
                    //     `j` reversed
     if(n==j)       //   If the input and `j` are equal:
       return i;}   //    Return `i` as result

Arithmetically reversing the integer is 1 byte longer (104 bytes):

n->{for(int i=0,j,t,r;;)for(j=++i;j<=n;){for(t=j,r=0;t>0;t/=10)r=r*10+t%10;if((j+=r)==n|i==n)return i;}}

Try it online.


C (gcc), 120 100 99 bytes

f(i,o,a,b,c,d){for(a=o=i;b=a;o=i/b?a:o,a--)for(;b<i;b+=c)for(c=0,d=b;d;d/=10)c=c*10+d%10;return o;}

Try it online!

Given input i, checks every integer from i to 0 for a sequence containing i.

  • i is the input value
  • o is the output value (the minimum root found so far)
  • a is the current integer being checked
  • b is the current element of a's sequence
  • c and d are used to add b to its reverse
  • \$\begingroup\$ Compiling with -DL=for would save you 2 bytes. \$\endgroup\$
    – user77406
    Commented Aug 13, 2018 at 9:44
  • \$\begingroup\$ Scratch that; doing math wrong. \$\endgroup\$
    – user77406
    Commented Aug 13, 2018 at 10:00
  • \$\begingroup\$ However, you can return the output value with i=o; if you use -O0, saving you 5 bytes. \$\endgroup\$
    – user77406
    Commented Aug 13, 2018 at 10:05

Japt, 16 15 11 bytes


Try it

@ÇX±swÃøU}a     :Implicit input of integer U
@        }a     :Loop over the positive integers as X & output the first that returns true
 Ç              :  Map the range [0,U)
  X±            :    Increment X by
    sw          :    Its reverse
      Ã         :  End map
       øU       :  Contains U?

Physica, 57 bytes

Credit for the method goes to Doorknob.


Try it online!


C (gcc), 89 bytes

I run each sequence in [1,n) until I get a match; zero is special-cased because it doesn't terminate.


Try it online!


Husk, 9 bytes


Try it online!

first element in natural numbers which has an infinite list that contains the input.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.