# RTA (Reverse-Then-Add) root of a number

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

Input
Output

44
5

72
72

132
3

143
49

1111
1

999
999


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

# Perl 6, 45 44 bytes

->\a{first {a∈($_,{$_+.flip}...*>a)},1..a}


Try it online!

### Explanation:

->\a{                                    }  # Anonymous code block
->\a     # That takes a number a
first  # Find the first element
1..a  # In the range 1 to a
{                       },    # Where
a∈       # a is an element of
(             ...   )  # A sequence defined by
$_, # The first element is the number we're checking {$_+.flip}  # Each element is the previous element plus its reverse
*>$a # The last element is larger than a  • The Perl 6 ellipsis syntax gets more magical every time I come across it. That lambda-based sequence specification is such a neat idea! – sundar - Reinstate Monica Aug 11 '18 at 17:06 • @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) – Ramillies Aug 12 '18 at 14:11 # Brachylog, 24 22 bytes {~{ℕ≤.&≜↔;?+}{|↰₁}|}ᶠ⌋  • 2 bytes thanks to sundar noticing that I had a {{ and }} # Explanation  -- 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! • The use of {|↰₁} there is simple but brilliant. Good work! – sundar - Reinstate Monica Aug 11 '18 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! ## Explanation 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.

• You can save 2 bytes by using until for the outer loop as well: TIO – user1472751 Aug 14 '18 at 19:06

# 05AB1E, 7 bytes

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

### Code

L.ΔλjÂ+


Try it online!

### Explanation

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.

• 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? – Kevin Cruijssen Feb 6 '19 at 13:22
• @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 λ<...>}¹£). – Adnan Feb 7 '19 at 11:46

# Jelly, 12 11 bytes

ṚḌ+ƊÐ¡€œi¹Ḣ


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.
Ṛ                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:

m.to_s.reverse.to_i
(m.digits*'').to_i
eval(m.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

fqQ.W<HQ+s_


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

LʒIFDÂ+})Iå}н


Try it online!

Explanation

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

• 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.. >.> – Kevin Cruijssen Aug 12 '18 at 14:40

# JavaScript (ES6), 61 bytes

n=>(g=k=>k-n?g(k>n?++x:+[...k+''].reverse().join+k):x)(x=1)


Try it online!

### Commented

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
)                     //     end of recursive call
:                       //   else (k = n):
x                     //     success: return the RTA root
)(x = 1)                  // initial call to g() with k = x = 1


# 05AB1E, 2116 15 bytes

G¼N¹FÂ+Ð¹Qi¾q]¹


-1 byte thanks to @Emigna.

Try it online.

Explanation:

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'
#    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

• You don't need the print due to implicit printing. – Emigna Aug 13 '18 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

@G:"ttVPU+]vG-}@


Try it online!

### Explanation

         % 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
]       %   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)

• 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! – sundar - Reinstate Monica Aug 12 '18 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.

Explanation:

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), 120100 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
• Compiling with -DL=for would save you 2 bytes. – user77406 Aug 13 '18 at 9:44
• Scratch that; doing math wrong. – user77406 Aug 13 '18 at 10:00
• However, you can return the output value with i=o; if you use -O0, saving you 5 bytes. – user77406 Aug 13 '18 at 10:05

# Japt, 1615 11 bytes

@ÇX±swÃøU}a


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.

F=>N:Min@Map[->m:N==m+Int[Str[m]{%%-1}]&&F@m||N;…[1;N]]


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.

j,k,l,m;r(i){for(j=k=0;k-i&&++j<i;)for(k=j;k<i;k+=m)for(l=k,m=0;l;l/=10)m=m*10+l%10;j=j;}


Try it online!