Die baumsüße Sequenz (A086747 mit einem Dreh)

Nehmen Sie eine positive ganze Zahl nund drucken Sie die ganzen Zahlen von 1 bis n, für die die Baum-Sweet-Sequenz true zurückgibt. Die Baum-Sweet-Sequenz sollte falsch zurückgegeben werden, wenn die binäre Darstellung der Zahl eine ungerade Anzahl aufeinanderfolgender Nullen irgendwo in der Zahl enthält, und ansonsten wahr . Für weitere Informationen klicken Sie auf den Link. Hier sind einige Beispiele:

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

Hier ist ein Beispiel n=32

Schritt 1: Die für visualisierte Baum-Sweet-Sequenz 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)

Also, nachdem Sie die Baum-Sweet-Folge für n berechnet haben, nehmen Sie die Zahlen, die für die Folge wahr waren, und sammeln Sie sie für das Endergebnis. Denn n=32wir hätten:

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

Als endgültige Antwort.

Dies ist Code-Golf , die kürzeste Anzahl an Bytes gewinnt.

05AB1E , 10 9 Bytes

Ein Byte dank Adnan gespeichert

ƒNb00¡SP–

Probieren Sie es online!

Erläuterung

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

Etwas interessantere rekursive Lösung:

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

67 Bytes dank @Neil.

g ist die aufzurufende Funktion.

Python 2, 62 Bytes

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

Prüft 00, ob in der Binärdarstellung ungerade Einsen vorkommen, indem aufgespalten wird und überprüft wird, ob in der Zeichenfolgendarstellung der resultierenden Liste noch Nullen vorhanden sind. Ärgerlicherweise beginnen Binärzahlen mit 0beiner Null, die entfernt werden muss, um ein falsches Positiv zu vermeiden.

Die Aufzählung erfolgt durch rekursives Herunterfahren.

Bash, 5846 Bytes

EDITS:

• Ersetzt bc mit dc (Thx @Digital Trauma!)
• Beginnen Sie mit 1;

Golf gespielt

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

Prüfung

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

Erklärt

Schale

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

Probieren Sie es online!

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

Versuch es

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

( []werden für nicht erfassende Gruppierungen verwendet, bei <[]>Verwendung für Zeichenklassen)

PowerShell , 79 61 Bytes

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

Probieren Sie es online!

Ich hatte heute Morgen Inspiration, um zu ändern, wie ich die -splitOperation durchführe, und dann zu sehen, dass es ähnlich ist, wie die Antwort von xnor aufgebaut ist. Also denke ich, große Köpfe denken gleich?

Wir durchlaufen eine Schleife von 1bis zur Eingabe $args[0]und verwenden einen Where-ObjectOperator, um die entsprechenden Zahlen herauszuholen |?{...}. Die Klausel ist eine einfache Boolesche Wert - wir sind sicher , dass 0ist -notindas Ergebnis (...).

Innerhalb der Parens geben wir [convert]::die aktuelle Zahl $_ ToStringmit der Basis an 2(dh verwandeln sie in eine binäre Zeichenkette). Wir haben dann -splitdie Zeichenfolge auf der Regex 1|00- dies ist eine gierige Übereinstimmung und führt zu einer Reihe von Zeichenfolgen (zum Beispiel 100010würde sich in '','','0','','0'und so weiter verwandeln ).

Wenn also jeder Lauf von 0s in der Binärzeichenfolge gerade ist (was bedeutet, dass die Regex sie in leere Zeichenfolgen aufgeteilt hat), ist 0dies -notindas Ergebnis. Die WhereKlausel ist also wahr, und die Zahl wird ausgewählt. Diese Zahlen verbleiben in der Pipeline und die Ausgabe ist implizit.

Python 2 , 67 47 Bytes

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

Danke an @xnor um 20 (!) Bytes abzuspielen!

Gibt eine ungeordnete Liste zurück. Es ist sehr effizient: Die Eingabe von 100.000 dauert bei TIO ungefähr 40 ms.

Probieren Sie es online!

Mathematica, 59 Bytes

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

Mathematica Antwort Nummer 4 ...

MATL , 12 11 Bytes

:"@BY'og)?@

Probieren Sie es online!

Erläuterung

Um festzustellen, ob eine Zahl gültig ist, wird diese in eine Binärzahl konvertiert, die Lauflängencodierung angewendet, nur Läufe ungerader Länge beibehalten und überprüft, ob kein Lauf von Nullen überlebt.

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

Liest die Eingabe von stdin und konvertiert mit der binFunktion aus dem miscFuncsPaket von einem Dezimal- in einen Binärvektor. Führt folglich eine Lauflängencodierung durch, um zu überprüfen, ob Werte == 0und Längen ungerade sind.

Gestapelt , 69 Bytes

Probieren Sie es hier aus!

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

Oder nicht konkurrierend bei 67 Bytes:

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

Und noch konkurrenzloser bei 49 Bytes:

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

Alle nehmen Eingaben als TOS und lassen Ausgaben auf TOS.

Erläuterung

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

Die Funktion:

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

Erklärung des Nichtkonkurrierens:

Es ist dasselbe wie oben, mit ein paar wesentlichen Unterschieden:

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

Nach einigem Experimentieren stellte ich fest, dass ich mit einer Technik, die der von Neil entwickelten Batch-Antwort ähnelt, einiges besser machen konnte als meine ursprüngliche Lösung .

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

Probieren Sie es online!

Wie bei meiner ursprünglichen Lösung gibt es zwei Schleifen - die äußere Schleife, die über die zu testenden Zahlen iteriert, und eine innere Schleife, die die Bitsequenz für jede Zahl testet. Die Art und Weise, wie der Test funktioniert, besteht darin, zwei Bits gleichzeitig zu untersuchen (Modulo 4 des aktuellen Werts). Wenn das gleich 2 ist, haben wir eine ungerade Folge von Nullen und können die innere Schleife abbrechen und zur nächsten Zahl übergehen.

Wenn das Modulo 4 nicht gleich 2 ist, müssen wir die verbleibenden Bits weiter testen, damit wir die bereits getesteten Bits nach oben verschieben. Dies geschieht durch Teilen des Wertes, nennen wir ihn n , durch 2+2*!(n%2). Das heißt, wenn das erste Bit eine 1 war, teilen wir durch 2 (und lassen dieses 1-Bit fallen), aber wenn es eine 0 war, teilen wir durch 4, sodass wir immer Nullenpaare fallen lassen.

Wenn wir irgendwann auf Null kommen, bedeutet das, dass es keine ungeraden Folgen von Null-Bits gab, also schreiben wir die Zahl aus.

163 Byte Visual Basic (.net 4.5)

Antworte hier zum ersten Mal, also bin ich sicher, dass ich etwas vermasselt habe. Lass es mich wissen und ich werde es reparieren. Sind Visual Basic Lambdas überhaupt erlaubt?

Vielen Dank an MamaFunRoll für die Idee, aufeinanderfolgende Nullen zu entfernen

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) Ausgänge

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

Java, 144 130 128 Bytes

Dies ist nicht so gut, wie ich denke, es kann sein, aber ich dachte, es wäre eine nette Lösung, einen Regex zu verwenden, obwohl ich noch nie einen benutzt habe.

Golf gespielt:

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
}

Bearbeiten: Ich konnte 14 Bytes sparen, indem ich die Regex 00 | 1 anstelle von 00 erstellte und ".replace (" 1 "," ")" zwischen "replaceAll" und "isEmpty!" Entfernte.

Edit 2: Ich konnte 2 Bytes sparen, indem ich eine Ganzzahl machte und Integer.toString mit i.toString referenzierte.

Clojure, 103 Bytes

Ich denke nicht, dass dies der kürzeste Weg ist ...

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

Verwendet re-seq, um aufeinanderfolgende Nullen zu finden, ordnet ihre Modulo-2-Längen a zu set, verwirft sie, wenn eine Zahl 1aus dem Satz gefunden wird.

Wunder , 38 Bytes

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

Verwendung:

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

Erläuterung

Besser lesbar:

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

rng 1 +1 #0: Bereich von 1 bis Eingang.

fltr@ ...: Filterbereich mit folgendem Prädikat.

bn #0: Aktuelles Element in Binär umwandeln. (Dies wird eine führende haben0b ).

Rstr #["00"]: Alle Vorkommen von rekursiv beschneiden 00 in der Zeichenfolge .

len iO 0: Zähle die Mengen von 0 s in der Zeichenkette.

=1: Überprüfen Sie, ob der Betrag gleich 1 ist. Befindet sich der einzige 0Rest in der Zeichenfolge nach dem Beschneiden in der ersten Zeile 0b, wird true zurückgegeben. Andernfalls wird false zurückgegeben.

Rubin, 78 69 68 Bytes

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

Ältere Versionen:

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

Berechnet für jeden Lauf aufeinanderfolgender Ziffern einer Zahl {die gemeinsame Ziffer in diesem Lauf plus (1, wenn die Länge ungerade ist, 2, wenn die Länge gerade ist)}; Wenn eine der Antworten {1} ist, ist die Nummer nicht in der Reihenfolge.

Mathematica, 75 Bytes

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

#~IntegerDigits~2berechnet die Liste der Binärziffern der Eingabe #. SplitDiese Liste wird in Reihen identischer Elemente aufgeteilt. Nehmen Sie die CasesÜbereinstimmungen {0..}, nehmen Sie die Lengtheinzelnen Elemente, nehmen Sie EvenQdie Längen und geben Sie Anddie Ergebnisse zurück.

Python 3, 86 82 Bytes

Golfen im Gange ...

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

4 Bytes durch Ändern bin(x)[2:]in "Nur" entfernt bin(x)- dies verbleibt 0bam Anfang der Zeichenfolge, aber ich habe festgestellt, dass dies die Berechnungen nicht beeinflusst :)

Python, 142 Bytes

Dies dient hauptsächlich zum Üben des Golfspiels mit meinem 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)]

Gelee , 10 Bytes

2ṗx"`ḂḄf@R

Schrecklich ineffizient. Probieren Sie es online!

Ruby, 54 53 48 Bytes

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

Ich hätte nicht gedacht, dass der reguläre Ausdruck dafür so einfach sein würde.

edit 1: wurde auf ablehnen um die Negation für -1 loszuwerden.

edit 2: umgestellt matchauf =~-5.

C # 159 157 155 Bytes

2 x 2 Bytes dank TuukkaX gespeichert.

Hinweis: Die Angaben werden in umgekehrter Reihenfolge ausgedruckt.

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

Erläuterung:

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

Die gleiche Länge:

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

Rubin, 53 Bytes

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

Jelly, 15 13 10 Bytes

sparte zwei Bytes nachdem ich andere Antworten angeschaut hatte, weitere 3 Bytes dank Dennis

Bœṣ0,0Ȧµ€T

Erläuterung

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)