La base cero más pequeña

28

Dado un número entero positivo n, genera la base más pequeña b >= 2donde la representación de nin base bsin ceros a la izquierda no contiene a 0. Puede suponer eso b <= 256para todas las entradas.

Casos de prueba

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])
Mego
fuente
1
¿Cuáles son los valores para diez, once, etc. en las bases más altas que está utilizando? ¿Contienen ceros?
Stephen
19
@Stephen Los valores elegidos para los dígitos anteriores 9no importan, porque no lo son 0.
Mego
99
Este es OEIS A106370 .
Ingeniero Toast
1
@Titus Ese es un buen punto. Limitaré la base a algo razonable.
Mego
1
@Mego: Pruebe 232792560. Es el mcm de 2,3, ..., 20, por lo que en cada base <= 20 tiene un 0 como el dígito menos significativo.
Nate Eldredge

Respuestas:

15

Pyth , 6 bytes

f*FjQT

Verifique todos los casos de prueba.

Cómo funciona

f * FjQT ~ Programa completo.

f ~ Primer entero positivo donde la condición es verdadera.
   jQT ~ La entrada convertida a la base del elemento actual.
 * F ~ Producto. Si la lista contiene 0, entonces es 0, de lo contrario es estrictamente positivo.
          0 -> Falsy; > 0 -> Verdad.
        ~ Salida del resultado implícitamente.

Aunque Pyth's fopera en 1, 2, 3, 4, ...(comenzando en 1), Pyth trata los números en la base 1 (unario) como un montón de ceros, por lo que la base 1 se ignora.

Sr. Xcoder
fuente
Agradable abuso del hecho de que la representación de base 1 de Pyth es todo ceros.
Erik the Outgolfer
@EriktheOutgolfer ¡Gracias! Agregaré una explicación al respecto.
Sr. Xcoder
Pyth no es el único idioma cuya representación unaria usa ceros como pista de dígitos : P
Mego
Usted escribió 0 -> Falsy; > 0 -> Truthy. ¿Es eso intencional que 0es ambos Truthyy Falsyen esa situación?
Brian J
@BrianJ Hay un >signo delante del segundo 0, lo que significa que todo lo que sea superior a 0 es verdadero.
Sr. Xcoder
11

C,  52  50 bytes

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

Pruébalo en línea!

C (gcc),  47  45 bytes

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

Pruébalo en línea!


¡Dos bytes guardados gracias a la sugerencia de @ Nevay sobre la respuesta de @Kevin Cruijssen!

Steadybox
fuente
2
La última versión funciona solo por suerte al azar, incluso si insiste en un compilador específico. Y, por supuesto, ninguna de las versiones es realmente C.
AnT
3
@ ANT es C .. dará muchas advertencias pero se compilará. siempre y cuando encuentres un compilador que funcione para tu código, estás bien
Felipe Nardi Batista
1
@Blacksilver k%ies un cheque ternario aquí. Una variante más legible sería k=(k%i?k:n*++i);o incluso con mayor claridad: if(k%i){k=k;}else{k=n*++i;}.
Kevin Cruijssen
1
Además, puede jugar golf por 2 bytes: i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;return i;}y i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;n=i;}. Todo el crédito va a @Nevay que publicó esta sugerencia en mi respuesta Java 8 portada .
Kevin Cruijssen
1
@Felipe Nardi Batista: Soy consciente del hecho de que las reglas de CodeGolf dicen "siempre que se compile" y así sucesivamente. Sin embargo, el hecho de que "compila" de ninguna manera prueba que es C. Esto no es C. Declaraciones sin tipo como i, k;y f(n)existían en versiones antiguas de C (K&R), sino solo en la era cuando se returnrequerían corchetes alrededor de su argumento. Si desea usar K&R con i,k;, también debe usarlo return(i);. Lo anterior podría ser gnuc, pero no C.
AnT
8

Haskell , 56 52 48 bytes

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

Pruébalo en línea!

Bastante básico pero no se me ocurren buenas maneras de acortarlo

EDITAR: ¡Gracias a Laikoni por salvarme 4 bytes! No sé por qué nunca pensé !!0. Probablemente debería haber intentado eliminar esos paréntesis, pero tengo vagos recuerdos de algún error extraño cuando intentas usarlos ||y &&juntos. Tal vez lo estoy confundiendo con los operadores de igualdad.

EDIT 2: ¡Gracias @Lynn por afeitar otros 4 bytes! No sé cómo nunca supe untilantes.

usuario1472751
fuente
1
Me ganaste por un minuto con casi exactamente la misma solución. :) !!0es más corto que heady creo que puedes colocar el paréntesis #.
Laikoni
2
El criminal infravalorado until :: (a → Bool) → (a → a) → a → aahorra cuatro bytes:f n=until(#n)(+1)2
Lynn
6

Casco , 7 bytes

→V▼MBtN

Pruébalo en línea!

Explicación

→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
León
fuente
5

Python 2 , 57 bytes

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

Pruébalo en línea!

Este es un byte más corto que una función recursiva:

f=lambda n,b=1,x=1:b*(x<1)or f(n,b+(x%b<1),[x/b,n][x%b<1])
Lynn
fuente
1
Por cierto, esto es bastante similar a mi solución.
Erik the Outgolfer
3

05AB1E , 6 bytes

-4 bytes gracias a Adnan

1µNвPĀ

Pruébalo en línea!

Okx
fuente
10 bytes:[¹NÌDŠвPĀ#
Neil
2
1µNвPĀfunciona para 6 bytes
Adnan
@Adnan Sabía que era demasiado tiempo
Okx
LB0.å0kes otro método completamente> _>.
Urna de pulpo mágico
3

Casco , 9 bytes

←foΠ`B⁰tN

Pruébalo en línea!

Explicación

            -- 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
ბიმო
fuente
3

Java 8, 61 56 54 bytes

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

Pruébalo aquí

Explicación:

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

Tengo la sensación de que esto se puede jugar utilizando un enfoque aritmético. De hecho, puede, con un puerto de respuesta @Steadybox 'C , y luego jugar golf por 2 bytes gracias a @Nevay .

Respuesta anterior ( 61 bytes ):

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

Pruébalo aquí

Explicación:

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
Kevin Cruijssen
fuente
2
54 bytes:n->{int b=2,t=n;for(;t>0;)t=t%b++<1?n:t/--b;return b;}
Nevay
2

Japt , 8 bytes

@ìX e}a2

Pruébalo en línea!

Explicación

@    }a2

Devuelve el primer número ( X) para pasar la función, comenzando en2

ìX

Convierta el número de entrada en una matriz de Xdígitos base .

e

Verifique si todos los dígitos son verdaderos.

Justin Mariner
fuente
¿No fallará esto si la matriz contiene algún múltiplo de 10?
Shaggy
@Shaggy Entendí que, según el comentario de los OP, que los dígitos para las bases superiores a 9 no cuentan como cero.
Justin Mariner
Ah, ya veo eso ahora. Hay un problema con la formulación del desafío, entonces (¡o estoy demasiado cansado!).
Shaggy
2

JavaScript (ES6), 43 41 37 bytes

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

Casos de prueba

Arnauld
fuente
2

Brachylog , 11 bytes

;.≜ḃ₎¬∋0∧1¬

Pruébalo en línea!

Explicación

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

Python 2 , 57 bytes

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

Pruébalo en línea!

-1 gracias a Felipe Nardi Batista .
-2 gracias a Lynn (y ahora este es un engaño de su solución: D)

Erik el Outgolfer
fuente
59 bytes cambiando a,b=a+c,daa+=c;b=d
Felipe Nardi Batista
Creo que puedes reemplazar while m>1por while m(¡y luego estamos atados!)
Lynn
@ Lynn Es por eso que comenté tu solución, sería exactamente la misma entonces.
Erik the Outgolfer
1
@ Lynn ya lo sabía: p, de lo contrario, te habría pedido que borraras el tuyo.
Erik the Outgolfer
2

APL (Dyalog) , 20 19 bytes

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

Pruébalo en línea!

Como de costumbre, gracias a @ Adám por ayudar en el chat y hacer que el código funcione en TIO. Además, ahorrando 1 byte.

Esto se tradfn ( trad itional f unctio n ) cuerpo. Para usarlo, debe asignarle un nombre (que está en el campo de encabezado de TIO), encerrarlo en s (uno antes del nombre y otro en el campo de pie de página de TIO), y luego llamarlo usando su nombre. Como usa un quad ( ) para tomar la entrada del usuario, se llama como en f \n inputlugar de lo habitualf input

¿Cómo?

1+⍣{~0∊⍺⊥⍣¯1n}≢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)

La función luego devuelve la base resultante.

J. Sallé
fuente
1
Consejo de golf: dado n←⎕que será un número simple y que necesita 1como argumento inicial para el resto del código, puede contar el número de elementos en n(que es 1), reemplazando 1⊣con . Pruébalo en línea!
Adám
1

Protón , 40 bytes

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

Pruébalo en línea!

Hiperneutrino
fuente
1
Esto no es valido. 2..xcomprueba las bases en el intervalo [2, x), por lo tanto, falla para los casos de prueba 1y 2.
Sr. Xcoder
1

R , 79 71 66 63 65 bytes

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

Pruébalo en línea!

Esta respuesta se basa en la reorganización de Giuseppe en un solo bucle.

Guardado 8 bytes gracias a JDL, y 6 bytes gracias a Giuseppe.

NofP
fuente
1
Puede sub bpara T, que comienza definido como TRUE == 1, eliminando la necesidad de b=1. Del mismo modo se puede sub Fpara k( Fes FALSE)
JDL
Veo lo que hiciste alli. ¡Es útil saberlo!
NofP
1
66 bytes usando m%/%T(división entera) en lugar de(m-m%%T)/T
Giuseppe
65 bytes . estaba un poco desordenado pero sospechaba que deshacerme de los bucles anidados salvaría algo ; Solo pensé que sería más de 1 byte :(
Giuseppe
1

MATL , 13 12 bytes

`G@Q_YAA~}@Q

Pruébalo en línea!

-1 byte gracias a Luis Mendo. Este programa no maneja casos de prueba mayores de 2 ^ 53 ( flintmaxel número entero consecutivo máximo representable por un tipo de punto flotante), ya que el tipo de datos predeterminado está doubleen MATL. Sin embargo, debería poder encontrar cualquier base cero arbitraria debajo de ese número.

`            % 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.
Sanchises
fuente
@LuisMendo Realmente debería comenzar a leer mejor los documentos. Gracias.
Sanchises
Esto no parece funcionar para los casos de prueba más grandes, pero no sé lo suficiente sobre MATL / Matlab para saber si eso es causado por límites enteros o no.
Mego
@Mego Probé mi versión de 13 bytes que debería ser equivalente a la versión actual hasta 1e6, en MATLAB R2017a. ¿Qué configuración de prueba le causó problemas?
Sanchises
Los últimos 2 casos de prueba causan errores.
Mego
@Mego Ah, no vi esas pruebas antes. Esto se debe a la implementación de MATLs que YAusan dobles internamente, por lo que solo puede manejar entradas hasta el máximo entero consecutivo representable por un doble (ver flintmax). ¿Esto invalida la respuesta? En principio, el algoritmo funciona para una base arbitraria, he trabajado explícitamente en torno a otro comando que solo funcionaría hasta la base 36.
Sanchises
0

PHP, 59 + 1 bytes

usando incorporados , base máxima 36:

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

sin construcciones, 63 60 + 1 bytes , cualquier base:

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

Ejecutar como tubería -nRo probarlos en línea .

Titus
fuente
0

J 26 bytes

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

Me encantaría saber si esto se puede mejorar.

El verbo principal es una frase diádica:

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

que recibe la entrada a la izquierda y la constante 2 a la derecha. Esa frase verbal principal usa J's Do..Mientras construye, incrementando el argumento y derecho siempre que 0 sea un elemento del e.argumento original en base y.

Pruébalo en línea!

Jonás
fuente
0

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)

Pruébalo en línea!

Felipe Nardi Batista
fuente
0

Vía Láctea , 38 bytes

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

uso: ./mw base.mwg -i 3


Explicación

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.

Estoy seguro de que esto se puede acortar usando un ciclo while en lugar de un ciclo for, pero no pude hacerlo funcionar.

ovs
fuente
0

Apilado , 23 bytes

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

Pruébalo en línea!

Esto incrementa ( [1+]) J a partir de dos ( 2) mientras que la representación J base de la entrada no tiene ceros ( ally until).

Conor O'Brien
fuente