# Evolution of OEIS

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.

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.

 # [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.

# 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> • You know, I think this is might just be the single coolest codegolf.sx question I've ever seen asked. It's not just cool, but actually useful as an archive. Commented Apr 26, 2015 at 19:08 • Given the OEIS is online, takes N terms of a sequence as a search term, and contains mathematica or maple code for many of the sequences, it would be possible to write a meta-entry which searched for the best scoring entry for which code exists in OEIS which is a descendent of any given entry here and posted it. Commented Apr 26, 2015 at 19:10 • Can I recommend some way of marking on the graph the snippet generates that a node is terminal, ie there are no unused sequences of a greater depth available on the OEIS? Commented Apr 27, 2015 at 5:52 • I think the only way to keep this challenge going would be to provide something where you give your username, and it lists the OEIS problems you could do, in order from highest depth to lowest. Otherwise it takes too long to find the next sequence to post. Commented May 4, 2015 at 22:38 • The SVG is slightly too narrow. Commented Apr 8, 2016 at 1:17 ## 153 Answers # 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. # 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. # 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. # 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 2nth prime numbers divided by the 2nth composite numbers for all natural numbers greater than 1, rounded down. Method g finds the 2nth 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  • Oh that's what prime(2^n) meant... really had trouble figuring that out for some reason. Commented Apr 29, 2015 at 2:40 • I was also confused by that at first. What really hung me up was the formula for composite numbers; the denominator of the first one made no sense. :P – TNT Commented Apr 29, 2015 at 3:13 # Java, 29 bytes, depth 5, A000325 from A000108 int f(int n){return(1<<n)-n;}  This sequence is 2n-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  # 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  # 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. # 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). # 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. # 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  # 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  # 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  # Haskell, 32 bytes, depth 7, A018819 from A016116 l=1:zipWith(+)l(taill>>=(:[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(mdiv2)


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


# 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


# 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


# 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


# 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


# Mathematica, 6 bytes, depth 1, A002522

#^2+1&


1


# Mathematica, 4 bytes, depth 2, A000244 from A000012

3^#&


1, 3


# Mathematica, 3 bytes, depth 2, A005843 from A001477

2#&


0, 2


# CJam, 21 bytes, depth 7, A095884 from A025581

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


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.".

• Since this violates the chaining requirement of "You cannot directly chain two of your answers to the same ancestor" this answer does not count towards your score, although it will still appear on the diagram. Commented Apr 26, 2015 at 22:22
• Oops, I seem to have forgotten that rule. Thanks for the reminder. Commented Apr 26, 2015 at 22:59

# CJam, 5 bytes, depth 5, A179081 from A001590

r1b2%


0, 1, 0, 1, 0


Parity of decimal digit sum.

# CJam, 9 bytes, depth 3, A025192 from A000027

3ri(#2*m]


1, 2, 6


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

For that sequence.

# 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


# Octave, 28 bytes, depth 6, A196564 from A179081

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


Number of odd digits in decimal representation of n.

0, 1, 0, 1, 0, 1


# CJam, 13 bytes, depth 7, A037888 from A196564

ri2b_W%.^:+2/


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


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

# 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


# CJam, 25 bytes, depth 13, A238263 from A135020

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


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.

# 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


# 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

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