Menor Base Zeroless

28

Dado um número inteiro positivo n, produza a menor base em b >= 2que a representação da nbase bsem zeros à esquerda não contém a 0. Você pode assumir queb <= 256 para todas as entradas.

Casos de teste

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
fonte
1
Quais são os valores para dez, onze etc. nas bases mais altas que você está usando? Eles contêm zeros?
Stephen
19
@ Stephen Os valores escolhidos para os dígitos acima 9não importam, porque não são 0.
Mego 25/10
9
Este é o OEIS A106370 .
Engenheiro Toast
1
@Titus Esse é um bom argumento. Limitarei a base a algo razoável.
Mego 25/10
1
@Mego: Tente 232792560. É o lcm de 2,3, ..., 20, portanto, em cada base <= 20, ele tem 0 como o dígito menos significativo.
Node Eldredge

Respostas:

15

Pitão , 6 bytes

f*FjQT

Verifique todos os casos de teste.

Como funciona

f * FjQT ~ Programa completo.

f ~ Primeiro número inteiro positivo em que a condição é verdadeira.
   jQT ~ A entrada convertida na base do elemento atual.
 * F ~ Produto. Se a lista contém 0, então é 0, caso contrário, é estritamente positivo.
          0 -> falsidade; > 0 -> Verdade.
        ~ Saída do resultado implicitamente.

Embora o Pyth ffuncione 1, 2, 3, 4, ...(começando em 1), o Pyth trata os números na base 1 (unário) como um monte de zeros, portanto a base 1 é ignorada.

Mr. Xcoder
fonte
Bom abuso do fato de que a representação base-1 de Pyth é totalmente zero.
Erik the Outgolfer
@EriktheOutgolfer Thanks! Vou adicionar uma explicação sobre isso.
Xcoder
Pyth não é o único idioma cuja representação unária usa zeros como dica de dígitos : P
Mego 25/10
Você escreveu 0 -> Falsy; > 0 -> Truthy. É que intencional que 0é ao mesmo tempo Truthye Falsyem que situação?
Brian J
@BrianJ Há uma >placa na frente do segundo0 , o que significa que tudo mais que 0 é verdadeiro.
Mr. Xcoder
11

C,  52  50 bytes

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

Experimente online!

C (gcc),  47  45 bytes

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

Experimente online!


Dois bytes salvos graças à sugestão de @ Nevay na resposta de @Kevin Cruijssen!

Steadybox
fonte
2
A última versão funciona apenas com sorte aleatória, mesmo se você insistir em um compilador específico. E, é claro, nenhuma das versões é realmente C.
AnT 26/10
3
@ ANT é C .. dará muitos avisos, mas será compilado. contanto que você encontrar um compilador que trabalha para o seu código, você está bem
Felipe Nardi Batista
1
@Blacksilver k%ié uma verificação ternária aqui. Uma variante mais legível seria k=(k%i?k:n*++i);ou mesmo mais claramente: if(k%i){k=k;}else{k=n*++i;}.
Kevin Cruijssen 26/10
1
Além disso, você pode jogar golfe por 2 bytes: i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;return i;}e i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;n=i;}. Todo o crédito vai para o @Nevay, que postou esta sugestão na minha resposta do Java 8 portada .
Kevin Cruijssen 26/10
1
@Felipe Nardi Batista: Estou ciente do fato de que as regras do CodeGolf dizem "contanto que seja compilado" e assim por diante. No entanto, o fato de "compilar" de forma alguma prova que é C. Isso não é C. Declarações sem letra como i, k;e f(n)existiam em versões antigas de C (K&R), mas apenas na época em returnque eram necessários colchetes em volta de seu argumento. Se você deseja usar o K&R i,k;, também precisa usar return(i);. A descrição acima poderia ser gnuc, mas não 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

Experimente online!

Bastante básico, mas não consigo pensar em nenhuma maneira de reduzi-lo

EDIT: Obrigado a Laikoni por me salvar 4 bytes! Não sei por que nunca pensei nisso !!0. Eu provavelmente deveria ter tentado remover esses parênteses, mas tenho vagas lembranças de algum erro estranho quando você tenta usar ||e &&juntos. Talvez eu esteja confundindo isso com os operadores de igualdade.

EDIT 2: Obrigado @Lynn por raspar mais 4 bytes! Não sei como eu nunca soube untilantes.

user1472751
fonte
1
Você me venceu por um minuto com quase exatamente a mesma solução. :) !!0é mais curto que heade acho que você pode colocar o parêntese #.
Laikoni 25/10
2
O subestimado criminalmente until :: (a → Bool) → (a → a) → a → asalva quatro bytes:f n=until(#n)(+1)2
Lynn
6

Casca , 7 bytes

→V▼MBtN

Experimente online!

Explicação

→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
Leo
fonte
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

Experimente online!

Este é um byte menor que uma função 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
fonte
1
BTW, isso é bastante semelhante à minha solução.
Erik the Outgolfer
3

05AB1E , 6 bytes

-4 bytes graças a Adnan

1µNвPĀ

Experimente online!

Okx
fonte
10 bytes:[¹NÌDŠвPĀ#
Neil
2
1µNвPĀtrabalha para 6 bytes
Adnan
@Adnan eu sabia que era um caminho muito longo
Okx
LB0.å0ké outro método inteiramente> _>.
Magic Octopus Urn
3

Casca , 9 bytes

←foΠ`B⁰tN

Experimente online!

Explicação

            -- 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
ბიმო
fonte
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;}

Experimente aqui.

Explicação:

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

Tenho a sensação de que isso pode ser praticado usando uma abordagem aritmética. De fato, ele pode, com uma porta de resposta C do @Steadybox ' , e depois tachar em 2 bytes graças ao @Nevay .

Resposta antiga ( 61 bytes ):

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

Experimente aqui.

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

Japonês , 8 bytes

@ìX e}a2

Experimente online!

Explicação

@    }a2

Retorne o primeiro número ( X) para passar a função, começando em2

ìX

Converta o número de entrada em uma matriz de Xdígitos base .

e

Verifique se todos os dígitos são verdadeiros.

Justin Mariner
fonte
Isso não irá falhar se a matriz contiver vários múltiplos de 10?
Shaggy
@ Shaggy Meu entendimento era que, de acordo com o comentário do OP, os dígitos das bases acima de 9 não contam como zero.
23717 Justin Mariner
Ah, eu vejo isso agora. Há um problema com o fraseado do desafio, então (ou estou cansado demais!).
Shaggy
2

JavaScript (ES6), 43 41 37 bytes

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

Casos de teste

Arnauld
fonte
2

Braquilog , 11 bytes

;.≜ḃ₎¬∋0∧1¬

Experimente online!

Explicação

;.≜ḃ₎           The Input represented in base Output…
     ¬∋0        …contains no 0
        ∧1¬     And Output ≠ 1
Fatalizar
fonte
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

Experimente online!

-1 graças a Felipe Nardi Batista .
-2 graças a Lynn (e agora esse é um truque da sua solução: D)

Erik, o Outgolfer
fonte
59 bytes alterando a,b=a+c,dpara #a+=c;b=d
Felipe Nardi Batista 26/10
Eu acho que você pode substituir while m>1por while m(e, em seguida, estamos unidos!)
Lynn
@ Lynn É por isso que comentei sua solução, seria exatamente o mesmo então.
Erik the Outgolfer
1
@ Lynn eu já sabia: p caso contrário, eu teria pedido para você excluir o seu.
Erik the Outgolfer
2

APL (Dyalog) , 20 19 bytes

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

Experimente online!

Como sempre, agradeço a @ Adám por ajudar no bate-papo e fazer com que o código funcione no TIO. Além disso, economizando 1 byte.

Isto é tradfn ( trad itional f unctio n corpo). Para usá-lo, é necessário atribuir um nome (que está no campo de cabeçalho do TIO), coloque-o em s (um antes do nome e outro no campo de rodapé do TIO) e, em seguida, chame-o usando seu nome. Como ele usa um quad ( ) para receber a entrada do usuário, é chamado como em f \n inputvez do usualf input

Quão?

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)

A função então retorna a base resultante.

J. Sallé
fonte
1
Dica de golfe: como n←⎕será um número simples e você precisará 1como argumento inicial para o restante do código, basta contar o número de elementos em n(que é 1), substituindo 1⊣por . Experimente online!
Adám 27/10/19
1

Próton , 40 bytes

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

Experimente online!

HyperNeutrino
fonte
1
Isto é inválido. 2..xverifica as bases no intervalo [2, x), portanto, falha nos casos de teste 1e 2.
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}

Experimente online!

Essa resposta é baseada no rearranjo de Giuseppe em um único loop.

Economizou 8 bytes graças ao JDL e 6 bytes graças ao Giuseppe.

NofP
fonte
1
Você pode sub bpara T, que começa definida como TRUE == 1, eliminando a necessidade de b=1. Da mesma forma, você pode inscrever-se Fem k(F éFALSE )
JDL
Eu vi o que você fez lá. É útil saber!
NofP 27/10
1
66 bytes usando m%/%T(divisão inteira) em vez de(m-m%%T)/T
Giuseppe
65 bytes . estava um pouco confuso, mas suspeitei que me livrar dos loops aninhados salvaria algo ; Eu apenas pensei que seria mais do que 1 byte :(
Giuseppe
1

MATL , 13 12 bytes

`G@Q_YAA~}@Q

Experimente online!

-1 byte graças a Luis Mendo. Este programa não processa casos de teste maiores que 2 ^ 53 ( flintmaxo número inteiro consecutivo máximo representável por um tipo de ponto flutuante), pois o tipo de dados padrão está doubleem MATL. No entanto, ele deve ser capaz de encontrar qualquer base arbitrária sem zeros abaixo desse 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
fonte
@LuisMendo Eu realmente deveria começar a ler melhor os documentos. Obrigado.
Sanchises
Isso parece não funcionar para os casos de teste maiores, mas eu não sei o suficiente sobre o MATL / Matlab para saber se isso é causado por limites inteiros ou não.
Mego
@Mego Testei minha versão de 13 bytes, que deve ser equivalente à versão atual até 1e6, no MATLAB R2017a. Qual configuração de teste resultou em problemas para você?
Sanchises
Os últimos 2 casos de teste causam erros.
Mego
@ Mega Ah, eu não vi esses casos de teste antes. Isso ocorre devido à implementação de MATLs YAusando dobros internamente, portanto, ele só pode manipular entradas até o número inteiro consecutivo máximo representável por um dobro (consulte flintmax). Isso invalida a resposta? Em princípio, o algoritmo funciona para base arbitrária, trabalhei explicitamente em torno de outro comando que funcionaria apenas até a base 36.
Sanchises
0

PHP, 59 + 1 bytes

usando builtins , base máxima 36:

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

sem builtins, 63 60 + 1 bytes , qualquer base:

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

Execute como pipe -nRou experimente-os online .

Titus
fonte
0

J, 26 bytes

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

Gostaria de saber se isso pode ser melhorado.

O verbo principal é uma frase diádica:

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

que recebe a entrada à esquerda e a constante 2 à direita. Essa frase verbal principal usa a construção Do.While de J, incrementando o argumento y certo, desde que 0 seja um elemento dee. argumento original na base y.

Experimente online!

Jonah
fonte
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)

Experimente online!

Felipe Nardi Batista
fonte
0

Via Láctea , 38 bytes

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

uso: ./mw base.mwg -i 3


Explicação

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.

Tenho certeza de que isso pode ser reduzido usando um loop while em vez de um loop for, mas não consegui fazê-lo funcionar.

ovs
fonte
0

Empilhados , 23 bytes

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

Experimente online!

Isso incrementa ( [1+]) J a partir de dois ( 2) enquanto a representação J base da entrada não possui zeros ( alle until).

Conor O'Brien
fonte