Evolution of OEIS

Question

In this challenge, the goal is to recreate the On-Line Encyclopedia of Integer Sequences one sequence at a time. Similar to the Evolution of Hello World, each answer depends on a previous answer.

Over time, this challenge will create a "family tree" of the OEIS sequences. It is simple to add on to this tree.

1. Find a previous answer, which can be at any depth N of the tree.
2. Determine the first N numbers generated by that answer's sequence.
3. Find a sequence in OEIS which starts with those same numbers and which hasn't been used before.
4. Write a program to generate this new sequence you just found.
5. Submit your answer as depth N+1

Since the level of your answer influences scoring, you should always add your answer onto the tree at the deepest level possible. If you cannot fit your answer anywhere on the tree, you can start a new branch of the tree and put your answer as depth 1.

Answer Requirements

There are a few ways to output a sequence.

The first option is to write a program or function that inputs a number (from STDIN or as an argument) and returns the Nth number in your chosen sequence. You can assume that the sequence will be defined for N and that N and S_N are "reasonably sized" (so it won't cause overflows). You can also use any reasonable indexing, such as 0 indexing, 1 indexing, or the indexing listed under "offset" on the sequence's OEIS page, that doesn't matter. The term produced by the first index must match the first term of the OEIS entry.

The second option is to write a program or function that inputs a number and returns the first N terms of the sequence. The first terms of the output must be the first terms of the OEIS entry (you can't leave off the first few terms). Consecutive terms must be delimited by arbitrary strings of non-digit characters, so 0,1 1.2/3,5;8,11 works but 011235811 does not count.

The third option is to create a program that outputs a continuous stream of numbers. Similarly to the second option, there must be delimiters between consecutive terms.

Your answer should contain a header like this to aid Stack Snippet parsing:

 # [language], [number] bytes, depth [number], A[new sequence] from A[old sequence] 

Your answer should contain the code to generate the sequence, along with the first few terms that any descendants will need to contain. These few terms should be preceded by the exact word terms: so that the controller can use them as part of the tree diagram. It is also recommended to write a description of the sequence you chose.

If your post is a depth 1 answer and thus has no ancestor, you should simply omit the from A[number] in your header.

Here is an example answer:

# Perl, 26 bytes, depth 3, A026305 from A084912

    various code here
    and here

The next answer should match the following terms:

    1, 4, 20

This sequence is .... and does ....

Chaining Requirements

In order to make this challenge more fair, there are restrictions on which answers you can chain yours to. These rules are mostly to prevent a single person from creating a whole branch of the tree by themselves or owning a lot of "root" nodes.

• You cannot chain to yourself.
• You cannot directly chain two of your answers to the same ancestor.
• You cannot make more than one "Level 1" answer.

Also, if the ancestor was of depth N, your post must have depth N+1, even if more than the required number of terms agree.

Scoring

Your score as a user is the sum of the scores of all of your answers. The score of a single answer is determined by the following formula:

Answer Score = Sqrt(Depth) * 1024 / (Length + 256)

This scoring system should encourage users to submit a large number of deeper answers. Shorter answers are preferred over longer answers, but depth has a much larger influence.

Below is a stack snippet that generates a leaderboard as well as a tree diagram of all of the answers. I would like to thank Martin Büttner and d3noob as the sources for a lot of this code. You should click "Full screen" to see the complete results.

function answersUrl(t){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+t+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(t){answers.push.apply(answers,t.items),t.has_more?getAnswers():process()}})}function shouldHaveHeading(t){var e=!1,r=t.body_markdown.split("\n");try{e|=/^#/.test(t.body_markdown),e|=["-","="].indexOf(r[1][0])>-1,e&=LANGUAGE_REG.test(t.body_markdown)}catch(a){}return e}function shouldHaveScore(t){var e=!1;try{e|=SIZE_REG.test(t.body_markdown.split("\n")[0])}catch(r){}return e}function getAuthorName(t){return t.owner.display_name}function decodeEntities(t){return $("<textarea>").html(t).text()}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.reverse();var t={},e=[],r=1,a=null,n=1,s=[];answers.forEach(function(t){var r=t.body_markdown.split("\n")[0],a=getAuthorName(t),n=r.match(SEQUENCE_REG)[0];n=n.trim();var o="from A000000";PARENT_REG.test(r)&&(o=r.match(PARENT_REG)[0]),o=o.substring(5).trim(),"A000000"==o&&(o="OEIS");var i="";SEQDATA_REG.test(t.body_markdown)&&(i=t.body_markdown.match(SEQDATA_REG)[1]);for(var u=!0,c=0;c<e.length;++c)u=u&&!(e[c]===n);for(var l=!0,c=0;c<e.length;++c)l=!(!l||e[c]===n||e[c]===n+a||e[c]===o+a);e.push(n),e.push(n+a),e.push(o+a),u&&data.push({name:n,parent:o,term:i+" : ",author:decodeEntities(a),URL:t.share_link}),l&&s.push(t)}),answers.sort(function(t,e){var r=t.body_markdown.split("\n")[0].match(SEQUENCE_REG),a=e.body_markdown.split("\n")[0].match(SEQUENCE_REG);return a>r?-1:r>a?1:void 0}),answers.forEach(function(e){var o=e.body_markdown.split("\n")[0],i=(o.match(NUMBER_REG)[0],(o.match(SIZE_REG)||[0])[0]),u=parseInt((o.match(DEPTH_REG)||[0])[0]).toString(),c=o.match(SEQUENCE_REG)[0],l="from A000000";PARENT_REG.test(o)&&(l=o.match(PARENT_REG)[0]),l=l.substring(5);var d=o.match(LANGUAGE_REG)[1];d.indexOf("]")>0&&(d=d.substring(1,d.indexOf("]")));for(var p=getAuthorName(e),E=!1,h=0;h<s.length;++h)E=E||s[h]===e;if(E){var f=jQuery("#answer-template").html();i!=a&&(n=r),a=i,++r;var m=1024*Math.pow(parseInt(u),.5)/(parseInt(i)+256);f=f.replace("{{SEQUENCE}}",c).replace("{{SEQUENCE}}",c).replace("{{NAME}}",p).replace("{{LANGUAGE}}",d).replace("{{SIZE}}",i).replace("{{DEPTH}}",u).replace("{{LINK}}",e.share_link),f=jQuery(f),jQuery("#answers").append(f),t[p]=t[p]||{lang:d,user:p,size:"0",numanswers:"0",link:e.share_link},t[p].size=(parseFloat(t[p].size)+m).toString(),t[p].numanswers=(parseInt(t[p].numanswers)+1).toString()}});var o=[];for(var i in t)t.hasOwnProperty(i)&&o.push(t[i]);o.sort(function(t,e){return parseFloat(t.size)>parseFloat(e.size)?-1:parseFloat(t.size)<parseFloat(e.size)?1:0});for(var u=0;u<o.length;++u){var c=jQuery("#language-template").html(),i=o[u];c=c.replace("{{RANK}}",u+1+".").replace("{{NAME}}",i.user).replace("{{NUMANSWERS}}",i.numanswers).replace("{{SIZE}}",i.size),c=jQuery(c),jQuery("#languages").append(c)}createTree()}function createTree(){function t(){var t=i.nodes(root).reverse(),e=i.links(t);t.forEach(function(t){t.y=180*t.depth});var r=c.selectAll("g.node").data(t,function(t){return t.id||(t.id=++o)}),a=r.enter().append("g").attr("class","node").attr("transform",function(t){return"translate("+t.y+","+t.x+")"});a.append("a").attr("xlink:href",function(t){return t.URL}).append("circle").attr("r",10).style("fill","#fff"),a.append("text").attr("x",function(){return 0}).attr("y",function(){return 20}).attr("dy",".35em").attr("text-anchor",function(){return"middle"}).text(function(t){return t.term+t.name}).style("fill-opacity",1),a.append("text").attr("x",function(){return 0}).attr("y",function(){return 35}).attr("dy",".35em").attr("text-anchor",function(){return"middle"}).text(function(t){return t.author}).style("fill-opacity",1);var n=c.selectAll("path.link").data(e,function(t){return t.target.id});n.enter().insert("path","g").attr("class","link").attr("d",u)}var e=data.reduce(function(t,e){return t[e.name]=e,t},{}),r=[];data.forEach(function(t){var a=e[t.parent];a?(a.children||(a.children=[])).push(t):r.push(t)});var a={top:20,right:120,bottom:20,left:120},n=3203-a.right-a.left,s=4003-a.top-a.bottom,o=0,i=d3.layout.tree().size([s,n]),u=d3.svg.diagonal().projection(function(t){return[t.y,t.x]}),c=d3.select("body").append("svg").attr("width",n+a.right+a.left).attr("height",s+a.top+a.bottom).append("g").attr("transform","translate("+a.left+","+a.top+")");root=r[0],t(root)}var QUESTION_ID=49223,ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",data=[{name:"OEIS",parent:"null",term:"",author:"",URL:"https://oeis.org/"}],answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*,)/,DEPTH_REG=/\d+, A/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/,SEQUENCE_REG=/A\d+/,PARENT_REG=/from\s*A\d+/,SEQDATA_REG=/terms:\s*(?:(?:-)?\d+,\s*)*((?:-)?\d+)/;

body{text-align: left !important}#answer-list{padding: 10px; width: 550px; float: left;}#language-list{padding: 10px; width: 290px; float: left;}table thead{font-weight: bold;}table td{padding: 5px;}.node circle{fill: #fff; stroke: steelblue; stroke-width: 3px;}.node text{font: 12px sans-serif;}.link{fill: none; stroke: #ccc; stroke-width: 2px;}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script src="http://d3js.org/d3.v3.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answer-list"> <h2>Sequence List</h2> <table class="answer-list"> <thead> <tr> <td>Sequence</td><td>Author</td><td>Language</td><td>Size</td><td>Depth</td></tr></thead> <tbody id="answers"></tbody> </table></div><div id="language-list"> <h2>Leaderboard</h2> <table class="language-list"> <thead> <tr> <td>Rank</td><td>User</td><td>Answers</td><td>Score</td></tr></thead> <tbody id="languages"></tbody> </table></div><table style="display: none"> <tbody id="answer-template"> <tr> <td><a href="https://oeis.org/{{SEQUENCE}}">{{SEQUENCE}}</a></td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td>{{DEPTH}}</td><td><a href="{{LINK}}">Link</a> </td></tr></tbody></table><table style="display: none"> <tbody id="language-template"> <tr> <td>{{RANK}}</td><td>{{NAME}}</td><td>{{NUMANSWERS}}</td><td>{{SIZE}}</td></tr></tbody></table>

Answer 1

Haskell, 32 bytes, depth 4, A015919 from A011760

filter(\n->mod(2^n-2)n==0)[1..]

The next sequence should start with the following terms:

1, 2, 3, 5

It outputs an infinite list:

[1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,...

It looks like it's just the sequence of 1 together with the prime numbers. In fact, the first composite number in the sequence is 341, and the first composite even number is 161038.

Answer 2

R, 79 bytes, depth 3, A000945 from A000043

f=function(n)if(n-1){m=prod(sapply(1:(n-1),f))+1;p=2;while(m%%p)p=p+1;p}else{2}

The next sequence should contain the following terms:

2, 3, 7

The sequence is such that a(n+1) is the smallest prime factor of prod(a(k) for k in 1:n)+1. f=function(n)if(n-1){m=prod(sapply(1:(n-1),f))+1;p=(2:m)[!m%%2:m];p[1]}else{2} would be one character shorter but can't perform f(9) because it can't create of vector of length 38 709 183 810 570.

Answer 3

Piet, 96 bytes, depth 5, A209229 from A010060

with size 10 codels for legibility. Tested on PietDev. The next sequence should start with the terms:

0, 1, 1, 0, 1

This is the characteristic function of powers of 2 (i. e. it outputs 1 if n is a power of 2 and 0 if not). It starts on the red codel in the first row: it takes input as stdin and pushes it to the stack n, it then duplicates it twice n n nand pushes 1 to the stack n n n 1 [the loop starts on the red codel at the end of the second row] that it also duplicates twice n n n 1 1 1 it then rolls the first one near the bottom n 1 n n 1 1 and again n 1 1 n n 1 then check if the first two are equal (if yes than it is a power of 2 so it change direction and outputs 1), then check if the first number of the stack (on first iteration, 1) is smaller than the second. If yes it stops and output 0 and if no it continues on the loop (at that point the stack only contains n 1 as the first two pairs of n 1 were used for the comparisons). It pushes 2 on the stack and multiply n 1 2->n 2 then rolls it at the bottom, 2 n, duplicates twice 2 n n n rolls the bottom number on top of the stack n n n 2 and reaches back the beginning of the loop.

Answer 4

Java, 186 bytes, depth 10, A073719 from A072490

int f(int n){return g(1<<n,0)/g(1<<n,1);}int g(int n,int o){int k=2,c=1;while(c<n)if(h(++k)>0&&o<1||h(k)<1&&o>0)c++;return k;}int h(int n){for(int k=2;k<n;)if(n%k++<1)return 0;return 1;}

Long version:

int f(int n) {
    return g(1<<n,0) / g(1<<n,1);
}

int g(int n, int o) {
    int k=2, c=1;
    while(c<n)
        if (h(++k)>0 && o<1 || h(k)<1 && o>0)
            c++;
    return k;
}

int h(int n) {
    for (int k=2; k<n;)
        if (n % k++ < 1)
            return 0;
    return 1;
}

This is the sequence of the 2ⁿth prime numbers divided by the 2ⁿth composite numbers for all natural numbers greater than 1, rounded down. Method g finds the 2ⁿth prime or composite number while method h checks if numbers are prime or composite. Due to the inefficiency of the algorithm, lag becomes apparent at n = 12.

This is a one-indexed function (n starts at 1). The next answer should start with the following terms:

0, 0, 1, 2, 2, 3, 4, 5, 5, 6

Answer 5

Java, 29 bytes, depth 5, A000325 from A000108

int f(int n){return(1<<n)-n;}

This sequence is 2ⁿ-n for all n >= 0. This is a zero-indexed function. The next answer should start with the following terms:

1, 1, 2, 5, 12

Answer 6

Java, 30 bytes, depth 6, A016116 from A000010

int f(int n){return 1<<(n/2);}

This sequence is the powers of two, twice. This is a zero-indexed function. The next answer should match the following terms:

1, 1, 2, 2, 4, 4

Answer 7

Ruby, 75 bytes, depth 2, A125710 from A000211

def r n;n==2??0:n%2==0??0+r(n/2):?1+r(n*3+1);end;p (r 2*gets.to_i+1).to_i 2

The next sequence should contain the following terms:

4, 80

This is a complicated sequence so I will just quote OEIS:

In the "3x+1" problem, let 0 denote a halving step and 1 denote an x->3x+1 step. Then a(n) is obtained by writing the sequence of steps needed to reach 1 from 2n+1 and reading it as a decimal number.

My code is not short; but It was fun to make.

Answer 8

Ruby, 35 bytes, depth 6, A008998 from A014137

a=->n{n<0?0:n>0?2*a(n-1)+a(n-3):1}

The next sequence should contain the following terms:

1, 2, 4, 9, 20, 44

Defined recursively as:a(n) = 2*a(n-1) + a(n-3).

Answer 9

Ruby, 26 bytes, depth 4, A006882 from A000142

a=->n{n>1?n*a.call(n-2):1}

The next answer should start with the terms:

1,1,2,3

The Double factorial sequence.

Answer 10

Ruby, 30 bytes, depth 6, A010051 from A209229

->n{(2..n).one?{|x|n%x<1}?1:0}

The next answer should start with the terms:

0,1,1,0,1,0

Answer 11

Mathematica, 51 bytes, depth 11, A025765 from A226190

SeriesCoefficient[1/((1-x)(1-x^2)(1-x^9)),{x,0,#}]&

Just another infinite series. The next answer should start with the terms:

1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7

Answer 12

Python, 14 bytes, depth 3, A010872 from A000030

x=lambda x:x%3

The next sequence should start with the following terms:

0, 1, 2

Answer 13

Haskell, 32 bytes, depth 7, A018819 from A016116

l=1:zipWith(+)l(tail$l>>=(:[0]))

This defines an infinite list containing all the values.

As more easily readable function that (could be golfed some more and) is much less efficient the sequence can be defined by

a 0=1; a m|odd m=a(m-1); a m=a(m-1)+a(m`div`2)

So it starts with 1, and then we always take the previous value and, in the even case, add the value from m/2. The list definition uses l>>=(:[0]) to create a list that alternates between values from l and zeroes ([l0,0,l1,0,l2,0,...]) to achieve the same effect.

The sequence is the binary partition function, giving the number of partitions of a number into powers of 2, for example for 5 it is 4, because 5 can be written in four ways: as 1+1+1+1+1, 1+1+1+2, 1+2+2 and 1+4.

The next sequence should match the following terms:

1, 1, 2, 2, 4, 4, 6

Answer 14

Vyxal, 5 bytes, depth 5, A000041 from A006882

[ṄL|1

Try it Online!

Calculates A000041(n). Could have been 2 bytes, but it wouldn't have worked correctly for an input of 0. The sequence is the number of integer partitions of n.

[ṄL|1 # Takes an integer input
[     # If input is not 0...
 Ṅ    # Integer partitions of n
  L   # And take the length
   |  # Otherwise...
    1 # Push 1
      # After which the top of the stack is printed

The next answer should match the following terms:

1, 1, 2, 3, 5

Answer 15

Vyxal, 6 bytes, depth 6, A002379 from A000041

3$e$Eḭ

Try it Online!

The next answer should match the following terms:

1, 1, 2, 3, 5, 7

Answer 16

Vyxal, 9 bytes, depth 5, A027383 from A000123

→ʀƛ←ε∵E;∑

Try it Online!

The next answer should match the following terms:

1, 2, 4, 6, 10

Answer 17

Vyxal, 4 bytes, depth 8, A079584 from A01881

¡b1O

Try it Online!

The next sequence should match the following terms:

1, 1, 2, 2, 4, 4, 6, 6

Answer 18

Mathematica, 6 bytes, depth 1, A002522

#^2+1&

The next answer should start with the terms:

1

Answer 19

Mathematica, 4 bytes, depth 2, A000244 from A000012

3^#&

Powers of 3. The next answer should start with the terms:

1, 3

Answer 20

Mathematica, 3 bytes, depth 2, A005843 from A001477

2#&

Even numbers. The next answer should start with the terms:

0, 2

Answer 21

CJam, 21 bytes, depth 7, A095884 from A025581

1{_),(;{_@_@-@#p}/)}h

The next answer should start with the terms:

0, 1, 0, 2, 1, 0, 3

My second CJam program! I wonder if there's a better way to get n (n-k)^k from n k than _@_@-@# - any tips?

This sequence is simply "Triangle read by rows: T(n,k) = (n-k)^k, n>=1, 1<=k<=n.".

Answer 22

CJam, 5 bytes, depth 5, A179081 from A001590

r1b2%

The next answer should start with the terms:

0, 1, 0, 1, 0

Parity of decimal digit sum.

Answer 23

CJam, 9 bytes, depth 3, A025192 from A000027

3ri(#2*m]

The next answer should start with the terms:

1, 2, 6

2*3^(n-1) with a special case.

For that sequence.

Answer 24

PARI/GP, 19 bytes, depth 4, A056486 from A016957

n->(9*2^n+(-2)^n)/4

It's just (9*2^n+(-2)^n)/4. The old name was "Number of periodic palindromes using a maximum of four different symbols", but I don't know what it means.

The next answer should match the following terms:

4, 10, 16, 40

Answer 25

Octave, 28 bytes, depth 6, A196564 from A179081

@(n)sum(mod(int2str(n)+0,2))

Number of odd digits in decimal representation of n.

The next answer should start with the terms:

0, 1, 0, 1, 0, 1

Answer 26

CJam, 13 bytes, depth 7, A037888 from A196564

ri2b_W%.^:+2/

The next answer should start with the terms:

0, 1, 0, 1, 0, 1, 0

How many bits to change to make a palindrome binary number.

Answer 27

Pyth, 16 bytes, depth 3, A006521 from A000244

@f!%+^2T1Tr1^3QQ

Takes input via STDIN and outputs the Nth number.

Explanation

@              Q   Nth item of
 f                  filter by
  !%+^2T1T           (2^Z + 1) mod Z is 0
          r1^3Q      integers 1..3^(N-1)

The next answer should match the following terms:

1, 3, 9

Answer 28

CJam, 25 bytes, depth 13, A238263 from A135020

ri,(;{2*mF,3<}%_W%.&1b)2/

The next answer should start with the terms:

1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7

Number of ways of n=2^k1*p1^k2+2^k3*p2^k4, starting from n=2.

Answer 29

R, 36 bytes, depth 9, A083912 from A103181

f=function(n)sum(!n%%1:n&1:n%%10==2)

The next sequence should match the following terms:

0, 1, 0, 1, 0, 1, 0, 1, 0

It is the sequence containing the number of divisors of n that are congruent to 2 modulo 10.

Usage:

> f(1)
[1] 0
> f(9)
[1] 0
> sapply(1:40, f)
[1] 0 1 0 1 0 1 0 1 0 1 0 2 0 1 0 1 0 1 0 1 0 2 0 2 0 1 0 1 0 1 0 2 0 1 0 2 0 1 0 1

Answer 30

Pyth, 34 bytes, depth 13, A075355 from A135020

L?*bytbb1VQ~Z1J]ZW<.xJyhN~Z1aJZ;lJ

Explanation

L                  define function y(b): return
  *bytb              b * y(b - 1)
 ?     b            if b is not 0, else
        1            1
VQ                 iterate N over 0..input-1
  ~Z1              increment Z (initialized to 0)
  J]Z               set J to array of Z
  W                 while
    .xJ               product of J
   <                 is less than
       yhN            factorial of N+1
          ~Z1          increment Z
          aJZ          add Z to J
;
lJ                 print length of J

The next answer should match the following terms:

1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6