18
\$\begingroup\$

\$ 1089 \$ is a very special number. To prove why, select any 3-digit number whose first and last digits differ by at least 2. Then, reverse the digits, and take the difference of these two numbers. Reverse the digits once more, and add these two numbers together. You will get \$ 1089 \$. The magic is left as an exercise to the reader.

Taking this a step further, let's define an algorithm for all possible integers:

  • Choose any positive integer \$ n \$
  • Reverse the digits of \$ n \$, and call it \$ x \$
  • Set \$ n \$ equal to \$ n - x \$ if \$ x < n \$, and \$ n + x \$ otherwise
  • Repeat the above step until \$ n \$ reaches a number it has already visited

In turns out that this algorithm gets stuck in an infinite loop, for certain numbers. Let's call a number 1089-able™, if it does in fact terminate (in other words, a duplicate is reached at some point). For example, everyone's favorite number, 2022, is 1089-able™:

2022 + 2202 ->
4224 + 4224 ->
8448 + 8448 ->
16896 + 69861 ->
86757 - 75768 ->
10989 + 98901 ->
109890 - 98901 ->
10989 (*)

In this challenge, you are given a positive integer, and are required to determine whether it is 1089-able™. This is , so the shortest solution in bytes wins.

The first 50 non-1089-able™ numbers are as follows:

[10057, 10118, 10168, 10254, 10458, 10598, 10698, 10798, 10898, 11047, 11108, 11158, 11244, 11448, 11499, 11588, 11688, 11788, 11888, 11998, 11999, 12037, 12148, 12234, 12438, 12489, 12578, 12678, 12778, 12878, 12988, 12989, 13027, 13138, 13224, 13428, 13479, 13568, 13668, 13768, 13868, 13978, 13979, 14017, 14128, 14198, 14214, 14418, 14469, 14558]
\$\endgroup\$
13
  • 1
    \$\begingroup\$ Is it a valid format to have a max recursion depth error when it's not 1089-able? \$\endgroup\$
    – Steffan
    Apr 22 at 3:11
  • 1
    \$\begingroup\$ @Steffan I'd say no, because if your recursion depth is infinite, it would run forever. On the other hand, if it were finite, even a 1089-able number can encounter such an error. \$\endgroup\$ Apr 22 at 3:28
  • 1
    \$\begingroup\$ @Steffan codegolf.meta.stackexchange.com/questions/24411/… \$\endgroup\$
    – allxy
    Apr 22 at 5:22
  • 3
    \$\begingroup\$ Is it actually a decidable problem? Unless one studies the problem, there is no guarantee that a given solution is correct for all numbers, and not just the tested ones. \$\endgroup\$
    – Matteo C.
    Apr 22 at 9:53
  • 6
    \$\begingroup\$ I was sure this was gonna be a question about tax forms. \$\endgroup\$
    – qwr
    Apr 23 at 0:08

6 Answers 6

7
\$\begingroup\$

Python, 117 bytes

def f(n):
    v={n}
    while 1:
        x=int(str(n)[::-1]);n-=[-x,x][x<n]
        if n in v:return 1
        if n/100in v:return 0
        v|={n}

Attempt This Online!

It works for all positive integers less or equal to the 50th non-1089-able™ number.

Haven't proven that it works for numbers greater than 14558.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ use a recursive lambda for 88 bytes \$\endgroup\$
    – friddo
    Apr 22 at 11:11
  • 1
    \$\begingroup\$ 87 bytes based on @friddo's version by changing the if else (and with n-[-(x:=int(str(n)[::-1])),x][x<n] instead of n+(r:=int(str(n)[::-1]))-2*r*(n>r) to more closely resemble your original answer - although both are the same byte-count, so not too important). \$\endgroup\$ Apr 22 at 12:49
  • 1
    \$\begingroup\$ 79 bytes based on @KevinCruijssen's version. \$\endgroup\$
    – ovs
    Apr 22 at 13:36
  • 1
    \$\begingroup\$ -1 byte from @ovs': Try it online! \$\endgroup\$
    – pxeger
    Apr 22 at 15:56
5
\$\begingroup\$

Python, 162 136 128 bytes

def h(n,e=0):e=(e or[])+[n];n+=(x:=int(str(n)[::-1]),-x)[x<n];return f"1089{(len(z:=str(n))-7)*'9'}099"!=z and(n in e or h(n,e))

Attempt This Online!

Haven't proven that it works for non-1089-able™ numbers past the first 50.

-26 bytes thanks to benrg and ovs (and for pointing out the rules with reusable functions)

-8 bytes thanks to Jo King

\$\endgroup\$
3
  • 2
    \$\begingroup\$ n+=(x:=int(str(n)[::-1]),-x)[x<n] is a bit shorter. I think the last three lines can be just return f"1089{(len(z:=str(n))-7)*'9'}099"!=z and(n in e or h(n,e)) (no need to test the length of z, it'll compare unequal anyway) \$\endgroup\$
    – benrg
    Apr 22 at 6:20
  • 6
    \$\begingroup\$ Functions have to be reusable, and requiring an additional input is not allowed. But this can be fixed without costing bytes: def h(n,*e):, e+=n, and return h(n,*e) save two bytes even. \$\endgroup\$
    – ovs
    Apr 22 at 7:49
  • 1
    \$\begingroup\$ the first statement can be replaced with e=(e or[])+[n] \$\endgroup\$
    – Jo King
    Apr 26 at 2:39
3
\$\begingroup\$

Retina, 70 bytes

^
$($^$%')*_;$%'*_¶
^(_+);\1\B|;

_+
$.&
D^`
/^./}s`^1099+8900+¶.+

^¶

Try it online! Link only includes two test cases as it's too slow otherwise. Explanation:

^
$($^$%')*_;$%'*_¶

Take the first number and its reverse and convert them both to unary with the reversed number first.

^(_+);\1\B|;

Subtract the two numbers of the second is larger otherwise add them.

_+
$.&

Convert back to decimal.

D^`

Delete the total if it's been seen before.

s`^1099+8900+¶.+

But delete the entire buffer if the value will increase infinitely.

/^./}`

Repeat until at least the current total was deleted.

Check to see whether an infinite loop was detected.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I've verified that the algorithm is valid up to a billion, although since Retina calculates via string manipulation you'll probably find that it can't actually deal with values that high in practice. \$\endgroup\$
    – Neil
    Apr 23 at 14:32
3
\$\begingroup\$

Javascript, 149 145 137 128 bytes

c=n=>{a=[n];while(n){x=+[...''+n].reverse().join``;n=x<n?n-x:n+x;if(a[i='includes'](n))return 1;if(a[i](n/100))break;a.push(n)}}
  • Thanks to @Radvylf Programs for saving 4 bytes!
  • Saved 8 bytes replacing return false with break now that the loop is wrapped
  • Thanks to @Steffan for saving 9 bytes!

Try me online.

Javascript, 171 bytes (readable)

c=n=>{
    a = [n]
    while(n){
        x=+n.toString().split('').reverse().join('')
        n=x<n?n-x:n+x
        if(a.includes(n)) return true
        if(a.includes(n/100)) break
        a.push(n)
    }
}

Try me online.

A good chunk of the bytes in this are coming from included functions .reverse(), .includes(), etc. Have not tested past the 50 provided.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Welcome to Code Golf! You can save a few bytes with .split`` and .join``, which abuse tagged template strings. \$\endgroup\$ Apr 23 at 2:59
  • 1
    \$\begingroup\$ also, (''+n).split`` can be [...''+n] \$\endgroup\$
    – Steffan
    Apr 23 at 3:43
  • 1
    \$\begingroup\$ also, instead of the first a.includes, you can do a[i='includes'], and then on the second a.includes, you can do a[i] to shave off a byte \$\endgroup\$
    – Steffan
    Apr 23 at 3:46
  • 2
    \$\begingroup\$ you can also return 1 instead of return true \$\endgroup\$
    – Steffan
    Apr 23 at 3:47
  • 1
    \$\begingroup\$ @David it uses the spread operator, which spreads the string out into a list. \$\endgroup\$
    – Steffan
    Apr 25 at 18:54
2
\$\begingroup\$

Ruby, 84 bytes

->n,*r{q=0;1while(r!=r|=[n+=(w=n.digits.join.to_i)*(w<n ?-1:1)])&&q=[]!=[n/100]-r;q}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Javascript, 94 87 bytes

f=(n,s={},x=+[...``+n].reverse().join``,m=x<n?n-x:n+x)=>s[m]?!!(m-11e12+11):f(s[m]=m,s)

How it works!

If the function does get stuck in a forever loop it will max out at the magic number 11e12+11 and this function returns the result minus that number casted to a boolean.

Try it online!

\$\endgroup\$
1

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.