Urutan Baum-Sweet (A086747 dengan Twist)

Ambil bilangan bulat positif ndan cetak bilangan bulat dari 1 ke n di mana urutan Baum-Sweet mengembalikan true. The Baum-manis urutan harus kembali falsy jika representasi biner dari nomor mengandung ganjil nol berturut-turut di mana saja di nomor tersebut, dan truthy sebaliknya. Untuk informasi lebih lanjut, klik tautannya. Berikut beberapa contoh:

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

Berikut ini contoh yang diberikan n=32

Langkah 1: Urutan Baum-Sweet divisualisasikan untuk 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)

Jadi, setelah menghitung urutan Baum-Sweet untuk n, ambil angka yang benar untuk urutan tersebut dan kumpulkan untuk hasil akhir. Karena n=32kita akan memiliki:

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

Sebagai jawaban akhir.

Ini adalah kode-golf , kemenangan jumlah byte terpendek.

05AB1E , 10 9 byte

Menyimpan satu byte, terima kasih kepada Adnan

ƒNb00¡SP–

Cobalah online!

Penjelasan

ƒ          # 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 byte

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

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

Solusi rekursif yang sedikit lebih menarik:

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

67 byte berkat @Neil.

g adalah fungsi untuk memanggil.

Python 2, 62 byte

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

Memeriksa untuk menjalankan aneh 1 dalam representasi biner dengan membelah 00dan memeriksa apakah ada nol tetap dalam representasi string dari daftar yang dihasilkan. Mengganggu, angka-angka biner mulai dengan 0b, yang memiliki nol yang perlu dihapus untuk menghindari positif palsu.

Pencacahan dilakukan dengan berulang.

Pesta, 58, 46 byte

EDIT:

• Diganti bc dengan dc (Thx @Digital Trauma!)
• Mulai dengan 1;

Golf

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

Uji

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

Dijelaskan

kulit

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

Cobalah secara Online!

Batch, 143 byte

@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 byte

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

Cobalah

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

( []digunakan untuk pengelompokan yang tidak menangkap, dengan <[]>digunakan untuk kelas karakter)

PowerShell , 79 61 byte

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

Cobalah online!

Saya mendapat inspirasi pagi ini untuk mengubah cara saya melakukan -splitoperasi, kemudian melihat bahwa itu mirip dengan bagaimana jawaban xnor dibangun, jadi, saya kira orang-orang hebat berpikir sama?

Kami beralih dari 1 atas ke input $args[0], dan menggunakan Where-Objectoperator untuk mengeluarkan nomor yang sesuai |?{...}. Klausa adalah nilai Boolean sederhana - kami ingin memastikan bahwa 0adalah -notinhasil (...).

Di dalam parens, kami [convert]::nomor saat ini$_ ToString dengan pangkalan 2(yaitu, mengubahnya menjadi string biner). Kami kemudian -splitstring pada regex 1|00- ini adalah pertandingan serakah, dan menghasilkan berbagai string (misalnya, 100010akan berubah menjadi '','','0','','0'dan sebagainya).

Jadi, jika setiap run dari 0s dalam string biner adalah genap (artinya regex telah membaginya menjadi string kosong), maka 0akan menjadi-notin hasilnya, jadi Whereklausa itu benar, dan nomor tersebut dipilih. Angka-angka itu ditinggalkan di jalur pipa dan hasilnya tersirat.

Python 2 , 67 47 byte

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

Terima kasih kepada @xnor untuk bermain golf dengan 20 (!) Byte!

Mengembalikan daftar tidak terurut. Ini cukup efisien: masukan 100.000 membutuhkan sekitar 40 ms pada TIO.

Cobalah online!

Mathematica, 59 byte

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

Matematika nomor jawaban 4 ...

MATL , 12 11 byte

:"@BY'og)?@

Cobalah online!

Penjelasan

Untuk mendeteksi jika suatu angka valid, ini dikonversi ke biner, menerapkan enkode run-length, hanya menjalankan run dengan panjang ganjil, dan memeriksa apakah tidak ada run dari nol yang bertahan.

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

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

Membaca input dari stdin dan menggunakan binfungsi dari miscFuncspaket untuk mengkonversi dari desimal ke vektor biner. Akibatnya melakukan pengkodean run-length untuk memeriksa nilai == 0dan panjang ganjil.

Ditumpuk , 69 byte

Coba di sini!

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

Atau, tidak bersaing pada 67 byte:

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

Dan, bahkan lebih tidak bersaing di 49 byte:

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

Semua menerima input sebagai KL dan meninggalkan output pada KL.

Penjelasan

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

Fungsi:

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

Penjelasan tentang tidak bersaing:

Sama seperti di atas, dengan beberapa perbedaan utama:

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

Setelah sedikit bereksperimen, saya menyadari saya bisa melakukan sedikit lebih baik daripada solusi asli saya dengan menggunakan teknik yang mirip dengan jawaban Batch bahwa Neil datang dengan.

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

Cobalah online!

Seperti dengan solusi asli saya, ada dua loop - loop luar iterasi atas angka yang ingin kami uji, dan loop dalam menguji urutan bit untuk setiap nomor. Cara kerja tes ini adalah dengan memeriksa dua bit sekaligus (modulo 4 dari nilai saat ini). Jika itu sama dengan 2 kita punya urutan nol aneh dan dapat membatalkan loop dalam dan melanjutkan ke nomor berikutnya.

Jika modulo 4 tidak sama dengan 2, kita perlu terus menguji bit yang tersisa, jadi kita menggeser bit yang sudah diuji. Ini dilakukan dengan membagi nilai, sebut saja n , dengan 2+2*!(n%2). Ini berarti jika bit pertama adalah 1, kita membaginya dengan 2 (menjatuhkan 1 bit itu), tetapi jika itu adalah 0, kita membaginya dengan 4, jadi kita akan selalu menjatuhkan pasangan nol.

Jika kita akhirnya turun ke nol, itu berarti tidak ada urutan aneh dari bit nol, jadi kami menuliskan nomornya.

Visual Basic (.net 4.5) 163 byte

Pertama kali menjawab di sini jadi saya yakin saya telah mengacaukan sesuatu. Beritahu saya dan saya akan memperbaikinya. Apakah lambdas Visual Basic bahkan diperbolehkan?

Terima kasih kepada MamaFunRoll untuk menghapus ide nol berturut-turut

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

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

Java, 144 130 128 Bytes

Ini tidak golf seperti yang saya kira bisa, tapi saya pikir itu akan menjadi solusi yang lucu untuk menggunakan Regex, meskipun tidak pernah menggunakannya.

Golf:

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

Tidak Disatukan:

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
}

Sunting: Saya dapat menyimpan 14 byte dengan membuat regex 00 | 1 bukannya 00, dan menghapus ".replace (" 1 "," ")" antara replaceAll dan isEmpty!

Sunting 2: Saya dapat menyimpan 2 byte dengan menjadikan saya Integer dan mereferensikan Integer.toString dengan i.toString.

Clojure, 103 byte

Saya tidak berpikir ini adalah cara terpendek ...

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

Menggunakan re-sequntuk menemukan nol berturut-turut, memetakan panjang modulo-2 mereka ke a set, membuangnya jika nomor 1ditemukan dari set.

Bertanya-tanya , 38 byte

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

Pemakaian:

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

Penjelasan

Lebih mudah dibaca:

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

rng 1 +1 #0: Rentang dari 1 hingga input.

fltr@ ...: Rentang filter dengan predikat berikut.

bn #0: Konversi item saat ini ke biner. (Ini akan memiliki pemimpin 0b).

Rstr #["00"]: Memangkas secara rekursif setiap kejadian 00dalam string.

len iO 0: Hitung jumlah 0s dalam string.

=1: Periksa apakah jumlahnya sama dengan 1. Jika satu-satunya yang 0tersisa di string setelah pemangkasan adalah di depan 0b, maka ini mengembalikan true; jika tidak, ini mengembalikan false.

Rubi, 78 69 68 byte

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

Versi yang lebih lama:

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

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

Menghitung, untuk setiap putaran digit berturut-turut dalam suatu angka, {digit umum dalam jangka tersebut ditambah (1 jika panjangnya ganjil, 2 jika panjangnya genap)}; jika salah satu jawabannya adalah {1} maka angkanya tidak dalam urutan.

Mathematica, 75 byte

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

#~IntegerDigits~2menghitung daftar digit biner dari input #. Splitdaftar itu menjadi elemen-elemen identik, ambil Caseskorek api itu {0..}, ambil Lengthmasing-masingnya, ambil EvenQpanjangnya dan kemudian kembalikan Andhasilnya.

Python 3, 86 82 byte

Golf sedang berlangsung ...

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

Golf off 4 byte dengan mengubah bin(x)[2:]hanya bin(x)- ini meninggalkan 0bpada awal string, tapi saya menyadari ini tidak benar-benar mempengaruhi perhitungan :)

Python, 142 byte

Ini terutama hanya untuk berlatih bermain golf Python saya.

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

Jelly , 10 byte

2ṗx"`ḂḄf@R

Sangat tidak efisien. Cobalah online!

Ruby, 54 53 48 byte

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

Saya tidak berpikir regex untuk ini akan menjadi sangat mendasar.

edit 1: beralih untuk menolak untuk menyingkirkan negasi untuk -1.

sunting 2: beralih matchke =~untuk -5.

C # 159 157 155 byte

Disimpan 2 x dua byte berkat TuukkaX.

Catatan: mencetak int dalam urutan terbalik.

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

Penjelasan:

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 byte

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

Panjang yang sama:

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

Jelly, 15 13 10 byte

menyimpan dua byte setelah melihat jawaban lain, 3 byte lainnya berkat Dennis

Bœṣ0,0Ȧµ€T

Penjelasan

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)