Berechnen Sie die Binary Sierpinski Triangle Sequence

23

Die Binär-Sierpinski-Dreieck-Folge ist die Folge von Zahlen, deren binäre Darstellungen die Reihen des Binär-Sierpinski-Dreiecks ergeben, die gegeben sind, indem mit einer 1 in einer unendlichen Reihe von Nullen begonnen wird und dann jedes Bitpaar wiederholt durch das xor dieser Bits ersetzt wird , wie so:

f(0)=      1                    =1
f(1)=     1 1                   =3
f(2)=    1 0 1                  =5
f(3)=   1 1 1 1                 =15
f(4)=  1 0 0 0 1                =17

Weitere Ziffern finden Sie unter OEIS: https://oeis.org/A001317

Eingabe: Eine nicht negative Ganzzahl n in einem beliebigen Format. (Muss für alle n bis 30 arbeiten.)

Ausgabe: Der n-te Term (0-indiziert) der Sequenz als Dezimalzahl.

Das ist also versuchen Sie, die kürzeste Antwort in Bytes zu geben, die Ihre Sprache beherrscht. Es wird keine Antwort akzeptiert. Standard Lücken gelten (zB keine Hartcodierung der Sequenz), mit der Ausnahme , dass Sie möglicherweise wurde eine Sprache erstellt / geändert , nachdem diese Herausforderung geschrieben verwenden. (Posten Sie keine andere Lösung in einer Sprache, die bereits verwendet wurde, es sei denn, Ihre Lösung ist kürzer.)

Bestenliste

Das Stapel-Snippet am Ende dieses Beitrags generiert den Katalog aus den Antworten a) als Liste der kürzesten Lösungen pro Sprache und b) als Gesamt-Bestenliste.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

## Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

## Perl, 43 + 2 (-p flag) = 45 bytes

Sie können den Namen der Sprache auch als Link festlegen, der dann im Snippet angezeigt wird:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Quintopie
quelle
8
Ich bin kein großer Fan von darf für keine n eine falsche Antwort ausgeben . Dies zwingt Sprachen, die standardmäßig keine Ganzzahlen mit willkürlicher Genauigkeit verwenden, zu prüfen, ob die Eingabe klein genug ist ...
Dennis
Bitte klären Sie, ob die Regeln richtig verstanden wurden (siehe Kommentare hier und hier ) und ob eine gerundete Ausgabe (z. B. 1.288490189e10 für Eingabe 33) als falsch gilt .
Dennis
Msgstr "Muss für alle n bis 30 funktionieren und darf für keine n eine falsche Antwort ausgeben." . Das ist widersprüchlich - sicher "darf keine falsche Antwort ausgeben" ist dasselbe wie "muss funktionieren" ???
Digital Trauma
5
Aufgrund des überwältigenden Widerstandes der Bevölkerung gegen die unzumutbare und erdrückende Last der Eingabevalidierung wurde diese Anforderung entfernt. Sie können beliebig viel Müll für große n ausgeben. Genießen!
Quintopia
2
Anstatt zu sagen, dass die Ausgabe nicht falsch sein sollte, würde ich nur empfehlen, zu sagen, dass Übermittlungen Eingaben bis zu den größten unterstützen müssen, nfür die nichts überläuft.
Alex A.

Antworten:

14

05AB1E , 5 4 Bytes

Ich präsentiere Ihnen stolz, 05AB1E. Obwohl es sehr kurz ist, ist es bei langen Herausforderungen wahrscheinlich sehr schlecht.

Danke an ETHproductions für das Abschneiden von 1 Byte :)

$Fx^

Erläuterung:

$      # Pushes 1 and input
 F     # Pops x, creates a for-loop in range(0, x)
  x    # Pops x, pushes x and 2x
   ^   # Bitwise XOR on the last two elements
       # Implicit, ends the for-loop
       # Implicit, nothing has printed so the last element is printed automatically
Adnan
quelle
Sie wissen, eine gute Möglichkeit, ein Byte aus vielen Programmen in einer benutzerdefinierten Sprache abzuspielen, besteht darin, ein Trailing }automatisch einzufügen. Dann wären das 4 Bytes. :)
ETHproductions
1
@ETHproductions Moment mal, das wurde schon implementiert :). Vielen Dank, dass du 1 Byte gespart hast, haha.
Adnan
2
Dieser Code enthält einen Fehler. Wie soll ich wissen? Es schlägt Dennis.
Arcturus
2
@Ampora Es schlägt nicht nur Dennis, sondern auch Dennis 'eigene Golfsprache. ;)
ETHproductions
@Adnan Wow. Du bist auf etwas.
RK.
12

Pari / GP , 27 Bytes

n->lift(Mod(x+1,2)^n)%(x-2)

Die Funktion nimmt die n-te Potenz des Polynoms x + 1 im Ring F 2 [x], hebt sie auf Z [x] und wertet sie dann bei 2 aus.

Probieren Sie es online!

Alephalpha
quelle
6

Gelee , 6 Bytes

1Ḥ^$³¡

Probieren Sie es online!

Die Binärversion, die mit dieser Version des Jelly-Interpreters funktioniert, hat den xxd-Dump

0000000: 31 a8 5e 24 8b 80  1.^$..

Wie es funktioniert

1Ḥ^$³¡    Input: n

1         Set the left argument to 1.
 Ḥ        Multiple the left argument by two.
  ^       Hook; XOR it with its initial value.
   $      Create a monadic chain from the last two insructions.
    ³¡    Call the chain n times, updating the left argument after each call.
Dennis
quelle
5

Haskell, 44 Bytes

import Data.Bits
f n=iterate((2*)>>=xor)1!!n

In der ((->) r)Monade (f >>= g) xgleich g (f x) x.

Lynn
quelle
Ich denke , man kann die letzte Zeile anonymisieren(iterate((2*)>>=xor)1!!)
xnor
Ich habe es versucht, aber es funktioniert aus gefürchteten Gründen der Monomorphismusbeschränkung nicht.
Lynn
Dies kann jedoch als legaler Ausdruck gelten, da die Monomorphismus-Einschränkung nicht für Ausdrücke, sondern für Deklarationen gilt. Und Ausdrücke gelten als legale Antworten, wenn ich mich nicht irre.
stolzer Haskeller
4

Matlab, 45 Bytes

Lösung:

@(i)2.^[0:i]*diag(mod(fliplr(pascal(i+1)),2))

Prüfung:

ans(10)
ans =
1285

Erläuterung: pascalKonstruiert ein Pascal-Dreieck, beginnt jedoch bei 1, sodass die Eingabe erfolgen sollte i+1. fliplrKippt das Array von links nach rechts. mod(_,2)Rest nach Division durch 2. diagExtrahiert die Hauptdiagonale. Die Multiplikation mit 2.^[0:i]konvertiert den Vektor in eine Dezimalzahl

Ich bin froh, @flawr, dass ich hier einen Matlab-Konkurrenten gefunden habe :)

brainkz
quelle
Scheint auch mit Octave zu arbeiten.
Dennis
4

JavaScript (ES6), 23 Byte

f=x=>x?(y=f(x-1))^y*2:1

Basierend auf der ersten Formel auf der OEIS-Seite. Wenn es Ihnen nichts ausmacht, dass der Code bei einer Eingabe von 30 fast ewig dauert, können wir ein Byte entfernen:

f=x=>x?f(--x)^f(x)*2:1

Hier ist eine nicht-rekursive Version mit einer forSchleife in einem eval: (32 Bytes)

x=>eval("for(a=1;x--;a^=a*2);a")
ETHproductions
quelle
Die derzeit verfassten Regeln machen diese Antwort ungültig, da sie f(35)zurückgegeben wird 15. Gabelbombenalarm: Ich musste Chromium zwangsweise schließen, um die f(30)Ausführung zu stoppen (ursprüngliche Revision). : P
Dennis
1
@Dennis Warte, wenn ich also keinen falschen Wert ausgeben kann, was soll ich dann mit Eingaben über 30 machen?
ETHproductions
Ich bin nicht sicher (und ich hoffe, die Regel wird geändert ), aber so etwas f=x=>x?(y=f(x-(x<31)))^y*2:1würde funktionieren.
Dennis
@Dennis Ah, unendlich rekursiv = keine Ausgabe. Ich werde das Problem beheben, wenn ich wieder an meinem Computer bin. Ich hoffe, dass sich auch diese Regel ändert.
ETHproductions
Die Regel wurde aus der Frage entfernt.
Dennis
3

Matlab, 77 70 Bytes

Diese Funktion berechnet die n-te Zeile des Pascal-Dreiecks durch wiederholte Faltung mit [1,1](auch als Binomial-Erweiterung oder wiederholte Multiplikation mit einem Binomial bezeichnet) und berechnet daraus die Zahl.

function r=c(n);k=1;for i=1:n;k=conv(k,[1,1]);end;r=2.^(0:n)*mod(k,2)'
Fehler
quelle
3

Ruby, 26 Bytes

anonyme Funktion mit Iteration.

->n{a=1;n.times{a^=a*2};a}

Diese rekursive Funktion ist ein Byte kürzer, aber da sie benannt werden muss, um auf sich selbst verweisen zu können, endet sie ein Byte länger.

f=->n{n<1?1:(s=f[n-1])^s*2}
Level River St
quelle
3

Ruby, 25 Bytes

->n{eval"n^=2*"*n+?1*n=1}

Kürzer als die anderen Antworten hier bisher. Es erstellt diese Zeichenfolge:

n^=2*n^=2*n^=2*n^=2*1

Dann setzt es n=1(dies geschieht tatsächlich, während die Zeichenfolge erstellt wird) und wertet die obige Zeichenfolge aus und gibt das Ergebnis zurück.

Lynn
quelle
Spart das *n=1wirklich etwas mehr alsm=1;"m^=2*"*n+?1
Martin Ender
Nein, aber es mit nur einer Variablen zu machen ist sehr auffällig :)
Lynn
3

Samau , 4 Bytes

Jetzt verfügt Samau über integrierte Funktionen für die XOR-Multiplikation und die XOR-Potenz.

▌3$ⁿ

Hex-Dump (Samau verwendet CP737-Codierung):

dd 33 24 fc

Erläuterung:

▌       read a number
 3      push 3
  $     swap
   ⁿ    take the XOR power
Alephalpha
quelle
Könnte dies auf 3 Bytes reduziert werden, indem die ersten beiden Befehle ausgetauscht und der Austausch beseitigt werden?
Quintopia
Samau schiebt die Eingabe automatisch als Zeichenfolge auf den Stapel und liest eine Zahl aus der Zeichenfolge. Wenn wir die ersten beiden Befehle vertauschen, wird versucht, eine Zahl auszulesen 3, die keine Zeichenfolge ist.
Alephalpha
Warum versucht Samau nicht, die Zeichenfolge zu bewerten, wenn dies möglich ist?
Quintopia
2

CJam, 10 Bytes

1ri{_2*^}*

Teste es hier.

Einfache iterative Lösung mit bitweisem XOR.

Martin Ender
quelle
2

Pure Bash (keine externen Dienstprogramme), 37

Bash-Ganzzahlen sind mit 64-Bit-Vorzeichen versehen. Dies funktioniert also für Eingaben bis einschließlich 62:

for((x=1;i++<$1;x^=x*2)){
:
}
echo $x
Digitales Trauma
quelle
2

Python 2.7.6, 38 33 Bytes

Vielen Dank an Dennis für ein paar Bytes!

x=1
exec'x^=x*2;'*input()
print x
MCS-Kaijin
quelle
1
Willkommen bei Programming Puzzles & Code Golf! exec'x^=x*2;'*input()spart ein paar Bytes über den forAnsatz.
Dennis
Dies schlägt meinen Python-Eintrag, den ich nur für die Nachwelt hier lassen werde:f=lambda n:f(n-1)^2*f(n-1)if n>0 else 1
Jack Brounstein
2

Pyth, 7 Bytes

uxyGGQ1

Probieren Sie es online aus: Demonstration

Erläuterung:

u    Q1   apply the following statement input-times to G=1:
 xyGG        update G with (2*G xor G)
Jakube
quelle
2

MIPS, 28 Bytes

Eingabe in $a0, Ausgabe in $v0.

0x00400004  0x24020001          li      $v0, 1
0x00400008  0x10800005  loop:   beqz    $a0, exit
0x0040000c  0x00024021          move    $t0, $v0
0x00400010  0x00021040          sll     $v0, $v0, 1
0x00400014  0x00481026          xor     $v0, $v0, $t0
0x00400018  0x2084ffff          addi    $a0, $a0, -1
0x0040001c  0x08100002          j       loop
qwr
quelle
1

Mathematica, 40 24 Bytes

Nest[BitXor[#,2#]&,1,#]&
Alephalpha
quelle
1

k4, 26 Bytes

{x{2/:~(=). 0b\:'1 2*x}/1}

0b\:konvertiert eine Zahl in einen Booleschen Vektor (dh Bitstring), XOR wird als "ungleich" implementiert, 2/:konvertiert einen Bitstring zurück in eine Zahl, indem es als Polynom behandelt wird, um es auszuwerten, und x f/ymit xeiner ganzen Zahl wird fes yzuerst und dann auf sein angewendet aufeinanderfolgende Ausgabenx .

Probelauf:

  {x{2/:~(=). 0b\:'1 2*x}/1}'!5                                                                                                                                                                                    
1 3 5 15 17
Aaron Davies
quelle
1

Ruby, 31 26 Bytes

EDIT: Wurde komplett in eine andere Sprache geändert! Alle Golfvorschläge sind willkommen!

Dieses Programm führt eine bitweise XOR-Verknüpfung des vorherigen Elements der Sequenz mit dem doppelten Wert durch, d f(n) = f(n-1) ^ 2*f(n-1). H.

->n{v=1;n.times{v^=2*v};v}
Sherlock9
quelle
1

MATL , 15 Bytes

Ähnlich wie bei der Antwort von @ flawr :

i:1w"TToX+]2\XB

BEARBEITEN (20. Mai 2016) Probieren Sie es online! mit X+ersetzt durchY+ um Version 18.0.0 der Sprache zu entsprechen.

Beispiel

>> matl i:1w"TToX+]2\XB
> 5
51

Erläuterung

i              % input                                                     
:              % vector of values 1, 2, ... to previous input                           
1              % number literal                                            
w              % swap elements in stack                                    
"              % for                                                       
    TTo        % vector [1 1]
    X+         % convolution                                               
]              % end                                                       
2\             % modulo 2
XB             % convert from binary to decimal              
Luis Mendo
quelle
1

Brainfuck , 87 Bytes

,[>>[>]++<[[->+>+<<]>-->[-<<+>>]<[>+<-[>-<-]]>+<<<]>>>[[-<+>]>]<<[<]<-]>>[<[->++<]>>]<+

Probieren Sie es online!

Nimmt Zellen mit unendlicher Größe an (andernfalls kann es nicht über 7 hinausgehen, was günstigerweise 255 ist). Die Pascal-Triangel-Mod-2-Methode ist aufgrund der teuren Mod-2-Operation viel länger, während XOR viel einfacher zu implementieren ist.

Scherzen
quelle
0

APL, 31 Bytes

{({2⊥⊃~1 2=.{(64⍴2)⊤⍺×⍵}⍵}⍣⍵)1}

Dies ist mit ziemlicher Sicherheit ein schrecklicher Code, aber ich bin ein kompletter APL-Neuling. Ich gehe davon aus, dass jeder mit jeglichem Können alle D-Funktionen loswerden und erheblich verkürzen kann. Die Logik ist mehr oder weniger die gleiche wie meine k4Antwort - multiplizieren mit 1oder 2in Bits konvertieren mit , XOR verwenden ungleich, zurück in eine Zahl konvertieren mit , das Ganze in eine Funktion einwickeln und nach einer bestimmten Anzahl von Iterationen fragen mit . Ich habe keine Ahnung, warum das Ergebnis, das aus dem inneren Produkt kommt, eingeschlossen ist, aber räumt das auf.

Aaron Davies
quelle
Sie sollten in der Lage sein, ein Byte zu speichern, indem Sie ~1 2=.auf "1 2≠.
Zacharý
Und auf welchem ​​APL-System läuft das? Wenn es auf Dyalog ist, solltest du es schaffen {({2⊥⊃1 2≠.((64⍴2)⊤×)⍵}⍣⍵)1}[28 bytes]
Zacharý
0

Im Ernst, 12 Bytes

2,╣`2@%`Mεj¿

Hex Dump:

322cb960324025604dee6aa8

Probieren Sie es online aus

Da Seriously keine Möglichkeit enthält, ein bitweises xor auszuführen, nimmt diese Lösung die Herausforderung vollständig wörtlich und berechnet direkt die angegebene Zeile des Dreiecks. Diese Methode liefert korrekte Antworten bis n = 1029 (danach ist nicht mehr genügend Speicher vorhanden, um die angegebene Zeile des Pascalschen Dreiecks zu berechnen).

Erläuterung:

 ,                       get input
  ╣                 push the nth row of pascal's triangle
   `2@%`M           take each element of the row mod 2
         εj         join all the binary digits into a string
2          ¿        interpret it as a base 2 number
Quintopie
quelle
0

Pyt , 40 10 Bytes

Đ0⇹Řć2%ǰ2Ĩ

Erläuterung:

In der Beobachtung, dass das binäre Sierpinski-Dreieck Pascals Triangle Mod 2 entspricht,

                      Implicit input
Đ                     Duplicate input
 0⇹Ř                  Push [0,1,2,...,input]
    ć2%               Calculate the input-th row of Pascal's Triangle mod 2
       ǰ              Join elements of the array into a string
        2Ĩ            Interpret as a binary number
                      Implicit print

Probieren Sie es online!

mudkip201
quelle
0

Stax , 5 Bytes

±s┤ε─

Online ausführen und debuggen!

Port of the Jelly antworten.

Verwendet ASCII-Darstellung, um Folgendes zu erklären:

ODcH|^
O         Put 1 under top of stack
 D        Repeat for times specified by input
  cH|^    Xor the number with itself doubled
          Implicit output
Weijun Zhou
quelle