Find the length of a number's "base-jumping" path

Question

Consider a positive integer N written in base b. A sequence is generated from this number by finding the largest digit d in the expansion of N and writing N in base d+1, repeating until the base the number is written in can be decreased no further. For example, the sequence generated by 346 (10) in starting base 16 has length 6: 15A (16) = 295 (11) = 346 (10) = 1003 (7) = 11122 (4) = 110211 (3). Note that the next term in the sequence would be in base 3 again, which is invalid since the base does not decrease.

The goal of this code golf challenge is to write a program/function that takes two inputs (a decimal integer and a starting base - order doesn't matter and the two numbers must be integers) and outputs the length of the sequence generated according to the above rules.

Some test cases:

(24, 4) = 2
(19, 10) = 1
(346, 16) = 6
(7557, 97) = 20

Answer 1

Jelly, 7 bytes

b@Ṁ‘ɗƬL

A dyadic Link accepting b on the left and N on the right which yields the sequence length.

Try it online!

How?

b@Ṁ‘ɗƬL - Link: b; N
     Ƭ  - Collect up until no longer unique, applying:
    ɗ   -   last three links as a dyad - i.e. f(X[initially b], N):
 @      -     with swapped arguments:
b       -       convert (N) to base (X)
  Ṁ     -     maximum
   ‘    -     incremented
      L - length

Answer 2

Ruby, 44 bytes

->n,b{r=1;r+=1while b>b=n.digits(b).max+1;r}

Try it online!

Answer 3

Python 2, 67 bytes

edit: bug fix

S=lambda n,b,p=0:p-b and S(n,max(n/b**x%b for x in range(n))+1,b)+1

Try it online!

Explanation:

def S(Nr, Base, PrevBase=0):
    if Base != PrevBase:     # break recursion if Base repeats
        # find maximum digit in current base
        M=max([ (Nr//Base**x) % Base for x in range(Nr)])
        # return number of remaining steps plus one
        return 1 + S(Nr,M+1,Base)
    return 0

Answer 4

J, ⁴⁰ 37 bytes

[:<:@#(h,])^:([>h=.1+[:>./#.inv)/^:a:

Try it online!

-3 bytes thanks to Galen Ivanov

Answer 5

Japt, 22 19 14 bytes

{aU=VìU rÔÄ}f1

Try it

Takes input as base,number

{           }f1     repeat until function return false  starting with 1, increment in 
 a                  difference between 1st input U and..
  U=                U, which is assigned..
    VìU             2nd input V to base U
        rÔ          reduced to max
          Ä         add 1

Saved 5 thanks to @Shaggy suggestion to use reduce to max instead of sort, plus using counter of f() instead of manually count using T

Answer 6

Charcoal, 24 bytes

ＮθＮηＷ∧⊞Ｏυη⁻⊖η⌈↨θη≧⁻ιηＩＬυ

Try it online! Link is to verbose version of code. Explanation:

ＮθＮη

Input N and b.

Ｗ∧⊞Ｏυη⁻⊖η⌈↨θη

Push b to the predefined empty list to build up the sequence, then convert N to base b, and subtract the largest resulting digit from b-1. Repeat until this is zero.

≧⁻ιη

Calculate the new base.

ＩＬυ

Output the length of the sequence. (-1 byte to output the sequence itself.)

Answer 7

Python 2, 87 bytes

h=lambda n,b:n>=b and max(n%b,h(n/b,b))or n
f=lambda n,b,c=0:b!=c and f(n,h(n,b)+1,b)+1

Try it online!

Answer 8

JavaScript (ES6), 60 bytes

Takes input as (n)(b).

n=>g=b=>(x=(h=n=>n&&Math.max(n%b,h(n/b|0)))(n)+1)<b?1+g(x):1

Try it online!

Answer 9

C# (Visual C# Interactive Compiler), 83 bytes

x=>y=>{int g=y,t=0;for(;x>(x=new int[32].Max(l=>g-(g/=x)*x)+1);t++,g=y);return++t;}

Try it online!

Answer 10

Julia 1.0, 46 44 bytes

N*b=(d=max(digits(N,base=b)...)+1)==b||N*d+1

This uses a recursive approach together with the short-circuit operator || and makes use of the fact that Julia promotes booleans to integers under addition, so true + 1 == 2. This also overwrites the * operator, which you wouldn't normally do, but this lets me write f(N,d) infix as N*d to save 3 bytes.

Try it online!

Answer 11

J, 22 bytes

[:#([:>./1+#.inv~)^:a:

Try it online!

Simplified version of Jonah's solution.

How it works

[:#([:>./1+#.inv~)^:a:  Left: number N, Right: initial base B
   (             )^:a:  Collect all intermediate values up to fixpoint:
           #.inv~         Compute digits of N in base B
         1+               Increment
    [:>./                 Max; this becomes the new value of B
[:#                     Length of the result

Answer 12

05AB1E, 8 7 bytes

Δвà>¼}¾

-1 byte thanks to @Grimmy.

Start-base \$b\$ as first input; number \$N\$ as second input.

Try it online or verify all test cases.

Explanation:

Δ     # Loop until the top of the stack no longer changes:
 в    #  Convert the (implicit) input-integer N to (implicit) input-base b as list
  à   #  Pop the list and push the maximum
   >  #  Increase it by 1 (which will be the new base b for the next iteration,
      #                    with the same (implicit) input-integer N)
 ¼    #  And in every loop-iteration: increase the counter_variable by 1
}¾    # After the loop: push the counter_variable
      # (after which it is output implicitly as result)

Answer 13

K (ngn/k), 18 bytes

{#{1+|/y\:x}[x]\y}

Try it online!

Answer 14

Red, 89 bytes

func[n b][k: 0 until[k: k + 1 m: n t: 1 until[t: max t m % b 1 > m: m / b]b = b: 1 + t]k]

Try it online!

Answer 15

MIT-Scheme, 117 bytes

(define(g n r)(if(= n 0)0(max(modulo n r)(g(quotient n r)r))))
(define(f n r)(if(=(+(g n r)1)r)1(1+(f n(1+(g n r))))))

(newline added for readability)

g is a helper function that computes the maximum digit of the number in a radix, and f is the main function.

Answer 16

Haskell, 104 bytes

i=iterate
d n b=1+maximum(take(n+1)$snd<$>i((`divMod`b).fst)(n,0))
u(a:b:c)|a==b=1|2>1=1+u(b:c)
(u.).i.d

Haskell has no base conversion function. So I have to implement it normally.

snd<$>i((divModb).fst)(n,0) returns an infinite list with zero as the first element, followed by represented by the representation of n at base b, followed by infinite number of zeros. (((divModb).fst)(0,0) returns (0,0))

I just iterate function d until the value stopped changing and count the number of iteration. (In haskell, you do that by iterateing the function infinitely and take only the first few elements)