22
\$\begingroup\$

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.

\$\endgroup\$

18 Answers 18

13
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 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 - Reinstate Monica Aug 11 '18 at 17:06
  • \$\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 Aug 12 '18 at 14:11
7
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ The use of {|↰₁} there is simple but brilliant. Good work! \$\endgroup\$ – sundar - Reinstate Monica Aug 11 '18 at 16:40
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save 2 bytes by using until for the outer loop as well: TIO \$\endgroup\$ – user1472751 Aug 14 '18 at 19:06
5
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
  • \$\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\$ – Kevin Cruijssen Feb 6 '19 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 Feb 7 '19 at 11:46
3
\$\begingroup\$

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.
   Ɗ           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.
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\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\$ – Kevin Cruijssen Aug 12 '18 at 14:40
2
\$\begingroup\$

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
          + 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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 21 16 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'
     +          #   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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You don't need the print due to implicit printing. \$\endgroup\$ – Emigna Aug 13 '18 at 7:27
1
\$\begingroup\$

Charcoal, 33 bytes

Nθ≔⊗θηW›ηθ«≔L⊞OυωηW‹ηθ≧⁺I⮌Iηη»ILυ

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

Nθ

Input \$q\$.

≔⊗θη

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

W›ηθ«

Repeat while \$h>q\$:

≔L⊞Oυωη

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

W‹ηθ

repeat while \$h<q\$:

≧⁺I⮌Iηη

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

»ILυ

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
    +     %     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)
| improve this answer | |
\$\endgroup\$
  • 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 - Reinstate Monica Aug 12 '18 at 12:12
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

Japt, 16 15 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?
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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