"Prime" pyramid

Question

The pyramid begins with the row 1 1. We'll call this row 1. For each subsequent row, start with the previous row and insert the current row number between every adjacent pair of numbers that sums to the current row number. $$ 1\quad1\\ 1\quad\color{red}{2}\quad1\\ 1\quad\color{red}{3}\quad2\quad\color{red}{3}\quad1\\ 1\quad\color{red}{4}\quad3\quad2\quad3\quad\color{red}{4}\quad1\\ 1\quad\color{red}{5}\quad4\quad3\quad\color{red}{5}\quad2\quad\color{red}{5}\quad3\quad4\quad\color{red}{5}\quad1\\ 1\quad\color{red}{6}\quad5\quad4\quad3\quad5\quad2\quad5\quad3\quad4\quad5\quad\color{red}{6}\quad1\\ \cdots $$

This pyramid is an example of a false pattern. It seems to encode the prime numbers in the lengths of its rows, but the pattern breaks down later on. You may wish to learn more about this sequence from a recent Numberphile video which is the inspiration for this question.

Task

Output the sequence. You may do so in any of the following ways:

Method	Example input	Example output
The infinite sequence as rows. We must be able to tell the rows apart somehow.	-	1 1 1 2 1 1 3 2 3 1 1 4 3 2 3 4 1 ...
The infinite sequence as numbers, top to bottom, left to right.	-	1 1 1 2 1 1 3...
The first \$n\$ rows of the pyramid, 1-indexed. We must be able to tell the rows apart somehow.	3	1 1 1 2 1 1 3 2 3 1
The first \$n\$ rows of the pyramid, 0-indexed. We must be able to tell the rows apart somehow.	3	1 1 1 2 1 1 3 2 3 1 1 4 3 2 3 4 1
The first \$n\$ numbers in the pyramid, 1-indexed.	4	1 1 1 2
The first \$n\$ numbers in the pyramid, 0-indexed.	4	1 1 1 2 1
The \$n\$th row in the pyramid, 1-indexed.	2	1 2 1
The \$n\$th row in the pyramid, 0-indexed.	2	1 3 2 3 1
The \$n\$th number in the pyramid, 1-indexed.	7	3
The \$n\$th number in the pyramid, 0-indexed.	7	2

Rules

• Please specify which of the above methods your answer uses.
• Output format is highly flexible. It may take the form of your language's collection type, for instance.
• Sequence rules apply, so infinite output may be in the form of a lazy list or generator, etc.
• This is code-golf, so the answer with the fewest bytes (in each language) wins.
• Standard loopholes are forbidden.

Answer 1

Python 2, ^{52 50} 48 bytes

-1 byte thanks to @loopy walt

Takes as input an integer \$ n \$ and outputs the \$ n^{th} \$ row. Based on the Wikipedia formula for the Farey sequence.

f=lambda n,b=1,d=1:1/d%b*[1]or[d]+f(n,d+n,n-b%d)

Try it online!

Answer 2

K (ngn/k), 26 bytes

Returns the \$n\$th row, 0-indexed.

1 1{x?[;;y]/|&y=+':x}/2+!:

Try it online!

A very literal implementation of the construction described in the challenge.

2+!: Integers from 2 to input+1. These are the row numbers to insert.
1 1{...}/ Using 1 1 as a seed, reduce the range of integers left to right.

+':x Sums of adjacent elements in the last row. The first value in the result will be 0+ first value.
&y= Indices where this is equal to the new row number.
| Reverse the list of indices. We will insert the row numbers one after the other, inserting from left to right would mess up later indices.
x?[;;y]/ Starting with the last row, insert the new row number at each of the indices.

Answer 3

Jelly, 8 bytes

!:Żg$$fR

A monadic Link that accepts a positive integer, \$n\$, and yields the \$n\$^th row as a list of positive integers.

Try it online!

How?

!:Żg$$fR - Link: integer, n                  e.g. 4
!        - factorial (n)                          24
     $   - last two links as a monad - f(x=n!):
    $    -   last two links as a monad - f(x):
  Ż      -     zero-range (x)                     [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]
   g     -     (that) greatest common divisor (x) [24, 1, 2, 3, 4, 1, 6, 1, 8, 3, 2, 1,12, 1, 2, 3, 8, 1, 6, 1, 4, 3, 2, 1,24]
 :       -   (x) integer divide (that)            [ 1,24,12, 8, 6,24, 4,24, 3, 8,12,24, 2,24,12, 8, 3,24, 4,24, 6, 8,12,24, 1]
       R - range (n)                              [ 1, 2, 3, 4]
      f  - filter keep                            [ 1,                4,    3,          2,          3,    4,                1]
                                                = [ 1, 4, 3, 2, 3, 4, 1]

Answer 4

Wolfram Language (Mathematica), 26 bytes

Denominator@*FareySequence

Try it online!

Inputs \$n\$ and returns the \$n\$th row, 1-indexed.

---

Wolfram Language (Mathematica), 33 bytes

1||1//.x_||y_/;x+y<=#:>x||x+y||y&

Try it online!

---

Wolfram Language (Mathematica), 39 bytes

Cases[#!/GCD[Range[0,#!],#!],a_/;a<=#]&

Try it online!

Answer 5

Julia 0.7, 40 39 bytes

!n=(a=(p=lcm(1:n))./gcd.(p,0:p))[a.<=n]

Try it online!

Thanks to alephalpha for a saved byte.

Answer 6

PARI/GP, 35 bytes

n->[d|i<-[0..n!],n>=d=n!/gcd(n!,i)]

Inputs \$n\$ and returns the \$n\$th row, 1-indexed.

Attempt This Online!

Answer 7

JavaScript (ES10), 61 bytes

Returns the \$n\$-th row (1-indexed), as an array.

This version naively builds all rows up to the requested one.

f=(n,a=[r=1,1])=>r++<n?f(n,a.flatMap(v=>n+(n=v)^r?v:[r,v])):a

Try it online!

---

JavaScript (ES6), 43 bytes

-1 thanks to @loopywalt

Returns the \$n\$-th row (1-indexed), as a comma-separated string.

This is a port of dingledooper's answer.

f=(n,b=n,d=1)=>n*~d+b?d+[,f(n,d+n,n-b%d)]:1

Try it online!

Answer 8

Excel (ms365), 163 bytes

Formula in B1:

=IFERROR(REDUCE({1,1},SEQUENCE(A1,,2),LAMBDA(a,b,VSTACK(a,LET(x,TAKE(a,-1),y,DROP(x,,-1),HSTACK(TOROW(VSTACK(y,IF(y+DROP(x,,1)=b,b,NA())),2,1),TAKE(x,,-1)))))),"")

---

I designed this answer to be complient with the rule:

"The first n rows of the pyramid, 0-indexed. We must be able to tell the rows apart somehow."

---

The idea here is as follows:

• REDUCE({1,1},SEQUENCE(A1,,2),LAMBDA(a,b, - This bit is basically telling Excel to take the input {1,1} and recurse the following SEQUENCE(A1,,2) times where 'the following' consists of two these two variables. The iteration will now start;
• VSTACK(a, - The iteration will then VSTACK() (vertically build) what is in variable 'a' and stack the following to it;
• LET(x,TAKE(a,-1),y,DROP(x,,-1),HSTACK(TOROW(VSTACK(y,IF(y+DROP(x,,1)=b,b,NA())),2,1),TAKE(x,,-1))) - Bulk of the iteration where we use LET() to store the last row from 'a' variable, then take all columns but the last and another variable to take all columns but the first. We compare these two arrays to test if the summation of each element would equal 'b' variable. If so, then use array modification to stack these numbers into the correct location.

Answer 9

05AB1E, 13 9 bytes

-4 bytes porting @JonathanAllan's Jelly answer, also outputting the \$n^{th}\$ row based on input \$n\$ (so make sure to upvote him as well!):

!ÐÝδ¿÷ILÃ

Try it online or verify the first 8 rows. (The footer ï casts strings to integers, so the output looks better. Feel free to remove it to see the outputs as strings.)

Explanation:

!         # Get the factorial of the (implicit) input-integer
 Ð        # Triplicate it
  Ý       # Pop one, and push a list in the range [0,input!]
   δ      # Apply double-vectorized, mapping over the list using another input! as
          # argument:
    ¿     #  Get the greatest common divisor of the current value and input!
     ÷    # Integer-divide the third input! by each of these GCD's
      IL  # Push a list in the range [1,input]
        Ã # Only keep those values from the list
          # (after which the result is output implicitly)

Original 13 bytes approach that outputs the infinite sequence (although pretty slowly):

X‚[=Dü+.ιNÌLÃ

Try it online. (The footer ï casts strings to integers, so the output looks better. Feel free to remove it, and change integer X to a literal string 1, to see the outputs as strings.)

Explanation:

X             # Push a 1
 ‚            # Pair the top two values together. Since the stack only contains a single
              # item and there is no input, it uses it twice to create pair [1,1]
  [           # Start an infinite loop:
   =          #  Print the current list with trailing newline (without popping the list)
    D         #  Duplicate the list
     ü        #  For each overlapping pair:
      +       #   Sum them together
       .ι     #  Interleave the two lists together
         N    #  Push the 0-based loop index
          Ì   #  Increase it by 2
           L  #  Pop and push a list in the range [1,index+2]
            Ã #  Only keep those values from the list

Answer 10

Nibbles, 14 bytes (28 nibbles)

`.:1 1|;>>+!!:0$@+@:-+<2@

Returns the infinite sequence of rows.
Follows the steps in the challenge description.

`.:1 1|;>>+!!:0$@+@:-+<2@
`.                          # iterate until unique
  :1 1                      # starting with a list of 1,1
      |;>>+!!:0$@+@:-+<2@   # this function:
           !       :        #   join each element of 
                  @         #   this list
            !:0$@+          #   to pairwise sums of this list (with initial 1),
          +                 #   flatten this list of lists,
        >>                  #   and remove the initial 1;
       ;                    #   (remember this list)
      |                     #   now filter this list 
                            #   keeping only elements that are >0 (truthy) after
                    -       #   subtracting from
                     +      #   the sum of
                      <2@   #   the first two elements of the remembered list

Answer 11

Haskell, 56 bytes

scanl(!)[1,1][2..]
(a:b:t)!i=a:[i|a+b==i]++(b:t)!i
x!i=x

Try it online!

Is an infinite list of rows.

If not valid output this is an infinite list of numbers for 61 Bytes.

id=<<scanl(!)[1,1][2..]
(a:b:t)!i=a:[i|a+b==i]++(b:t)!i
x!i=x

Answer 12

Vyxal, 9 bytes

¡Dʀvġḭ?ɾ↔

Try it Online!

Port of Jonathan Allan's Jelly answer

¡D        # n!, 3 times
   vġ     # Gcd with
  ʀ       # Range(0, n+1)
     ḭ    # Integer divide n by that
      ?ɾ↔ # Keep those from range(1, n+1)

Answer 13

Python, 73 bytes

a=x,=1,
while[print(1,*a)]:a=sum(([x+y][x+y+~a[0]:]+[x:=y]for y in a),[])

Attempt This Online!

Prints forever.

Naive implementation. Feel a bit silly, since everybody else seems to do something clever.

Answer 14

Charcoal, 27 bytes

Ｎθ⊞υ¹Ｗ⁼¹№υ¹⊞υ⁻θ﹪⁺θ§υ±²↨υ⁰Ｉυ

Try it online! Link is to verbose version of code. Outputs the nth row. Explanation: Based on @dingledooper's formula.

Ｎθ

Input n.

⊞υ¹

Start with 1 as the first term in the nth row.

Ｗ⁼¹№υ¹

Repeat until there are two 1s in the row.

⊞υ⁻θ﹪⁺θ§υ±²↨υ⁰

Calculate the next term as n-(n+b)%d where d is the previous term and b is the penultimate term. Note that on the first loop there is no penultimate term so cyclic indexing gives b a value of 1 but d=1 so the result is n anyway.

Ｉυ

Output all of the terms in the nth row.

A naive approach takes 34 bytes:

Ｆ²⊞υ¹Ｆ…·²Ｎ≔ΣＥυΦ⟦ικ⟧∨ν∧λ⁼ι⁺κ§υ⊖λυＩυ

Attempt This Online! Link is to verbose version of code. Outputs the nth row. Explanation:

Ｆ²⊞υ¹

Start with [1, 1] as the first row.

Ｆ…·²Ｎ

Loop over the remaining rows.

≔ΣＥυΦ⟦ικ⟧∨ν∧λ⁼ι⁺κ§υ⊖λυ

Insert the current row number into the list at the appropriate places.

Ｉυ

Output the final list.

Answer 15

Retina 0.8.2, 71 bytes

.+
$*
1
,1$`
^
1,1¶
{`\b(1+)(?=(,1+)\b.*¶\2\1\b)
$1$2$1
}`¶,1+
¶
1+
$.&

Try it online! Outputs the nth row but link is to test suite that outputs the first n rows. Explanation:

.+
$*

Convert n to unary.

1
,1$`

Create a list from 1 to n.

^
1,1¶

Start with [1, 1] as the first row.

{`
}`

Loop over each row.

\b(1+)(?=(,1+)\b.*¶\2\1\b)
$1$2$1

Insert the current index between every pair of adjacent values with that as its sum.

¶,1+
¶

Remove the current index so that the next loop uses the next index.

1+
$.&

Convert to decimal.

Answer 16

Haskell, 63 bytes

scanl(#)[1,1][2..]
(a:t@(b:_))#r|r==a+b=a:r:t#r|0<1=a:t#r
l#_=l

The first line generates a lazy infinite list of rows. Try it online!

Explanation

The core of the solution is the operator #, which takes a list of numbers (the previous row) and an integer (the next row number) and recursively computes the next row.

-- If the first argument is a list with at least two elements, unpack it as
-- follows: first element is a, all but first element is t, second element is b
-- Second argument is r
(a:t@(b:_)) # r
-- If r equals a+b, prepend a and r to the result of a recursive call on t
  | r == a+b  = a:r:(t#r)
-- Else, just prepend a
  | otherwise = a:(t#r)

-- If the first argument has fewer than two elements, return it unchanged
l # _ = l

Then, to generate the infinite list of rows, we start from [1,1] and do a left scan over increasing row numbers:

scanl (#) [1,1] [2..]

Answer 17

Pyth, 24 bytes

JU2VQ
=-.iJm*qhNdd+VtJJ0

Try it online!

Prints the first \$n\$ rows as lists.

Explanation

JU2                        assign J to [0, 1]
   VQ                      for N in range eval(input())
                           print
     =   J                 assign J to
      -               0    remove zeros from
       .iJ                 interleave J with
          m*qhNdd          if not N map to 0
                 +VtJJ     pairwise sums of J

Answer 18

C (gcc), 82 bytes

o;g(n,b,d){o=n*~d+b?asprintf(&o,"%d %s",d,g(n,d+n,n-b%d)),o:"1";}f(n){n=g(n,n,1);}

Try it online!

C port of dingledooper's answer.

Answer 19

Ruby, 40 bytes

This is a port of dingledooper's answer and Arnauld's answer.

->n,b,d=1{b+n*~d<0?[d,f[n,d+n,n-b%d]]:1}

Attempt This Online!

Answer 20

Zsh, 92 100 bytes

p=(1 1)
for j ({2..$1})<<<$p&&p=(`for i ({1..$#p})echo $p[i] ${$((p[i]+p[i+1]==j?j:0)):#0}`)

Try it Online! ... 100 bytes