05AB1E, 10 7 bytes

ΔZ>ö}N‚

-3 bytes thanks to @CommandMaster

Try it online or verify all test cases.

Explanation:

Δ      # Loop until the result no longer changes,
       # using the (implicit) input-integer initially:
  Z    #  Push the largest digit (without popping the integer)
   >   #  +1
    ö  #  Convert the number from base-10 to base-(maxDigit+1)
 }N    # After the loop: push the last 0-based index of the changes-loop
   ‚   # Pair the top two items together
       # (which is output implicitly as result)

x86-64 machine code, 45 bytes

97 31 C9 50 31 FF 8D 77 0A 99 F7 F6 39 FA 0F 47 FA F7 DA 52 85 C0 75 F1 FF C7 A9 F7 E7 01 F0 5E F7 DE 79 F7 01 C6 E0 DB F7 D1 89 CA C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes a 32-bit integer in EDI and returns two 64-bit integers in RAX and RDX.

This is based on my code for the single rebase, adding a loop and counting its iterations, with several other changes.

In assembly:

f:  xchg eax, edi   # Switch the number into EAX.
    xor ecx, ecx    # Set ECX to 0.
rA: push rax        # Save RAX (contains the current number) onto the stack.
    xor edi, edi    # Set EDI to 0 by XORing it with itself.
    lea esi, [rdi + 10] # Set ESI to 10.
r0: cdq             # Sign-extend EAX, setting up for the next instruction.
    div esi         # Divide by ESI (which is 10);
                    #  put the quotient in EAX and the remainder in EDX.
    cmp edx, edi    # Compare the remainder (a digit) to EDI.
    cmova edi, edx  # If the digit is greater, set EDI to that value.
    neg edx         # Negate the digit in EDX. (This will later help
                    #  distinguish the digits from the saved initial number.)
    push rdx        # Push RDX (contains EDX; a negated digit) onto the stack.
    test eax, eax   # Check the value of the quotient.
    jnz r0          # Jump back, to repeat, if it's nonzero.
    inc edi         # Add 1 to the highest digit (in EDI) to get the base.
    .byte 0xA9      # Bypass the next two instructions by absorbing them into
                    #  the 32-bit immediate operand of a TEST instruction.
r1: mul edi             # Multiply EAX by EDI.
    add eax, esi        # Add ESI to EAX.
    pop rsi         # Pop a value from the stack into RSI (contains ESI).
    neg esi         # Negate the value.
    jns r1          # Jump back, to repeat, if it's now nonnegative.
    add esi, eax    # Add the current number to the negated initial number.
    loopne rA       # Subtract 1 from RCX, and jump back if
                    #  the sum from the last instruction is nonzero
                    #  and RCX is nonzero (which is always true here).
    not ecx         # Invert all the bits of ECX, for the number of rebases.
    mov edx, ecx    # Move that value into EDX.
    ret             # Return.

R, 75 67 bytes

_{-8 bytes by Giuseppe}

g=\(n)`if`(n-(r=min(mapply(strtoi,n,2:10),na.rm=T)),g(r)+0:1,r*1:0)

Attempt This Online!

Google Sheets, 103 bytes

=let(f,lambda(f,n,i,let(m,decimal(n,1+sort(mid(n,row(A:A),1),1,)),if(n=m,{n,i},f(f,m,i+1)))),f(f,A2,0))

Prettified:

=let(
  f, lambda(f, n, i, let(
    m, decimal(n, 1 + sort(mid(n, row(A:A), 1), 1,)),
    if(n = m,
      { n, i },
      f(f, m, i + 1)
    )
  )),
  f(f, A2, 0)
)

Explained:

• f() is a recursive function that takes self, number n, counter i

• the next number m in the series is calculated by finding the base by separating digits in n, sorting them in descending order, and adding 1 to the first element in the resulting array, discarding the rest; n is then converted to decimal using that base

• if() tests whether n === m; if so, output n and the counter i

• if not, the function calls itself recursively with m and an incremented counter

Tested up to \$n = 677083325011\$ with the OEIS list.

This would be shorter as a named function because that way there's no need to add a reference to self in a recursive function signature.

Vyxal 3 -o, 8 bytes

⑶G›⊣lƵ,L

Vyxal It Online!

⑶G›⊣lƵ,L­⁡​‎‎⁡⁠⁡‏⁠⁠⁠‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁣⁡​‎‏​⁢⁠⁡‌­
⑶         # ‎⁡next 3 as a lambda:
 G        # ‎⁢maximum of the digits
  ›       # ‎⁣incremented
   ⊣      # ‎⁤digit from base ^ to 10
    l     # ‎⁢⁡apply the lambda repeatedly until fixpoint, collecting results
     Ƶ    # ‎⁢⁢get the tail and the rest below
      ,   # ‎⁢⁣print the tail (the fixpoint)
       L  # ‎⁢⁤get the length of the rest
# ‎⁣⁡-o flag prints the top of stack.
💎

Created with the help of Luminespire.

<script type="vyxal3">
⑶G›⊣lƵ,L,
</script>
<script>
    args=[["1011010"],["10201"],["12345"],["56789"],["8314"],["88"],["3"],["80852"]]
</script>
<script src="https://themoonisacheese.github.io/snippeterpreter/snippet.js" type="module"/>

Lua, 171 165 bytes

Since this is a sequel, I figured I ought to steal my old solution for this.

n=io.read()m=n i=-1repeat t={}n=tostring(m)n:gsub(".",function(c)table.insert(t,tonumber(c))end)i=i+1table.sort(t)m=tonumber(n,t[#t]+1)until n==tostring(m)print(m,i)

• Current version (io.read() instead of function)
• Original version

APL(NARS), 35 chars

{0{⍵=m←k⊥⍨1+⌈/k←⍎¨⍕⍵:⍵,⍺⋄(⍺+1)∇m}⍵}

Input one positive integer number, output 2 integers: the first is the result of all rebases, the second is the number times of rebases.

  f←{0{⍵=m←k⊥⍨1+⌈/k←⍎¨⍕⍵:⍵,⍺⋄(⍺+1)∇m}⍵}
  f 1011010
90 1 
  f 10201
4 2 
  f 12345
293 4 
  f 56789
56789 0 
  f 8314
19 6 
  f 88
3 8 
  f 3
3 0 
  f 80852
3 18 

Vyxal, 9 bytes

fG›β)ẋ÷!"

Try it Online!

Explained

fG›β)ẋ÷!"­⁡​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌­
    )ẋ     # ‎⁡Loop, collecting values, while the result of the following does not change
f          # ‎⁢  flatten the top of the stack
 G›β       # ‎⁣  and convert from base max(digits) + 1
     ẋ     # ‎⁤The initial value is not included in the list
      ÷    # ‎⁢⁡Dump all values to the stack
       !   # ‎⁢⁢and push the length of the stack
        "  # ‎⁢⁣Pair into a list
💎

Created with the help of Luminespire.

-2 bytes by porting Kevin's dump to stack idea

Charcoal, 23 bytes

⊞υＳＷ⁻ＥυＩ↨κ⊕⌈κυ«→≔ιυ»υＩⅈ

Try it online! Link is to verbose version of code. Outputs the the final number followed by the number of steps. Explanation:

⊞υＳ

Input n as a string and push it to the predefined empty list.

Ｗ⁻ＥυＩ↨κ⊕⌈κυ«

Map the rebase function over the list and perform set difference with the previous value. While this is true, ...

→≔ιυ

... increment the step count and save the new list.

»υＩⅈ

Output the final list and the step count.

Alternative approach, also 23 bytes:

ＮθＷ⁻θ↨Ｉθ⊕⌈Ｉθ«→≧⁻ιθ»Ｉ⟦θⅈ

Try it online! Link is to verbose version of code. Outputs the final number followed by the number of steps, although this can be easily reversed at no byte cost. Explanation:

Ｎθ

Input n as a number.

Ｗ⁻θ↨Ｉθ⊕⌈Ｉθ«

While performing the rebase function on n results in a different value, ...

→≧⁻ιθ

... increment the step count and update n to the new value.

»Ｉ⟦θⅈ

Output the final value and the step count.

I also tried accumulating the values in the predefined empty list and using the length instead of tracking the count but this turned out to be a byte longer despite not having to use «»s.

Python, 72 70 69 bytes

f=lambda n,p=0:n>(m:=int(o:=str(n),int(max(o))+1))and f(m,p+1)or(n,p)

Attempt This Online!

Takes input as int, outputs a tuple (inert, passes).

"Straightforward" recursive translation of the iterative approach, with some assignment expression to shorten repeated variable use.

Changelog

• 72 initial commit
• 70 (-2) @Arnauld by flipping the ternary expression and making n==rebase_result a simple n-rebase_result evaluated as a boolean.
• 69 (-1) @Jonathan Allan finds a way to save 1 bytes using logical short-circuiting to replace the "bulky" ternary expression. (tl;dr: result if base_case else recursive_path can often roughly become (not base_case)and recursive_path or result if you can shorten not base_case by writing a shorter condition, saving on spaces and keyword letter(s).

JavaScript (ES6), 59 bytes

Returns [steps, inert].

n=>[(g=_=>n-(n=parseInt(n,Math.max(...n+_)+1))&&g``+1)``,n]

Try it online!

Try the first 35 values of A091049 (OEIS)

Commented

n => [              // n = input
  ( g = _ =>        // g is a recursive function:
    n - (           //   compare n with its updated value:
      n = parseInt( //     the value obtained by
        n,          //     parsing n
        Math.max(   //     using the base equal to:
          ...n + _  //       the highest digit in n ...
        )           //
        + 1         //       ... plus 1
      )             //
    ) &&            //   end of comparison; stop if we get 0
    g``             //   otherwise, do a recursive call
    + 1             //   and increment the final result
  )``,              // initial call to g -> number of steps
  n                 // also return the last value of n
]                   //

NB: Because g doesn't expect any meaningful input, we use the tagged template calls g`` so that we get [""] in _. This allows us to coerce n to a string with n+_ (1 byte shorter than n+"").

C (gcc), 88 86 bytes

o;f(int*s){sprintf(s,"%d",strtol(s,0,10-strcspn("98765432",s)),o=*s);s=*s^o?f(s)+1:0;}

Try it online!

• -2 bytes thanks to @c--!

Uiua, 15 bytes

°⍥°(⌝⊥+₁⊸/↥⊥₁₀)

Try it in the pad!

Explanation

°⍥°(⌝⊥+₁⊸/↥⊥₁₀)
°⍥°(          ) # Repeat until inert and output count
           ⊥₁₀  # Get base 10 digits
      +₁⊸/↥     # Find max and add one
    ⌝⊥          # Convert digits to that base

Rust, 132 bytes

fn f(n:u64,c:u64)->[u64;2]{let r=(2..).find_map(|b|u64::from_str_radix(&n.to_string(),b).ok()).unwrap();if r<n{f(r,c+1)}else{[r,c]}}

Attempt This Online!

Feels a lot less clean than my Rust solution to the simpler problem. The need to perform type conversions can't be avoided here, since you regularly have to shift back and forth between string and numeric form, recursion means you need an fn function, not just a closure, with full type annotations (the choice between a tuple and an array for the return value only mattered for the annotation).

Excel VBA, 150 bytes

Global c
Sub b(n)
For i=1To Len(n)
v=Mid(n,i,1)
If v>m Then m=v
Next
a=WorksheetFunction.Decimal(n,m+1)
If a=n Then Debug.?a,c Else c=c+1:b a
End Sub

VBA will automatically expand this into the slightly easier to read version:

Global c
Sub b(n)
For i = 1 To Len(n)
v = Mid(n, i, 1)
If v > m Then m = v
Next
a = WorksheetFunction.Decimal(n, m + 1)
If a = n Then Debug.Print a, c Else c = c + 1: b a
End Sub

The excellent Google Sheets answer by doubleunary cannot directly port into Excel because it doesn't play nicely with circular references so we are forced to rely on VBA. The solution is fairly straightforward.

Global c declares a global variable c so it can be incremented. You could pass it as a parameter and iterate it that way but then you have to either require 0 as a second input or make it optional and handle the special case when it isn't passed by the user. This felt better.

The For...Next loop finds the highest digit in the current number.

WorksheetFunction.Decimal converts that number into a new base

If the result is the same, then output the number and the counter. Otherwise, iterate the counter and recurse.

Swift 6.1, 99 bytes

{var x=$0+0
return((0...).first{_ in x==(x=Int("\(x)",radix:Int("\("\(x)".max()!)")!+1)!,x).1}!,x)}

Try it on SwiftFiddle!

Perl 5 -MPOSIX -MList::Util=max -p, 47 bytes

$b++,$_=strtol$_,1+max/./g until/^.$|9/;say$b*1

Try it online!

Outputs the step count followed by the inert number.

Japt, 17 bytes

Takes input as a digit array, outputs [steps,inert] where inert is also a digit array.

[@eU=ìUrÔÄ ì}a U]

Try it