# Smallest Zeroless Base

Given a positive integer n, output the smallest base b >= 2 where the representation of n in base b with no leading zeroes does not contain a 0. You may assume that b <= 256 for all inputs.

## Test Cases

1 -> 2 (1)
2 -> 3 (2)
3 -> 2 (11)
4 -> 3 (11)
5 -> 3 (12)
6 -> 4 (12)
7 -> 2 (111)
10 -> 4 (22)
17 -> 3 (122)
20 -> 6 (32)
50 -> 3 (1212)
100 -> 6 (244)
777 -> 6 (3333)
999 -> 4 (33213)
1000 -> 6 (4344)
1179360 -> 23 ([12, 9, 21, 4, 4])
232792560 -> 23 ([15, 12, 2, 20, 3, 13, 1])
2329089562800 -> 31 ([20, 3, 18, 2, 24, 9, 20, 22, 2])
69720375229712477164533808935312303556800 -> 101 ([37, 17, 10, 60, 39, 32, 21, 87, 80, 71, 82, 14, 68, 99, 95, 4, 53, 44, 10, 72, 5])
8337245403447921335829504375888192675135162254454825924977726845769444687965016467695833282339504042669808000 -> 256 ([128, 153, 236, 224, 97, 21, 177, 119, 159, 45, 133, 161, 113, 172, 138, 130, 229, 183, 58, 35, 99, 184, 186, 197, 207, 20, 183, 191, 181, 250, 130, 153, 230, 61, 136, 142, 35, 54, 199, 213, 170, 214, 139, 202, 140, 3])

• What are the values for ten, eleven, etc. in higher bases you are using? Do they contain zeroes? Commented Oct 25, 2017 at 19:05
• @Stephen The values chosen for digits above 9 do not matter, because they are not 0.
– user45941
Commented Oct 25, 2017 at 19:06
• This is OEIS A106370. Commented Oct 25, 2017 at 19:36
• @Titus That's a good point. I'll limit the base to something reasonable.
– user45941
Commented Oct 25, 2017 at 20:13
• @Mego: Try 232792560. It's the lcm of 2,3,...,20, so in every base <= 20 it has a 0 as the least significant digit. Commented Oct 27, 2017 at 13:49

# Pyth, 6 bytes

f*FjQT


Verify all the test cases.

## How it works

f*FjQT  ~ Full program.

f       ~ First positive integer where the condition is truthy.
jQT  ~ The input converted to base of the current element.
*F     ~ Product. If the list contains 0, then it's 0, else it is strictly positive.
0 -> Falsy; > 0 -> Truthy.
~ Output the result implicitly.


Although Pyth's f operates on 1, 2, 3, 4, ... (starting at 1), Pyth treats numbers in base 1 (unary) as a bunch of zeros, so base 1 is ignored.

• Nice abuse of the fact that Pyth's base-1 representation is all-zeroes. Commented Oct 25, 2017 at 19:04
• @EriktheOutgolfer Thanks! I will add an explanation regarding that. Commented Oct 25, 2017 at 19:05
• Pyth isn't the only language whose unary representation uses zeroes as digits hint :P
– user45941
Commented Oct 25, 2017 at 19:05
• You wrote 0 -> Falsy; > 0 -> Truthy. Is that intentional that 0 is both Truthy and Falsy in that situation? Commented Oct 27, 2017 at 14:39
• @BrianJ There is a > sign in front of the second 0, which means that everything higher than 0 is truthy. Commented Oct 27, 2017 at 15:35

# C,  52  50 bytes

i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;return i;}


Try it online!

# C (gcc),  47  45 bytes

i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;n=i;}


Try it online!

Two bytes saved thanks to @Nevay's suggestion on @Kevin Cruijssen's answer!

• The latter version works only by random luck, even if you insist on a specific compiler. And, of course, neither version is really C. Commented Oct 26, 2017 at 8:51
• @AnT it is C.. it will give a lot of warnings but it will compile. as long as you find a compiler that works for your code, you're fine Commented Oct 26, 2017 at 10:38
• @Blacksilver k%i is a ternary-check here. A more readable variant would be k=(k%i?k:n*++i); or even more clearly: if(k%i){k=k;}else{k=n*++i;}. Commented Oct 26, 2017 at 12:40
• Also, you can golf both by 2 bytes: i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;return i;} and i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;n=i;}. All credit goes to @Nevay who posted this suggestion on my ported Java 8 answer. Commented Oct 26, 2017 at 12:44
• @Felipe Nardi Batista: I'm aware of the fact that CodeGolf rules say "as long as it compiles" and so on. However, the fact that it "compiles" does not in any way prove that it is C. This is not C. Typeless declarations like i, k; and f(n) existed in ancient versions of C (K&R), but only in the era when return required round brackets around its argument. If you want to use K&R with i,k;, you also have to use return(i);. The above might be gnuc, but not C. Commented Oct 26, 2017 at 14:12

b#n=n<1||mod n b>0&&b#div n b
f n=until(#n)(+1)2


Try it online!

Pretty basic but can't think of any good ways to shorten it

EDIT: Thanks to Laikoni for saving me 4 bytes! Don't know why I never thought of !!0. I probably should've tried removing those parentheses but I have vague memories of some weird error when you try to use || and && together. Maybe I'm confusing it with the equality operators.

EDIT 2: Thanks @Lynn for shaving another 4 bytes! Don't know how I never knew about until before now.

• You beat me by a minute with nearly exactly the same solution. :) !!0 is shorter than head and I think you can drop the parenthesis in #. Commented Oct 25, 2017 at 19:37
• The criminally underrated until :: (a → Bool) → (a → a) → a → a saves four bytes: f n=until(#n)(+1)2
– lynn
Commented Oct 26, 2017 at 13:41

# Wolfram Language (Mathematica), 33 bytes

2//.i_/;DigitCount[#,i,0]>0:>i+1&


Try it online!

# Husk, 7 bytes

→V▼MBtN


Try it online!

### Explanation

→V▼MBtN
tN    list of natural numbers starting from 2
MB      convert the (implicit) input to each of those bases
V▼        find the (1-based) index of the first result where the minimum digit is truthy
→          add 1 to this index


# Jelly, 7 bytes

2b@Ạ¥1#


Try it online!

# Python 2, 57 bytes

n=x=input()
b=2
while x:z=x%b<1;b+=z;x=[x/b,n][z]
print b


Try it online!

This is one byte shorter than a recursive function:

f=lambda n,b=1,x=1:b*(x<1)or f(n,b+(x%b<1),[x/b,n][x%b<1])

• BTW this is pretty similar to my solution. Commented Oct 26, 2017 at 11:22

# 05AB1E, 6 bytes

1µNвPĀ


Try it online!

• 10 bytes: [¹NÌDŠвPĀ#
– Neil
Commented Oct 25, 2017 at 19:24
• 1µNвPĀ works for 6 bytes Commented Oct 25, 2017 at 19:52
• @Adnan I knew it was way too long
– Okx
Commented Oct 25, 2017 at 20:10
• LB0.å0k is another method entirely >_>. Commented Oct 27, 2017 at 14:17

# Husk, 9 bytes

←foΠB⁰tN


Try it online!

## Explanation

            -- input N
tN  -- tail of [1..] == [2..]
←f(    )    -- filter with the following:
B⁰     --   convert N to that base
Π        --   product (0 if it contains 0)
←           -- only keep first element


# Java 8, 6156 54 bytes

n->{int b=2,t=n;for(;t>0;)t=t%b++<1?n:t/--b;return b;}


Try it here.

Explanation:

n->{            // Method with integer as both parameter and return-type
int b=2,      //  Base-integer, starting at 2
t=n;      //  Temp-integer, copy of the input
for(;t>0;)    //  Loop as long as t is not 0
t=t%b++<1?  //   If t is divisible by the base b
//   (and increase the base b by 1 afterwards with b++)
n        //    Set t to the input n
:         //   Else:
t/--b;   //    Divide t by the b-1
//    (by decreasing the base b by 1 first with --b)
//  End of loop (implicit / single-line body)
return b;     //  Return the resulting base
}               // End of method


I have the feeling this can be golfed by using an arithmetic approach. It indeed can, with a port of @Steadybox' C answer, and then golfed by 2 bytes thanks to @Nevay.

n->{int b=1;for(;n.toString(n,++b).contains("0"););return b;}


Try it here.

Explanation:

n->{         // Method with Integer as both parameter and return-type
int b=1;   //  Base-integer, starting at 1
for(;n.toString(n,++b).contains("0"););
//  Loop as long as the input in base-b does contain a 0,
//  after we've first increased b by 1 before every iteration with ++b
return b;  //  Return the resulting base
}            // End of method

• 54 bytes: n->{int b=2,t=n;for(;t>0;)t=t%b++<1?n:t/--b;return b;} Commented Oct 26, 2017 at 11:43

# APL (Dyalog), 20 19 bytes

1+⍣{~0∊⍺⊥⍣¯1⊢n}≢n←⎕


Try it online!

As usual, thanks to @Adám for helping out in chat and getting the code to work in TIO. Also, saving 1 byte.

This is tradfn (traditional function) body. To use it, you need to assign it a name (which is in TIO's header field), enclose it in ∇s (one before the name and one in TIO's footer field), and then call it using its name. Since it uses a quad (⎕) to take the user's input, it's called as f \n input instead of the usual f input

### How?

1+⍣{~0∊⍺⊥⍣¯1⊢n}≢n←⎕  ⍝ Main function.
n←⎕ ⍝ Assigns the input to the variable n
1+⍣{           }≢     ⍝ Starting with 1, add 1 until the expression in braces is truthy
~0∊               ⍝ returns falsy if 0 "is in"
⊥             ⍝ convert
⊢n        ⍝ the input
⍣¯1          ⍝ to base
⍺              ⍝ left argument (which starts at 1 and increments by 1)


The function then returns the resulting base.

• Golfing tip: since n←⎕ will be a simple number and you need 1 as initial argument to the rest of the code, you can just count the number of elements in n (which is 1), by replacing 1⊣ with ≢. Try it online!
Commented Oct 27, 2017 at 11:20

# Japt, 8 bytes

@ìX e}a2


Try it online!

## Explanation

@    }a2


Return the first number (X) to pass the function, starting at 2

ìX


Convert the input number to an array of base-X digits.

e


Check if all digits are truthy.

• Won't this fail if the array contains any multiple of 10? Commented Oct 25, 2017 at 22:18
• @Shaggy My understanding was that, according to OPs comment, that the digits for bases above 9 don't count as zero. Commented Oct 25, 2017 at 22:36
• Ah, I see that now. There's a problem with the phrasing of the challenge, so (or I'm just too tired!). Commented Oct 25, 2017 at 22:39

# JavaScript (ES6), 4341 37 bytes

n=>(g=x=>x?g(x%b++?x/--b|0:n):b)(b=1)


### Test cases

let f =

n=>(g=x=>x?g(x%b++?x/--b|0:n):b)(b=1)

console.log(f(1   )) // 2 (1)
console.log(f(2   )) // 3 (2)
console.log(f(3   )) // 2 (11)
console.log(f(4   )) // 3 (11)
console.log(f(5   )) // 3 (12)
console.log(f(6   )) // 4 (12)
console.log(f(7   )) // 2 (111)
console.log(f(10  )) // 4 (22)
console.log(f(17  )) // 3 (122)
console.log(f(20  )) // 6 (32)
console.log(f(50  )) // 3 (1212)
console.log(f(100 )) // 6 (244)
console.log(f(777 )) // 6 (3333)
console.log(f(999 )) // 4 (33213)
console.log(f(1000)) // 6 (4344)

# Brachylog, 11 bytes

;.≜ḃ₎¬∋0∧1¬


Try it online!

### Explanation

;.≜ḃ₎           The Input represented in base Output…
¬∋0        …contains no 0
∧1¬     And Output ≠ 1


# Python 2, 57 bytes

n=m=input()
b=2
while m:c=m%b<1;b+=c;m=(m/b,n)[c]
print b


Try it online!

-1 thanks to Felipe Nardi Batista.
-2 thanks to Lynn (and now this is a dupe of her solution :D)

• 59 bytes by changing a,b=a+c,d to a+=c;b=d Commented Oct 26, 2017 at 10:12
• I think you can replace while m>1 by while m (and then we’re tied!)
– lynn
Commented Oct 26, 2017 at 13:32
• @Lynn That's why I commented on your solution, it would be exactly the same then. Commented Oct 26, 2017 at 13:33
• That’s okay!
– lynn
Commented Oct 26, 2017 at 13:42
• @Lynn I already knew :p otherwise I'd have asked you to delete yours. Commented Oct 26, 2017 at 13:43

# Proton, 40 bytes

x=>filter(y=>all(digits(y,x)),2..x+3)[0]


Try it online!

• This is invalid. 2..x checks for bases in the interval [2, x), hence it fails for test cases 1 and 2. Commented Oct 25, 2017 at 20:21

# R, 79716663 65 bytes

function(n){while(!{T=T+1;all(n%/%T^(0:floor(log(n,T)))%%T)})T
T}


Try it online!

This answer is based on Giuseppe's re-arrangement in one single loop.

Saved 8 bytes thanks to JDL, and 6 bytes thanks to Giuseppe.

• You can sub b for T, which starts out defined as TRUE == 1, removing the need for b=1. Similarly you can sub F for k (F is FALSE)
– JDL
Commented Oct 27, 2017 at 8:30
• I see what you did there. That's a useful one to know!
– NofP
Commented Oct 27, 2017 at 10:09
• 66 bytes using m%/%T (integer division) instead of (m-m%%T)/T Commented Oct 27, 2017 at 11:00
• 65 bytes. it was a bit messy but I suspected getting rid of the nested loops would save something; I just thought it would be more than 1 byte :( Commented Oct 27, 2017 at 15:51

# MATL, 13 12 bytes

G@Q_YAA~}@Q


Try it online!

-1 byte thanks to Luis Mendo. This program does not handle testcases bigger than 2^53 (flintmax, the maximum consecutive integer representable by a floating point type), as the default datatype is double in MATL. However, it should be able to find any arbitrary zeroless base below that number.

            % Do while
G           %  Push input
@ _        %  Outputs the iteration number, negate.
YA      %  Convert input to base given by the iteration number, the negative number is to instruct MATL we want an arbitrary high base with a integer vector rather than the default character vector we know from hexadecimal
A~    %  If they're not all ones, repeat
}   % But if they are equal, we finally
@  %  Push the last base
Q       Q %  As base 1 makes no sense, to prevent MATL from errors we always increase the iteration number by one.

• @LuisMendo I should really start reading the docs better. Thanks. Commented Oct 26, 2017 at 20:22
• This doesn't seem to work for the larger test cases, but I don't know enough about MATL/Matlab to know if that's caused by integer limits or not.
– user45941
Commented Oct 27, 2017 at 20:50
• @Mego I tested my 13 byte version which should be equivalent to the current version up to 1e6, on MATLAB R2017a. What test setup resulted in problems for you? Commented Oct 27, 2017 at 22:59
• The last 2 test cases cause errors.
– user45941
Commented Oct 28, 2017 at 4:57
• @Mego Ah I didn't see those testcases before. This is due to the implementation of MATLs YA using doubles internally, so it can only handle inputs up to the maximum consecutive integer representable by a double (see flintmax). Does this invalidate the answer? In principle the algorithm works for arbitrary base, I've explicitly worked around another command that would only do up to base 36. Commented Oct 28, 2017 at 10:54

# ><>, 565251 49 bytes

:2&v
1(?\:&:&:@%@,:1%-:
v~<
l<*v?=2
&v?/:&+1
n>&


Try it online!

The interpreter bugs out on the last 2 testcases.
It only reads the first 16 digits of the input correct and then replaces the rest with other digits.

# PHP, 59+1 bytes

using builtins, max base 36:

for($b=1;strpos(_.base_convert($argn,10,++$b),48););echo$b;


no builtins, 6360+1 bytes, any base:

for($n=$b=1;$n&&++$b;)for($n=$argn;$n%$b;$n=$n/$b|0);echo$b;


Run as pipe with -nR or try them online.

# Actually,  12  11 bytes

╗1⌠╜¡m'0<⌡╓


Try it online!

Uses this consensus. Thanks to Mego for byte-saving help in chat.

# J, 26 bytes

]>:@]^:(0 e.]#.inv[)^:_ 2:


Would love to know if this can be improved.

The main verb is a the dyadic phrase:

>:@]^:(0 e.]#.inv[)^:_


which is given the input on the left and the constant 2 on the right. That main verb phrase then uses J's Do..While construct, incrementing the right y argument as long as 0 is an element of e. the original argument in base y.

Try it online!

# Lua, 77 76 bytes

b=2n=...N=n
while~~N>0 do
if N%b<1then
b=b+1N=n
else
N=N//b
end
end
print(b)


Try it online!

# Milky Way, 38 bytes

^^'%{255£2+>:>R&{~^?{_>:<;m_+¡}}^^^}


usage: ./mw base.mwg -i 3

## Explanation

code                                 explanation                    stack layout

^^                                   clear the preinitialized stack []
'                                  push the input                 [input]
%{                              } for loop
255£                             push next value from 0..254   [input, base-2]
2+                           add 2 to the get the base     [input, base]
>                          rotate stack right            [base, input]
:                         duplicate ToS                 [base, input, input]
>                        rotate stack right            [input, base, input]
R                       push 1                        [input, base, input, 1]
&{~             }      while ToS (=remainder) is true ...
^                    pop ToS                      [input, base, number]
?{         }        if ToS (=quotient) ...
_>:<;              modify stack                [input, base, number, base]
m            divmod                      [input, base, quotient, remainder]
_+¡         else: output ToS (0) + SoS and exit
^^^   pop everything but the input.


I'm sure this can be shortened using a while-loop instead of a for loop, but I couldn't get it to work.

# Stacked, 23 bytes

{!2[1+][n\tb all]until}


Try it online!

This increments ([1+]) J starting from two (2) while the baseJ representation of the input has no zeroes (all and until).

$\=1;while($_&&=$F[0]){$\++;$_=int$_/$\while$_%$\}}{  Try it online! # Ruby, 41 bytes ->n{(2..).find{!n.digits(_1).include? 0}}  Attempt This Online! # Stax, 7 bytes Ç╔ü$■╖Ö


Run and debug it

Trivial brute force approach

# Pip, 12 bytes

T NyYaTD Uoo


Try It Online!

### Explanation

An iterative solution:

T NyYaTD Uoo
a is command-line input; y is ""; o is 1 (implicit)
T             Loop until
Ny          Min(y) is truthy:
Uo     Increment o
aTD        Convert a to list of digits in that base
Y           Store that list in y
o  After the loop, output o


Alternate solution using filter, also 12 bytes:

@:NaTD_FI2,m
a is command-line input; m is 1000 (implicit)
2,m  Range from 2 to 999 (could be 256, but using m is shorter)
FI     Filter, keeping elements for which this function returns truthy:
aTD_         Convert a to list of digits in base (function argument)
N             Get the minimum
@:            Take the first element of the filtered list


Try It Online!