Compute the Binary Sierpinski Triangle Sequence

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

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♦, Dec 23 '15 at 15:46
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♦, Dec 23 '15 at 19:25
"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, Dec 23 '15 at 19:49
Due to overwhelming popular opposition to the unreasonable and soul-crushing burden of input validation, this requirement has been removed. You may output whatever garbage you want for large n. Enjoy! — quintopia, Dec 23 '15 at 20:13
Rather than saying that the output shouldn't be wrong, I would recommend just saying that submissions have to support input up to the largest n for which nothing overflows. — Alex A.♦, Dec 23 '15 at 20:17

Adnan · Answer 1 · 2015-12-23 21:26:14Z

up vote 14 down vote

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

edited Dec 23 '15 at 21:26

answered Dec 23 '15 at 14:22

Adnan

11.7k128114

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 Dec 23 '15 at 15:54

1

@ETHproductions Wait a minute, that already has been implemented :). Thanks for shaving off 1 byte haha. – Adnan Dec 23 '15 at 15:58

1

There's a bug in this code. How do I know? It's beating Dennis. – A Nerd - I Dec 23 '15 at 20:43

@Ampora ampora pls – Adnan Dec 23 '15 at 20:46

2

@Ampora Not only is it beating Dennis, it's beating Dennis's custom golfing language. ;) – ETHproductions Dec 23 '15 at 20:54

| show 2 more comments

alephalpha · Answer 2 · 2015-12-23 14:46:57Z

up vote 11 down vote

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 F₂[x], lifts it to Z[x], and substitutes x by 2.

answered Dec 23 '15 at 14:46

alephalpha

11k21458

2

+1 for the "magical algebra nonsense" approach – Lynn Dec 23 '15 at 18:10

add a comment |

Dennis · Answer 3 · 2015-12-23 15:42:00Z

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.

brainkz · Answer 4 · 2015-12-23 20:01:15Z

up vote 4 down vote

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

edited Dec 23 '15 at 20:01

answered Dec 23 '15 at 18:55

brainkz

2895

Seems to work with Octave as well. – Dennis♦ Dec 23 '15 at 20:14

add a comment |

ETHproductions · Answer 5 · 2015-12-23 20:56:15Z

up vote 4 down vote

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")

edited Dec 23 '15 at 20:56

answered Dec 23 '15 at 14:41

ETHproductions

11.5k21772

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♦ Dec 23 '15 at 15:59

1

@Dennis Wait, so if I can't output any wrong value, what am I supposed to do with inputs higher than 30? – ETHproductions Dec 23 '15 at 16:04

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♦ Dec 23 '15 at 16:09

@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 Dec 23 '15 at 16:11

The rule has been removed from the question. – Dennis♦ Dec 23 '15 at 20:13

add a comment |

flawr · Answer 6 · 2015-12-23 13:54:59Z

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)'

Level River St · Answer 7 · 2015-12-23 14:30:10Z

up vote 3 down vote

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}

answered Dec 23 '15 at 14:30

Level River St

13.3k21560

add a comment |

Lynn · Answer 8 · 2015-12-23 18:21:18Z

up vote 3 down vote

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.

answered Dec 23 '15 at 18:21

Lynn

14.1k12978

I think you can anonymize the last line to (iterate((2*)>>=xor)1!!) – xnor Dec 23 '15 at 19:38

I tried that, but it doesn't work, for dreaded monomorphism restriction reasons. – Lynn Dec 24 '15 at 0:33

add a comment |

alephalpha · Answer 9 · 2015-12-24 13:40:23Z

up vote 3 down vote

Samau, 4 bytes

Now Samau has built-in functions for 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

answered Dec 24 '15 at 13:40

alephalpha

11k21458

Could this be reduced to 3 bytes by swapping the first two commands and eliminating the swap? – quintopia Jan 22 at 20:33

@quintopia No. Samau automatically pushes the input onto the stack as a string , and ▌ reads a number from the string. If we swap the first two commands, it would try to read a number from 3, which is not a string. – alephalpha Jan 23 at 4:48

why doesn't samau try to eval the string when possible? – quintopia Jan 23 at 5:06

add a comment |

Martin Büttner · Answer 10 · 2015-12-23 14:24:57Z

up vote 2 down vote

CJam, 10 bytes

1ri{_2*^}*

Test it here.

Simple iterative solution using bitwise XOR.

answered Dec 23 '15 at 14:24

Martin Büttner♦

89.4k35213508

add a comment |

Digital Trauma · Answer 11 · 2015-12-23 17:40:16Z

up vote 2 down vote

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

answered Dec 23 '15 at 17:40

Digital Trauma

37.3k653154

add a comment |

qwr · Answer 12 · 2015-12-23 17:46:35Z

up vote 2 down vote

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

edited Dec 23 '15 at 17:46

answered Dec 23 '15 at 17:06

qwr

4,44141847

add a comment |

MCS-Kaijin · Answer 13 · 2015-12-23 19:04:57Z

up vote 2 down vote

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

edited Dec 23 '15 at 19:04

answered Dec 23 '15 at 18:03

MCS-Kaijin

1093

1

Welcome to Programming Puzzles & Code Golf! exec'x^=x*2;'*input() saves a few bytes over the for approach. – Dennis♦ Dec 23 '15 at 18:20

This beats my Python entry, which I'll just leave here for posterity: f=lambda n:f(n-1)^2*f(n-1)if n>0 else 1 – Jack Brounstein Dec 23 '15 at 22:33

add a comment |

Lynn · Answer 14 · 2015-12-25 08:02:03Z

up vote 2 down vote

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.

answered Dec 25 '15 at 8:02

Lynn

14.1k12978

Does that *n=1 actually save anything over m=1;"m^=2*"*n+?1 – Martin Büttner♦ Dec 25 '15 at 8:13

No, but doing it with just one variable is very showy :) – Lynn Dec 25 '15 at 8:14

add a comment |

alephalpha · Answer 15 · 2015-12-23 13:58:24Z

up vote 1 down vote

Mathematica, 40 24 bytes

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

answered Dec 23 '15 at 13:58

alephalpha

11k21458

add a comment |

Aaron Davies · Answer 16 · 2015-12-23 18:05:14Z

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

Luis Mendo · Answer 17 · 2015-12-24 11:46:44Z

MATL, 15 bytes

Similar to @flawr's answer:

i:1w"TToX+]2\XB

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

Jakube · Answer 18 · 2015-12-25 09:45:03Z

up vote 1 down vote

Pyth, 7 bytes

uxyGGQ1

Try it online: Demonstration

Explanation:

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

answered Dec 25 '15 at 9:45

Jakube

17.7k31592

add a comment |

Sherlock9 · Answer 19 · 2016-03-30 07:29:45Z

up vote 1 down vote

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}

edited Mar 30 at 7:29

answered Dec 25 '15 at 5:22

Sherlock9

2,798734

add a comment |

Aaron Davies · Answer 20 · 2015-12-23 19:21:19Z

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.

quintopia · Answer 21 · 2015-12-23 20:30:41Z

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

asked	4 months ago
viewed	1278 times
active	1 month ago

current community

your communities

more stack exchange communities

Compute the Binary Sierpinski Triangle Sequence

Leaderboard

21 Answers 21

05AB1E, 5 4 bytes

PARI/GP, 32 bytes

Jelly, 6 bytes

How it works

Matlab, 45 bytes

JavaScript (ES6), 23 bytes

Matlab, 77 70 bytes

Ruby, 26 bytes

Haskell, 44 bytes

Samau, 4 bytes

CJam, 10 bytes

Pure Bash (no external utilities), 37

MIPS, 32 bytes

Python 2.7.6, 38 33 bytes

Ruby, 25 bytes

Mathematica, 40 24 bytes

k4, 26 bytes

MATL, 15 bytes

Example

Explanation

Pyth, 7 bytes

Explanation:

Ruby, 31 26 bytes

APL, 31 bytes

Seriously, 12 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf sequence binary bitwise or ask your own question.

Linked

Hot Network Questions

current community

your communities

more stack exchange communities

Compute the Binary Sierpinski Triangle Sequence

Leaderboard

21 Answers 21

05AB1E, 5 4 bytes

PARI/GP, 32 bytes

Jelly, 6 bytes

How it works

Matlab, 45 bytes

JavaScript (ES6), 23 bytes

Matlab, 77 70 bytes

Ruby, 26 bytes

Haskell, 44 bytes

Samau, 4 bytes

CJam, 10 bytes

Pure Bash (no external utilities), 37

MIPS, 32 bytes

Python 2.7.6, 38 33 bytes

Ruby, 25 bytes

Mathematica, 40 24 bytes

k4, 26 bytes

MATL, 15 bytes

Example

Explanation

Pyth, 7 bytes

Explanation:

Ruby, 31 26 bytes

APL, 31 bytes

Seriously, 12 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf sequence binary bitwise or ask your own question.

Linked

Related

Hot Network Questions