[Question]
  [
The Binary Sierpinski Triangle sequence is the sequence of numbers whose binary representations give the rows of the Binary Sierpinski Triangle, which is given by starting with a 1 in an infinite row of zeroes, then repeatedly replacing every pair of bits with the xor of those bits, like 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
```
More digits are given at OEIS: <https://oeis.org/A001317>
Input: A non-negative integer n in any format you like. (Must work for all n up to 30.)
Output: The nth term (0-indexed) of the sequence as a decimal number.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so try give the shortest answer in bytes of which your language is capable. No answer will be accepted.
Standard loopholes apply (e.g. no hard-coding the sequence), except that you *may* use a language created/modified after this challenge was posted. (Do avoid posting another solution in a language that has already been used unless your solution is shorter.)
## Leaderboard
The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.
To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:
```
## Language Name, N bytes
```
where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:
```
## Ruby, <s>104</s> <s>101</s> 96 bytes
```
If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:
```
## Perl, 43 + 2 (-p flag) = 45 bytes
```
You can also make the language name a link which will then show up in the snippet:
```
## [><>](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>
```
  
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~5~~ 4 bytes
I proudly present to you, 05AB1E. Although it is very short, it is probably very bad at long challenges.
Thanks to ETHproductions for shaving off 1 byte :)
```
$Fx^
```
Explanation:
```
$      # 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
```
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 27 bytes
```
n->lift(Mod(x+1,2)^n)%(x-2)
```
The function takes the \$n\$-th power of the polynomial \$x+1\$ in the ring \$\mathbb{F}\_2[X]\$, lifts it to \$\mathbb{Z}[X]\$, and then evaluates it at \$x=2\$.
[Try it online!](https://tio.run/##K0gsytRNL/ifpmCr8D9P1y4nM61Ewzc/RaNC21DHSDMuT1NVo0LXSPN/Wn6RRh5QkYGOgiEQFxRl5pUABZQUdO2ARJpGnqam5n8A "Pari/GP – Try It Online")
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), 6 bytes
```
1Ḥ^$³¡
```
[Try it online!](http://jelly.tryitonline.net/#code=MeG4pF4kwrPCoQ&input=&args=NA)
The binary version that works with [this revision](https://github.com/DennisMitchell/jelly/commit/c282f46eac85e15e2ca789b2cb11ad0abd454ac8) of the Jelly interpreter has the xxd dump
```
0000000: 31 a8 5e 24 8b 80  1.^$..
```
### How it works
```
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.
```
[Answer]
# Haskell, 44 bytes
```
import Data.Bits
f n=iterate((2*)>>=xor)1!!n
```
In the `((->) r)` monad, `(f >>= g) x` equals `g (f x) x`.
[Answer]
## Matlab, 45 bytes
Solution:
```
@(i)2.^[0:i]*diag(mod(fliplr(pascal(i+1)),2))
```
Test:
```
ans(10)
ans =
1285
```
Explanation:
`pascal` constructs Pascal triangle, but it starts from 1, so input should be `i+1`. `fliplr` flips array from left to right. `mod(_,2)` takes remainder after division by 2. `diag` extracts main diagonal.Multiplication using `2.^[0:i]` converts vector to decimal
I'm glad, @flawr that I found Matlab competitor here :)
[Answer]
# JavaScript (ES6), 23 bytes
```
f=x=>x?(y=f(x-1))^y*2:1
```
Based on the first formula on the OEIS page. If you don't mind the code taking almost forever to finish for an input of 30, we can shave off a byte:
```
f=x=>x?f(--x)^f(x)*2:1
```
Here's a non-recursive version, using a `for` loop in an `eval`: (32 bytes)
```
x=>eval("for(a=1;x--;a^=a*2);a")
```
[Answer]
# Matlab, ~~77~~ 70 bytes
This function calculates the n-th row of the Pascal triangle via repeated convolution with `[1,1]` (a.k.a. binomial expansion or repeated multiplication with a binomial), and calculates the number from that.
```
function r=c(n);k=1;for i=1:n;k=conv(k,[1,1]);end;r=2.^(0:n)*mod(k,2)'
```
[Answer]
## CJam, 10 bytes
```
1ri{_2*^}*
```
[Test it here.](http://cjam.aditsu.net/#code=1ri%7B_2*%5E%7D*&input=4)
Simple iterative solution using bitwise XOR.
[Answer]
# Ruby, 26 bytes
anonymous function with iteration.
```
->n{a=1;n.times{a^=a*2};a}
```
this recursive function is one byte shorter, but as it needs to be named to be able to refer to itself, it ends up one byte longer.
```
f=->n{n<1?1:(s=f[n-1])^s*2}
```
[Answer]
# Ruby, 25 bytes
```
->n{eval"n^=2*"*n+?1*n=1}
```
Shorter than the other answers on here so far. It constructs this string:
```
n^=2*n^=2*n^=2*n^=2*1
```
Then it sets `n=1` (this actually happens while the string is being made) and evaluates the above string, returning the result.
[Answer]
# [Samau](https://github.com/AlephAlpha/Samau/tree/master/OldSamau), 4 bytes
Now Samau has built-in functions for [XOR multiplication](https://codegolf.stackexchange.com/questions/50240/xor-multiplication) and XOR power.
```
▌3$ⁿ
```
Hex dump (Samau uses CP737 encoding):
```
dd 33 24 fc
```
Explanation:
```
▌       read a number
 3      push 3
  $     swap
   ⁿ    take the XOR power
```
[Answer]
# Pure Bash (no external utilities), 37
Bash integers are 64-bit signed, so this works for inputs up to and including 62:
```
for((x=1;i++<$1;x^=x*2)){
:
}
echo $x
```
[Answer]
## Python 2.7.6, 38 33 bytes
Thanks to Dennis for shaving off a few bytes!
```
x=1
exec'x^=x*2;'*input()
print x
```
[Answer]
# Pyth, 7 bytes
```
uxyGGQ1
```
Try it online: [Demonstration](https://pyth.herokuapp.com/?code=uxyGGQ1&input=4&debug=0)
### Explanation:
```
u    Q1   apply the following statement input-times to G=1:
 xyGG        update G with (2*G xor G)
```
[Answer]
# [MATL](https://esolangs.org/wiki/MATL), 15 bytes
Similar to [@flawr's answer](https://codegolf.stackexchange.com/a/67500/36398):
```
i:1w"TToX+]2\XB
```
*EDIT (May 20, 2016) [Try it online!](http://matl.tryitonline.net/#code=aToxdyJUVG9ZK10yXFhC&input=NQ) 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              
```
[Answer]
# [Perl 5](https://www.perl.org/), 23 bytes
```
$.^=2*$.for 1..<>;say$.
```
[Try it online!](https://tio.run/##K0gtyjH9/19FL87WSEtFLy2/SMFQT8/Gzro4sVJF7/9/k3/5BSWZ@XnF/3V9TfUMDA0A "Perl 5 – Try It Online")
[Answer]
# 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
```
[Answer]
# Mathematica, ~~40~~ 24 bytes
```
Nest[BitXor[#,2#]&,1,#]&
```
[Answer]
## 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
```
[Answer]
# 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}
```
[Answer]
# [brainfuck](https://github.com/TryItOnline/brainfuck), 87 bytes
```
,[>>[>]++<[[->+>+<<]>-->[-<<+>>]<[>+<-[>-<-]]>+<<<]>>>[[-<+>]>]<<[<]<-]>>[<[->++<]>>]<+
```
[Try it online!](https://tio.run/##bY87DsJADER7TrG9MSew5iKWixAFFBEFlM/5l/FCJAq28crPM2Nfl26cb3v/qPXsgCNEzF0hELOAKlzNBAhzttShphFJiakgFgSxuQURW5Z6SRwm9blvr31bSz9MU@nWMs7bcB@WE@NaSNNQ1FKgkdWNufQ4XjoyOteAyzeyLWVtD9c4lXJMu30qzdJX8PvJ8Ug//BknuNCLh9Q3 "brainfuck – 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.
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 5 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
±s┤ε─
```
[Run and debug online!](https://staxlang.xyz/#p=925b5dde17&i=%5B1+0+10+0+-127+0+-460+0+576%5D%0A%5B1+0+-4+0%5D%0A%5B1%5D&a=1&m=2)
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
```
[Answer]
## 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.
[Answer]
## Seriously, 12 bytes
```
2,╣`2@%`Mεj¿
```
Hex Dump:
```
322cb960324025604dee6aa8
```
[Try it online](http://seriouslylang.herokuapp.com/link/code=322cb960324025604dee6aa8&input=5)
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
```
[Answer]
# [Pyt](https://github.com/mudkip201/pyt), ~~40~~ 10 [bytes](https://github.com/mudkip201/pyt/wiki/Codepage)
```
Đ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!](https://tio.run/##ARoA5f9weXT//8SQMOKHucWYxIcyJcewMsSo//8zMA)
]