La secuencia Baum-Sweet (A086747 con un toque)

Tome un entero positivo ne imprima los enteros de 1 a n para los cuales la secuencia Baum-Sweet devuelve verdadero. La secuencia Baum-Sweet debería devolver falso si la representación binaria del número contiene un número impar de ceros consecutivos en cualquier parte del número, y la verdad es lo contrario. Para más información, haga clic en el enlace. Aquí hay un par de ejemplos:

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

Aquí hay un ejemplo dado n=32

Paso 1: La secuencia 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)

Entonces, después de calcular la secuencia Baum-Sweet para n, tome los números que fueron verdaderos para la secuencia y recójalos para el resultado final. Porque n=32tendríamos:

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

Como la respuesta final.

Este es el código de golf , el conteo de bytes más corto gana.

05AB1E , 10 9 bytes

Salvó un byte gracias a Adnan

ƒNb00¡SP–

Pruébalo en línea!

Explicación

ƒ          # 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(", "))

Solución recursiva un poco más interesante:

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

67 bytes gracias a @Neil.

g es la función para llamar.

Python 2, 62 bytes

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

Comprueba corridas impares de 1 en la representación binaria al dividir 00y comprobar si quedan ceros en la representación de cadena de la lista resultante. Molesto, los números binarios comienzan con 0bun cero que debe eliminarse para evitar un falso positivo.

La enumeración se realiza recurriendo hacia abajo.

Golpetazo, 5846 bytes

EDICIONES:

• Se reemplazó bc por dc (¡Thx @Digital Trauma!)
• Comience con 1;

Golfed

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

Prueba

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

Explicado

cáscara

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

¡Pruébelo en línea!

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..$_}

Intentalo

{
  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
}

( []se usan para la agrupación sin captura, con las <[]>usadas para las clases de caracteres)

PowerShell , 79 61 bytes

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

Pruébalo en línea!

Me inspiré esta mañana para cambiar la forma en que realizo la -splitoperación, luego vi que es similar a cómo se construye la respuesta de xnor , así que, ¿creo que las grandes mentes piensan igual?

Realizamos un bucle desde 1arriba hasta la entrada $args[0], y utilizamos un Where-Objectoperador para extraer los números apropiados |?{...}. La cláusula es un valor booleano simple: nos aseguramos de que 0sea -notinel resultado de (...).

Dentro de los parens, tenemos [convert]::el número actual $_ ToStringcon la base 2(es decir, lo convertimos en una cadena binaria). Luego -splitcolocamos la cadena en la expresión regular 1|00: esta es una coincidencia codiciosa y da como resultado una serie de cadenas (por ejemplo, 100010se convertiría en '','','0','','0'y así sucesivamente).

Por lo tanto, si cada ejecución de 0s en la cadena binaria es par (lo que significa que la expresión regular los ha dividido en cadenas vacías), entonces 0será -notinel resultado, por lo que la Wherecláusula es verdadera y se selecciona el número. Esos números se dejan en la tubería y la salida es 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)

¡Gracias a @xnor por jugar golf en 20 (!) Bytes!

Devuelve una lista desordenada. Es bastante eficiente: la entrada 100,000 toma aproximadamente 40 ms en TIO.

Pruébalo en línea!

Mathematica, 59 bytes

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

Respuesta de Mathematica número 4 ...

MATL , 12 11 bytes

:"@BY'og)?@

Pruébalo en línea!

Explicación

Para detectar si un número es válido, esto se convierte en binario, aplica codificación de longitud de ejecución, mantiene solo ejecuciones de longitud impar y comprueba si no sobrevive ninguna ejecución de ceros.

:       % 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,"")}

Lee la entrada de stdin y utiliza la binfunción del miscFuncspaquete para convertir de decimal a binario. En consecuencia, realiza la codificación de longitud de ejecución para verificar que los valores == 0y las longitudes sean impares.

Apilado , 69 bytes

Pruébalo aquí!

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

O, sin competencia a 67 bytes:

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

Y, aún más sin competencia a 49 bytes:

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

Todos toman la entrada como TOS y dejan la salida en TOS.

Explicación

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

La función:

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

Explicación de la no competencia:

Es igual que el anterior, con algunas diferencias clave:

:>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

Después de un poco de experimentación, me di cuenta de que podía hacerlo bastante mejor que mi solución original al usar una técnica similar a la respuesta de Batch que se le ocurrió a Neil .

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

Pruébalo en línea!

Al igual que con mi solución original, hay dos bucles: el bucle externo que itera sobre los números que queremos probar y un bucle interno que prueba la secuencia de bits para cada número. La forma en que funciona la prueba es examinando dos bits a la vez (módulo 4 del valor actual). Si es igual a 2, tenemos una secuencia impar de ceros y podemos abortar el ciclo interno y pasar al siguiente número.

Si el módulo 4 no es igual a 2, debemos continuar probando los bits restantes, por lo que cambiamos los bits que ya se han probado. Esto se hace dividiendo el valor, llamémoslo n , por 2+2*!(n%2). Esto significa que si el primer bit fue un 1, dividimos por 2 (eliminando ese 1 bit), pero si era un 0, dividimos entre 4, por lo que siempre eliminaremos pares de ceros.

Si finalmente llegamos a cero, eso significa que no hubo secuencias impares de bits cero, por lo que escribimos el número.

Visual Basic (.net 4.5) 163 bytes

Primero respondo aquí, así que estoy seguro de que he arruinado algo. Avísame y lo arreglaré. ¿Se permiten las lambdas de Visual Basic?

Gracias a MamaFunRoll por la idea de eliminar ceros 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))))

R (32) salidas

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

Java, 144 130 128 Bytes

Esto no es tan divertido como creo que puede ser, pero pensé que sería una linda solución usar un Regex, a pesar de nunca haberlo usado.

Golfizado:

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;}

Sin golf:

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: pude guardar 14 bytes al hacer la expresión regular 00 | 1 en lugar de 00, y eliminar ".replace (" 1 "," ")" entre replaceAll e isEmpty!

Edición 2: pude guardar 2 bytes al convertir i en un número entero y hacer referencia a Integer.toString con i.toString.

Clojure, 103 bytes

No creo que este sea el camino más corto ...

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

Usos re-seqpara encontrar ceros consecutivos, los mapas de sus longitudes de módulo 2 a una set, los descartes si el número 1se encuentra en el conjunto.

Maravilla , 38 bytes

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

Uso:

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

Explicación

Más legible:

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

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

fltr@ ...: Rango de filtro con el siguiente predicado.

bn #0: Convierte el elemento actual a binario. (Esto tendrá un liderazgo 0b).

Rstr #["00"]: Pode recursivamente cualquier aparición de 00en la cadena.

len iO 0: Cuenta las cantidades de 0s en la cadena.

=1: Verifique si la cantidad es igual a 1. Si lo único que 0queda en la cadena después de la poda está al frente 0b, entonces esto devuelve verdadero; de lo contrario, esto devuelve falso.

Rubí, 78 69 68 bytes

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

Versiones anteriores:

->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 ejecución de dígitos consecutivos en un número, {el dígito común en esa ejecución más (1 si la longitud es impar, 2 si la longitud es par)}; Si alguna de las respuestas es {1}, el número no está en la secuencia.

Mathematica, 75 bytes

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

#~IntegerDigits~2calcula la lista de dígitos binarios de la entrada #. Splitesa lista en series de elementos idénticos, tome la Casescoincidencia {0..}, tome la Lengthde cada uno de ellos, tome EvenQlas longitudes y luego devuelva Andlos resultados.

Python 3, 86 82 bytes

Golf en progreso ...

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

Golfé 4 bytes cambiando bin(x)[2:]a solo bin(x): esto se va 0bal comienzo de la cadena, pero me di cuenta de que esto no afecta los cálculos :)

Python, 142 bytes

Esto es principalmente para practicar golf en mi 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)]

Jalea , 10 bytes

2ṗx"`ḂḄf@R

Terriblemente ineficiente. Pruébalo en línea!

Ruby, 54 53 48 bytes

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

No pensé que la expresión regular para esto fuera tan básica.

editar 1: se cambió a rechazar para deshacerse de la negación de -1.

editar 2: cambiado matcha =~-5.

C # 159 157 155 bytes

Guardado 2 x dos bytes gracias a TuukkaX.

Nota: imprime las entradas en orden inverso.

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);}

Explicación:

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]&]&

La misma longitud:

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

Rubí, 53 bytes

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

Jalea, 15 13 10 bytes

ahorró dos bytes después de mirar otras respuestas, otros 3 bytes gracias a Dennis

Bœṣ0,0Ȧµ€T

Explicación

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)