Os primeiros n números sem dígitos binários iguais consecutivos

32

A sequência contém a representação decimal dos números binários da forma:, em 10101...que o n-ésimo termo tem n bits.

A sequência é provavelmente mais fácil de explicar, mostrando apenas os relacionamentos entre as representações binária e decimal dos números:

0       ->  0
1       ->  1
10      ->  2
101     ->  5
1010    ->  10
10101   ->  21
101010  ->  42

Desafio:

Pegue um número inteiro de entrada ne retorne os primeiros n números na sequência. Você pode optar por ter a sequência indexada em 0 ou 1.

Casos de teste:

n = 1   <- 1-indexed
0

n = 18
0, 1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461, 10922, 21845, 43690, 87381

As explicações são incentivadas, como sempre.

Este é o OEIS A000975 .

Stewie Griffin
fonte
Dada sua própria solução MATL, é aceitável produzir o resultado em ordem inversa?
Shaggy
Sim, desde que seja classificado. @Shaggy
Stewie Griffin
Empurrando minha sorte aqui, mas esse formato de saída seria aceitável [85,[42,[21,[10,[5,[2,[1,0]]]]]]]?
Salsicha

Respostas:

66

Python 2 , 36 bytes

lambda n:[2**i*2/3for i in range(n)]

Experimente online! Explicação: A representação binária de éassim, resta simplesmente multiplicá-lo por uma potência apropriada de 2 e tomar a parte inteira.230.101010101...

Neil
fonte
11
Pena que seja janeiro de 2018, caso contrário, eu o teria indicado como Melhor insight matemático para o Melhor do PPCG 2017 . Espero que ainda me lembre no início de 2019.; p
Kevin Cruijssen
@KevinCruijssen este é o melhor que eu já vi de todos os codegolf.stackexchange.com/a/51574/17360
qwr
3
@KevinCruijssen não esqueça!
Bassdrop Cumberwubwubwub 07/02
2
@BassdropCumberwubwubwub Obrigado pelo lembrete, porque eu tinha me esquecido completamente dele! Foi adicionado às indicações.
Kevin Cruijssen 07/02
11

05AB1E , 4 bytes

2 bytes salvos usando o truque 2/3 de Neil

Lo3÷

Experimente online!

Explicação

L      # push range [1 ... input]
 o     # raise 2 to the power of each
  3÷   # integer division of each by 3

05AB1E , 6 bytes

TRI∍ηC

Experimente online!

Explicação

T        # push 10
 R       # reverse it
  I∍     # extend to the lenght of the input
    η    # compute prefixes
     C   # convert each from base-2 to base-10
Emigna
fonte
9

Gelatina , ... 4 bytes

Graças milhas por -1 byte!

ḶḂḄƤ

Experimente online!

Explicação:

owered range, or Unength. Get [0, 1, 2, 3, ..., n-1]
 Ḃ    it. Get the last bit of each number. [0, 1, 0, 1, ...]
   Ƥ  for each Ƥrefixes [0], [0, 1], [0, 1, 0], [0, 1, 0, 1], ...
  Ḅ   convert it from inary to integer.

Gelatina , 4 bytes

Versão de Jonathan Allan.

Ḷ€ḂḄ

Experimente online!

owered range, or Unength.
 €    Apply for each. Automatically convert the number n
      to the range [1,2,..,n]. Get [[0],[0,1],[0,1,2],..].
  Ḃ   it. Get the last bit from each number.
      Current value: [[0],[0,1],[0,1,0],..]
   Ḅ  Convert each list from inary to integer.

Uma versão baseada no truque 2/3 de Neil fornece 5 bytes, consulte o histórico de revisões.

user202729
fonte
ḶḂḄƤo prefixo quick foi criado para isso
milhas
Não há necessidade do prefixo rápido mesmo - Ḷ€ḂḄtambém funcionaria.
Jonathan Allan
5

MATL , 5 bytes

:WI/k

Baseado na resposta de Neil .

Explicação

:       % Implicit input, n. Push range [1 2 ... n]
W       % 2 raised to that, element-wise. Gives [2 4 ...2^n] 
I       % Push 3
/       % Divide, element-wise
k       % Round down, element-wise. Implicit display

Experimente online!


MATL , 9 bytes

:q"@:oXBs

Experimente online!

Explicação

:       % Implicit input n. Range [1 2 ... n]
q       % Subtract 1, element-wise: gives [0 1 ... n-1]
"       % For each k in [0 1 ... n-1]
  @     %   Push k
  :     %   Range [1 2 ... k]
  o     %   Modulo 2, element-wise: gives [1 0 1 ...]
  XB    %   Convert from binary to decimal
  s     %   Sum. This is needed for k=0, to transform the empty array into 0
        % Implicit end. Implicit display
Luis Mendo
fonte
5

Python 2 , 45 37 36 bytes

-3 bytes graças a user202729
-1 byte graças a mathmandan

s=0
exec"print s;s+=s+~s%2;"*input()

Experimente online!

Cajado
fonte
Dobrar sé o mesmo que adicionar sa si próprio, por isso acredito que você poderia fazer s+=s+~s%2para salvar um byte.
mathmandan
5

Python 3, 68 61 54 48 43 bytes

c=lambda x,r=0:x and[r]+c(x-1,2*r+~r%2)or[]  

Agradecemos a user202729 por ajudar a salvar 19 bytes e ovs por ajudar a salvar 6 bytes.

Experimente Online

Manish Kundu
fonte
Obrigado por esse byte -1. E acho que não posso substituir se mais por e ou?
Manish Kundu
Ok, já fiz isso.
Manish Kundu
2
Como x == 0é equivalente a not xse xfor um número inteiro, troque os operandos (isto é, x if c else y= y if not c else x) economizarão mais alguns bytes.
user202729
Você também pode soltar i%2e usar em 1-r%2vez disso
Rod
11
Então você não precisa acompanhar i.
precisa saber é o seguinte
4

Casca , 7 bytes

mḋḣ↑Θݬ

Experimente online!

Com base em 1, a entrada n fornece os primeiros n resultados.

Explicação

     ݬ   The infinite list [1, 0, 1, 0, 1, ...]
    Θ     Prepend a zero.
   ↑      Take the first n elements.
  ḣ       Get the prefixes of that list.
mḋ        Interpret each prefix as base 2.
Martin Ender
fonte
4

APL (Dyalog Unicode) , 11 bytes SBCS

Assume ⎕IO( I ndex O rigin) como sendo 0, o padrão em muitos sistemas. Função de prefixo tácito anônimo. 1 indexado.

(2⊥⍴∘1 0)¨⍳

Experimente online!

ɩ ndices 0 ... n-1

( Aplique a seguinte função tácita a cada

⍴∘1 0 remodelar ciclicamente a lista [1,0]com esse comprimento

2⊥ converter do número base-2 (binário) para o normal

Adão
fonte
4

Perlv5.10 -n , 24 + 1 bytes

-3 bytes graças a Nahuel Fouilleul !

say$v=$v*2|$|--while$_--

Experimente online!

Mesma lógica da minha versão do Ruby, mas mais curta porque o perl é mais conciso. Por alguma estranha razão, printnão faria um separador (caramba!), Então eu tive que usar sayfrom v5.10;para que isso funcionasse, não sei como pontuar isso, então estou deixando de fora por enquanto ?. ..

Explicação

say    # Like shouting, but milder.
  $v = $v*2 | $|-- # Next element is this element times 2 bitwise-OR
                   # with alternating 0 1 0 1..., so 0b0, 0b1, 0b10, 0b101...
                   # $. is OUTPUT_AUTOFLUSH, which is initially 0 and
                   #   setting all non-zero values seem to be treated as 1
  while $_-- # do for [input] times
Unihedron
fonte
para a pontuação eu diria: 27 + 1 ( -n) = 28 bytes, porque para executar um liner perl, deve-se usar -ee usar 5.10, você só precisa usar -E, que é do mesmo comprimento
Nahuel Fouilleul
pode salvar 3 bytes usando em $|--vez de($.^=1)
Nahuel Fouilleul
4

C , 81 55 59 bytes

1 indexado.

i,j;f(c){for(i=j=0;i<c;)printf("%d ",i++&1?j+=j+1:(j+=j));}

Programa completo, menos golfe:

i;j;main(c,v)char**v;{c=atoi(*++v);for(;i<c;i++)printf("%d ",i&1?j+=j+1:(j+=j));}

Experimente online!

EDIÇÃO 2: Eu assumi que as funções não precisavam ser reutilizáveis ​​agora que penso nisso; faz todo o sentido que elas precisem ser reutilizáveis: P

Edição: Eu estava sob o equívoco de que eu tinha que incluir todo o programa na resposta, acontece que eu só precisava da função que faz isso. Isso é bom.

Tenho certeza de que posso raspar alguns bytes aqui e ali. Eu já empreguei alguns truques. Uma grande parte do programa é dedicada a obter o argumento e transformá-lo em um int. Este é o meu primeiro código de golfe. Se estou fazendo algo errado, diga-me: P

Minerscale
fonte
2
Bem-vindo ao PPCG! :) Eu não sou do tipo C, mas você pode conseguir algumas dicas da solução da Steadybox .
Salsicha
Ok, isso faz mais sentido agora, incluí o programa inteiro quando tudo o que preciso é de uma função e o restante pode ser feito em um rodapé. Eu acho que isso pode ser significativamente melhorado então.
Minerscale
Bem-vindo ao PPCG! Você pode salvar um byte removendo i++e alterando i&1para i++&1. Além disso, embora como variáveis ​​globais ie jsejam inicializadas com zero inicialmente, elas precisam ser inicializadas dentro da função, porque os envios de funções precisam ser reutilizáveis .
Steadybox
11
Melhor ainda, é possível economizar mais 2 bytes, eliminando totalmente o ternário.
precisa saber é o seguinte
2
50 bytes: i,j;f(c){for(i=j=0;i<c;)printf("%d ",j+=j+i++%2);} Experimente online!
Steadybox
4

Haskell , 47 40 53 49 44 40 34 bytes

-4 bytes graças ao usuário202729
-6 bytes graças a Laikoni

(`take`l)
l=0:[2*a+1-a`mod`2|a<-l]

Experimente online!

oktupol
fonte
Você pode substituir otherwisepor exemplo 1>0( otherwise == True))
flawr
Para jogar ainda mais, você pode usar o protetor para atribuir algo, por exemplo: Faça isso online!
flawr
11
PS: Confira também dicas de golfe em haskell , bem como nossa sala de chat com mônadas e homens .
flawr
11
Você precisa criar uma função que retorne os primeiros n elementos da lista em que n é o argumento.
totallyhuman
11
Sim, exatamente. Posso recomendar o nosso Guia de Regras de Golfe em Haskell , que tenta capturar o consenso atual sobre o que é permitido e o que não é.
Laikoni 22/01
4

Ruby , 26 bytes

->n{(1..n).map{|i|2**i/3}}

Experimente online!

Supera todas as respostas ruby ​​mais antigas.

Explicação

1/3em binário parece 0.01010101..., então, se você o multiplicar por potências de dois, obtém:

n| 2^n/3
-+---------
1|0.1010101...
2|01.010101...
3|010.10101...
4|0101.0101...
5|01010.101...
6|010101.01...

Mas Ruby calcula os números na divisão int, fornecendo a sequência que eu preciso.

MegaTom
fonte
4

J , 9 bytes

[:#.\2|i.

Como funciona?

i. - lista 0..n-1

2| - os itens da lista mod 2

\ - todos os prefixos

#. - para decimal

[: - bata o garfo (como eu tenho o número par (4) de verbos)

Experimente online!

Galen Ivanov
fonte
3

Retina , 28 bytes

)K`0
"$+"+¶<`.+
$.(*__2*$-1*

Experimente online!

Com base em 0, então a entrada n fornece os primeiros n + 1 resultados.

Explicação

Usa a recursão do OEIS:

a(n) = a(n-1) + 2*a(n-2) + 1

Vamos seguir o programa:

)K`0

Este é um estágio constante: descarta a entrada e define a cadeia de trabalho como 0o valor inicial da sequência. O )quebra esta fase em um grupo. Esse grupo em si não faz nada, mas quase todas as etapas (incluindo as de grupo) registram o resultado em um log, e precisaremos de duas cópias 0desse log para que o programa funcione.

"$+"+¶<`.+
$.(*__2*$-1*

Há várias configurações aqui: "$+"+envolve o palco em um loop. O "$+"é tratado como uma substituição e $+refere-se à entrada do programa, ou seja, n . Isso significa que o loop é executado n vezes.

Em seguida, ¶<agrupa cada iteração em um estágio de saída, que imprime a entrada do estágio com um avanço de linha à direita (para que a primeira iteração imprima o zero, a segunda iteração imprima o resultado da primeira iteração e assim por diante).

O estágio em si substitui toda a cadeia de trabalho pela substituição na última linha. Esse utiliza um parêntese de fechamento implícito e argumentos implícitos para o operador de repetição *, portanto, é realmente a abreviação de:

$.($&*__2*$-1*_)

O material dentro dos parênteses pode ser dividido em três partes:

  • $&*_: fornece uma sequência de a (n-1) _ s.
  • _: dá um único _.
  • 2*$-1*_: fornece uma sequência de 2 * a (n-1) _ . O $-1refere-se ao penúltimo resultado no log de resultados, ou seja, a iteração do loop antes do último. É por isso que precisamos fazer cópias do zero no log, caso contrário, isso se refere à entrada do programa na primeira iteração.

Em seguida, $.(…)mede o comprimento da sequência resultante. Em outras palavras, calculamos a(n) = a(n-1) + 1 + 2*a(n-2)passando por unário (na verdade, não: $.(…)é preguiçoso e, na verdade, não avalia seu conteúdo, se é possível determinar o comprimento resultante diretamente por meio da aritmética, portanto isso é bastante eficiente).

O resultado da iteração final do loop (o n + 1 o elemento da sequência) é impresso devido à saída implícita de Retina no final do programa.

Martin Ender
fonte
3

Brain-Flak , 36 bytes

{([()]{}<((({}<>)<>){}([{}]()))>)}<>

Experimente online!

Explicação:

O próximo número na sequência é obtido por n*2+1ou n*2+0.

{([()]{}< Loop input times
  (
   (({}<>)<>){} Copy n to other stack; n*2
   ([{}]())  i = 1-i
  ) push n*2 + i
>)} End loop
<> Output other stack
MegaTom
fonte
3

Ruby 42 41 43 41 37 35 31 33 30 bytes

-2 bytes graças ao Unihedron

-3 bytes graças a GB

->x{a=0;x.times{a-=~a+p(a)%2}}

Experimente online!

Asone Tuhid
fonte
Bom trabalho! Eu gosto da sua fórmula ^^
Unihedron
11
salvar 3 bytes:->x{a=0;x.times{a-=~a+p(a)%2}}
GB
2

> <> , 22 + 3 bytes (sinalizador -v)

0:nao::1+2%++$1-:?!;$!

Experimente online!

Explicação

A pilha é inicializada com o contador de loop.

0:nao                  : Push 0 to the stack, duplicate and print with a new line.
                         [7] -> [7, 0]
     ::1+              : Duplicate the stack top twice more then add 1 to it.
                         [7, 0] -> [7, 0, 0, 1]
         2%++          : Mod the stack top by 2 then add all values on the stack bar the loop counter.
                         [7, 0, 0, 1] -> [7, 1]
             $1-:?!;$! : Swap the loop counter to the top, minus 1 from it and check if zero, if zero stop the program else continue.
Pelicano-verde
fonte
2

Java 8, 115 81 80 52 bytes

n->{for(int i=2;n-->0;i*=2)System.out.println(i/3);}

Porto da resposta Python 2 de @Neil .
1 indexado e emitido diretamente, cada valor em uma linha separada.

Explicação:

Experimente online.

n->{                           // Method with integer parameter and no return-type
  for(int i=2;                 //  Start integer `i` at 2
      n-->0;                   //  Loop `n` times:
      i*=2)                    //    Multiply `i` by 2 after every iteration
    System.out.println(i/3);}  //   Print `i` integer-divided by 3 and a new-line

Resposta antiga de 80 bytes:

n->{String t="",r=t;for(Long i=0L;i<n;)r+=i.parseLong(t+=i++%2,2)+" ";return r;}

Entrada indexada em 1 e Stringsaída delimitada por espaço

Explicação:

Experimente online.

n->{                             // Method with integer parameter and String return-type
  String t="",r=t;               //  Temp and result-Strings, both starting empty
  for(Long i=0L;i<n;)            //  Loop from 0 to `n` (exclusive)
    r+=                          //   Append the result-String with:
       i.parseLong(        ,2);  //    Binary to integer conversion
                   t+=           //     append the temp-String with:
                      i  %2      //      current index `i` modulo-2
                       ++        //      and increase `i` by one afterwards
       +" ";                     //    + a space
  return r;}                     //  Return the result-String
Kevin Cruijssen
fonte
2

C, 47 46 bytes

a;f(n){for(a=0;n--;a+=a-~a%2)printf("%d ",a);}

O acumulador acomeça com zero. Em cada etapa, dobramos ( a+=a) e adicionamos um se o bit menos significativo anterior era zero ( !(a%2)ou equivalente -(~a)%2).

Programa de teste

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv)
{
    while (*++argv) {
        f(atoi(*argv));
        puts("");
    }
}

Resultados

$ ./153783 1 2 3 4 5 6
0 
0 1 
0 1 2 
0 1 2 5 
0 1 2 5 10 
0 1 2 5 10 21 
Toby Speight
fonte
2

Japonês , 10 9 7 6 bytes

Todos derivados independentemente de outras soluções.

1 indexado.

õ!²mz3

Tente


Explicação

õ        :[1,input]
 !²      :Raise 2 to the power of each
   m     :Map
    z3   :Floor divide by 3

Tente


Versão de 7 bytes

õ_ou ì2

Tente

õ            :[1,input]
 _           :Pass each through a function
   o         :[0,current element)
    u        :Modulo 2 on above
      ì2     :Convert above from base-2 array to base-10

Versão de 9 bytes

õ_îA¤w)n2

Tente

õ            :[1,input]
 _           :Pass each through a function
   A         :10
    ¤        :Convert to binary
     w       :Reverse
  î          :Repeat the above until it's length equals the current element
      )      :Close nested methods
       n2    :Convert from binary to base-10
Shaggy
fonte
1

MATL , 7 bytes

:&+oRXB

Experimente online!

Explicação:

         % Implicitly grab input, n
:        % Range: 1 2 ... n

 &+      % Add the range to itself, transposed
         % 2 3 4 5 ...
         % 3 4 5 6 ...
         % 4 5 6 7 ...
         % 5 6 7 8 ...

   o     % Parity (or modulus 2)
         % 0 1 0 1 ...
         % 1 0 1 0 ...
         % 0 1 0 1 ...
         % 1 0 1 0 ...

    R    % Upper triangular matrix:
         % 0 1 0 1
         % 0 0 1 0
         % 0 0 0 1
         % 0 0 0 0

    XB   % Convert rows to decimal:
         % [5, 2, 1, 0]
         % Implicitly output

A saída seria 0, 1, 2, 5 ...se Pfoi adicionada ao final ( flip), tornando-o em 8 bytes.

Stewie Griffin
fonte
11
Boa ideia,&+
Luis Mendo
1

Ruby -n ,32. 30 + 1 bytes

Como temos exatamente 1 linha de entrada, $.é muito conveniente!

EDIT: Estou surpreso por ter conseguido me superar, mas parece usar o -nque conta como 1 (pela regra 2 em condições especiais padrão , pois o Ruby pode ser executado com ruby -e 'full program'(portanto, -né 1) todas as instâncias getsusadas apenas uma vez Seja um jogador de golfe dessa maneira; acredito que esse é um marco para o ruby, fale se você não concorda com essa linha de pensamento antes de reutilizá-la repetidamente no futuro)

v=0
?1.upto($_){p v=v*2|$.^=1}

Experimente online!

Explicação

# while gets(); -- assumed by -n
v=0            # First element of the sequence
?1.upto($_){   # Do from "1" to "$LAST_READ_LINE" aka: Repeat [input] times
  p            # print expression
  v=v*2|$.^=1  # Next element is current element times two
               # bitwise-or 0 or 1 alternating
               # $. = lines of input read so far = 1 (initially)
}
# end           -- assumed by -n
Unihedron
fonte
Interessante. É possível em 27 bytes , no entanto.
Eric Duminil
11
Agradável! Parece que todos nós fomos derrotados por 26b.
Unihedron
1

AWK a=0 , 31 bytes

{for(;$1--;a=a*2+1-a%2)print a}

Experimente online!

Usa a fórmula roubada descaradamente desta outra resposta Ruby.

Apesar de não ter a=0iria trabalhar (awk trata "vazio" como 0), o primeiro elemento de 0 não vai ficar impresso e em vez disso ser uma emptylinha, que enquanto eu diria é uma saída válida provavelmente não vai passar, então não há a=0o que pode ser inserido como argumento de linha de comando.

Unihedron
fonte
Eu gosto da sua fórmula ^^
Asone Tuhid
1

brainfuck , 40 bytes

,[>.>>[>]<[.->[>]+[<]+<]+<[[-<+>]>-<]<-]

Experimente online!

Indexado a 0. Entrada como código de caractere, saída como unário com bytes nulos que separam séries de códigos de caracteres 1s. Assume células de 8 bits, a menos que você queira inserir mais de 255. Assume células negativas, embora isso possa ser corrigido à custa de vários bytes.

Anteriormente, 50 bytes

,[[<]>->>[<-<->>>>-<]<[->>++<<]>>+[-<<+>>]<<.<<+>]

Experimente online!

Entradas como código de caracteres, saídas como código de caracteres. 1 indexado. Provavelmente poderia jogar um pouco de golfe.

O @Unihedron aponta que eu esqueci de especificar que isso precisa de células de tamanho infinito, caso contrário, ele chega ao 8º número.

Brincadeira
fonte
Quando o executo com `` (0d018) como o caso de teste, seu código imprime `* UªUªUªUªUªUª` (0x01 02 05 0a 15 2a 55 aa 55 aa 55 aa 55 aa 55 aa 55 aa; 0d001 002 005 010 021 042 085 170 085 170 085 170 085 170 085 170 085 170) :( tio.run/##SypKzMxLK03O/…
Unihedron
Ok, parece que é um problema de tamanho de célula. Eu acho que qualquer um o seu código deve adaptar-se às grandes inteiros ou você precisa especificar a implementação que iria executar o código corretamente, mas o padrão de células de 8 bits não é suficiente
Unihedron
Esqueceu-se disso, obrigado @Unihedron! Vou pensar em uma versão de 8 bits, provavelmente com saída unária.
Jo rei
Usando um intérprete com células de 32 bits, ele funciona. Embora eu acho que eu poderia ter uma chance em uma versão bitinteger (8 bits) me se você não tem por fim de semana: D
Unihedron