# 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. – Todd Lehman Apr 26 '15 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. – abligh Apr 26 '15 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? – Claudiu Apr 27 '15 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. – Claudiu May 4 '15 at 22:38
• The SVG is slightly too narrow. – CalculatorFeline Apr 8 '16 at 1:17

# Haskell, 32 bytes, depth 4, A015919 from A011760

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


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. – Claudiu Apr 29 '15 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 Apr 29 '15 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}


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}


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,#}]&


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


# Python, 14 bytes, depth 3, A010872 from A000030

x=lambda x:x%3


0, 1, 2


# 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. – PhiNotPi Apr 26 '15 at 22:22
• Oops, I seem to have forgotten that rule. Thanks for the reminder. – Claudiu Apr 26 '15 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
;
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

• You should change to be from A135020, because the submission for A110654 is wrong. – Peter Taylor Apr 27 '15 at 11:53
• And if your code works, it's surely A075355? – Peter Taylor Apr 27 '15 at 11:55
• @PeterTaylor Yep, I calculate the sequence exactly how it's defined. – PurkkaKoodari Apr 27 '15 at 11:56
• A075352 begins 1, 2, 12, 30, 504, 1320, ... The only one which begins 1,1,2,2,3,3,4,4,5,5,6,6,6 is A075355. – Peter Taylor Apr 27 '15 at 11:57
• @PeterTaylor Whoops, that's what I meant. I apparently screwed up when naming my code file. Edited post. – PurkkaKoodari Apr 27 '15 at 11:58

# Julia, 20 bytes, depth 6, A017910 from A000010

f(n)=ifloor(2^(n/2))


Note the use of ifloor instead of floor to force the conversion to integer. The next answer should start with the terms:

1, 1, 2, 2, 4, 5


# Pyth, 23 bytes, depth 6, A136855 from A136859

#Ig{10456{+Z^Z2Z)~Z1


The next answer should match the following terms:

0, 1, 4, 10, 40, 100


My program prints an infinite stream of numbers, which where n and n^2 only use the digits 01456.

# Mathematica, 57 bytes, depth 5, A145132 from A000292

Series[n/((1-n-n^4)(1-n)^3),{n,0,#}]~SeriesCoefficient~#&


The nth coefficient of the expansion of x/((1-x-x^4)(1-x)^3). The next answer should start with the terms:

0, 1, 4, 10, 20


# Mathematica, 25 bytes, depth 3, A172275 from A000004

Floor[#(Sqrt@13-Sqrt@7)]&


Simply {0, 0, 1, 2, 3, ...}. The next answer should start with the terms:

0, 0, 1


# Pyth, 7 bytes, depth 4, A001317 from A005408

uxGyGQ1


### Explanation

u    Q     reduce to do N times

1, 3, 5, 15
`