Tudo sobre binário básico

29

Por favor, desculpe o título punny.

Esta é uma pergunta inspirada em Uma propriedade curiosa de 82000 . Nele, o autor aponta que o número 82000 é binário nas bases 2, 3, 4 e 5. A publicação então coloca a questão "existe um número que é binário nas bases 2, 3, 4, 5 e 6? "? (Para aqueles curiosos, verifiquei valores de até 10 ^ 1.000.000 e até agora a resposta é não.)

Isso me fez pensar: dado um número, em que bases ele é binário?

Nosso número curioso, 82000, é realmente binário em seis bases:

Base 2 = 10100000001010000
Base 3 = 11011111001
Base 4 = 110001100
Base 5 = 10111000
Base 81999 = 11
Base 82000 = 10

Nem todos os números terão bases binárias que são seqüenciais. Considere o número 83521. É binário nas bases 2, 17, 289, 83520 e 83521.

Seu desafio é determinar e exibir em que bases um número é binário.

Regras

  • Um número é considerado "binário" em uma determinada base se sua representação nessa base consistir apenas em zeros e uns. 110110é um valor binário, enquanto 12345não A380Fé , definitivamente não é.
  • Seu número será fornecido na entrada padrão. Será um valor inteiro entre 2 e 2 ^ 32-1, inclusive, e será fornecido no formato base 10.
  • Em ordem crescente, exiba cada base maior que aquela em que o número é binário. Cada base deve estar em sua própria linha. Se você incluir o valor binário nessa base (veja a pontuação de bônus abaixo), separe a base e o valor binário com um espaço. Somente a saída para saída padrão será julgada, o erro padrão e outras fontes serão ignoradas.

Pontuação

Sua pontuação é o tamanho do seu programa em bytes. Quanto menor a pontuação, melhor.

Bônus :
Se o seu programa também exibir os valores binários nas bases encontradas, multiplique sua pontuação por 0,75. O
valor binário exibido não deve ter pontuação extra, zeros estranhos, ponto decimal, apenas zeros e uns.

Exemplos

Entrada:

82000

Saída (recebe bônus):

2 10100000001010000
3 11011111001
4 110001100
5 10111000
81999 11
82000 10

Entrada:

1234321

Saída (sem bônus):

2
1111
1234320
1234321
Mr. Llama
fonte
A entrada pode terminar com uma nova linha?
LegionMammal978
@ LegionMammal978 - Uhhh ... com certeza? Minha intenção era que você fosse capaz de obter o número de entrada com um simples recurso, linha de leitura ou algo semelhante.
Llama
11
Em geral, né sempre pelo menos em binário bases 1(não contadas), 2, n-1, e n.
mbomb007
11
Quando você diz: "seu número será fornecido na entrada padrão", você quer dizer apenas STDIN, ou podemos aceitar o número como argumento de função, como é padrão no site?
Alex A.
A representação binária (na parte de bônus) deve ter um determinado formato? Particularmente seria [1, 0, 1, 1, 0]bom, ou os números precisam ser unidos como 10110?
Jakube

Respostas:

14

Pitão, 14 13

jbf!-jQTU2tSQ

Obrigado a Jakube por apontar a nova Sfunção.

Experimente aqui.

A versão online é muito lenta para fazer 1234321. Isso simplesmente converte a entrada em cada base de 2 para si mesma e descarta os resultados que contêm valores diferentes de 0 e 1.

Explicação:

                           : Q=eval(input) (implicit)
jb                         : join on newlines the list...
  f!                       : filter away nonempty values (impliticly named T)
    -jQTU2                 : sewtise difference of number converted to base and range(2)
     jQT                   : convert Q to base T
        U2                 : range(2)
          tSQ              : over the range [2 Q+1)

Além disso, esta é uma versão bônus ( não muito bem agora, bem agora, novamente graças a Jakube) (20 * 0,75 = 15):

VQI!-JjQK+2NU2pdKjkJ

Experimente aqui

FryAmTheEggman
fonte
Pyth acabou de ser atualizado. Para que você possa conectar-se a soluções reais.
Jakube 3/15
E aqui está uma solução 20 * 0,75 = 15: VQI!-JjQK+2NU2pdKjkJÀs vezes, a programação funcional não é a melhor abordagem.
Jakube 3/15
10

Julia, 72 70 bytes

Na verdade, é mais longo com o bônus, então não há bônus aqui.

n=int(readline());for j=2:n all(i->i0:1,digits(n,j))&&println(j)end

Isso lê uma linha de STDIN, converte-a em um número inteiro e imprime o resultado. Apesar de ser um método de força bruta, a entrada 1234321 levou menos de 1 segundo para mim.

Ungolfed + explicação:

# Read n from STDIN and convert to integer
n = int(readline())

# For every potential base from 2 to n
for j = 2:n
    # If all digits of n in base j are 0 or 1
    if all(i -> i0:1, digits(n, j))
        # Print the base on its own line
        println(j)
    end
end

Exemplos:

julia> n=int(readline());for j=2:n all(i->i0:1,digits(n,j))&&println(j)end
1234321
2
1111
1234320
1234321

julia> n=int(readline());for j=2:n all(i->i0:1,digits(n,j))&&println(j)end
82000
2
3
4
5
81999
82000

NOTA : Se a entrada puder ser tomada como argumento de função e não a partir de STDIN (aguardando confirmação do OP), a solução será 55 bytes.

Alex A.
fonte
7

CJam, 20 bytes (ou 27 bytes * 0,75 = 20,25)

Aqui está a versão sem bônus, 20 bytes:

ri:X,2f+{X\b2,-!},N*

Tente isso aqui.

Apenas por diversão, aqui está a versão bônus, 27 bytes:

ri:X{X\)b2,-!},1>{)SX2$bN}/

Experimente online aqui

Optimizer
fonte
Certo. Uma vez que eu terminei um pouco de golfe.
Optimizer
11
ri_,f{2+S@2$bN}4/{2=2,-!},(19,5 bytes)
Dennis
7

Mathematica, 59 bytes

Print/@Select[1+Range[n=Input[]],Max@IntegerDigits[n,#]<2&]

Ugh ... IntegerDigitsD:

Não há realmente muito a explicar sobre o código ... 12 bytes são desperdiçados pelo requisito para usar STDIN e STDOUT.

Acho que não posso reivindicar o bônus. O melhor que eu tenho são 84 bytes (o que gera uma pontuação acima de 60):

Print@@@Select[{b=#+1," ",##&@@n~IntegerDigits~b}&/@Range[n=Input[]],Max@##3<2&@@#&]
Martin Ender
fonte
7

Python 2, 88 86 80

Bastante simples, sem bônus. Python é agradável e branda com variáveis ​​globais.

N=input();g=lambda n:n<1or(n%b<2)*g(n/b)
for b in range(2,N+1):
 if g(N):print b

O melhor que consegui obter para o bônus é 118 * .75 = 87,75 :

N=input();g=lambda n:0**n*" "or" "*(n%b<2)and(g(n/b)+`n%b`)*(g(n/b)>'')
for b in range(2,N+1):
 if g(N):print`b`+g(N)
KSab
fonte
Solução agradável, me supere com um código muito mais curto.
Kade
Seria mais curto fazer apenas em g(N)vez de n=N.
feersum
@feersum Oh sim (costumava ser g(N,b)assim a vírgula tornava os dois iguais), mas como assim eu não precisaria de uma variável para N?
KSab
@KSab eu apaguei essa segunda parte; não importa.
feersum
Posso estar errado, mas você não conseguiu o bônus apenas mudando g(n/b)para (g(n/b)+'n%b')onde 'representa um backtick?
feersum
4

Python 2, 90 * 0,75 = 67,5

n=input();b=1
while b<n:
 b+=1;s="";c=k=n
 while k:s=`k%b`+s;c*=k%b<2;k/=b
 if c:print b,s

Abordagem iterativa bastante direta.

Sem o bônus, são 73 bytes:

n=input();b=1
while b<n:
 b+=1;c=k=n
 while k:c*=k%b<2;k/=b
 if c:print b
Sp3000
fonte
4

SQL (PostgreSQL), 247,5 255 230,25 (307 * .75)

Como o SQL é conhecido por ser maravilhoso nesses tipos de desafios, achei melhor montar um :) O bônus realmente valeu a pena.
Ele deve estar em conformidade com as especificações, mas não tenho uma maneira fácil de testar o COPY I FROM STDIN .
Editar ordem fixa. Mudou a maneira como a coluna R é manipulada para usar uma matriz.

CREATE TABLE IF NOT EXISTS I(I INT);TRUNCATE TABLE I;COPY I FROM STDIN;WITH RECURSIVE R AS(SELECT n,I/n I,ARRAY[I%n] R FROM generate_series(2,(SELECT I FROM I))g(n),(SELECT I FROM I)I(I)UNION ALL SELECT n,I/n,I%n||R FROM R WHERE I>0)SELECT n||' '||array_to_string(R,'')FROM R WHERE 2>ALL(R)and i=0ORDER BY n

Como teste, usei pastilhas retas na Imesa. A execução do teste foi expandida e comentada.

-- Create the table to accept the input from the copy command
CREATE TABLE IF NOT EXISTS I(I INT);
-- Make sure that it is empty
TRUNCATE TABLE I;
-- Popoulate it with a value from STDIN
--COPY I FROM STDIN;
INSERT INTO I VALUES(82000); -- Testing
--Using a recursive CTE query
WITH RECURSIVE R AS (
    -- Recursive anchor
    SELECT n,                -- base for the row
       I/n I,                -- integer division
       ARRAY[I%n] R   -- put mod value in an array
    FROM generate_series(2,(SELECT I FROM I))g(n), -- series for the bases
         (SELECT I FROM I)I(I) -- Cross joined with I,  saves a few characters
    UNION ALL 
    -- for each row from r recursively repeat the division and mod until i is 0
    SELECT n,
        I/n,
        I%n||R -- Append mod to beginning of the array
    FROM R WHERE I>0
    )
-- return from r where i=0 and r has 1's and 0's only
SELECT n||' '||array_to_string(R,'')
FROM R 
WHERE 2 > ALL(R)and i=0
ORDER BY n -- Ensure correct order

2 10100000001010000
3 11011111001
4 110001100
5 10111000
81999 11
82000 10

MickyT
fonte
Tão perto! As bases de saída precisam estar em ordem crescente. 1 por usar um idioma não convencional.
Llama
@ Mr.Llama consertou com um order by. Agora, para ver se eu posso obter esses personagens de volta
MickyT
3

Haskell 109 * 0,75 = 81,75 bytes

0#x=[]
n#x=n`mod`x:div n x#x 
f n=[show x++' ':(n#x>>=show)|x<-[2..n+1],all(<2)$n#x]
p=interact$unlines.f.read

Exemplo de uso (nota: os valores binários são lsb primeiro):

p 82000

2 00001010000000101
3 10011111011
4 001100011
5 00011101
81999 11
82000 01

Sem restrições de entrada / saída, ou seja, entrada via argumento da função, saída em formato nativo via REPL):

Haskell, 67 * 0,75 = 50,25 bytes

0#x=[]
n#x=n`mod`x:div n x#x
f n=[(x,n#x)|x<-[2..n+1],all(<2)$n#x]

Retorna uma lista de pares (base, valor). Os valores são lsb primeiro, por exemplo (novas linhas / espaços adicionados para melhor exibição):

 f 82000
 [ (2,[0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1]),
   (3,[1,0,0,1,1,1,1,1,0,1,1]),
   (4,[0,0,1,1,0,0,0,1,1]),
   (5,[0,0,0,1,1,1,0,1]),
   (81999,[1,1]),
   (82000,[0,1]) ] 
nimi
fonte
2

R, 111

Provavelmente há muito espaço para melhorar isso no momento

i=scan();b=2:i;R=i%%b;I=rep(i,i-1);while(any(I<-I%/%b))R=cbind(I%%b,R);for(x in b)if(all(R[x-1,]<2))cat(x,'\n')

Executa com avisos

> i=scan();b=2:i;R=i%%b;I=rep(i,i-1);while(any(I<-I%/%b))R=cbind(I%%b,R);for(x in b)if(all(R[x-1,]<2))cat(x,'\n')
1: 82000
2: 
Read 1 item
There were 17 warnings (use warnings() to see them)
2 
3 
4 
5 
81999 
82000
>
MickyT
fonte
@AlexA. Avisos causados ​​por coagir o I%/%ba uma lógica na any()cláusula. `
MickyT
2

Java, 181 155,25 (207 * .75) 151,5 (202 * .75) bytes

class I{public static void main(String[]a){a:for(long b=new java.util.Scanner(System.in).nextLong(),c,d=1;d++<b;){String e="";for(c=b;c>0;e=c%d+e,c/=d)if(c%d>1)continue a;System.out.println(d+" "+e);}}}

Expandido com explicação:

class I {
    public static void main(String[]a){
        a:for(long b=new java.util.Scanner(System.in).nextLong(),c,d=1; //b = input(), d = base
              d++<b;) {                                           //For all bases in range(2,b+1)
            String e="";
            for(c = b;c > 0; e = c % d + e,c /= d)                //Test all digits of base-d of b
                           //e = c % d + e                        //Append digits to string
                if (c % d > 1)                                    //Reject base if the digit is greater than 1
                    continue a;
            System.out.println(d+" "+e);                          //Print base and digits.
        }
    }
}

Original (sem bônus):

class I{public static void main(String[]a){long b=new java.util.Scanner(System.in).nextLong(),c,d=1;a:for(;d++<b;){c=b;while(c>0){if(c%d>1)continue a;c/=d;}System.out.println(d);}}}

3,75 bytes graças a Ypnypn :)

O número um
fonte
2

R, 94 83 79

n=scan();cat((2:n)[!sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})],sep="\n")

Uso:

> n=scan();cat((2:n)[!sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})],sep="\n")
1: 82000
2: 
Read 1 item
2
3
4
5
81999
82000
> n=scan();cat((2:n)[!sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})],sep="\n")
1: 1234321
2: 
Read 1 item
2
1111
1234320
1234321

O núcleo da função é !sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})que, para cada base x de 2 a n, mantém o quociente n / x desde que o restante seja 0 e 1. Em seguida, gera o resultado (que é 0 se todos os restantes forem 1 ou 0) e nega (0 nega para VERDADEIRO, todo o resto nega para FALSO). Graças ao escopo da função, não há necessidade de criar uma variável dummy para n. O vetor resultante de booleanos é então usado para indexar 2:ne, portanto, gera apenas as bases para as quais ele trabalhou.

plannapus
fonte
1

TI-Basic, 45 bytes

Input N
For(B,2,N
If prod(seq(BfPart(iPart(N/B^X)/B),X,0,log(N)/log(B))<2
Disp B
End

Explicação

  • Entrada N
  • Para cada B de 2 a N
    • Se N é apenas 0 e 1 na base B
      • Visor B
  • Laço final

A parte complicada

A segunda linha funciona da seguinte maneira:

  • Para cada X de 0 ao log B N
  • B × fPart (iPart (N / B X ) / B) é o enésimo dígito na base B, contando para trás
  • Considere isso como uma lista
  • Para cada elemento, se o dígito for menor que 2, produza 1 (verdadeiro), caso contrário, 0 (falso)
  • Pegue o produto: 1 se todos os elementos forem 1

Nota

O programa executa significativamente mais rápido se um parêntese de fechamento )for colocado no final da segunda linha. Veja aqui mais sobre isso.

Ypnypn
fonte
1

TI-BASIC, 31 29

For(B,2,Ans
If 2>round(Bmax(fPart(Ans/B^randIntNoRep(1,32
Disp B
End

Provavelmente, isso é ideal para o TI-BASIC.

Explicação:

randIntNoRep(1,32)retorna uma permutação aleatória dos números de 1 a 32 (tudo o que precisamos é desses números em alguma ordem; o TI-BASIC não tem nada parecido com o comando iota da APL). 32 elementos é suficiente porque a menor base possível é 2 e o maior número é 2 ^ 32-1. B^randIntNoRep(1,31)eleva essa lista ao poder B, o que resulta na lista que contém todos B^1,B^2,...,B^32(em alguma ordem).

Em seguida, a entrada (na Ansvariável wer, que é inserida no formulário [number]:[program name]) é dividida por esse número. Se sua entrada for 42 e a base for 2, o resultado será a lista 21,10.5,5.25,...,42/32,42/64,[lots of numbers less than 1/2], novamente em alguma ordem.

Tomando a parte fracionária e multiplicando o número pela sua base, obtém o dígito nessa posição na representação da base-b. Se todos os dígitos forem menores que 2, o maior dígito será menor que 2.

Como Ypnypn afirmou, um parêntese de fechamento na Forinstrução acelera isso devido a um erro do analisador.

31-> 31: Salva um byte, mas corrige erros de arredondamento que adicionam o byte novamente.

31-> 29: salvou dois bytes usando em RandIntNoRep()vez de cumSum(binomcdf()).

lirtosiast
fonte
O TI-BASIC possui uma função de sequência?
Llama
Sim, o comando é seq(expression, variable, start, end[, step]). Se nenhum passo for dado, o padrão será 1. No entanto, cumSum(binomcdf(31,0são 8 bytes seq(X,X,1,32e 9 bytes.
precisa saber é o seguinte
Ah, isso explica isso. Não estou familiarizado com trabalhos de pontuação no TI-Basic.
Mr. Llama
1

Geléia , 9 bytes

³bṀỊµÐfḊY

Experimente online!

Feito ao lado de caird coinheringaahing no chat .

Como funciona

³bṀỊµÐfḊY Programa completo.

     Ðf Filtre o intervalo gerado implicitamente [1, entrada].
    µ Inicia uma nova cadeia monádica.
³b Converta a entrada na base do número atual, como uma lista.
  Ṁ Máximo.
   Ign Insignificante. Verifica se abs (Z) ≤ 1.
       Que desenfileirar; Remove o primeiro elemento da lista (para descartar a base 1).
        Y Associe-se por novas linhas.
Mr. Xcoder
fonte
0

Javascript, ES6, 118 * .75 = 88,5 110 * .75 = 82,5

f=x=>{res={};for(b=2;b<=x;++b)if(!+(res[b]=(c=x=>x%b<2?x?c(x/b|0)+""+x%b:"":"*")(x)))delete res[b];return res}

Versão anterior:

f=x=>{res={};for(q=2;q<=x;++q)if(!+(res[q]=(c=(x,b)=>x%b<2?x?c(x/b|0,b)+""+x%b:"":"*")(x,q)))delete res[q];return res}

Verifica:

f(82000)
Object { 2: "10100000001010000", 3: "11011111001", 4: "110001100", 5: "10111000", 81999: "11", 82000: "10" }
Qwertiy
fonte
Aqui você não tem entrada nem saída.
Edc65
0

JavaScript ( ES6 ) 65

68 bytes para uma função com um parâmetro e saída do console.

f=n=>{s=n=>n%b>1||b<n&&s(n/b|0);for(b=1;b++<n;)s(n)||console.log(b)}

65 bytes com E / S via pop-up

n=prompt(s=n=>n%b>1||b<n&&s(n/b|0));for(b=1;b++<n;)s(n)||alert(b)

Reivindicando o bônus: 88 * 0,75 => 66

n=prompt(s=n=>n%b>1?9:(b<=n?s(n/b|0):'')+n%b);for(b=1;b++<n;)s(n)<'9'&&alert(b+' '+s(n))
edc65
fonte
0

Mathematica, 76 * 0,75 = 57

n=Input[];G=#~IntegerDigits~b&;If[Max@G@n<2,Print[b," ",Row@G@n]]~Do~{b,2,n}

Inicialmente esqueci os requisitos de entrada ... Felizmente, eles não adicionaram muito mais.

Tally
fonte
0

Ruby , 44 bytes

->n{(2..n).select{|i|n.digits(i)-[0,1]==[]}}

Experimente online!

daniero
fonte
0

Perl 5 , 63 bytes

map{$t=$n;1while($f=$t%$_<2)&&($t=int$t/$_);say if$f}2..($n=<>)

Experimente online!

Não há bônus nisso, porque a pontuação é um pouco melhor que a minha versão com o bônus:

Perl 5 , 85 bytes * 0,75 = 63,75

map{my$r;$t=$n;$r=$/.$r while($/=$t%$_)<2&&($t=int$t/$_);say"$_ 1$r"if$/<2}2..($n=<>)

Experimente online!

Xcali
fonte