Code the Levine sequence

Question

Introduction

• Note that I learned it from a Numberphile Video, where Neil Sloane explains it better. I recommend you to watch his Video. But for a quick Introduction:

The Levine Sequence is made from the Levine's Triangle, which is made as follows:
First you have \$0\$ ones, and \$1\$ twos.
Then you read the list backwards (right to left) and you have the same number of ones, as the \$0\$^\$th\$ element of the list.
Then you have the same number of twos, as the \$1\$^\$th\$ element of the list. That goes on and on, till the list ends. These are the first few rows:

ln[0]: 2
ln[1]: 11
ln[2]: 12
ln[3]: 112
ln[4]: 1123
ln[5]: 1112234
ln[6]: 11112223344567

Really, I don't think I've explained it good, so check out Neil's Video to learn more about it.

So, now, the Levine's Sequence. The \$n\$^\$th\$ Term of the sequence (starting at \$0\$), is just the sum of the \$n\$^\$th\$ row of the Levine's Triangle. These are the first few terms: 2, 2, 3, 4, 7, 14.
Then it just blows up.

Disclaimer: In the Numberphile video, also when you follow the steps I told, the \$0\$^\$th\$ term is \$2\$. But in OEIS the first term is \$1\$. So I will accept both sequences.

Rules

• The output must be printed to the program's output.
• The output must be in base 10 (outputting them in any other base is not allowed).
• Your program must can take input, the nth term.
• Outputting the integers with trailing / leading spaces is allowed.
• This is code-golf, so the shortest (original) code in each language wins!

I'm a bit free about this, so you can output just the \$n\$^\$th\$ term, up to the \$n\$^\$th\$ term, or even the whole sequence!

Leaderboard

I liked the leaderboard thingy, so here it is again: This uses uses @manatwork's layout.

/* Configuration */

var QUESTION_ID = 222856; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 96037; // 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 "https://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 "https://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,]*[^\s,]),.*?(-?\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,
      });
    
  });
  
  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;
    if (! /<a/.test(lang)) lang = '<i>' + lang + '</i>';
    lang = jQuery(lang).text().toLowerCase();

    languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link, uniq: lang};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.uniq > b.uniq) return 1;
    if (a.uniq < b.uniq) 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/Sites/codegolf/all.css?v=617d0685f6f3">
<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>
<div id="language-list">
  <h2>Winners 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>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr>
  </tbody>
</table>

Answer 1

J, ¹⁷ 15 bytes

1#.0&(]|.##\)&2

Try it online!

^{-2 thanks to FrownyFrog!}

On TIO, handles up to the 11th term 6837625106787 (where term 1 is 2).

how

J's "Copy" verb # is tailor made for this challenge:

   1 2 3 # 'abc'
abbccc

The rest is just mechanics needed to reverse and iterate:

• 0&(...)&2 Iterate ... as many times as the input. This occurs as a result of a special rule J has for the bond & conjunction. The &2 on the right hand side also sets the starting value of the iteration.
• ]... Ignores the left argument of 0 (resulting from 0&), and returns the result of ..., which is processed as a single argument verb, because this entire phrase is a dyadic hook.
  • |.##\ Reverse current list |., and use it as a mask to duplicate # the numbers 1...<length of current list>.
• 1#. Sum the result of that iteration.

Answer 2

Python 3, 91 87 85 bytes

f=lambda n,l=[2]:n and f(n-1,[n+1for n,e in enumerate(l[::-1])for _ in[0]*e])or l[-1]

Try it online!

Inputs \$1\$-based index \$n\$ and returns the \$n^{\text{th}}\$ element of the Levine Sequence starting at \$1\$.

Explanation

Starts at [2] and successively computes the next row in Levine's Triangle. The last element in the \$(n+2)^{\text{th}}\$ row is equal to the sum of the \$n^{\text{th}}\$ row or the \$n^{\text{th}}\$ term of the Levine Sequence starting at \$2\$. By using a \$1\$-based index and starting the sequence at \$1\$ we simply return the last element in the \$(n+1)^{\text{th}}\$ row.

Answer 3

R, 49 48 bytes

Edit: -1 byte thanks to Giuseppe

i=1:0;repeat{i=rep(seq(!i),rev(i));show(sum(i))}

Try it online!

Prints the infinite sequence (well, until it fails to allocate vector of size 25472.1 Gb at the 12th iteration...)

Answer 4

Python 2, 62 bytes

-3 bytes thanks to @xnor

Outputs the Levine sequence indefinitely, starting at 1.

a=[2]
while 1:i=len(a);print i;exec'a+=a.pop(i-1)*[i];i-=1;'*i

Try it online!

Answer 5

Scratch, 734 715 Bytes

-19 thanks to Lyxal!
Try it online!

Previously discussed, there doesn't seem to be a consensus on how to score Scratch code. I converted the code to scratchblocks4 and counted the characters:

when gf clicked
delete all of[B v
delete all of[E v
delete all of[T v
ask[]and wait
add(2)to[E v
add(1)to[T v
set[D v]to(1
repeat(answer
set[C v]to(0
A
repeat((item(length of [T v])of[T v])-(1
A
if<not<(R)=(item((length of[B v])-(1))of[B v])>>then
change[C v]by(()-(length of(D
change[D v]by(-1
delete(length of[B v])of[B v
A
end
end
set[D v]to(length of[B v
set[S v]to(
set[V v]to(1
set[t v]to(0
repeat(length of[B v
repeat(item(1)of[B v
set[S v]to(join(S)(V
end
change[V v]by(1
change[t v]by(item(1)of[B v
delete(1)of[B v
end
add(S)to[E v
add(t)to[T v
define A
set[R v]to(
repeat(length of(D
set[l v]to(item(length of[E v])of[E v
set[R v]to(join(letter((length of(l))-(C))of(l))(R
change[C v]by(1
end
add(R)to[B v

Alternatively, the program is 73 blocks: Obviously, Scratch isn't the first choice for any serious program, but I enjoyed making this! Lyxal substituted (item(length of[E v])of(E v for a variable, saving 19 bytes.

Answer 6

Jelly, 7 bytes

2JxṚƊ¡S

Try it online!

Outputs the \$n\$th term.

Explanation

2JxṚƊ¡S   Main monadic link
2         Start with 2
     ¡    Repeat n times
    Ɗ     (
 J          Indices (range [1..length])
  x         Repeat each item a number of times given by the corresponding item in
   Ṛ          The list reversed
    Ɗ     )
      S   Sum

Answer 7

Wolfram Language (Mathematica), 71 bytes

prints the nth 0-indexed term

Tr@Nest[Join@@MapThread[Table,{Range@Length[a=#],Reverse@a}]&,{1,0},#]&

Try it online!

Answer 8

Husk, 10 bytes

mΣ¡o`ṘN↔;2

Try it online!

Prints the infinite sequence. If you let it time out, you can see upto 11 terms.

Explanation

mΣ¡o`ṘN↔;2
        ;2 start with [2]
  ¡o       create the next iteration by
       ↔   reversing it
    `Ṙ     and replicating each element(flipped arg)
      N    times each element in the natural numbers
mΣ         map each list to its sum

Answer 9

JavaScript (Node.js), 110 bytes

n=6;a=[2];for(;n-->0;a=a.reverse().reduce((v,e,i)=>v.concat(Array(e*1).fill(i+1)),[]));console.log(a.join(""))

Try it online!

Set n at the start to change which element of the sequence is calculated.

Unfortunately, this is a rather long answer, due to JavaScript's wordy array operator functions.

Answer 10

Python 2, 82 bytes

x=[2]
exec'x=sum([v*[i]for i,v in enumerate(x[::-1],1)],[]);'*input()
print sum(x)

Prints the n^th, 0-indexed, term.

Try it online!

---

Others at 82:

x=[2]
exec'i=1;x=x[::-1];exec"x+=x.pop(0)*[i];i+=1;"*len(x);'*input()
print sum(x)

x=[2]
exec'i=1;exec"x=x.pop()*[i]+x;i+=1;"*len(x);x=x[::-1];'*input()
print sum(x)

x=2,
exec'x=sum([v*(i,)for i,v in enumerate(x[::-1],1)],());'*input()
print sum(x)

Answer 11

JavaScript (ES6), 81 bytes

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

f=(n,a=[2])=>a.map(k=>A=n?[...Array(k).fill(++i),...A]:+A+k,i=A=[])&&n?f(n-1,A):A

Try it online!

Commented

f = (               // f is a recursive function taking:
  n,                //   n = input
  a = [2]           //   a[] = Levine sequence
) =>                //
a.map(k =>          // for each value k in a[]:
  A =               //   compute A, which is either the updated Levine sequence
                    //   or the sum of the terms of the last sequence if this is
                    //   the last iteration:
    n ?             //     if n is not equal to 0:
      [ ...Array(k) //       build an array consisting of k entries
        .fill(++i), //       equal to i (which is first incremented)
        ...A        //       followed by the existing entries in A[]
      ]             //
    :               //     else:
      +A + k,       //       coerce A to a number and add k
  i = A = []        //   start with i = A = []
)                   // end of map()
&& n ?              // if n is not equal to 0:
  f(n - 1, A)       //   do a recursive call with n - 1 and a[] = A[]
:                   // else:
  A                 //   we're done: return A

Answer 12

Haskell, ⁵⁷ 55 bytes

• -2 bytes thanks to kops.

sum<$>iterate(!1)[2]
(x:y)!n=y!(n+1)++(n<$[1..x])
e!_=e

Try it online!

The whole Levine sequence.

Answer 13

APL (Dyalog Unicode), 2̶3̶ 2̶2̶ 21 bytes

-1 thanks to @Razetime
-1 thanks to @User

+/{×⍵:/∘⍳∘⍴⍨⌽∇⍵-1⋄,2}
+/ ⍝ summation
 ×⍵: ⍝ conditional
   /∘⍳∘⍴⍨ ⍝ expand range 0 to length of L(n-1) inclusive
     ⌽∇⍵-1 ⍝ reverse L(n-1)
       ⋄ ⍝ statement separator (effectively an else clause)
         ,2 ⍝ return value

Try it online!

Answer 14

05AB1E, 15 bytes

1‚¸λRεN>yи}˜}εθ

Try it online!

prints the whole sequence forever

1     pushes 1 to the stack
‚     because there is no input, pairs 1 with itself, pushing [1, 1]
¸     listify, pushing [[1,1]]
λ     recursive environment, with [1, 1] as the base case
 R    reverse the implicit last value
 ε    and map each element to
  N>  index + 1
  y   that element
  и   repeated, pushes index + 1 repeated the element
 }
 ˜    flatten, to a flat list
}
ε     and for each such list
θ     take the last element

Answer 15

Factor, 68 bytes

[ { 2 } swap [ reverse [ 1 + <array> ] map-index concat ] times Σ ]

Try it online!

Explanation:

It's a quotation (anonymous function) that takes an integer from the data stack as input and puts an integer (the nth term of the Levine sequence) on the data stack as output. Assuming 4 is on top of the stack when this quotation is called...

• { 2 } Push a sequence to the stack containing one element, 2.

  Stack: 4 { 2 }

• swap Swap two objects (because times needs access to the 4 later).

  Stack: { 2 } 4

• [ reverse [ 1 + <array> ] map-index concat ] Push a quotation for times to use later. This is a quotation that produces the next row of the Levine's Triangle from the previous one.

  Stack: { 2 } 4 [ reverse [ 1 + <array> ] map-index concat ]

• times Call a quotation a certain number of times. Inside the quotation now for the first iteration...

  Stack: { 2 }

• reverse Reverse a sequence.

  Stack: { 2 }

• [ 1 + <array> ] Push a quotation for map-index to use later.

  Stack: { 2 } [ 1 + <array> ]

• map-index Take a sequence and a quotation and apply the quotation to each element of the sequence, collecting the results into a new sequence of the same length. However, it also places the index of the element on top of the stack. Inside the quotation now for the first iteration...

  Stack: 2 0

• 1 Push 1.

  Stack: 2 0 1

• + Add.

  Stack: 2 1

• <array> Create an array from a count and an element.

  Stack: { 1 1 }

• Now map-index has exhausted its elements. Since we are mapping numbers to arrays, the result will be an array of arrays.

  Stack: { { 1 1 } }

• concat Concatenate a sequence of sequences together into one sequence.

  Stack: { 1 1 }

• Now we have produced the second row of Levine's Triangle. times will run the quotation three more times...

  Stack: { 1 1 2 3 }

• Σ Sum a sequence.

  Stack: 7

Answer 16

Python 3, 316 bytes

print(*[11,12,112,1123],sep="\n");n="11|2|3";x=2;t="";j=0
while 1:
 for y,z in enumerate(''.join([str(w)[::-1] for w in n.split("|")[1:][::-1]])):
  t+=str(y+1)*int(z)
  if j==0:t+="|"
  j+=1;k=y+2
 n=t+''.join(map(lambda z:'|'+str(z),list(range(k,k+(len(n)-len(n.lstrip('1')))))))
 print(n.replace("|",""));t="";j=0

Try it online!

In one word, horrible

Answer 17

Charcoal, 29 bytes

⊞υ²ＦＮ«≔⟦⟧θＦＬυＦ§⮌υκ⊞θ⊕κ≔θυ»ＩΣυ

Try it online! Link is to verbose version of code. 0-indexed, I think? Explanation:

⊞υ²

Start with [2].

ＦＮ«

Repeat n times.

≔⟦⟧θ

Start a new list.

ＦＬυ

Iterate up to the length of the previous list.

Ｆ§⮌υκ

Repeat according to the value in the reversed list.

⊞θ⊕κ

Push the next integer to the list.

≔θυ

Copy the new list to the previous list.

»ＩΣυ

Print the final sum.

Answer 18

JavaScript (Node.js), 76 bytes

function that take n and output A[n]

f=(n,a=[2],q=a.length)=>n?f(n-1,a.flatMap(n=>Array(a[--q]).fill(++i),i=0)):q

Try it online!

JavaScript (Node.js), 77 bytes

output all A[i]

for(a=[2];;a=a.flatMap(n=>Array(a[--q]).fill(i++)))i=!console.log(q=a.length)

Try it online!

Answer 19

Pyth, 28 bytes

J[2)W1K_JsK=JYFklK=+J*@Kk[hk

Try it online!

Prints the infinite sequence.

Explanation

J[2)      # Initialize J to [2]
W1        # While 1...
K_J       # Initialize K to reverse of J
sK        # Print the sum of elements of K
=JY       # Y is an empty list by default. Set J to it.
FklK      # For loop from 0 till length of K, with iterator as k
@Kk       # k'th element of K
[hK       # A list containing only k+1
*         # Repeats the sequence specified number of times.
=+J       # Append that to J.

Answer 20

Scala 3, 84 bytes

Seq.iterate(Seq(2),_){s=>s.reverse.zip(1 to s.sum)flatMap(Seq.fill(_)(_))}map(_.sum)

Try it in Scastie!

Outputs the first n items.

Infinite list + nth element, 85 bytes

Stream.iterate(Seq(2)){s=>s.reverse.zip(1 to s.sum)flatMap(Seq.fill(_)(_))}map(_.sum)

Try it in Scastie!

Here is an infinite Stream that also acts as a function giving the nth element, but it's a byte longer.