22
\$\begingroup\$

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 , so make your code as short as possible!
  • Relevant sequence: A072140
\$\endgroup\$
  • \$\begingroup\$ Related. Related. \$\endgroup\$ – Martin Ender Jun 30 '16 at 14:28
  • \$\begingroup\$ An interesting note: it is possible to construct an arbitrarily long integer with a looping period of 2, as described in the comments on A072141. The method is identical for other periods as well, like 12, 14, 17, and 22. \$\endgroup\$ – mbomb007 Jun 30 '16 at 16:17

20 Answers 20

18
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Nice use of the auto-fill variables! \$\endgroup\$ – FryAmTheEggman Jun 30 '16 at 14:47
  • 1
    \$\begingroup\$ *abuse – – – – – \$\endgroup\$ – Leaky Nun Jun 30 '16 at 14:48
  • \$\begingroup\$ How does that work, for someone that does not know Pyth? \$\endgroup\$ – Fatalize Jun 30 '16 at 14:54
  • 3
    \$\begingroup\$ how is pyth so short yet still in ASCII range ._. \$\endgroup\$ – Downgoat Jun 30 '16 at 16:36
  • 3
    \$\begingroup\$ @Downgoat Because it is pyth. \$\endgroup\$ – Leaky Nun Jun 30 '16 at 16:37
11
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

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 × 10k - 1 positive integers n with k digits.

  2. The difference of a number and its reverse is always a multiple of 9, so only 10k - 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 × 10k - 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 × 10k - 2 + 9 × 10k - 2 + … ≤ 10k - 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.
\$\endgroup\$
  • 11
    \$\begingroup\$ Did Pyth beat Jelly? \$\endgroup\$ – Leaky Nun Jun 30 '16 at 15:24
  • 3
    \$\begingroup\$ Well, it's a tie. \$\endgroup\$ – Dennis Jun 30 '16 at 21:48
  • \$\begingroup\$ These ain't no bytes. \$\endgroup\$ – mik Jul 1 '16 at 18:25
  • 1
    \$\begingroup\$ @mik Please click the bytes link in the header. \$\endgroup\$ – Dennis Jul 1 '16 at 18:31
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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"?

\$\endgroup\$
4
\$\begingroup\$

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 × 10k - 1 positive integers n with k digits.

  2. The difference of a number and its reverse is always a multiple of 9, so only 10k - 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 × 10k - 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 × 10k - 2 + 9 × 10k - 2 + … ≤ 10k - 1 ≤ n iterations to enter a loop or reach 0.

\$\endgroup\$
4
\$\begingroup\$

CJam, 15 13 bytes

ri_{_sW%i-z}*

Test it here.

Same as my Mathematica answer.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ That's officially a (nice) abuse of infinite recursion. \$\endgroup\$ – Leaky Nun Jun 30 '16 at 14:51
  • \$\begingroup\$ return a and rev(a) \$\endgroup\$ – Leaky Nun Jun 30 '16 at 14:52
  • 3
    \$\begingroup\$ Isn't it possible to get a RuntimeError due to the recursion being very long without it being necessarily infinite? \$\endgroup\$ – Fatalize Jun 30 '16 at 14:53
  • \$\begingroup\$ a=[n-x,x-n][n>x] \$\endgroup\$ – Leaky Nun Jun 30 '16 at 14:55
  • \$\begingroup\$ You can shorten it drastically: def rev(n):a=abs(n-int(str(n)[::-1]));return a and rev(a). Also, name the method something short (like r instead of rev) \$\endgroup\$ – shooqie Jun 30 '16 at 15:02
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I believe print n<1 works (since n is always non-negative) and it saves a byte \$\endgroup\$ – NonlinearFruit Jun 30 '16 at 17:55
  • \$\begingroup\$ def f(n,L=[]):¶ if n<1or n in L:print n<1¶ else:f(abs(n-int(`n`[::-1])),L+[n]) saves 5 bytes \$\endgroup\$ – Leaky Nun Jul 1 '16 at 7:45
3
\$\begingroup\$

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Â-Ä
\$\endgroup\$
  • \$\begingroup\$ Okay, this is a bit of a weird golf but DFÂ-Ä works in version 7.9 but not in the current version. In the current version, you need to convert it to an int first (like this DFÂï-Ä), but you can use version 7.9 to make it 5 bytes :p. \$\endgroup\$ – Adnan Jul 1 '16 at 18:00
  • \$\begingroup\$ @Adnan I can't believe I forgot about the bifurcation function. I'll stick to the current version though. You could post the 7.9 one as a separate answer if you'd like. Otherwise I'll put it as a note. \$\endgroup\$ – Emigna Jul 1 '16 at 18:06
  • \$\begingroup\$ I probably won't post it, since it's just 1 byte away from this answer :p. \$\endgroup\$ – Adnan Jul 1 '16 at 18:42
1
\$\begingroup\$

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;}
\$\endgroup\$
  • \$\begingroup\$ Noting that I've seen imports and functions done before. example \$\endgroup\$ – Poke Jun 30 '16 at 15:10
  • \$\begingroup\$ Is 1 truthy ? \$\endgroup\$ – Leaky Nun Jun 30 '16 at 15:15
  • 1
    \$\begingroup\$ @LeakyNun 1 isn't considered truthy in java but OP lists (True,1) and (False,0) as acceptable outputs. \$\endgroup\$ – Poke Jun 30 '16 at 15:16
  • \$\begingroup\$ @LeakyNun Does Java even have a sense of truthy or falsy? \$\endgroup\$ – Neil Jun 30 '16 at 20:35
  • \$\begingroup\$ @Neil Java has a sense of leveraging synergistic opportunities in vertical market contexts -- that's it \$\endgroup\$ – cat Jun 30 '16 at 23:12
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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 )

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 31 29 bytes

perl -pe'for$x(1..$_){$_=abs$_-reverse}'

perl -pe'eval"\$_=abs\$_-reverse;"x$_'

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.

New version uses eval and x repeat operator instead of for loop.

\$\endgroup\$
  • \$\begingroup\$ Nice answer, and welcome to PPCG! Note that for Perl, command-line options must be included in your byte-count, so this isn't quite 30 bytes. \$\endgroup\$ – AdmBorkBork Jul 1 '16 at 19:04
  • \$\begingroup\$ @TimmyD ok, +1 for -p option, -l is not necessary for a single input \$\endgroup\$ – mik Jul 1 '16 at 19:24
0
\$\begingroup\$

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)
\$\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.