1

$s(x)$ is $x$ with digits sorted in increasing order, e.g. $s(452) = 245, s(604270) = 2467$.

$$f(x) = x - s(x)$$

Does applying $f(x)$ repeatedly for any non-negative integer always reach a sorted-digit number? (after which the next step is $0$ as the sorted version of an already sorted number is itself and $x - x = 0$)

Is there a way to mathematically predict how many steps it will take before reaching 0?

Here is a python program that shows the steps before reaching 0:

def s(x):
    return int("".join(sorted(list(str(x)))))

def f(x):
    yield x
    while x != 0:
        x = x - s(x)
        yield x


for step in f(int(input("> "))):
    print(step)
Bill Dubuque
  • 272,048
Wagner Martins
  • 537
  • 1
    Yes, it will always reach a "sorted-digit number" and this can be proven by induction. As for predicting how long it would take, I don't know of any effort into answering this question but it certainly does not seem easy. See https://oeis.org/A193582 – JMoravitz Apr 18 '23 at 14:05
  • 6
    You're subtracting a positive integer at each step, so of course you'll reach 0. – Karl Apr 18 '23 at 15:03
  • 1
    It's easier to see (by using @Karl's argument) that you'll reach $0$, than it is to see that you'll reach a "sorted-digit number" (but it's quite obvious that those are the only pre-images of $0$, so you must pass one. – Henrik supports the community Apr 19 '23 at 13:45

0 Answers0