Последовательность Баум-Сладкий (A086747 с изюминкой)

Возьмите положительное целое число nи выведите целые числа от 1 до n, для которых последовательность Baum-Sweet возвращает true. Последовательность Баума-Сладкого должна возвращать ложь, если двоичное представление числа содержит нечетное число последовательных нулей в любом месте числа, и верно в противном случае. Для получения дополнительной информации, нажмите на ссылку. Вот пара примеров:

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

Вот пример n=32

Шаг 1: последовательность Baum-Sweet, визуализированная для 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)

Итак, после вычисления последовательности Баума-Свита для n, возьмите числа, которые были правдивыми для последовательности, и соберите их для конечного результата. Ибо n=32мы бы имели:

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

В качестве окончательного ответа.

Это код-гольф , выигрывает самый короткий счетчик байтов.

05AB1E , 10 9 байтов

Сохранил байт благодаря Аднану

ƒNb00¡SP–

Попробуйте онлайн!

объяснение

ƒ          # 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 байта

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

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

Чуть более интересное рекурсивное решение:

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

67 байт благодаря @Neil.

g это функция для вызова.

Python 2, 62 байта

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

Проверяет наличие нечетных серий единиц в двоичном представлении путем разделения 00и проверки, остаются ли какие-либо нули в строковом представлении результирующего списка. Досадно, что двоичные числа начинаются с 0bнуля, который нужно удалить, чтобы избежать ложного срабатывания.

Перечисление выполняется путем повторения вниз.

Bash, 5846 байтов

правок:

• Заменены bc на dc (Thx @Digital Trauma!)
• Начните с 1;

Golfed

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

Тестовое задание

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

Разъяснения

ракушка

seq $1 #generate a sequence of integers from 1 to N, one per line
|sed   #process with 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

Попробуйте онлайн!

Пакет, 143 байта

@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 байт

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

Попытайся

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

( []используются для группирования без захвата, с <[]>использованием для классов символов)

PowerShell , 79 61 байт

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

Попробуйте онлайн!

Сегодня утром у меня появилось вдохновение изменить способ выполнения -splitоперации, а затем увидеть, что это похоже на то , как построен ответ xnor , так что, думаю, великие умы думают одинаково?

Мы выполняем цикл от 1до ввода $args[0]и используем Where-Objectоператор для извлечения соответствующих чисел |?{...}. Предложение является простым логическим значением - мы гарантируем, что 0это -notinрезультат (...).

Внутри скобок мы [convert]::текущее число $_ ToStringс основанием 2(то есть, превратить его в двоичную строку). Затем мы получаем -splitстроку в регулярном выражении 1|00- это жадное совпадение, и в результате получается массив строк (например, 100010превратится в '','','0','','0'и т. Д.).

Таким образом, если каждый запуск 0s в двоичной строке является четным (это означает, что регулярное выражение разделило их на пустые строки), то результатом 0будет -notinрезультат, поэтому Whereпредложение истинно и выбрано число. Эти числа остаются на конвейере и вывод неявный.

Python 2 , 67 47 байт

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

Благодаря @xnor от игры в гольф 20 (!) Байтов!

Возвращает неупорядоченный список. Это довольно эффективно: ввод 100 000 занимает около 40 мс на TIO.

Попробуйте онлайн!

Mathematica, 59 байт

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

Mathematica ответ № 4 ...

MATL , 12 11 байт

:"@BY'og)?@

Попробуйте онлайн!

объяснение

Чтобы определить, является ли число допустимым, оно преобразуется в двоичное, применяет кодирование по длинам серий, сохраняет только серии с нечетной длиной и проверяет, не сохранилось ли число нулей.

:       % 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 байт

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

Читает ввод из stdin и использует binфункцию из miscFuncsпакета для преобразования из десятичного в двоичный вектор. Следовательно, выполняет кодирование длин серий, чтобы проверить значения == 0и длины нечетные.

С накоплением , 69 байтов

Попробуй это здесь!

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

Или неконкурентоспособный в 67 байтов:

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

И, еще более неконкурентоспособный на 49 байтов:

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

Все принимают вход как TOS и оставляют вывод на TOS.

объяснение

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

Функция:

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

Объяснение неконкурентоспособности:

Это то же самое, что и выше, с несколькими ключевыми отличиями:

:>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 байтов

После небольшого количества экспериментов я понял, что могу сделать немного лучше, чем мое оригинальное решение, используя технику, похожую на пакетный ответ, который придумал Нейл .

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

Попробуйте онлайн!

Как и в моем исходном решении, есть два цикла - внешний цикл, повторяющийся над числами, которые мы хотим проверить, и внутренний цикл, проверяющий последовательность битов для каждого числа. Тест работает, проверяя два бита за раз (по модулю 4 текущего значения). Если это равно 2, мы получили нечетную последовательность нулей и можем прервать внутренний цикл и перейти к следующему числу.

Если модуль 4 не равен 2, нам нужно продолжить тестирование оставшихся битов, поэтому мы сдвигаем биты, которые уже были протестированы. Это делается путем деления значения, давайте назовем его n , на 2+2*!(n%2). Это означает, что если первый бит был 1, мы делим на 2 (отбрасывая этот 1 бит), но если это был 0, мы делим на 4, поэтому мы всегда будем отбрасывать пары нулей.

Если в итоге мы опустимся до нуля, это означает, что не было никаких нечетных последовательностей нулевых битов, поэтому мы выписываем число.

Visual Basic (.net 4.5) 163 байта

Первый ответ здесь, так что я уверен, что что-то напортачил. Дайте мне знать, и я исправлю. Разрешены ли лямбды Visual Basic?

Спасибо MamaFunRoll за идею удаления последовательных нулей

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) выходов

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

Java, 144 130 128 байт

Это не так хорошо, как я думаю, но я подумал, что было бы неплохо использовать Regex, несмотря на то, что он никогда не использовался.

Golfed:

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
}

Изменить: мне удалось сохранить 14 байтов, сделав регулярное выражение 00 | 1 вместо 00 и удалив ".replace (" 1 "," ")" между replaceAll и isEmpty!

Редактировать 2: я смог сохранить 2 байта, сделав i Integer и ссылаясь на Integer.toString с i.toString.

Clojure, 103 байта

Я не думаю, что это самый короткий путь ...

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

Использует re-seqдля поиска последовательных нулей, отображает их длины по модулю 2 в a set, отбрасывает их, если число 1найдено из набора.

Чудо , 38 байт

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

Использование:

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

объяснение

Более читабельно:

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

rng 1 +1 #0: Диапазон от 1 до ввода.

fltr@ ...: Диапазон фильтра со следующим предикатом.

bn #0: Преобразовать текущий элемент в двоичный файл. (Это будет ведущий 0b).

Rstr #["00"]: Рекурсивно удалять любые вхождения 00в строке.

len iO 0: Подсчитать количество 0s в строке.

=1: Проверьте, равна ли сумма 1. Если 0в строке после обрезки осталась только одна строка 0b, то возвращается значение true; в противном случае возвращается false.

Рубин, 78 69 68 байт

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

Старые версии:

->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 байт

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

Вычисляет для каждой серии последовательных цифр в номере {общую цифру в этой серии плюс (1, если длина нечетная, 2, если длина четная)}; если какой-либо из ответов является {1}, то число не входит в последовательность.

Mathematica, 75 байт

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

#~IntegerDigits~2вычисляет список двоичных цифр ввода #. Splitэтот список разбивает на идентичные элементы, берет Casesто соответствие {0..}, берет Lengthкаждый из них, берет EvenQдлины и затем возвращает Andрезультаты.

Python 3, 86 82 байта

Гольф в прогрессе ...

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

Вычеркнул 4 байта, изменив bin(x)[2:]на «просто» bin(x)- это оставляет 0bв начале строки, но я понял, что это на самом деле не влияет на вычисления :)

Python, 142 байта

В основном это просто практика игры в гольф на моем Питоне.

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

Желе , 10 байт

2ṗx"`ḂḄf@R

Ужасно неэффективно. Попробуйте онлайн!

Рубин, 54 53 48 байтов

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

Я не думал, что регулярное выражение для этого будет настолько простым.

редактировать 1: переключено на отклонение, чтобы избавиться от отрицания на -1.

редактировать 2: включен matchв =~течение -5.

C # 159 157 155 байтов

Сохранено 2 x два байта благодаря TuukkaX.

Примечание: распечатывает входные данные в обратном порядке.

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

Объяснение:

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 байт

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

Одинаковой длины:

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

Рубин, 53 байта

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

Желе, 15 13 10 байт

сохранив два байта после просмотра других ответов, еще 3 байта благодаря Деннису

Bœṣ0,0Ȧµ€T

объяснение

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)