# Find the length of a number's “base-jumping” path

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

• Isn't (7557, 97) = 20? ([97, 89, 85, 78, 70, 68, 44, 40, 38, 34, 19, 18, 16, 14, 12, 10, 8, 7, 5, 3]) – Jonathan Allan Nov 29 at 19:09
• Suggested test case: (15*256+1,4) – Kritixi Lithos Nov 30 at 19:12

# 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


# Ruby, 44 bytes

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


Try it online!

# 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

• Fails for 15*256+1,4 (gives 2 instead of 1) – Kritixi Lithos Nov 30 at 19:11
• @Kritixi Lithos thanks, the problem is fixed now. Luckily runtime doesn't matter for code golf. – xibu Nov 30 at 19:34

# J, 40 37 bytes

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


Try it online!

-3 bytes thanks to Galen Ivanov

• Why not make it an oneliner – Galen Ivanov Nov 30 at 7:54
• Indeed. Thanks Galen. – Jonah Nov 30 at 14:50

# Japt, 2219 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


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

• – Shaggy Dec 1 at 7:17

# 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.)

# 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!

• and f(...)+1 ~> and-~f(...= would save a byte. != ~> - would save another. – Jonathan Frech Dec 1 at 0:11

# 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!

# 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!

# 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!

# 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


# 05AB1E, 8 7 bytes

Δвà>¼}¾


-1 byte thanks to @Grimmy.

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

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)

• No need to repeat the в. Alternative 7: Δвà>}N>. – Grimmy Dec 2 at 14:45
• @Grimmy Ah, of course. And I knew about that alternative. I actually had that one in mind as well, but liked this one more (especially because it also works in the legacy version and I prefer to keep the loop-index inside the loop when using it - if I have a choice like here). Thanks for the -1, though – Kevin Cruijssen Dec 2 at 16:50

# K (ngn/k), 18 bytes

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


Try it online!

# 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!

# 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))))))


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

i=iterate
d n b=1+maximum(take(n+1)$snd<$>i((divModb).fst)(n,0))

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)