Input:

A positive integer n consisting of digits in the range 0-9.

Challenge:

If d is the highest digit in the integer, assume the base of the number is d+1. E.g. if the integer is 1256 then you shall assume it's in base-7, if it's 10110 then you shall assume it's base-2 (binary), and if it's 159 then it's decimal.

Now, do the following until you either, 1: reach a base-10 integer, or 2: reach a single digit integer.

  1. Convert the integer from base-(d+1) to base-10
  2. Find the base of this new integer (again, base-(d+1) where d is the highest digit in the new number)
  3. Go to step 1.

Examples:

Assume the input is n = 413574. The highest digit d=7, so this is base-8 (octal). Convert this to decimal and get 137084. The highest digit d=8, so this is base-9. Convert this to decimal and get 83911. The highest digit is 9, so this is a decimal number and we stop. The output shall be 83911.

Assume the input is n = 13552. The highest digit is d=5, so this is base-6. Convert this to decimal and get 2156. The highest digit d=6, so this is base-7. Convert this to decimal and get 776. The highest digit is d=7, so this is base-8. Convert this to decimal and get 510. The highest digit is d=5 so this is base-6. Convert this to decimal and get 186. The highest digit is 8, so this is base-9. Convert this to decimal and get 159. The highest digit is 9, so this is a decimal number and we stop. The output shall be 159.

Assume the input is n=17. This will give us 15, then 11, then 3, which we will output since it's a single digit.


Test cases:

5
5

17
3

999
999

87654321  (base-9 -> 42374116 in decimal -> base-7 -> 90419978 in decimal) 
9041998

41253  (5505 -> 1265 -> 488 -> 404 -> 104 -> 29)
29

Notes:

  • Standard rules regarding I/O, loopholes etc. You may take the input as a string
  • Explanations are encouraged
  • You may use builtin base-conversion commands
    • Solutions that don't use the language's builtin base-conversion functions (if they exist) are welcome, even if they end up being much longer than the obvious approach using builtin functions.

Apparently, this is OEIS A091047.

  • 2
    Apparently I love matrices, so I thought I'd do a base-conversion challenge instead. – Stewie Griffin Jun 28 '17 at 7:27
  • 32
    "The best base is 10"... "10" is written in which base? – Olivier Grégoire Jun 28 '17 at 8:23
  • 5
    @OlivierGrégoire That's the clever thing... Whatever base we end up with, it will still be a valid statement! – Stewie Griffin Jun 28 '17 at 8:29
  • @StewieGriffin But how do you read it? "10" has a different name in each base. – user11153 Jun 28 '17 at 9:23
  • 10
    Well, that depends on the base... or as Meghan would say it "it's all about that base, 'Bout that base, no trouble" ;-) – Stewie Griffin Jun 28 '17 at 9:38

22 Answers 22

Mathematica, 56 bytes

#//.x_/;(b=Max[d=IntegerDigits@x]+1)<11:>d~FromDigits~b&

Try it online! (Using Mathics.)

I thought I'd check out what the sequence looks like:

enter image description here

And here is a plot of the number of steps it takes to find the result:

enter image description here

(Click for larger versions. See the revision history for plots only up to n = 1000.)

Looks like a very interesting mixture of large scale structure and fine scale chaos. I wonder what's up with the wider gaps around 30,000 and 60,000.

  • 4
    @StewieGriffin should be on the left side. The small gaps are there, because the numbers leading up to a multiple of a power of 10 contain a 9, so they're already in base 10. But for 30k and 60k it seems that numbers with an 8 or even 7 (would have to check) in place of that 9 always become base 10 after at most one step. – Martin Ender Jun 28 '17 at 10:39
  • @StewieGriffin To be precise, all numbers in the range [28051, 28888] are base 9 and translate to numbers of the form 19xxx, thus pretty much doubling that gap. – cmaster Jun 29 '17 at 10:59
  • Ah, got it... :) For the record: I knew why there were gaps on the left side of powers of 10's... It was only the double sized gaps that were strange (why 30/60, and not 20/40/50). I see now though that numbers in the range 28xxx -> 19xxx, but 38xxx -> 26xxx, not 29xxx. – Stewie Griffin Jun 29 '17 at 11:21

Java 8, 172 166 163 152 151 140 138 116 114 99 bytes

s->{for(Integer b=0;b<10&s.length()>1;s=""+b.valueOf(s,b=s.chars().max().getAsInt()-47));return s;}

Takes the input as a String.

-64 bytes thanks to @OlivierGrégoire. And here I thought my initial 172 wasn't too bad.. ;)

Try it here.

Explanation:

s->{                    // Method with String as parameter and return-type
  for(Integer b=0;b<10  //  Loop as long as the largest digit + 1 is not 10
      &s.length()>1;    //  and as long as `s` contains more than 1 digit
    s=""+               //   Replace `s` with the String representation of:
         b.valueOf(s,   //    `s` as a Base-`b` integer
          b=s.chars().max().ge‌tAsInt()-47)
                        //     where `b` is the largest digit in the String + 1
  );                    //  End of loop
  return s;             //  Return result-String
}                       // End of method
  • 1
    Promise to stay calm? :p Ok... let's go: s->{for(Integer b=0;b<10&s.length()>1;)s=""+b.valueOf(s,b=s.chars().max().getAsInt()-47);return s;}. Also I deleted most of my comments as they're totally irrelevant now (b is the base, your a; and s is the number we're working on). – Olivier Grégoire Jun 28 '17 at 10:21
  • 1
    I've tried to recursify this to shave off some bytes with: Integer b;return(b=s.chars().max().getAsInt()-47)>9|s.length()<2?s:c(""+b.valueOf(s,b)); (88), but I'm brand new to code golf. This is a snipppet, right? Is there a way to declare this as a method without needing to add public String c(String s) ? – Lord Farquaad Jun 28 '17 at 19:24
  • 1
    @LordFarquaad You don't need the public, but I'm afraid you'll indeed have to use String c(String s){} for recursive-calls, even in Java 8. When you create a lambda using java.util.function.Function<String, String> c=s->{Integer b;return(b=s.chars().max().getAsInt()-47)>9|s.length()<2?s:c‌.apply​(""+b.valueOf(s,b));} or interface using interface N{String c(String s);}N n = s->{Integer b;return(b=s.chars().max().getAsInt()-47)>9|s.length()<2?s:n.c‌​(""+b.valueOf(s,b));}; it will give an "self-reference in initializer error" in both cases. But very nice approach nonetheless! – Kevin Cruijssen Jun 28 '17 at 19:48
  • Ah, I guess I ungolfed it a few bytes then. But thanks for the help! I'll keep this in mind moving forward. – Lord Farquaad Jun 28 '17 at 19:51

Pyth, 9 bytes

ui`GhseS`

Test suite

Explanation:

ui`GhseS`
ui`GhseS`GQ    Implicit variable introduction
u         Q    Repeatedly apply the following function until the value repeats,
               starting with Q, the input.
        `G     Convert the working value to a string.
      eS       Take its maximum.
     s         Convert to an integer.
    h          Add one.
 i`G           Convert the working value to that base
  • It's a bit weird how you used a two-variable lambda ending up using one variable...and it didn't throw error(s). Oh, the two variables are Q and Q, I get it. – Erik the Outgolfer Jun 28 '17 at 9:22
  • @EriktheOutgolfer Not exactly. u without its third input is apply until repetition, whereas with a third input it is apply a fixed number of times. u lambda has G and H, but you don't need to use H. – isaacg Jun 28 '17 at 9:37
  • Actually replacing G with H would've had the same result...btw implicit variable is G? – Erik the Outgolfer Jun 28 '17 at 9:46
  • @EriktheOutgolfer The implicit variable is G, yes. H counts up from 0 with each iteration, so it's completely different. I'm not really sure what you're talking about. Here's an example program to show you what's going on: pyth.herokuapp.com/… – isaacg Jun 28 '17 at 9:58

JavaScript (ES6), 63 57 54 53 bytes

f=a=>a>9&(b=Math.max(...a+""))<9?f(parseInt(a,b+1)):a

Saved 8 bytes thanks to Shaggy and Dom Hastings

f=a=>a>9&(b=Math.max(...a+""))<9?f(parseInt(a,b+1)):a;

console.log(f("413574"))

  • Beat me to it. I think you could save a few bytes with +a>9||b<9 and reversing the ternary. – Shaggy Jun 28 '17 at 7:49
  • 1
    @Shaggy edit: I'm dumb – Tom Jun 28 '17 at 7:53
  • 1
    Don't be so hard on yourself Tom! You're not dumb,,, but you're definitely not as smart as @Shaggy! – Stewie Griffin Jun 28 '17 at 7:55
  • 1
    Alternative for 55 bytes f=n=>n>9&&(k=Math.max(...n+"")+1)<10?f(parseInt(n,k)):n – Dom Hastings Jun 28 '17 at 7:55
  • @DomHastings Thanks for the improvements! :) – Tom Jun 28 '17 at 8:03

Python 3, 91 78 76 75 73 bytes

@Emigna shaved off 5 bytes. @FelipeNardiBatista saved 1 byte. @RomanGräf saved 2 bytes

i=input()
while'9'>max(i)and~-len(i):i=str(int(i,int(max(i))+1))
print(i)

Try it online!


Explanation

i=input()                                  - takes input and assigns it to a variable i
while '9'>max(i)and~-len(i):               - repeatedly checks if the number is still base-9 or lower and has a length greater than 1
    i=str(...)                             - assigns i to the string representation of ...
          int(i,int(max(i))+1)             - converts the current number to the real base 10 and loops back again
print(i)                                   - prints the mutated i

05AB1E, 10 5 bytes

5 bytes saved thanks to Magic Octopus Urn

F§Z>ö

As this grows slow very quickly for large input, I'm leaving the old much faster version here for testing. The algorithm is the same, only the number of iterations differ.

[©Z>öD®Q#§

Try it online!

Explanation

[             # start a loop
 ©            # store a copy of the current value in the register
  Z>          # get the maximum (digit) and increment
    ö         # convert the current value to base-10 from this base
     D        # duplicate
      ®Q#     # break loop if the new value is the same as the stored value
         §    # convert to string (to prevent Z from taking the maximum int on the stack)
  • Also, can't you just use тFZ>ö§? Seeing as the number of iterations (as seen here) seems to plateau? If you want to get technical, the rate at which the iterations rise is probably logarithmic... So you could just use something like: DFZ>ö§ and state it won't run for large n. OR maybe even: T.n>FZ>ö§ to directly calculate the number of iterations as log_10(n). – Magic Octopus Urn Jun 28 '17 at 19:02
  • @MagicOctopusUrn: Yeah, now that you mention it, as the sequence definitely seems slower than linear, F§Z>ö should do the trick. – Emigna Jun 28 '17 at 21:49
  • I think you can remove the §. – Erik the Outgolfer Jul 19 '17 at 19:16
  • @EriktheOutgolfer: Unfortunately no. If we remove the §, Z will take the highest number on the stack instead of the highest digit in the number on top of the stack. – Emigna Jul 19 '17 at 22:13
  • @Emigna Huh? – Erik the Outgolfer Jul 20 '17 at 7:51

APL (Dyalog), 20 16 bytes

Takes and returns a string

((⍕⊢⊥⍨1+⌈/)⍎¨)⍣≡

()⍣≡ apply the following function until two consecutive terms are identical:

⍎¨ execute each character (turns the string into a list of numbers)

() apply the following tacit function to that:

  ⌈/ find the maximum of the argument

  1+ add one

  ⊢⊥⍨ evaluate the argument in that base

   format (stringify, in preparation for another application of the outer function)

Try it online!

Ruby, 60 56 bytes

->n{n=(s=n.to_s).to_i(s.bytes.max-47)while/9/!~s&&n>9;n}

Try it online!

Mathematica, 52 bytes

FromDigits[s=IntegerDigits@#,Max@s+1]&~FixedPoint~#&

Pure function taking a nonnegative integer as input and returning a nonnegative integer. Uses the same core mechanic FromDigits[s=IntegerDigits@#,Max@s+1] as Jenny_mathy's answer, but exploits FixedPoint to do the iteration.

Perl 6, 49 bytes

{($_,{.Str.parse-base(1+.comb.max)}...*==*).tail}

Test it

Expanded:

{
  (

    $_,                 # seed the sequence with the input

    {
      .Str
      .parse-base(      # parse in base:
        1 + .comb.max   # largest digit + 1
      )
    }

    ...                 # keep generating values until

    * == *              # two of them match (should only be in base 10)

  ).tail                # get the last value from the sequence
}

PHP, 71 bytes

for(;$b<10&9<$n=&$argn;)$n=intval("$n",$b=max(str_split($n))+1);echo$n;

Try it online!

Pip, 17 bytes

Wa>9>YMXaaFB:1+ya

Takes input as a command-line argument. Try it online!

Explanation

This was fun--I got to pull out the chaining comparison operators.

We want to loop until the number is a single digit OR contains a 9. Equivalently, we want to loop while the number is multiple digits AND does not contain a 9. Equivalently, loop while the number is greater than 9 AND the maximum digit is less than 9: a>9>MXa.

Wa>9>YMXaaFB:1+ya
                   a is 1st cmdline arg (implicit)
     YMXa          Yank a's maximum digit into the y variable
Wa>9>              While a is greater than 9 and 9 is greater than a's max digit:
         aFB:1+y    Convert a from base 1+y to decimal and assign back to a
                a  At the end of the program, print a

Python 2, 60 59 56 53 bytes

Saved 4 byte thanks to Felipe Nardi Batista
Saved 3 bytes thanks to ovs

f=lambda x,y=0:x*(x==y)or f(`int(x,int(max(x))+1)`,x)

Try it online!

Using a recursive lambda, comparing the result of the base conversion to the previous iteration.

  • why not use x==y and x or ... as x will never be 0 (base 1). or even (x==y)*x or ... – Felipe Nardi Batista Jun 28 '17 at 10:57
  • @FelipeNardiBatista: Thanks! I tried x and x==y or ... which didn't work, but I'm not too proficient with these tricks so I didn't realize I could reverse it :) – Emigna Jun 28 '17 at 11:00
  • @ovs: Right you are. Thanks! – Emigna Jun 28 '17 at 14:28
  • @FelipeNardiBatista "Input: A positive integer n consisting of digits in the range 0-9." 0 is still valid input, and now the code rejects it. – Mast Jun 29 '17 at 12:10
  • @Mast: Fortunately for us, 0 isn't a positive integer so it won't be given as input. – Emigna Jun 29 '17 at 12:15

C#, 257 244 243 244 233 222 bytes

using System.Linq;z=m=>{int b=int.Parse(m.OrderBy(s=>int.Parse(s+"")).Last()+""),n=0,p=0;if(b<9&m.Length>1){for(int i=m.Length-1;i>=0;i--)n+=int.Parse(m[i]+"")*(int)System.Math.Pow(b+1,p++);return z(n+"");}else return m;};

Well, C# always takes a lot of bytes but this is just ridiculous. None of the built-ins can handle an arbitrary base, so I had to calculate the conversion myself. Ungolfed:

using System.Linq;
z = m => {
int b = int.Parse(m.OrderBy(s => int.Parse(s + "")).Last()+""), n = 0, p = 0; //Get the max digit in the string
if (b < 9 & m.Length > 1) //if conditions not satisfied, process and recurse
{
    for (int i = m.Length - 1; i >= 0; i--)
        n += int.Parse(m[i] + "") * (int)System.Math.Pow(b+1, p++); //convert each base-b+1 representation to base-10
    return z(n + ""); //recurse
}
else return m; };

Mathematica, 92 bytes

f[x_]:=FromDigits[s=IntegerDigits@x,d=Max@s+1];(z=f@#;While[d!=10&&Length@s>1,h=f@z;z=h];z)&

Javascript (ES6) with 0 arrow function, 74 bytes

function f(a){a>9&&b=Math.max(...a)<9&&f(parseInt(a,b+1));alert(a)}f('11')
  • 3
    Welcome to PPCG! :) This is probably a very nice answer, but I can't tell without an explanation. I (and probably others) never upvote answers that don't contain explanations. – Stewie Griffin Jun 28 '17 at 18:33
  • 1
    Why are you calling f('11') after the function? Unless I'm missing something that only looks to be usage not actually part of the submission. If so, you should take it out of the code section and put it in your explanation (when you add one) and update your byte count to 67. – PunPun1000 Jun 29 '17 at 13:27

K4, 19 bytes

Solution:

{(1+|/x)/:x:10\:x}/

Examples:

q)\
  {(1+|/x)/:x:10\:x}/413574
83911
  {(1+|/x)/:x:10\:x}/13552
159
  {(1+|/x)/:x:10\:x}/17
3
  {(1+|/x)/:x:10\:x}/41253
29    

Explanation:

Use /: built-in to convert base.

{(1+|/x)/:x:10\:x}/ / the solution
{                }/ / converge lambda, repeat until same result returned
            10\:x   / convert input x to base 10 (.:'$x would do the same)
          x:        / store in variable x
 (     )/:          / convert to base given by the result of the brackets
    |/x             / max (|) over (/) input, ie return largest
  1+                / add 1 to this

Kotlin, 97 bytes

fun String.f():String=if(length==1||contains("9"))this else "${toInt(map{it-'0'}.max()!!+1)}".f()

Beautified

fun String.f(): String = if (length == 1 || contains("9")) this else "${toInt(map { it - '0' }.max()!! + 1)}".f()

Test

fun String.f():String=if(length==1||contains("9"))this else "${toInt(map{it-'0'}.max()!!+1)}".f()
val tests = listOf(
        5 to 5,
        17 to 3,
        999 to 999,
        87654321 to 9041998,
        41253 to 29
)

fun main(args: Array<String>) {
    tests.forEach { (input, output) ->
        val answer = input.toString().f()
        if (answer != output.toString()) {
            throw AssertionError()
        }
    }
}

TIO

TryItOnline

Japt, 25 bytes

>9©(A=Uì rw)<9?ßUs nAÄ):U

Try it online!

Jelly, 9 bytes

DḅṀ‘$$µÐL

Try it online!

C, 159 157 bytes

#include <stdlib.h>
char b[99];i=0;m=-1;c(n){do{m=-1;sprintf(b,"%d",n);i=0;while(b[i]){m=max(b[i]-48,m);i++;}n=strtol(b,0,++m);}while(b[1]&&m<10);return n;}

Scala, 119 bytes

if(x.max==57|x.length==1)x else{val l=x.length-1
f((0 to l).map(k=>(((x(k)-48)*math.pow(x.max-47,l-k))) toInt).sum+"")}

Try it online!

Scala, 119 bytes

if(x.max==57|x.length==1)x else f((0 to x.length-1).map(k=>(((x(k)-48)*math.pow(x.max-47,x.length-1-k))) toInt).sum+"")

Try it online!

Both methods work the same way, but in the first one I put x.length-1 in a variable, and in the second one I don't.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.