Sign up ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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, and must not output a wrong answer for any n.)

Output: The nth term (0-indexed) of the sequence as a decimal number.

This is 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.)

The Catalogue

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>

share|improve this question
5  
I'm not a big fan of must not output a wrong answer for any n. This basically forces languages that do not use arbitrary precision integers by default to check if the input is small enough... – Dennis 4 hours ago
    
Please clarify if understood the rules correctly (see comments here and here) and if rounded output (e.g., 1.288490189e10 for input 33) counts as wrong. – Dennis 45 mins ago
    
"Must work for all n up to 30, and must not output a wrong answer for any n.". This is self-contradictory - surely "must not output a wrong answer" is the same as "Must work" ??? – Digital Trauma 21 mins ago

16 Answers 16

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^

$      # 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
share|improve this answer
    
You know, a good way to golf a byte off of many programs in a custom language is to make a trailing } be automatically inserted. Then this would be 4 bytes. :) – ETHproductions 4 hours ago
    
@ETHproductions Wait a minute, that already has been implemented :). Thanks for shaving off 1 byte haha. – Adnan 4 hours ago

PARI/GP, 32 bytes

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

The function takes the n-th power of the polynomial x+1 in the ring F2[x], lifts it to Z[x], and substitutes x by 2.

share|improve this answer
    
+1 for the "magical algebra nonsense" approach – Mauris 2 hours ago

Jelly, 6 bytes

1Ḥ^$³¡

Try it online!

The binary version that works with this revision 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.
share|improve this 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)'
share|improve this answer

CJam, 10 bytes

1ri{_2*^}*

Test it here.

Simple iterative solution using bitwise XOR.

share|improve this 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}
share|improve this answer

JavaScript (ES6), 28 bytes

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

Based on the first formula on the OEIS page. @Dennis helped me find a spot on the narrow, narrow margin between "must work for any input up to 30" and "must not output any wrong value": it simply recurses forever if the input is greater than 30. Do not try with inputs greater than 30 (unless you're fine with your browser crashing).

Here's a 23-byte version that works up to 30, but gets weird for larger inputs:

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

Here's a non-recursive version, using a for loop in an eval: (38 bytes)

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

Again, don't try this with inputs > 30; it will loop forever.

share|improve this answer
    
The rules, as currently written, invalidate this answer, since f(35) returns 15. Also, fork bomb alert: I had to force-close Chromium to stop f(30) (original revision) from running. :P – Dennis 4 hours ago
1  
@Dennis Wait, so if I can't output any wrong value, what am I supposed to do with inputs higher than 30? – ETHproductions 4 hours ago
    
I'm not sure (and I hope the rule gets changed), but something like f=x=>x?(y=f(x-(x<31)))^y*2:1 would work. – Dennis 4 hours ago
    
@Dennis Ah, recurse infinitely = no output. I'll fix this when I get back to my computer. I hope that rule gets changed as well. – ETHproductions 3 hours ago

Mathematica, 40 24 bytes

Nest[BitXor[#,2#]&,1,#]&
share|improve this 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
share|improve this answer
    
This prints -1 for input 63. If I understand the rules correctly, this is not allowed. – Dennis 53 mins ago
    
@Dennis IMO the spec is self-contradictory for this point. I hope the poster can clarify. – Digital Trauma 20 mins ago

MIPS, 32 bytes

Input in $a1. Saves 8 bytes if no output (value in $a0).

        li      $a0, 1
loop:   beqz    $a1, exit
        sll     $t1, $a0, 1
        xor     $a0, $a0, $t1
        addi    $a1, $a1, -1
        j       loop

exit:   li      $v0, 1
        syscall
share|improve this 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
share|improve this 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.

share|improve this answer
    
I think you can anonymize the last line to (iterate((2*)>>=xor)1!!) – xnor 32 mins ago

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
share|improve this answer
    
Welcome to Programming Puzzles & Code Golf! exec'x^=x*2;'*input() saves a few bytes over the for approach. – Dennis 1 hour ago

Seriously, 18 bytes

2,;3╤>óX╣`2@%`Mεj¿

Hex Dump:

322c3b33d13ea258b960324025604dee6aa8

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), but this one is set to fail fast for values over 999, since it is easier to represent 1000 in 2 bytes. Fully 1/3 of the program is checking this condition.

Explanation:

 ,;                       make two copies of the input
   3╤>óX                  quit immediately if the input copy is 1000 or higher
        ╣                 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
share|improve this 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.

share|improve this 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 :)

share|improve this answer
    
The output should be a decimal number. – Dennis 52 mins ago
    
@Dennis, OK, edited – brainkz 36 mins ago
    
The expected output for input 10 is 1285. – Dennis 35 mins ago
    
@Dennis that's embarrassing that only now I got the point – brainkz 8 mins ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.