# The best base is 10... Let's reach it!

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

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

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

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

(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.

• @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. Commented Jun 28, 2017 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. Commented Jun 29, 2017 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. Commented Jun 29, 2017 at 11:21

# Java 8, 172166163152151140138116114 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

• 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). Commented Jun 28, 2017 at 10:21
• 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) ? Commented Jun 28, 2017 at 19:24
• @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! Commented Jun 28, 2017 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. Commented Jun 28, 2017 at 19:51

# Pyth, 9 bytes

uiGhseS


Test suite

Explanation:

uiGhseS
uiGhseSGQ    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.
iG           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. Commented Jun 28, 2017 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. Commented Jun 28, 2017 at 9:37
• Actually replacing G with H would've had the same result...btw implicit variable is G? Commented Jun 28, 2017 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/… Commented Jun 28, 2017 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. Commented Jun 28, 2017 at 7:49
• @Shaggy edit: I'm dumb
– Tom
Commented Jun 28, 2017 at 7:53
• Don't be so hard on yourself Tom! You're not dumb,,, but you're definitely not as smart as @Shaggy! Commented Jun 28, 2017 at 7:55
• Alternative for 55 bytes f=n=>n>9&&(k=Math.max(...n+"")+1)<10?f(parseInt(n,k)):n Commented Jun 28, 2017 at 7:55
• @DomHastings Thanks for the improvements! :)
– Tom
Commented Jun 28, 2017 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). Commented Jun 28, 2017 at 19:02
• @MagicOctopusUrn: Yeah, now that you mention it, as the sequence definitely seems slower than linear, F§Z>ö should do the trick. Commented Jun 28, 2017 at 21:49
• I think you can remove the §. Commented Jul 19, 2017 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. Commented Jul 19, 2017 at 22:13
• @Emigna Huh? Commented Jul 20, 2017 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, 605956 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 ... Commented Jun 28, 2017 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 :) Commented Jun 28, 2017 at 11:00
• @ovs: Right you are. Thanks! Commented Jun 28, 2017 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
Commented Jun 29, 2017 at 12:10
• @Mast: Fortunately for us, 0 isn't a positive integer so it won't be given as input. Commented Jun 29, 2017 at 12:15

## C#, 257244243244233 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')

• 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. Commented Jun 28, 2017 at 18:33
• 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. Commented Jun 29, 2017 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()


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) ->
throw AssertionError()
}
}
}


TryItOnline

# Husk, 8 bytes

ωoṠBo→▲d


Try it online!

ωoṠBo→▲d
ω           # repeat until output no longer changes:
oṠ         # apply function to value & function-of-value
d    # value: digits of argument
Bo→▲     # function of value:
B        # interpret digits as base n, with n given by
o→▲     # max digit +1


# 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;}

• 126 bytes Commented Jun 10, 2020 at 7:58

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

# Japt, 12 bytes

_=ì)ìZrÔÄ}gN


Try it

# J, 22 bytes

(#.~1+>./)@(,.&.":)^:_


Try it online!

# Vyxal, 6 bytes

fG›β)Ẋ


Try it Online!

Will be 5 bytes once a bug fix is made.

## Explained

fG›β)Ẋ
)Ẋ # Until the result of applying the following does not change:
fG     #   Get the biggest digit of the current value - should just be G, but bugs
›β   #   and convert the current value from base (the biggest digit + 1) to base 10