Reverse and subtract

Question

Challenge description

Let's take a positive integer n, reverse its digits to get rev(n) and get the absolute value of the difference of these two numbers: |n - rev(n)| (or abs(n - rev(n))).

Example:

n = 5067 
rev(n) = 7605
|n - rev(n)| = |5067 - 7605| = |-2538| = 2538

After repeating this operation sufficiently many times, most numbers will become 0 (thus terminating the loop)...

5067 -> 2538 -> 5814 -> 1629 -> 7632 -> 5265 -> 360 -> 297 -> 495 -> 99 -> 0

...though some numbers (like 1584) get stuck in an infinite loop:

1584 -> 3267 -> 4356 -> 2178 -> 6534 -> 2178 -> 6534 -> 2178 -> 6534 -> ...
                        ^ infinite loop starts here

Your job is to determine if a given integer gets stuck in an infinite loop.

Input description

A positive integer.

Output description

A truthy value (True, 1) if the number gets stuck in an infinite loop, a falsy value (False, 0) otherwise.

Notes

• Trailing zeroes should be ommited. i.e. rev(5020) = 205.
• Remember that this is code-golf, so make your code as short as possible!
• Relevant sequence: A072140

Answer 1

Pyth, 5 bytes

4 bytes thanks to FryAmTheEggman

uas_`

Test suite.

The truthy value is one of the numbers in the loop.

The falsey value is 0.

Explanation

uas_`      Input:Q
uas_`GGQ   Implicit filling of variables.

u      Q   Set G as Q: do this repeatedly until result seen before: Set G as
 a             the absolute difference of
     G             G
    `              convert to string
   _               reverse
  s                convert to integer
      G        and G

Answer 2

Jelly, 6 5 bytes

ṚḌạµ¡

Try it online!

Background

This uses @MartinEnder's upper bound of 10n iterations and the following observations.

1. There are 9 × 10^{k - 1} positive integers n with k digits.

2. The difference of a number and its reverse is always a multiple of 9, so only 10^{k - 1} of them can occur after the first iteration.

3. Of the multiples, more than 1 / 10 will lose a digit in the next iteration (for starters, all that start and end with the same digits, and roughly twice as many if the first digit is neither a 1 nor a 9), so it takes at most 9 × 10^{k - 2} to either enter a loop or lose a digit.

4. Applying the same reasoning to the eventual resulting integer of k - 1 digits and so on, it takes at most 9 × 10^{k - 2} + 9 × 10^{k - 2} + … ≤ 10^{k - 1} ≤ n iterations to enter a loop or reach 0.

How it works

ṚḌạµ¡  Main link. Argument: n

   µ¡  Iteratively apply the chain to the left n times.
Ṛ      Reverse n (casts to digits).
 Ḍ     Undecimal; convert from base 10 to integer.
  ạ    Take the absolute difference of the result and the argument.

Answer 3

Mathematica, 39 37 bytes

Nest[Abs[#-IntegerReverse@#]&,#,#]<1&

Simply applies the reverse/subtract transformation n times to the input n and then checks whether the result is 0. It can never take more than 10n steps to reach a loop, because the transformation cannot increase the number of digits, and there are less than 10n numbers with no more digits than n. See Dennis's proof for how to reduce this bound to n.

Answer 4

Oracle SQL 11.2, 136 bytes

WITH v(n)AS(SELECT :1 FROM DUAL UNION ALL SELECT ABS(n-REVERSE(n||''))FROM v WHERE n>0)CYCLE n SET c TO 0 DEFAULT 1 SELECT MIN(c)FROM v;

Un-golfed

WITH v(n) AS
(
  SELECT :1 FROM DUAL
  UNION ALL
  SELECT ABS(n-REVERSE(n||''))FROM v WHERE n>0 
) CYCLE n SET c TO 0 DEFAULT 1
SELECT MIN(c)FROM v

Answer 5

APL, 26 chars

0∘{⍵∊⍺:×⍵⋄(⍺,⍵)∇|⍵-⍎⌽⍕⍵}

We use the left argument as the accumulator of the values we've seen already. We initialise it to "0", which is one of the two termination conditions. The guard ⍵∊⍺:×⍵ is read: "is the right argument something we've seen already (and that includes zero)? If so return the sign of the number, that is 1 or 0". Otherwise let's recurse by calling ourselves with the absolute value of the subtraction after having catenated the current value to the left argument.

A recast of the Mathematica solution by Martin Ender would clock at 21 chars:

 {×{|⍵-⍎⌽⍕⍵}⍣(10×⍵)⊣⍵}

It reads: "what is the sign of the result after applying the wanted 10n times"?

Answer 6

Python 2, 50 bytes

n=input()
exec'n=abs(n-int(`n`[::-1]));'*n
print n

Test it on Ideone.

Background

This uses @MartinEnder's upper bound of 10n iterations and the following observations.

1. There are 9 × 10^{k - 1} positive integers n with k digits.

2. The difference of a number and its reverse is always a multiple of 9, so only 10^{k - 1} of them can occur after the first iteration.

3. Of the multiples, more than 1 / 10 will lose a digit in the next iteration (for starters, all that start and end with the same digits, and roughly twice as many if the first digit is neither a 1 nor a 9), so it takes at most 9 × 10^{k - 2} to either enter a loop or lose a digit.

4. Applying the same reasoning to the eventual resulting integer of k - 1 digits and so on, it takes at most 9 × 10^{k - 2} + 9 × 10^{k - 2} + … ≤ 10^{k - 1} ≤ n iterations to enter a loop or reach 0.

Answer 7

CJam, 15 13 bytes

ri_{_sW%i-z}*

Test it here.

Same as my Mathematica answer.

Answer 8

Python, 129 120 96 bytes

If a exception is caught (normally the only exception that can be throwed with this function is a RuntimeError, due to the infinite recursion), print 1. Otherwise, print the result, 0.

def r(n):a=abs(n-int(str(n)[::-1]));return a and r(a)
try:print(r(int(input())))
except:print(1)

Thanks to @LeakyNun
Thanks to @shooqie

Answer 9

Python, 101 98 bytes

Tortoise and hare algorithm.

Truthy is any value in loop, falsey is 0.

g=lambda n:abs(n-int(str(n)[::-1]))
def r(n):
    t=g(n);h=g(t)
    while t-h:h=g(g(h));t=g(t)
    return h

Ideone it!

Answer 10

Python 2, 85 84 83 bytes

L=[]
def f(n,L=L):
    if n<1or n in L:print n<1
    else:L+=[n];f(abs(n-int(`n`[::-1])))

Another Python answer. It adds n to a list for every iteration, and if n is already in the list, it outputs False. Otherwise, it works down to 0.

Thanks @NonlinearFruit for one byte.

Answer 11

05AB1E, 11 8 6 bytes

DFÂï-Ä

Explained

DF          # input number of times do
  Â         # push current number and its reverse
   ï-       # convert reverse to int and subtract
     Ä      # absolute value
            # implicitly print after loop ends

Truthy value is a number from the loop.
Falsy value is 0.

Try it online

Uses the upper bound explained in Dennis' Jelly answer

Saved 2 bytes thanks to @Adnan

In version 7.9 of 05AB1E the following 5-byte solutions works as noted by @Adnan

DFÂ-Ä

Answer 12

Brachylog, 49 32 23 bytes

:10*N,?:N:{r:?-+.}itT'0

Returns true for infinite loops and false otherwise.

This is a shameless adaptation of Martin Ender's algorithm.

Previous answer, 32 bytes

g{tTr:T-+U(0!\;?:ImU;?:[U]c:1&)}

Explanation of the previous answer

g{                             } Call predicate with [Input] as input
  tT                             T is the last element of Input
    r:T-                         Subtract T from the reverse of T
        +U                       U is the absolute value of T
          (0!\                   If U is 0, return false
              ;                  Or
               ?:ImU             If U is in Input, return true
                    ;            Or
                     ?:[U]c:1&)  Recursive call with U concatenated to the Input

Answer 13

Java 7, 161 bytes

This requires an import but I wrote it as a function. Yell at me in the comments if a full program is preferred in this scenario. Outputs 1 if there's an infinite loop and 0 if the value gets to 0.

import java.util.*;int z(int a){int o,r,c=a;Set s=new HashSet();while(c!=0){for(r=0,o=c;o!=0;r=r*10+o%10,o/=10);c=Math.abs(c-r);if(!s.add(c))return 1;}return 0;}

Answer 14

PowerShell v2+, 94 bytes

param($n)for($a=,0;){if(($n=[math]::Abs($n-(-join"$n"["$n".length..0])))-in$a){$n;exit}$a+=$n}

Takes input $n, starts an infinite for loop, with $a=,0 as the initial condition (this uses the comma operator to set $a to an array of one element, 0). This $a is our array of already-seen values.

Each loop iteration we check an if. The condition first sets the next value of $n using string-reversing and the [math]::Abs .NET call, and checks whether that value is already -in $a. If so, we output $n and exit. Otherwise, we add that value to the array and continue the loop.

Outputs 0 for input values where it does not go into an infinite loop (which is falsey in PowerShell) and outputs the value where the loop was encountered otherwise (non-zero integers are truthy). For example, outputs 2178 for input 1584.

Answer 15

Haskell, 65 bytes

_#0=0
a#n|elem n a=1|1<2=(n:a)#abs(n-(read$reverse$show n))
([]#)

Returns 0 for False and 1 for True. Usage example: ([]#) 1584 -> 1.

The obvious approach: keep a list with all results seen so far. Calculate the next number until 0 or it's in the list.

Answer 16

JavaScript (ES6), 75 bytes

f=(n,...a)=>a.includes(n=n<0?-n:n)?n:f([...n+``].reverse().join``-n,n,...a)

n<0?n=-n:n and n*=n>0||-1 also work. Algorithm somewhat resembles the PowerShell answer, although this is a recursive formulation.

Answer 17

Ruby, 57 bytes

->n,*h{h[n]=n=(n-"#{n}".reverse.to_i).abs until h[n];n>0}

The initially empty array h tracks previously hit values. We iterate the number until we hit a previous value, then check the value on the last iteration. Since 0 is a cycle of 1, it'll be 0 if and only if there's no larger cycle. I take an extra 2 bytes to convert this to a Boolean because 0 is truthy in Ruby.

Answer 18

Perl 6  58 53 33  30 bytes

sub {$/=%;$^a,{return ?1 if $/{$_}++;abs $_-.flip}...0;?0}
{$/=%;?($_,{last if $/{$_}++;abs $_-.flip}...0)[*-1]}
{?($_,{abs $_-.flip}...0)[10**$_]}

{?($_,{abs $_-.flip}...0)[$_]}

Explanation:

{ # block lambda with implicit parameter $_

  # coerce the following to Bool
  # ( False for Nil or 0, True otherwise )
  ?

  (

    $_, # start a sequence with the input

    # block lambda with implicit parameter $_
    # subtracts the previous value in the sequence and its reverse
    # ( .flip is short for $_.flip where a term is expected )
    { abs $_ - .flip } 

    ... # repeat that lambda
    0   # until you get 0

  # get the element indexed with the block's input
  # may be 0, Nil, or a number that is part of a repeating sequence
  )[ $_ ]
}

( relies on the previous observation that you only need to do this transformation at most n times )

Answer 19

Matlab, 89 84 bytes

n=input('');z=n;while n
z=abs(z-str2num(fliplr(num2str(z))));n=[n z]*all(n~=z);end
z

Simple approach - stacks all numbers and checks if a number appeared before.

Explanation

n=input('');z=n;  -- take input, initiate z
while n           -- n is said to be positive
z=abs(z-str2num(fliplr(num2str(z)))) -- calculate the "reverse and substract"
n=[n z]           -- put the value at the end of the vector
       *all(n~=z) -- make the n all zeroes if z is previously in the vector (break the loop)
end
z                 -- print z (0 when not entered loop, >0 otherwise)

Answer 20

Perl 5 -p, 25 bytes

eval'$_=abs$_-reverse'x$_

Try it online!

It iterates n=|n-rev(n)| n times, so output is 0 if there is no loop, >0 otherwise. Dennis already proved this is enough.