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

3var, 15 bytes, depth 5, A004523 from A002620

aaama{pOpOipOi}

The next answer should match the following terms:

0, 0, 1, 2, 2

This simply prints a stream of two even numbers followed by an odd, i.e. 0, 0, 1, 2, 2, 3, 4, 4, 5, ...

3var is essentially a much better version of Deadfish that has three variables A, B, R. Here we only use the first two.

i        Increment A
p        Print A as num
a        Increment B
m        Square B
O        Print B as ASCII
{}       Infinite loop

If it wasn't for the fact that we had to separate the numbers in the output, {ppipi} would have been a lot shorter.

Answer 2

Python, 87 bytes, depth 1, A000040

def b(n):
 p,t=[],2
 while n>0:
  if all(t%a for a in p):
   p+=[t];n-=1;yield t
  t+=1

The prime numbers. The next answer should match the following terms:

2

Answer 3

Piet, 56 bytes, depth 4, A000124 from A000079

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

1, 2, 4, 7

This sequence is the "maximal number of pieces formed when slicing a pancake with n cuts" (i. e. sum(1:n) + 1 ). The sequence was so simple so i thought i could increase the difficulty a little by doing it in Piet. I tested it on PietDev.

It pushes 1 on the stack 1, then the number provided with stdin 1 n, duplicate the latter 1 n n [here the loop begins = bright green codel], pushes 1 1 n n 1, substracts it 1 n n-1, duplicates the result twice 1 n n-1 n-1 n-1 (the deeper one will be then one we ll add to n, the second one the one we ll compare to zero and the third one the loop counter), pushes 4 and then 1 1 n n-1 n-1 n-1 4 1 uses the last two to roll the "loop counter" to the bottom 1 n-1 n n-1 n-1, check if n-1 is equal to 0: if no the stack becomes 1 n-1 n n-1 0, which we negates 1 n-1 n n-1 1 and uses the 1 to change the pointer direction 1 n-1 n n-1, adds n-1 to n 1 n-1 (n+n-1) which we roll to the bottom with a 2 and 1 that we just pushed on the stack thus leaving the stack in this state 1 (n+n-1) n-1 when it starts the loop over. When the counter indeed reaches 0, it exits the loop with a stack looking like this 1 0 Sum(1:n) 0, it then pops the first number, adds the rest and outputs as a numeric.

Answer 4

TI-BASIC, 10 bytes, depth 5, A181857 from A001563

Input X
lcm(X²,X!

A181857 represents the least common multiple of the squares and factorials. The code length for TI-BASIC is always confusing, because it uses tokens, so most tokens are fewer bytes than their Unicode byte count. The next sequence should start with the terms:

0, 1, 4, 18, 48

Answer 5

Pyth, 6 bytes, depth 3, A002275 from A000030

&Q*Q\1

The next answer should match the following terms:

0, 1, 11

A002275 is the sequence of repunits. The n-th sequence number is (10^n - 1)/9, which consists of n 1s.

Answer 6

Python, 41 bytes, depth 6, A090017 from A104631

a=lambda n:n if n<2else 4*a(n-1)+2*a(n-2)

This is the lucas sequence U(-4, 2) The next sequence should start with the terms:

0, 1, 4, 18, 80, 356

Answer 7

Mathematica, 25 bytes, depth 6, A181860 from A181857

LCM[#^2,#!/⌊#/2⌋!^2]&

This is an unnamed function which simply computes the definition of the sequence. The next sequence should start with the terms:

0, 1, 4, 18, 48, 150

Answer 8

Clip, 14 bytes, depth 4, A007814 from A000035

([tmlt)%t1]bWn

The count of the terminal zeroes in the binary from of a number. The next answer should start with the terms:

0, 1, 0, 2

Answer 9

Mathematica, 29 bytes, depth 5, A129953 from A000292

a@0=0;a@1=1;a@n_=2^(n-2)(n+2)

The next sequence must start with the following terms:

0, 1, 4, 10, 24

Answer 10

CJam, 20 bytes, depth 7, A218254 from A025581

0p1{_{_p_2b:+-}hp)}h

The next answer should start with the terms:

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

My first CJam program! This is such a far superior language to GolfScript. It is like somebody re-did Golfscript, but properly.

A218254 itself is a cute sequence where you iterate the non-negative integers, and for each one, you print it out, then subtract the popcount (number of 1s in the binary expansion) of it, and iterate 'till you reach zero.

The program loops forever so you will have to run it locally.

Answer 11

CJam, 27 bytes, depth 8, A022336 from A218254

ri_),_ff{5\#Z2$#*[\]}:+$=W=

The next answer should start with the terms:

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

Exponent of 3 of every integer in the form of 3^j5^k.

Answer 12

Pyth, 4 bytes, depth 5, A070939 from A008619

l.BQ

A070939 is the length of n in binary. The approximation Python translation is

print(len(bin(eval(input()))-2))

Try it online here. The next answer should start with the terms:

1,1,2,2,3

Answer 13

Nagato Yuki, 225 bytes, depth 4, A063524 from A000035

…………………「・………。………………… …………。」………。・………………。・………………。…… ………………。・「・………………。… ………………。」

The next answer should start with the terms:

0, 1, 0, 0

Characteristic function of n=1, separated by slashes.

I don't know who invented the Nagato Yuki programming language. But I found an interpreter. I don't know Scala and don't know what's the correct way to run the interpreter. So I just replaced the sample Hello World program with my code, and ran sbt at the root directory, run and selected NagatoApp.

The interpreter seemed to only read one character per line. So I chose the format without input.

Brainfuck translation:

+++++++[->+++++++<]>-.-.++.-[-.+.]

Answer 14

J, 4 bytes, depth 2, A033999 from A000012

_1&^

The next answer should start with the terms:

1, -1

No negative numbers yet?

It is a function that may return the number -1, which is displayed as _1.

Answer 15

CJam, 14 bytes, depth 9, A026233 from A084054

ri,:):mp)f=:+)

The next answer should start with the terms:

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

Return k where the input (>=1) is the kth prime or non-prime.

Answer 16

Racket, 86 bytes, depth 8, A084054 from A000006

#lang racket
(lambda(n)(modulo(string->number(substring(number->string(* 5 n))0 1))5))

The next answer should match the following terms:

1, 1, 2, 2, 3, 3, 4, 4

The sequence is "5n digit-reversed mod 5", which is another way of saying "first digit of 5n, mod 5".

I'm no expert at Racket/Scheme but it appears that first only works on lists, hence the use of substring.

Test like:

#lang racket
(map
    (lambda(n)(modulo(string->number(substring(number->string(* 5 n))0 1))5))
    (range 0 100)
)

Answer 17

CJam, 14 bytes, depth 11, A025766 from A242681

ri),A~%2f/:):+

The next answer should start with the terms:

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

The sequence which has the generating function 1/((1-x)(1-x^2)(1-x^11)).

I'm not sure why it is useful.

Answer 18

GolfScript, 12 bytes, depth 12, A135020 from A025766

~).2/`-1@?%~

The next answer should start with the terms:

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

Each natural number is followed by its reversal. Indexed from 1. Gets interesting at A(20) = 1.

Answer 19

CJam, 17 bytes, depth 5, A000010 from A008619

ri:N,{mfNmf&!},,(

Euler's totient function - count of numbers <= N and relatively prime to N.

The next sequence must start with the terms:

1, 1, 2, 2, 4

Answer 20

Befunge, 7 bytes, depth 4, A002620 from A172275

&:*4/.@

The next answer should match the following terms:

0, 0, 1, 2

Answer 21

A:;, 63 bytes, depth 3, A010052 from A001333

n:j;l:0;b:l;?:j:=:l:2;p:1;k;?:j:<:l:2;p:0;k;a:b:1;l:b;m:l:l;g:3

The next sequence should match the terms:

1, 1, 0

The sequence generated here returns 1 if the input is a square and 0 if not. I wanted to try this language out of curiosity. The algorithm is dead simple so I don't think I made a mistake but if anyone sees one, please tell me!

Answer 22

CJam, 70 bytes, depth 6, A134452 from A179081

{_3%2<{_{_3%\3/T+}{;L}?}{)3/T-1\+}?}:T;{_{_1>{:+TR}{0=}?}{;0}?}:R;riTR

The next answer should start with the terms:

0, 1, 0, 1, 0, -1

This is the digital root of n in balanced ternary.

Balanced ternary is a ternary base system where the digits can be -1, 0, or 1. E.g. 4 is ++ = 3 + 1, 5 is +-- = 9 - 3 - 1, 6 is +-0 = 9 - 3 + 0.

The digital root is the digit you get when you keep adding the digits together. e.g. in base 10:

9685 --> 9 + 6 + 8 + 5 = 28
28   --> 2 + 8 = 10 
10   --> 1 + 0 = 1
1

Thus the digital root in base 10 for 9685 is 1.

T recursively converts a number to balanced ternary. R recursively computes the digital root.

See history for the original Python version. This is a straightforward translation of that. CJam golf tips are welcome! This one has that look like it could be golfed but I am not sure..

Answer 23

Python, 173 bytes, depth 5, A090245 from A014137

from itertools import*
C=combinations
f=lambda n:max(i for i in range(3**n+1)if any(all(any(sum(x)%3for x in zip(*s))for s in C(b,3))for b in C(product(*tee([0,1,2],n)),i)))

Call like f(2). The next answer should match the following terms:

1, 2, 4, 9, 20

This is the maximum number of cards you can have in n-attribute Set such that there is no set amongst the cards you chose.

For those who are unfamiliar with Set, a "set" in the game is a collection of three cards such that, for each attribute (e.g. colour, number, shape, shading) the cards are either all different or all the same. You can check out this paper which gives a very good explanation of the rules in the first two pages, as well as an example of 20 cards for the case n = 4 (i.e. regular Set) on the third page. Then proceed to buy the cards as an excellent timekiller with your nerdy friends.

Since the algorithm is brute force, it only solves up to n = 2 in a reasonable amount of time. Here's an ungolfed version with early exiting which manages to complete n = 3 within a few minutes, and outputs the boards it finds as it goes:

from itertools import *

def f(n):
    cards = list(product([0,1,2], repeat=n))

    for board_size in range(3**n+1):
        for board in combinations(cards, board_size):
            for three_cards in combinations(board, 3):
                if any(sum(attr)%3 != 0 for attr in zip(*three_cards)):
                    continue

                else:
                    break

            else:
                print("Board size {}: {}".format(board_size, board))
                break

        else:
            return

For n = 3 the final output is

Board size 9: ((0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 2), (1, 2, 2), (2, 1, 2))

which can be visualised as

The program makes use of the fact that, when representing an attribute by 0, 1, 2, "all the same or all different" is equivalent to the sum of the three cards' attributes being divisible by 3 (0+0+0 = 1+1+1 = 2+2+2 = 0+1+2 = 0 mod 3).

Answer 24

Mathematica, 11 bytes, depth 15, A086388 from A157271

Round[#/2]&

A086388 is just a duplicate of A008619. However, the question didn't disallow dead sequences, so I assume that this is valid. The next answer should start with the terms:

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

Answer 25

Mathematica, 53 bytes, depth 5, A182712 from A007814

Count[Select[IntegerPartitions@#,!#~MemberQ~1&],2,2]&

A182712 is the set of the total number of 2's in the last section of the partitions of n (the ones that don't contain 1.) The next answer should start with the terms:

0, 1, 0, 2, 1

Answer 26

Mathematica, 58 bytes, depth 6, A106391 from A104631

a=Binomial;Sum[a[#,2k]a[2(#-2k),#-2k+1],{k,0,Floor[#/2]}]&

Will add explanation later. The next answer should start with the terms:

0, 1, 4, 18, 80, 365

Answer 27

Mathematica, 30 bytes, depth 7, A051122 from A025581

a=Fibonacci;a@#~BitAnd~a[#+1]&

A051122(n) = Fib(n) AND Fib(n + 1). The next answer should start with the terms:

0, 1, 0, 2, 1, 0, 8

Answer 28

Mathematica, 8 bytes, depth 4, A003462 from A000290

3^#/2-2&

The next answer should start with the terms:

0, 1, 4, 13

Answer 29

Mathematica, 4 bytes, depth 3, A000079 from A000027

2^#&

The next answer should start with the terms:

1, 2, 4

Answer 30

Mathematica, 20 bytes, depth 2, A006370 from A000211

If[OddQ@#,3#+1,#/2]&

The mapping of n to the next term in its Collatz sequence. The next answer should start with the terms:

4, 1, 10