Binarna sekwencja trójkąta Sierpińskiego jest sekwencją liczb, których reprezentacje binarne dają rzędy binarnego trójkąta Sierpińskiego, którą podaje się zaczynając od 1 w nieskończonym rzędzie zer, a następnie wielokrotnie zastępując każdą parę bitów xor tych bitów , tak jak:

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

Więcej cyfr podano w OEIS: https://oeis.org/A001317

Dane wejściowe: nieujemna liczba całkowita n w dowolnym formacie. (Musi działać dla wszystkich n do 30.)

Wyjście: n-ty składnik (indeksowany 0) sekwencji jako liczba dziesiętna.

To jest golf golfowy, więc postaraj się udzielić najkrótszej odpowiedzi w bajtach, jaką potrafi Twój język. Żadna odpowiedź nie zostanie zaakceptowana. Obowiązują standardowe luki (np. Brak kodowania sekwencji na stałe), z wyjątkiem ciebie mogą używać języka utworzone / zmodyfikowane po to wyzwanie została wysłana. (Unikaj publikowania innego rozwiązania w języku, który był już używany, chyba że twoje rozwiązanie jest krótsze).

Tabela liderów

Fragment kodu na dole tego postu generuje katalog na podstawie odpowiedzi a) jako listy najkrótszych rozwiązań według języka oraz b) jako ogólnej tabeli wyników.

Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

## Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik to suma dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:

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

Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie:

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

/* Configuration */

var QUESTION_ID = 67497; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 47050; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();
    
    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}

body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

05AB1E , 5 4 bajtów

Z dumą przedstawiam wam, 05AB1E. Chociaż jest bardzo krótki, prawdopodobnie jest bardzo zły przy długich wyzwaniach.

Dzięki produktom ETH za golenie 1 bajtu :)

$Fx^

Wyjaśnienie:

$      # 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

Pari / GP , 27 bajtów

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

Funkcja przyjmuje n-tą potęgę wielomianu x + 1 w pierścieniu F ₂ [x], podnosi ją do Z [x], a następnie ocenia na 2.

Wypróbuj online!

Galaretka , 6 bajtów

1Ḥ^$³¡

Wypróbuj online!

Wersja binarna, która działa z tą wersją interpretera Jelly, ma zrzut xxd

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

Jak to działa

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.

Haskell, 44 bajty

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

W ((->) r)monadzie (f >>= g) xrówna się g (f x) x.

Matlab, 45 bajtów

Rozwiązanie:

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

Test:

ans(10)
ans =
1285

Objaśnienie: pascalkonstruuje trójkąt Pascala, ale zaczyna się od 1, więc wejście powinno być i+1. fliplrodwraca tablicę od lewej do prawej. mod(_,2)przyjmuje resztę po podzieleniu przez 2. diagwyodrębnia główną przekątną. Mnożenie za pomocą 2.^[0:i]przekształca wektor na dziesiętny

Cieszę się, @flawr, że znalazłem tutaj konkurenta Matlaba :)

JavaScript (ES6), 23 bajty

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

Na podstawie pierwszej formuły na stronie OEIS. Jeśli nie przeszkadza ci to, że kod zajmuje prawie wieczność, gdy dane wejściowe wynoszą 30, możemy zgolić bajt:

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

Oto wersja nierekurencyjna, wykorzystująca forpętlę w eval: (32 bajty)

x=>eval("for(a=1;x--;a^=a*2);a")

Matlab, 77 70 bajtów

Ta funkcja oblicza n-ty rząd trójkąta Pascala za pomocą powtarzalnego splotu z [1,1](aka ekspansji dwumianowej lub powtarzanego mnożenia przez dwumianowy) i na tej podstawie oblicza liczbę.

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

Rubinowy, 26 bajtów

anonimowa funkcja z iteracją.

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

ta funkcja rekurencyjna jest o jeden bajt krótsza, ale ponieważ należy ją nazwać, aby móc się do niej odwoływać, kończy się o jeden bajt dłużej.

f=->n{n<1?1:(s=f[n-1])^s*2}

Rubin, 25 bajtów

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

Krótszy niż inne dotychczasowe odpowiedzi tutaj. Konstruuje ten ciąg:

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

Następnie ustawia się n=1(dzieje się tak podczas tworzenia łańcucha) i ocenia powyższy ciąg, zwracając wynik.

Samau , 4 bajty

Teraz Samau ma wbudowane funkcje mnożenia XOR i mocy XOR.

▌3$ⁿ

Zrzut szesnastkowy (Samau używa kodowania CP737):

dd 33 24 fc

Wyjaśnienie:

▌       read a number
 3      push 3
  $     swap
   ⁿ    take the XOR power

CJam, 10 bajtów

1ri{_2*^}*

Sprawdź to tutaj.

Proste iteracyjne rozwiązanie wykorzystujące bitowe XOR.

Pure Bash (bez zewnętrznych narzędzi), 37

Liczby całkowite Bash są podpisane 64-bit, więc działa to na dane wejściowe do 62 włącznie:

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

Python 2.7.6, 38 33 bajtów

Dzięki Dennisowi za zgolenie kilku bajtów!

x=1
exec'x^=x*2;'*input()
print x

Pyth, 7 bajtów

uxyGGQ1

Wypróbuj online: demonstracja

Wyjaśnienie:

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

Perl 5, 23 bytes

$.^=2*$.for 1..<>;say$.

Try it online!

MIPS, 28 bytes

Input in $a0, output 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

Mathematica, 40 24 bytes

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

k4, 26 bytes

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

0b\: converts a number to a boolean vector (i.e. bitstring), XOR is implemented as "not equal", 2/: converts a bitstring back to a number by treating it as a polynomial to evaluate, and x f/y with x an integer is f applied to y first, and then to its successive outputs x times.

Sample run:

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

Ruby, 31 26 bytes

EDIT: Changed to a different language entirely! All golfing suggestions welcome!

This program bitwise XORs the previous element of the sequence with twice itself, i.e. f(n) = f(n-1) ^ 2*f(n-1).

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

MATL, 15 bytes

Similar to @flawr's answer:

i:1w"TToX+]2\XB

EDIT (May 20, 2016) Try it online! with X+ replaced by Y+ to conform to version 18.0.0 of the language.

Example

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

Explanation

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              

brainfuck, 87 bytes

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

Try it online!

Assumes infinite sized cells (otherwise it can’t get past 7, which is conveniently 255). The Pascal’s triangle mod 2 method is actually much longer because of the costly mod 2 operation, while XOR is much easier to implement.

APL, 31 bytes

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

This is almost certainly awful code, but I'm a complete APL newb. I expect anyone with any skill could get rid of all the D-functions and shorten it considerably. The logic is more or less the same as my k4 answer -- multiply by 1 or 2, convert to bits with ⊤, XOR using not equals, convert back to a number with ⊥, wrap the whole thing in a function and ask for a specific number of iterations using ⍣. I have no idea why the result coming out of the inner product is enclosed, but ⊃ cleans that up.

Seriously, 12 bytes

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

Hex Dump:

322cb960324025604dee6aa8

Try it online

Since Seriously does not include any means of doing a bitwise xor, this solution takes the challenge completely literally, directly computing the given row of the triangle. This method gives correct answers up to n=1029 (after which there is not enough memory to compute the given row of Pascal's triangle).

Explanation:

 ,                       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

Pyt, 40 10 bytes

Đ0⇹Řć2%ǰ2Ĩ

Explanation:

Observing that the Binary Sierpinski Triangle is equivalent to Pascal's Triangle mod 2,

                      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

Try it online!

Stax, 5 bytes

±s┤ε─

Run and debug online!

Port of the Jelly answer.

Uses ASCII representation to explain:

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