28
\$\begingroup\$

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])
\$\endgroup\$
  • 1
    \$\begingroup\$ What are the values for ten, eleven, etc. in higher bases you are using? Do they contain zeroes? \$\endgroup\$ – Stephen Oct 25 '17 at 19:05
  • 19
    \$\begingroup\$ @Stephen The values chosen for digits above 9 do not matter, because they are not 0. \$\endgroup\$ – Mego Oct 25 '17 at 19:06
  • 9
    \$\begingroup\$ This is OEIS A106370. \$\endgroup\$ – Engineer Toast Oct 25 '17 at 19:36
  • 1
    \$\begingroup\$ @Titus That's a good point. I'll limit the base to something reasonable. \$\endgroup\$ – Mego Oct 25 '17 at 20:13
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Nate Eldredge Oct 27 '17 at 13:49

25 Answers 25

15
\$\begingroup\$

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.

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

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ The latter version works only by random luck, even if you insist on a specific compiler. And, of course, neither version is really C. \$\endgroup\$ – AnT Oct 26 '17 at 8:51
  • 3
    \$\begingroup\$ @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 \$\endgroup\$ – Felipe Nardi Batista Oct 26 '17 at 10:38
  • 1
    \$\begingroup\$ @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;}. \$\endgroup\$ – Kevin Cruijssen Oct 26 '17 at 12:40
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Oct 26 '17 at 12:44
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – AnT Oct 26 '17 at 14:12
8
\$\begingroup\$

Haskell, 56 52 48 bytes

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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 #. \$\endgroup\$ – Laikoni Oct 25 '17 at 19:37
  • 2
    \$\begingroup\$ The criminally underrated until :: (a → Bool) → (a → a) → a → a saves four bytes: f n=until(#n)(+1)2 \$\endgroup\$ – Lynn Oct 26 '17 at 13:41
7
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes

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

Try it online!

\$\endgroup\$
6
\$\begingroup\$

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

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])
\$\endgroup\$
  • 1
    \$\begingroup\$ BTW this is pretty similar to my solution. \$\endgroup\$ – Erik the Outgolfer Oct 26 '17 at 11:22
4
\$\begingroup\$

Jelly, 7 bytes

2b@Ạ¥1#

Try it online!

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

05AB1E, 6 bytes

-4 bytes thanks to Adnan

1µNвPĀ

Try it online!

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

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

Java 8, 61 56 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.

Old (61 bytes) answer:

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
\$\endgroup\$
  • 2
    \$\begingroup\$ 54 bytes: n->{int b=2,t=n;for(;t>0;)t=t%b++<1?n:t/--b;return b;} \$\endgroup\$ – Nevay Oct 26 '17 at 11:43
2
\$\begingroup\$

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.

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

JavaScript (ES6), 43 41 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)

\$\endgroup\$
2
\$\begingroup\$

Brachylog, 11 bytes

;.≜ḃ₎¬∋0∧1¬

Try it online!

Explanation

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

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)

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – Adám Oct 27 '17 at 11:20
1
\$\begingroup\$

Proton, 40 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ This is invalid. 2..x checks for bases in the interval [2, x), hence it fails for test cases 1 and 2. \$\endgroup\$ – Mr. Xcoder Oct 25 '17 at 20:21
1
\$\begingroup\$

R, 79 71 66 63 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – JDL Oct 27 '17 at 8:30
  • \$\begingroup\$ I see what you did there. That's a useful one to know! \$\endgroup\$ – NofP Oct 27 '17 at 10:09
  • 1
    \$\begingroup\$ 66 bytes using m%/%T (integer division) instead of (m-m%%T)/T \$\endgroup\$ – Giuseppe Oct 27 '17 at 11:00
  • \$\begingroup\$ 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 :( \$\endgroup\$ – Giuseppe Oct 27 '17 at 15:51
1
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ @LuisMendo I should really start reading the docs better. Thanks. \$\endgroup\$ – Sanchises Oct 26 '17 at 20:22
  • \$\begingroup\$ 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. \$\endgroup\$ – Mego Oct 27 '17 at 20:50
  • \$\begingroup\$ @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? \$\endgroup\$ – Sanchises Oct 27 '17 at 22:59
  • \$\begingroup\$ The last 2 test cases cause errors. \$\endgroup\$ – Mego Oct 28 '17 at 4:57
  • \$\begingroup\$ @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. \$\endgroup\$ – Sanchises Oct 28 '17 at 10:54
0
\$\begingroup\$

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.

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

Actually,  12  11 bytes

╗1⌠╜¡m'0<⌡╓

Try it online!

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

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

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!

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

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!

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

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.

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

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

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

Perl 5, 52 + 2 (-pa) = 54 bytes

$\=1;while($_&&=$F[0]){$\++;$_=int$_/$\while$_%$\}}{

Try it online!

\$\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.