Pascal's Fibonacci Triangle

Question

What do you get when you cross Pascal's Triangle and the Fibonacci sequence? Well, that's what you have to find out!

Task

Create a triangle that looks like this:

          1
        1   1
       2  2  2
    3   5  5   3
  5  10  14  10  5
8  20  32  32  20  8

Basically, instead of each cell being the sum of the cells above it on the left and right, you also need to add the cell on the left above the cell on the left and the cell on the right above the cell on the right.

This is A036355.

You may choose to do one of the following:

• Output the \$n\$th row (indexed as you wish)
• Output the first \$n\$ rows
• Output all rows infinitely

Rules

• Each row may be represented as a string separated by some character that is not a digit or an ordered collection of numbers. You do not need to align the triangle like I did in the example.
• If you choose to output multiple rows, you need either an ordered list of rows, or a string that uses a different separator than the one you use within rows.
• Please specify which task you chose in your answer, along with the input (if applicable) and output format.
• You can receive input and output through any of the standard IO methods.
• This is code-golf, so shortest code in bytes wins!

Bounty

As Scala is the language of the month, I will be giving a 50 rep bounty for any Scala answers to this question (not just if you're a first-time user). If multiple Scala answers are posted, I will be happy to put a bounty on a different Scala answer of yours instead.

Answer 1

Python 2, 73 72 69 bytes

-1 byte thanks to dingledooper!
-3 bytes thanks to Sisyphus!

Prints the rows indefinitely.

c=a=[0]
b=[1]
while 1:print b;a,b=b,map(sum,zip(c*2+a,a+c*2,c+b,b+c))

Try it online!

Answer 2

Haskell, ^{82 \$\cdots\$} 60 bytes

[]%[1]
u%v=v:v%foldl1(zipWith(+))[0:0:u,u++[0,0],0:v,v++[0]]

Try it online!

-10 thanks to @user

-4 thanks to @ovs

Fairly new to Haskell, and never golfed in it before. Happy to be beaten!

Answer 3

J, 30 bytes

Returns the n'th row.

0{((+|.)@(+/)@,.,:{~)&0&(1,:0)

Try it online!

How it works

• f&0&(1,:0) (1,:0) f 0 will be executed n times
• (last two rows) g@,. (0) append a 0 to each row and execute g, f.e. g (2 2 2 0,: 1 1 0 0)
• (+|.)@(+/) sum the two rows 3 3 2 0 and add it to its reverse: 3 5 5 3
• ,:{~ append the previous row 3 5 5 3,:2 2 2 0
• 0{ after n iteration get the last row 3 5 5 3

Answer 4

Scala, 156..133 120 bytes

-23 bytes thanks to user!
-13 bytes thanks to Command Master!

()=>{var(a,b)=Seq(1,1)->Seq(1)
while(1>0){println(b)
val t=a
a=Seq(0+:0+:b,b:+0:+0,a:+0,0+:a).transpose.map(_.sum)
b=t}}

Try it online!

Output is infinite.

Explanation:

object M extends App {
  var (a, b) = Seq(1, 1) -> Seq(1)                                          // init (a, b) := ([1, 1], [1]])
  while (1 > 0) {                                                           // while true
    println(b)                                                              // print b
    val t = a                                                               // cache a in a local variable t
    a = Seq(0 +: 0 +: b, b :+ 0 :+ 0, a :+ 0, 0 +: a).transpose.map(_.sum)  // calculate the new triangle row with 
                                                                            // the help of the shifted lists a and b like in the example below
    b = t                                                                   // set b the cached previous value of a
  }
}

Example for n = 4:

   0  0  2  2  2
+  2  2  2  0  0
+  3  5  5  3  0
+  0  3  5  5  3
-----------------
=  5 10 14 10  5

Answer 5

05AB1E, 25 24 19 18 13 12 bytes

-6 bytes thanks to @ovs

-4 bytes thanks to @Neil, which allowed for additional -1

-2 bytes thanks to @Kevin Cruijssen

1‚ηλ₂0š+0šÂ+

Try it online!

A port of the python answer, basically. Outputs the rows infinitly

Explaination:

1 push 1
‚ pair. Since there is no input, it pairs 1 with 1, to get [1, 1]
η prefixes, get [[1], [1, 1]]
λ recursive environment
₂ push a(n-2)
0š prepend 0 to a(n-2)
+ sum with implicit a(n-1)
0š prepend a zero
 Bifurcate - push a and reversed(a)
+ sum

Answer 6

Haskell, 81 bytes

q=zipWith(+)
z=[0,0]
f=[]:[1]:[q(a++z)$q(z++a)$q(b++[0])$0:b|(a,b)<-zip f$tail f]

Try it online!

Returns an infinite list of all rows, 1-indexed (hence the tail in TIO to dispose of element 0).

Answer 7

Perl 5, 86 bytes

$,=$";@b=@c,@c=@,while say@,=map$,[$_]+($_>0)*$,[$_-1]+($_>1)*$b[$_-2]+$b[$_]||1,0..@,

Try it online!

Output is infinite.

Answer 8

Charcoal, 54 39 bytes

≔⟦¹⟧ηＦＮ«⊞υ⁰≔Ｅυ⁺κ§ηλι≔ηυ⊞ι⁰≔Ｅ⮌ι⁺κ§ιλη»Ｉη

Try it online! Link is to verbose version of code. Outputs the 0-indexed nᵗʰ row. Explanation: Relies on the symmetry of the triangle.

≔⟦¹⟧η

Start with the 0ᵗʰ row with just a 1 in it (using the predefined empty list for the "-1ᵗʰ" row).

ＦＮ«

Repeat n times.

⊞υ⁰

Append a 0 to the previous row.

≔Ｅυ⁺κ§ηλι

Sum the previous and current row to a temporary variable.

≔ηυ

Copy the current row to the previous row.

⊞ι⁰

Append a 0 to the new row.

≔Ｅ⮌ι⁺κ§ιλη

Add the new row to its reverse and save that as the current row.

»Ｉη

Print the final row.

Previous 54-byte version worked by creating the matrix formed by rotating the triangle anticlockwise by 45°:

Ｎθ⊞υＥθ⁼ι¹⊞υ⟦⁰⟧Ｆθ«≔⟦⁰⟧ηＦ⁻θι⊞ηΣ⁺…⮌η²Ｅ…⮌υ²§λ⊕κ⊞υη»Ｉ✂Ｅυ⊟ι²

Try it online! Link is to verbose version of code. Outputs the 1-indexed nᵗʰ row. Explanation:

Ｎθ

Input n.

⊞υＥθ⁼ι¹

Create a fictitious "-1ᵗʰ" row with a single 1 in the first column. This seeds the first row later.

⊞υ⟦⁰⟧

Create a "0ᵗʰ" row of zeros. (Because Charcoal uses cyclic indexing, I only need one zero.)

Ｆθ«

Loop over the desired output rows.

≔⟦⁰⟧η

Start with a "0ᵗʰ" column of just a zero.

Ｆ⁻θι

Loop over the additional numbers needed to complete this row of the rotated triangle.

⊞ηΣ⁺…⮌η²Ｅ…⮌υ²§λ⊕κ

Get the latest two numbers for this row plus the two numbers in the columns above and push the sum to the current row.

⊞υη

Push the completed row to the triangle.

»Ｉ✂Ｅυ⊟ι²

Print the last number in each row, excluding the two initial dummy rows.

Answer 9

AWK, 117 111 bytes

Prints the first n rows of the triangle, unformatted.

Edit: Let l and c be two integers. l c concatenates their values as a string. For example: in the first element, 0 0 evaluates "00" (str). 00 would evaluate 0 (int).

{print a[0 0]=1;for(;++l<$1;)for(c=0;c<=l;c++)printf a[l c]=a[l-1 c-1]+a[l-1 c]+a[l-2 c-2]+a[l-2 c](c~l?RS:FS)}

Step by step:

{
print a[0 0]=1;                  # sets the top of the triangle
for(;++l<$1;)                    # looping for the lines
  for(c=0;c<=l;c++)              # looping for the columns
    printf a[l c]=               # prints the ["l c"]th element of the array,
           a[l-1 c-1]+a[l-1 c]+  # which is the sum of these elements of the l-1 line
           a[l-2 c-2]+a[l-2 c]   # and these elements of the l-2 line.
           (c~l?RS:FS)           # if it's the last column, adds a line feed,
                                 # otherwise, a space.
}

Try it online!

Answer 10

Husk, 17 15 bytes

:;1mSż+oΘ↔Ẋż+Θ₀

Try it online!

Answering Razetime's challenge from the Husk chat

Explanation

:;1mSż+oΘ↔Ẋż+Θ₀
:;1                Begin with [1]
              ₀    Define the sequence recursively
          Ẋż+Θ     Pairwise sums of rows (e.g. [1,1]+[2,2,2]=[3,3,2])
   m               For each of these sums
    Sż+             Sum it to
       oΘ↔          itself reversed with an extra leading 0
                    (e.g. [3,3,2]+[0,2,3,3]=[3,5,5,3])

All the sums between lines are performed with ż+, which sums elements at the same indices and keeps elements from the longer line unchanged.

---

Previous solution, 17 bytes

∂ƒ(:İftS‡+T0Ẋż+ΘΘ

Try it online!

Here's my previous solution using an original approach.

Explanation

If we rotate the triangle 45° counterclockwise, we'll find out it is actually an infinite 2D matrix:

1  1  2  3  5 ...
1  2  5 10 20 ...
2  5 14 32 71 ...
3 10 32 84 ...
5 20 71 ...
...

This answer builds that matrix and then returns its antidiagonals, which will be the rows of the original triangle.

∂ƒ(:İftS‡+T0Ẋż+ΘΘ
∂                    Antidiagonals of
 ƒ(                  Fixpoint of the following function (defines the matrix recursively)
   :İft              Set the Fibonacci sequence as the first row
               ΘΘ    Add two empty rows before the matrix
            Ẋż+      and get the pairwise row sums
       S‡+T0         then sum this to itself transposed

The recursive definition computes the sums of each row with the previous one, and adds it to the sums of each column with the previous one; since the matrix is symmetric along the main diagonal, column sums are computed by transposing the row sums. Two empty rows need to be added to deal with the numbers near the sides of the triangle, where there are less than two rows/columns to sum.

Answer 11

JavaScript (V8), 82 bytes

f=(a=0,b=[1])=>print(b)+f(b,[...b,0].map((x,i)=>x+(a[i]|0)+(b[i-1]|0)+(a[i-2]|0)))

Try it online!

• Missing a JavaScript answer, hoping @Arnauld is fine

Answer 12

Jelly, 14 13 12 bytes

1WɓŻ+Ż++µ³¡0

Try it online!

Returns the nth row, indexed from 0.

Makes use of the fact that Jelly's “repeat n times” quick ¡, when given a dyad, behaves in a Fibonacci-ish way.

Answer 13

Husk, 29 28 23 19 bytes

• Saved 1 byte thanks to caird coinheringaahing
• Saved 5 bytes thanks to Razetime!
• Saved 4 bytes thanks to Leo!

¡öFz+S+m↔z+ḣ´e0↔;;1

Try it online!

Outputs an infinite list, explanation coming soon. This is really long, so it looks like I'm not going to get the bounty anyway.

¡öFz+S+m↔z+ḣ´e0↔;;1
¡                     Create infinite list by repeatedly applying function
                      that list of previous result to create new result
                ;;1   Initial list of results - [[1]]
  Fz+S+m↔z+ḣ`e0↔      Function to get next row from previous rows
               ↔      Reverse previous rows (so last 2 rows are at start)
            `e0       [0, 0]
           ḣ          Prefixes ([[0], [0,0]])
         z+           Zip by concatenating ([0, 1, 1], [0, 0, 1])
     S+               Then add those lists
       m↔             To their reverse ([1, 2, 1], [1, 0, 1])
  F                   Fold over that 2-element list of lists
   z+                 By adding them together to get the new row

Answer 14

Haskell, 59 bytes

x!y=zipWith(+)x$y++[0,0]
x#y=x:(0:0:y)!y!(0:x)!x#x
t=[1]#[]

Try it online!

Answer 15

Wolfram Language (Mathematica), 60 47 bytes

#3&@@@(#3&@@(1/(1-x(1+y+x+y^2x))+O@x^#)+O@y^#)&

Try it online!

1-indexed. Returns the first \$n\$ rows by truncating the generating function \$\frac1{1-x(1+x+y+xy^2)}\$.

---

older, 66 bytes

Sum[Multinomial[#-n-2i,n-2j,i,j],{i,0,#-n},{j,0,n}]~Table~{n,0,#}&

Try it online!

Answer 16

Julia 1.0, 53 bytes

f(i=1,j=[])=@show(i),f([i;0]+[0;i]+[j;0;0]+[0;0;j],i)

Try it online!

call f() for infinite output

Only correct up to 64-bit signed integer limit, replace i=1 with i=big(1) to make it work for any number

Answer 17

PHP, 124 115 112 bytes

echo 1;for($q=[1];print"
";$p=$q,$q=$r)for($i=-1;++$i<=count($q);)echo$r[$i]=$q[$i-1]+$q[$i]+$p[$i-2]+$p[$i].~_;

Try it online!

Did the world want this answer? Probably not. Did it deserve it? Definetly.

straightforward PHP soup that outputs all rows forever (at least until scientific notation -quickly- makes things unreadable)

EDIT: saved 9 bytes by not initializing $p and $r. There wasn't enough warnings for my taste.

EDIT2: saved another 3 bytes with another strategy for the newline output, thanks to print returning a truthy value (note that I'm aware that a byte could be saved with a "assumed constant" line separator like print A, but I preferred a readable output)

Answer 18

Pip -s, 22 bytes

Y^1LaS(l+:Py)+:RVlPE0y

Outputs the first n rows. Try it online!

Explanation

Each row of the triangle, represented as a list, can be obtained by a two-step process: first add the two previous rows; then take that result, reverse it, prepend 0, and add it to itself.

 [2 2 2]
+[3 5 5 3]
----------
 [5 7 7 3]
+[0 3 7 7 5]
------------
 [5 10 14 10 5]

Let's start with a less-golfed version of the code:

Y[1]La{Pyl+:yl+:RVlPE0Sly}
                            a is command-line argument; l is empty list (implicit)
Y[1]                        Yank the first row into y
    La{                  }  Loop a times:
       Py                    Print y, the current row
         l+:y                Add the two rows together, saving the result in l
                RVl          Reverse that list,
                   PE0       prepend 0,
             l+:             and add it back to l (the new row)
                      Sly    Swap l and y; y is now the new row and l the row above it

To get to 22 bytes:

• Using this tip, [1] → ^1.
• We can print y while adding it to l: l+:Py.
• An assignment expression evaluates to an lvalue, so we can use it in the swap command: S(l+:RVlPE0)y (parentheses not necessary, added for clarity).
• But then we can take the same idea one step further and replace the l in that assignment with the first l assignment. We'll need parentheses because assignment operators are right-associative; but since the body of the loop is now one statement, we can drop the curly braces for a net 1-byte savings: S(l+:Py)+:RVlPE0y.