A sequência Baum-Sweet (A086747 com um toque)

Pegue um número inteiro positivo ne imprima os números inteiros de 1 a n para os quais a sequência Baum-Sweet retorna verdadeira. A sequência Baum-Sweet deve retornar falso se a representação binária do número contiver um número ímpar de zeros consecutivos em qualquer lugar do número e, na verdade, de outra forma. Para mais informações, clique no link. Aqui estão alguns exemplos:

1 -> 1 -> Truthy
2 -> 10 -> Falsy
3 -> 11 -> Truthy
4 -> 100 -> Truthy (Even run of zeros)

Aqui está um exemplo dado n=32

Etapa 1: a sequência Baum-Sweet visualizada para n=32

1               1 (1)
1 0             0 (2)
11              1 (3)
1 00            1 (4)
1 0 1           0 (5)
11 0            0 (6)
111             1 (7)
1 000           0 (8)
1 00 1          1 (9)
1 0 1 0         0 (10)
1 0 11          0 (11)
11 00           1 (12)
11 0 1          0 (13)
111 0           0 (14)
1111            1 (15)
1 0000          1 (16)
1 000 1         0 (17)
1 00 1 0        0 (18)
1 00 11         1 (19)
1 0 1 00        0 (20)
1 0 1 0 1       0 (21)
1 0 11 0        0 (22)
1 0 111         0 (23)
11 000          0 (24)
11 00 1         1 (25)
11 0 1 0        0 (26)
11 0 11         0 (27)
111 00          1 (28)
111 0 1         0 (29)
1111 0          0 (30)
11111           1 (31)
1 00000         0 (32)

Portanto, depois de calcular a sequência Baum-Sweet para n, pegue os números que eram verdadeiros para a sequência e colete-os para o resultado final. Pois n=32teríamos:

[1, 3, 4, 7, 9, 12, 15, 16, 19, 25, 28, 31]

Como a resposta final.

Isso é código-golfe , a menor contagem de bytes ganha.

05AB1E , 10 9 bytes

Guardou um byte graças a Adnan

ƒNb00¡SP–

Experimente online!

Explicação

ƒ          # for N in [0 ... input]
 Nb        # convert N to binary
   00¡     # split at "00"
      S    # convert to list of digits
       P   # product of list
        –  # if 1, print N

JavaScript (ES6), 70 68 63 bytes

g=n=>n?g(n-1).concat(/0/.test(n.toString(2).split`00`)?[]:n):[]

console.log(g(1000).join(", "))

Solução recursiva um pouco mais interessante:

n=>[...Array(n+1).keys()].filter(f=n=>n<2?n:n%4?n&f(n>>1):f(‌​n/4))

67 bytes graças a @Neil.

g é a função a ser chamada.

Python 2, 62 bytes

g=lambda n:n*[0]and g(n-1)+[n]['0'in`bin(n)[1:].split('00')`:]

Verifica execuções ímpares de 1s na representação binária dividindo 00e verificando se há zeros na representação de string da lista resultante. Irritantemente, os números binários começam com 0bum zero que precisa ser removido para evitar um falso positivo.

A enumeração é feita recorrendo para baixo.

Bater, 58., 46 bytes

EDITAS:

• Substituído bc por dc (Thx @Digital Trauma!)
• Comece com 1;

Golfe

seq $1|sed 'h;s/.*/dc -e2o&p/e;s/00//g;/0/d;x'

Teste

>./baum 32
1 
3
4
7 
9
12
15
16
19
25
28
31

Explicado

Concha

seq $1 #generate a sequence of integers from 1 to N, one per line
|sed   #process with sed

sed

h                #Save input line to the hold space
s/.*/dc -e2o&p/e #Convert input to binary, with dc
s/00//g          #Remove all successive pairs of 0-es
/0/d             #If there are still some zeroes left
                 #(i.e. there was at least one odd sequence of them)
                 #drop the line, proceed to the next one
x                #Otherwise, exchange the contents of the hold 
                 #and pattern spaces and (implicitly) print

Experimente Online!

Lote, 143 bytes

@for /l %%i in (1,1,%1)do @call:c %%i
@exit/b
:c
@set/ai=%1
:l
@if %i%==1 echo %1&exit/b
@set/ar=%i%%%4,i/=4-r%%2*2
@if %r% neq 2 goto l

Perl 6 , 40 bytes

{grep {.base(2)!~~/10[00]*[1|$]/},1..$_}

Tente

{
  grep            # find all of them
  {
    .base(2)      # where the binary representation
    !~~           # does not match
    /
      10          # ｢10｣
      [ 00 ]*     # followed by an even number of ｢0｣s
      [ 1 | $ ]   # either at end or before a ｢1｣
    /
  }, 1 .. $_      # from one to the input
}

( []são usados ​​para agrupamento sem captura, com <[]>usado para classes de caracteres)

PowerShell , 79 61 bytes

1..$args[0]|?{0-notin([convert]::ToString($_,2)-split'1|00')}

Experimente online!

Tive inspiração nesta manhã para mudar a maneira como realizo a -splitoperação, e depois ver que é semelhante à forma como a resposta do xnor é construída, então, acho que as grandes mentes pensam da mesma forma?

Fazemos loop 1até a entrada $args[0]e usamos um Where-Objectoperador para obter os números apropriados |?{...}. A cláusula é um valor booleano simples - estamos garantindo que esse 0é -notino resultado de (...).

Dentro das parênteses, temos [convert]::o número atual $_ ToStringcom a base 2(ou seja, transformamos em uma sequência binária). Em seguida, colocamos -splita string no regex 1|00- esta é uma correspondência gananciosa e resulta em uma matriz de strings (por exemplo, 100010seria transformada em algo '','','0','','0'assim).

Portanto, se todas as execuções de 0s na cadeia binária forem pares (o que significa que a regex as dividiu em cadeias vazias), 0será -notino resultado, portanto a Wherecláusula é verdadeira e o número é selecionado. Esses números são deixados no pipeline e a saída é implícita.

Python 2 , 67 47 bytes

f=lambda n,k=1:n/k*[1]and[k]+f(n,k-~k)+f(n,4*k)

Graças a @xnor por jogar 20 (!) Bytes!

Retorna uma lista não ordenada. É bastante eficiente: a entrada 100.000 leva aproximadamente 40 ms no TIO.

Experimente online!

Mathematica, 59 bytes

Select[Range@#,!Or@@OddQ/@Tr/@Split[1-#~IntegerDigits~2]&]&

Número 4 da resposta do Mathematica ...

MATL , 12 11 bytes

:"@BY'og)?@

Experimente online!

Explicação

Para detectar se um número é válido, isso se converte em binário, aplica a codificação de comprimento de execução, mantém apenas execuções de comprimento ímpar e verifica se nenhuma execução de zeros sobrevive.

:       % Take input n implicitly. Push range [1 2 ... n]
"       % For each k in [1 2 ... n]
  @     %   Push k
  B     %   Convert to binary
  Y'    %   Run-length encoding. Pushes array of values and array of run-lengths
  o     %   Parity. Gives array that contains 0 for even lengths, 1 for odd
  g)    %   Convert to logical and use index into the array of values
  ?     %   If the result does not contain zeros
    @   %     Push k
        %   End
        % End
        % Implicitly display stack 

R, 75 bytes

for(i in 1:scan()){x=rle(miscFuncs::bin(i));if(!any(x$l%%2&!x$v))cat(i,"")}

Lê a entrada do stdin e usa a binfunção do miscFuncspacote para converter do vetor decimal para o binário. Conseqüentemente, executa a codificação de execução para verificar se os valores == 0e comprimentos são ímpares.

Empilhados , 69 bytes

Experimente aqui!

:>1+[bits{e.b:e b 0#=}chunkby[0 has]filter$sizemap 2%0 eq all]"filter

Ou, não competindo em 67 bytes:

:>1+[bits{e.b:e b 0#=}chunkby[0 has]filter$sizemap even all]"filter

E ainda mais não-competitivo em 49 bytes:

:>1+[bits rle{k:k 0=}filter values even all]fkeep

Todos recebem a entrada como TOS e deixam a saída no TOS.

Explicação

:>1+[...]"filter   input: n
:>                 range from [0, n)
  1+               range from [1, n]
    [...]          a function
         "filter   apply to each cell and filter

A função:

bits{e.b:e b 0#=}chunkby[0 has]filter$sizemap 2%0 eq all  input: c
bits                                                      convert c to binary
    {e.b:e b 0#=}chunkby                                  split into chunks of contiguous 0s
                        [0 has]filter                     take only chunks with 0s
                                     $sizemap             map each chunk to its size
                                              2%          vectorized modulus 2
                                                0 eq      vectorized equality with 0
                                                     all  all of them are of even lengths

Explicação de não-concorrentes:

É o mesmo que acima, com algumas diferenças importantes:

:>1+[bits rle{k:k 0=}filter values even all]fkeep   input: y
          rle                                       run length encode y
             {k:k 0=}filter                         keep keys that = 0
                            values                  get those values
                                            fkeep   like `filter`, but is implemented with
                                                    taking `f` as a boolean mask

Befunge, 84 51 49 bytes

Depois de um pouco de experimentação, percebi que poderia me sair um pouco melhor do que minha solução original usando uma técnica semelhante à resposta em lote que Neil apresentou.

<v::\<&1
:_v#:/+2*2!%2:_v#-2%4
:$<@_v#!:-1\+1$<:.

Experimente online!

Como na minha solução original, existem dois loops - o loop externo repetindo os números que queremos testar e um loop interno testando a sequência de bits para cada número. A maneira como o teste funciona é examinando dois bits de cada vez (módulo 4 do valor atual). Se for igual a 2, temos uma sequência ímpar de zeros e podemos abortar o loop interno e prosseguir para o próximo número.

Se o módulo 4 não for igual a 2, precisamos continuar testando os bits restantes, portanto aumentamos os bits que já foram testados. Isso é feito dividindo o valor, vamos chamá-lo de n , por2+2*!(n%2) . Isso significa que se o primeiro bit for 1, dividimos por 2 (diminuindo esse 1 bit), mas se for 0, dividimos por 4, portanto, sempre eliminamos pares de zeros.

Se finalmente chegarmos a zero, isso significa que não houve seqüências ímpares de zero bits, então escrevemos o número.

Visual Basic (.net 4.5) 163 bytes

A primeira vez que respondo aqui, tenho certeza de que estraguei tudo. Deixe-me saber e eu vou consertar. As lambdas do Visual Basic são permitidas?

Agradecimentos a MamaFunRoll pela idéia de remover zeros consecutivos

Dim R=Sub(m)System.Console.WriteLine(String.Join(",",System.Linq.Enumerable.Range(1, m).Where(Function(s) Not Convert.ToString(s,2).Replace("00","").Contains(0))))

Saídas R (32)

1,3,4,7,9,12,15,16,19,25,28,31

Java, 144 130 128 bytes

Isso não é tão eficiente quanto eu acho que pode ser, mas achei que seria uma solução interessante usar um Regex, apesar de nunca ter usado um.

Golfe:

static String a(int n){String s="";for(Integer i=0;i++<n;)if(i.toString(i,2).replaceAll("00|1","").isEmpty())s+=i+" ";return s;}

Ungolfed:

static String a(int n){
    String s="";                      //Cheaper than using a list/array
    for(Integer i=0;i++<n;)           //Loop n times
        if(i.toString(i,2)            //Convert int to base 2 string
                .replaceAll("00|1","")//Find and remove ones and consecutive zeroes
                .isEmpty())           //If any chars remain, i is truthy
            s+=i+" ";                 //Append i to the storage string
    return s;                         //Return all values
}

Editar: Consegui salvar 14 bytes criando o regex 00 | 1 em vez de 00 e removendo ".replace (" 1 "," ")" entre o replaceAll e o isEmpty!

Edição 2: Consegui salvar 2 bytes, transformando-o em um inteiro e referenciando Integer.toString a i.toString.

Clojure, 103 bytes

Eu não acho que este é o caminho mais curto ...

#(remove(fn[v]((set(map(fn[s](mod(count s)2))(re-seq #"0+"(Integer/toString v 2))))1))(range 1(inc %)))

Usa re-seqpara encontrar zeros consecutivos, mapeia seus comprimentos do módulo-2 para a set, descarta-os se o número 1for encontrado no conjunto.

Maravilha , 38 bytes

@(!>@=1len iO0Rstr#["00"]bn#0)rng1+1#0

Uso:

(@(!>@=1len iO0Rstr#["00"]bn#0)rng1+1#0) 32

Explicação

Mais legível:

@(
  fltr@
    = 1 
      len 
        iO 0 
          Rstr #["00"] 
            bn #0
) rng 1 +1 #0

rng 1 +1 #0: Faixa de 1 a entrada.

fltr@ ...: Intervalo de filtro com o seguinte predicado.

bn #0: Converte o item atual em binário. (Isso terá uma vantagem0b ).

Rstr #["00"]: Apaga recursivamente qualquer ocorrência de 00na sequência.

len iO 0: Conte as quantidades de 0s na string.

=1: Verifique se a quantidade é igual a 1. Se a única 0esquerda da sequência após a remoção estiver na liderança 0b, isso retornará verdadeiro; caso contrário, isso retornará falso.

Rubi, 78 69 68 bytes

->n{(1..n).select{|m|m.to_s(s=2).split(?1).map{|i|s|=i.size};s&1<1}}

Versões mais antigas:

->n{(1..n).select{|m|m.to_s(2).split(?1).select{|i|i.size%2>0}[0].!}}
->n{(1..n).select{|m|b=z=0;(m.to_s(2)+?1).each_char{|i|z+=i>?0?b|=z:1};b&1<1}}

Mathematica, 81 bytes

Select[Range@#,FreeQ[Union@#+Mod[Length@#,2,1]&/@Split[#~IntegerDigits~2],{1}]&]&

Calcula, para cada execução de dígitos consecutivos em um número, {o dígito comum nessa execução mais (1 se o comprimento for ímpar, 2 se o comprimento for par)}; se alguma das respostas for {1}, o número não estará na sequência.

Mathematica, 75 bytes

Select[Range@#,And@@EvenQ/@Length/@Cases[Split[#~IntegerDigits~2],{0..}]&]&

#~IntegerDigits~2calcula a lista de dígitos binários da entrada #. Splitessa lista em execuções de elementos idênticos, faça a Casescorrespondência {0..}, escolha a Lengthcada um deles, escolha EvenQos comprimentos e retorne Andos resultados.

Python 3, 86 82 bytes

Golfe em andamento ...

lambda n:[x for x in range(1,n+1)if 1-any(i%2for i in map(len,bin(x).split('1')))]

Jogou 4 bytes mudando bin(x)[2:]para apenas bin(x)- isso sai 0bno início da string, mas percebi que isso não afeta os cálculos :)

Python, 142 bytes

Isto é principalmente apenas para praticar golfe no meu Python.

def o(n):
 r=0
 for i in bin(n)[2:]:
  if i=='1':
   if r&1:return 0
   r=0
  else:r+=1
 return ~r&1
lambda n:[i for i in range(1,n+1)if o(i)]

Gelatina , 10 bytes

2ṗx"`ḂḄf@R

Terrivelmente ineficiente. Experimente online!

Ruby, 54 53 48 bytes

->n{(1..n).reject{|x|x.to_s(2)=~/10(00)*(1|$)/}}

Eu não acho que o regex para isso fosse tão básico.

edit 1: mudou para rejeitar e se livrar da negação para -1.

editar 2: comutada matchpara =~a -5.

C # 159 157 155 bytes

Economizou 2 x dois bytes graças ao TuukkaX.

Nota: imprime as entradas na ordem inversa.

void B(int n){var b=Convert.ToString(n,2);int c=0,i=0;for(;i<b.Length;){if(b[i++]<49)c++;else if(c%2>0)break;}if(c%2<1)Console.WriteLine(n);if(n>1)B(--n);}

Explicação:

void B(int n)
{
    // convert our int to a binary string
    var b = Convert.ToString(n, 2);

    // set our '0' counter 'c' and our indexer 'i' 
    int c = 0, i = 0;

    // loop over the binary string, without initialisation and afterthought
    for (; i < b.Length;)
    {
        // check for '0' (48 ASCII) and increment i. increment c if true
        if (b[i++] < 49)
            c++;

        // otherwise check if c is odd, and break if it is
        else if (c%2 > 0)
            break;
    }

    // print the int if c is even
    if (c%2 < 1)
        Console.WriteLine(n);

    // recursively call B again with the next number
    if (n > 1)
        B(--n);
}

Mathematica, 69 bytes

Select[Range@#,FreeQ[#~IntegerDigits~2//.{x___,0,0,y___}:>{x,y},0]&]&

O mesmo comprimento:

Select[Range@#,#~IntegerString~2~StringDelete~"00"~StringFreeQ~"0"&]&

Ruby, 53 bytes

->n{(1..n).each{|n|p n if n.to_s(2).count(?0).even?}}

Gelatina, 15 13 10 bytes

salvou dois bytes depois de procurar outras respostas, outros 3 bytes graças a Dennis

Bœṣ0,0Ȧµ€T

Explicação

Bœṣ0,0Ȧµ€T -Helper link: argument K (integer): ex. 24
B          -Convert K to a list of its binary digits: 24 -> [1,1,0,0,0]
   0,0     -Create a list of two 0's: [0,0]
 œṣ        -Split the binary digits on instances of the sublist: [1,1,0,0,0]-> [[1,1],[0]]
      Ȧ    -Any and All: Check if our list has any falsy values or is empty
       µ   -Take all our previous atoms and wrap them into one monad.
        €  -Map this new monad over a list. Since our input is an integer, this implicitly maps it over the range [1..N] (Like the 'R' atom)
         T -Get the indices of all truthy values (1's)