Generate Pascal's Braid

Question

This is Pascal's Braid:

 1 4  15  56   209   780    2911    10864     40545      151316      564719
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841
 1 4  15  56   209   780    2911    10864     40545      151316      564719

^{I totally made that up. Blaise Pascal didn't have a braid as far as I can tell, and if he did it was probably made of hair instead of numbers.}

It's defined like this:

1. The first column has a single 1 in the middle.
2. The second column has a 1 at the top and at the bottom.
3. Now we alternate between putting a number in the middle or two copies of a number at the top and bottom.
4. If the number goes on the top or the bottom, it will be the sum of the two adjacent numbers (e.g. 56 = 15 + 41). If you tilt your head a little, this is like a step in Pascal's triangle.
5. If the number goes in the middle, it will be the sum of all three adjacent numbers (e.g. 41 = 15 + 11 + 15).

Your task will be to print (some part of) this braid.

Input

You should write a program or function, which receives a single integer n, giving the index of the last column to be output.

You may choose whether the first column (printing only a single 1 on the middle line) corresponds to n = 0 or n = 1. This has to be a consistent choice across all possible inputs.

Output

Output Pascal's Braid up to the nth column. The whitespace has to match exactly the example layout above, except that you may pad the shorter line(s) to the length of the longer line(s) with spaces and you may optionally output a single trailing linefeed.

In other words, every column should be exactly as wide as the number (or pair of equal numbers) in that column, numbers in successive columns should not overlap and there should be no spaces between columns.

You may either print the result to STDOUT (or the closest alternative), or if you write a function you may return either a string with the same contents or a list of three strings (one for each line).

Further Details

You may assume that n won't be less than the index of the first column (so not less than 0 or 1 depending on your indexing). You may also assume that the last number in the braid is less than 256 or the largest number representable by your language's native integer type, whichever is greater. So if your native integer type can only store bytes, you can assume that the largest n is 9 or 10 (depending on whether you use 0- or 1-based n) and if it can store signed 32-bit integers, n will be at most 33 or 34.

Standard code-golf rules apply. The shortest code wins.

OEIS

Here are a few relevant OEIS links. Of course, these contain spoilers for different ways to generate the numbers in the braid:

• Top/bottom: A001353 or A010905 or A106707 or A195503
• Middle: A001835 or A079935
• Both: A002530

Test Cases

These test cases use 1-base indexing. Each test case is four lines, with the first being the input and the remaining three being the output.

1

1

---
2
 1
1
 1
---
3
 1
1 3
 1
---
5
 1 4
1 3 11
 1 4
---
10
 1 4  15  56   209
1 3 11  41  153
 1 4  15  56   209
---
15
 1 4  15  56   209   780    2911
1 3 11  41  153   571   2131    7953
 1 4  15  56   209   780    2911
---
24
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560

Answer 1

Pyth, 44 bytes

The number generation took 20 bytes, and the formatting took 24 bytes.

jsMC+Led.e.<bkC,J<s.u+B+hNyeNeNQ,1 1Qm*;l`dJ

Try it online!

jsMC+Led.e.<bkC,J<s.u+B+hNyeNeNQ,1 1Qm*;l`dJ   input as Q
                   .u          Q,1 1           repeat Q times, starting with [1,1],
                                               collecting all intermediate results,
                                               current value as N:
                                               (this will generate
                                                more than enough terms)
                       +hNyeN                  temp <- N[0] + 2*N[-1]
                     +B      eN                temp <- [temp+N[-1], temp]

now, we would have generated [[1, 1], [3, 4], [11, 15], [41, 56], ...]

jsMC+Led.e.<bkC,J<s                 Qm*;l`dJ
                  s                            flatten
                 <                  Q          first Q items
                J                              store in J
                                     m    dJ   for each item in J:
                                         `     convert to string
                                        l      length
                                      *;       repeat " " that many times

jsMC+Led.e.<bkC,
              C,     transpose, yielding:
[[1, ' '], [1, ' '], [3, ' '], [4, ' '], [11, '  '], ...]
(each element with as many spaces as its length.)
        .e            for each sub-array (index as k, sub-array as b):
          .<bk            rotate b as many times as k

[[1, ' '], [' ', 1], [3, ' '], [' ', 4], [11, '  '], ...]

jsMC+Led
    +Led              add to each sub-array on the left, the end of each sub-array
   C                  transpose
 sM                   sum of each sub-array (reduced concatenation)
j                     join by new-lines

Answer 2

Python 2, 120 bytes

a=1,1,3,4
n=input()
y=0
exec"y+=1;t='';x=0;%sprint t;"%(n*"a+=a[-2]*4-a[-4],;v=`a[x]`;t+=[v,len(v)*' '][x+y&1];x+=1;")*3

Try it on Ideone.

Answer 3

MATL, 38 bytes

1ti:"yy@oQ*+]vG:)!"@Vt~oX@o?w]&v]&hZ}y

Try it online!

Computing an array with the (unique) numbers takes the first 17 bytes. Formatting takes the remaining 21 bytes.

Explanation

Part 1: generate the numbers

This generates an array with the numbers from the first and second rows in increasing order: [1; 1; 3; 4; 11; 15; ...]. It starts with 1, 1. Each new number is iteratively obtained from the preceding two. Of those, the second is multiplied by 1 or 2 depending on the iteration index, and then summed to the first to produce the new number.

The number of iterations is equal to the input n. This means that n+2 numbers are generated. Once generated, the array needs to be trimmed so only the first n entries are kept.

1t      % Push 1 twice
i:      % Take input n. Generage array [1 2 ... n]
"       % For each
  yy    %   Duplicate the two most recent numbers
  @o    %   Parity of the iteration index (0 or 1)
  Q     %   Add 1: gives 1 for even iteration index, 2 for odd
  *+    %   Multiply this 1 or 2 by the most recent number in the sequence, and add
       %    to the second most recent. This produces a new number in the sequence
]       % End for each
v       % Concatenate all numbers in a vertical array
G:)     % Keep only the first n entries

Part 2: format the output

For each number in the obtained array, this generates two strings: string representation of the number, and a string of the same length consisting of character 0 repeated (character 0 is displayed as a space in MATL). For even iterations, these two strings are swapped.

The two strings are then concatenated vertically. So n 2D char arrays are produced as follows (using · to represent character 0):

·
1

1
·

· 
3

4
·

·· 
11

15
··

These arrays are then concatenated horizontally to produce

·1·4··15
1·3·11··

Finally, this 2D char array is split into its two rows, and the first is duplicated onto the top of the stack. The three strings are displayed in order, each on a different line, producing the desired output

!       % Transpose into a horizontal array [1 1 3 4 11 15 ...]
"       % For each
  @V    %   Push current number and convert to string
  t~o   %   Duplicate, negate, convert to double: string of the same length consisting 
        %   of character 0 repeated
  X@o   %   Parity of the iteration index (1 or 0)
  ?     %   If index is odd
    w   %     Swap
  ]     %   End if
  &v    %   Concatenate the two strings vertically. Gives a 2D char array representing
        %   a "numeric column" of the output (actually several columns of characters)
]       % End for
&h      % Concatenate all 2D char arrays horizontally. Gives a 2D char array with the
        % top two rows of the output
Z}      % Split this array into its two rows
y       % Push a copy of the first row. Implicitly display

Answer 4

Haskell, 101 bytes

a=1:1:t
t=3:4:zipWith((-).(4*))t a
g(i,x)=min(cycle" 9"!!i)<$>show x
f n=[zip[y..y+n]a>>=g|y<-[0..2]]

Defines a function f :: Int → [String].

• Michael Klein reminded me I didn’t need to call unlines on the result, saving 7 bytes. Thanks!

• I saved a byte by replacing " 9"!!mod i 2 with cycle" 9"!!i.

• Three more bytes by writing two corecursive lists instead of using drop.

• My girlfriend pointed out I can save two more bytes by starting my answers at 0 instead of 1.

Answer 5

Jelly, 31 30 29 bytes

Q;S⁹o_
3ḶḂç@⁸СIµa"Ṿ€o⁶z⁶Zµ€Z

This is a monadic link; it accepts a 0-based column index as argument and returns a list of strings.

Try it online!

How it works

Q;S⁹o_                  Helper link.
                        Arguments: [k, 0, k] and [0, m, 0] (any order)

Q                       Unique; deduplicate the left argument.
 ;                      Concatenate the result with the right argument.
  S                     Take the sum of the resulting array.
   ⁹o                   Logical OR with the right argument; replaces zeroes in the
                        right argument with the sum.
     _                  Subtract; take the difference with the right argument to
                        remove its values.
                        This maps [k, 0, k], [0, m, 0] to [0, k + m, 0] and
                        [0, m, 0], [k, 0, k] to [m + 2k, 0, m + 2k].


3ḶḂç@⁸СIµa"Ṿ€o⁶z⁶Zµ€Z  Monadic link. Argument: A (array of column indices)

3Ḷ                      Yield [0, 1, 2].
  Ḃ                     Bit; yield [0, 1, 0].
        I               Increments of n; yield [].
      С                Apply...
   ç@                       the helper link with swapped arguments...
     ⁸                      n times, updating the left argument with the return
                            value, and the right argument with the previous value
                            of the left one. Collect all intermediate values of
                            the left argument in an array.
         µ         µ€   Map the chain in between over the intermediate values.
            Ṿ€          Uneval each; turn all integers into strings.
          a"            Vectorized logical AND; replace non-zero integers with
                        their string representation.
              o⁶        Logical OR with space; replace zeroes with spaces.
                z⁶      Zip with fill value space; transpose the resulting 2D
                        array after inserting spaces to make it rectangular.
                  Z     Zip; transpose the result to restore the original shape.
                     Z  Zip; transpose the resulting 3D array.

Answer 6

C, 183 177 176 bytes

#define F for(i=0;i<c;i++)
int i,c,a[35],t[9];p(r){F printf("%*s",sprintf(t,"%d",a[i]),r-i&1?t:" ");putchar(10);}b(n){c=n;F a[i]=i<2?1:a[i-2]+a[i-1]*(i&1?1:2);p(0);p(1);p(0);}

Explanation

C is never going to win any prizes for brevity against a higher level language, but the exercise is interesting and good practice.

The macro F shaves off six bytes at the cost of readability. Variables are declared globally to avoid multiple declarations. I needed a character buffer for sprintf, but since K&R is loose with type checking, sprintf and printf can interpret t[9] as a pointer to a 36-byte buffer. This saves a separate declaration.

#define F for(i=0;i<c;i++)
int i,c,a[35],t[9];

Pretty printing function, where r is the row number. Sprintf formats the number and computes the column width. To save space we just call this three times, one for each row of output; the expression r-i&1 filters what gets printed.

p(r) {
    F
        printf("%*s", sprintf(t, "%d", a[i]), r-i&1 ? t
                                                    : " ");
    putchar(10);
}

Entry point function, argument is number of columns. Computes array a of column values a[], then calls printing function p once for each row of output.

b(n) {
    c=n;
    F
        a[i] = i<2 ? 1
                   : a[i-2] + a[i-1]*(i&1 ? 1
                                          : 2);
    p(0);
    p(1);
    p(0);
}

Sample invocation (not included in answer and byte count):

main(c,v) char**v;
{
    b(atoi(v[1]));
}

Updated

Incorporated the inline sprintf suggestion from tomsmeding. That reduced the count from 183 to 177 characters. This also allows removing the the braces around the printf(sprintf()) block since it's only one statement now, but that only saved one character because it still needs a space as a delimiter. So down to 176.

Answer 7

PowerShell v2+, 133 bytes

param($n)$a=1,1;1..$n|%{$a+=$a[$_-1]+$a[$_]*($_%2+1)};$a[0..$n]|%{$z=" "*$l+$_;if($i++%2){$x+=$z}else{$y+=$z}$l="$_".Length};$x;$y;$x

_{44 bytes to calculate the values, 70 bytes to formulate the ASCII}

Takes input $n as the zero-indexed column. Sets the start of our sequence array $a=1,1. We then loop up to $n with 1..$n|%{...} to construct the array. Each iteration, we concatenate on the sum of (two elements ago) + (the previous element)*(whether we're odd or even index). This will generate $a=1,1,3,4,11... up to $n+2.

So, we need to slice $a to only take the first 0..$n elements, and pipe those through another loop |%{...}. Each iteration we set helper $z equal to a number of spaces plus the current element as a string. Then, we're splitting out whether that gets concatenated onto $x (the top and bottom rows) or $y (the middle row) by a simple odd-even if/else. Then, we calculate the number of spaces for $l by taking the current number, stringifying it, and taking its .Length.

Finally, we put $x, $y, and $x again on the pipeline, and output is implicit. Since the default .ToString() separator for an array when printing to STDOUT is a newline, we get that for free.

Example

PS C:\Tools\Scripts\golfing> .\pascal-braid.ps1 27
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560       7865521        29354524
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841       5757961       21489003
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560       7865521        29354524

Answer 8

PHP 265 bytes

<?php $i=$argv[1];$i=$i?$i:1;$a=[[],[]];$s=['',''];$p='';for($j=0;$j<$i;$j++){$y=($j+1)%2;$x=floor($j/2);$v=$x?$y?2*$a[0][$x-1]+$a[1][$x-1]:$a[0][$x-1]+$a[1][$x]:1;$s[$y].=$p.$v;$a[$y][$x]=$v;$p=str_pad('',strlen($v),' ');}printf("%s\n%s\n%s\n",$s[0],$s[1],$s[0]);

Un-golfed:

$a = [[],[]];
$s = ['',''];

$p = '';

$i=$argv[1];
$i=$i?$i:1;
for($j=0; $j<$i; $j++) {
    $y = ($j+1) % 2;
    $x = floor($j/2);

    if( $x == 0 ) {
        $v = 1;
    } else {
        if( $y ) {
            $v = 2 * $a[0][$x-1] + $a[1][$x-1];
        } else {
            $v = $a[0][$x-1] + $a[1][$x];
        }
    }
    $s[$y] .= $p . $v;
    $a[$y][$x] = $v;
    $p = str_pad('', strlen($v), ' ');
}

printf("%s\n%s\n%s\n", $s[0], $s[1], $s[0]);

Python 278 bytes

import sys,math;a=[[],[]];s=['',''];p='';i=int(sys.argv[1]);i=1 if i<1 else i;j=0
while j<i:y=(j+1)%2;x=int(math.floor(j/2));v=(2*a[0][x-1]+a[1][x-1] if y else a[0][x-1]+a[1][x]) if x else 1;s[y]+=p+str(v);a[y].append(v);p=' '*len(str(v));j+=1
print ("%s\n"*3)%(s[0],s[1],s[0])

Answer 9

Ruby, 120 bytes

Returns a multiline string.

Try it online!

->n{a=[1,1];(n-2).times{|i|a<<(2-i%2)*a[-1]+a[-2]}
z=->c{a.map{|e|c+=1;c%2>0?' '*e.to_s.size: e}*''}
[s=z[0],z[1],s]*$/}

Answer 10

Matlab, 223 characters, 226 bytes

function[]=p(n)
r=[1;1];e={(' 1 ')',('1 1')'}
for i=3:n;r(i)=sum((mod(i,2)+1)*r(i-1)+r(i-2));s=num2str(r(i));b=blanks(floor(log10(r(i)))+1);if mod(i,2);e{i}=[b;s;b];else e{i}=[s;b;s];end;end
reshape(sprintf('%s',e{:}),3,[])

Ungolfed and commented:

function[]=p(n) 
r=[1;1];                                    % start with first two 
e={(' 1 ')',('1 1')'}                       % initialize string output as columns of blank, 1, blank and 1, blank, 1.
for i=3:n;                                  % for n=3 and up! 
    r(i)=sum((mod(i,2)+1)*r(i-1)+r(i-2));   % get the next number by 1 if even, 2 if odd times previous plus two steps back
    s=num2str(r(i));                        % define that number as a string
    b=blanks(floor(log10(r(i)))+1);         % get a number of space characters for that number of digits
    if mod(i,2);                            % for odds
        e{i}=[b;s;b];                       % spaces, number, spaces
    else                                    % for evens
        e{i}=[s;b;s];                       % number, spaces, number
    end;
end
reshape(sprintf('%s',e{:}),3,[])            % print the cell array of strings and reshape it so it's 3 lines high

Answer 11

PHP, 135 124 123 120 bytes

<?while($i<$argv[1]){${s.$x=!$x}.=${v.$x}=$a=$i++<2?:$v1+$v+$x*$v;${s.!$x}.=str_repeat(' ',strlen($a));}echo"$s
$s1
$s";

taking advantage of implicit typecasts and variable variables
a third of the code (37 bytes) goes into the spaces, 64 bytes altogether used for output

breakdown

$i=0; $x=false; $v=$v1=1; $s=$s1='';    // unnecessary variable initializations
for($i=0;$i<$argv[1];$i++)  // $i is column number -1
{
    $x=!$x; // $x = current row: true (1) for inner, false (empty string or 0) for outer
    // calculate value
    $a=
        $i<2?               // first or second column: value 1
        :$v1+(1+$x)*$v      // inner-val + (inner row: 1+1=2, outer row: 1+0=1)*outer-val
    ;
    ${s.$x}.=${v.$x}=$a;    // replace target value, append to current row
    ${s.!$x}.=str_repeat(' ',strlen($a));    // append spaces to other row
}
// output
echo "$s\n$s1\n$s";

Answer 12

Batch, 250 bytes

@echo off
set s=
set d=
set/ai=n=0,j=m=1
:l
set/ai+=1,j^^=3,l=m+n*j,m=n,n=l
set t=%s%%l%
for /l %%j in (0,1,9)do call set l=%%l:%%j= %%
set s=%d%%l%
set d=%t%
if not %i%==%1 goto l
if %j%==1 echo %d%
echo %s%
echo %d%
if %j%==2 echo %s%

Since the first and third lines are the same, we just have to build two strings. Here d represents the string that ends with the last entry and s represents the string that ends with spaces; the last four lines ensure that they are printed in the appropriate order. i is just the loop counter (it's slightly cheaper than counting down from %1). j is the toggle between doubling the previous number before adding it to the current number to get the next number. m and n contain those numbers. l, as well as being used as a temporary to calculate the next number, also gets its digits replaced with spaces to pad out s; s and d are exchanged each time via the intermediate variable t.