15
\$\begingroup\$

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
\$\endgroup\$
  • 3
    \$\begingroup\$ 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]) \$\endgroup\$ – Jonathan Allan Nov 29 at 19:09
  • \$\begingroup\$ Suggested test case: (15*256+1,4) \$\endgroup\$ – Kritixi Lithos Nov 30 at 19:12

16 Answers 16

4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

Ruby, 44 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Fails for 15*256+1,4 (gives 2 instead of 1) \$\endgroup\$ – Kritixi Lithos Nov 30 at 19:11
  • \$\begingroup\$ @Kritixi Lithos thanks, the problem is fixed now. Luckily runtime doesn't matter for code golf. \$\endgroup\$ – xibu Nov 30 at 19:34
2
\$\begingroup\$

J, 40 37 bytes

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

Try it online!

-3 bytes thanks to Galen Ivanov

\$\endgroup\$
  • 1
    \$\begingroup\$ Why not make it an oneliner \$\endgroup\$ – Galen Ivanov Nov 30 at 7:54
  • 1
    \$\begingroup\$ Indeed. Thanks Galen. \$\endgroup\$ – Jonah Nov 30 at 14:50
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 24 bytes

NθNηW∧⊞Oυη⁻⊖η⌈↨θη≧⁻ιηILυ

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

NθNη

Input N and b.

W∧⊞Oυη⁻⊖η⌈↨θη

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.

ILυ

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

\$\endgroup\$
1
\$\begingroup\$

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!

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

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ No need to repeat the в. Alternative 7: Δвà>}N>. \$\endgroup\$ – Grimmy Dec 2 at 14:45
  • \$\begingroup\$ @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 \$\endgroup\$ – Kevin Cruijssen Dec 2 at 16:50
1
\$\begingroup\$

K (ngn/k), 18 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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)

\$\endgroup\$

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.