One OEIS after another

Question

As of 13/03/2018 16:45 UTC, the winner is answer #345, by Khuldraeseth na'Barya. This means the contest is officially over, but feel free to continue posting answers, just so long as they follow the rules.

As well, just a quick shout out to the top three answerers in terms of numbers of answers:

1. NieDzejkob - 41 answers

2. KSmarts - 30 answers

3. Hyper Neutrino - 26 answers

---

This is an answer chaining question that uses sequences from OEIS, and the length of the previous submission.

This answer chaining question will work in the following way:

• I will post the first answer. All other solutions must stem from that.
• The next user (let's call them userA) will find the OEIS sequence in which its index number (see below) is the same as the length of my code.
• Using the sequence, they must then code, in an unused language, a program that takes an integer as input, n, and outputs the nth number in that sequence.
• Next, they post their solution after mine, and a new user (userB) must repeat the same thing.

The nth term of a sequence is the term n times after the first, working with the first value being the first value given on its OEIS page. In this question, we will use 0-indexing for these sequences. For example, with A000242 and n = 3, the correct result would be 25.

However!

This is not a code-golf, so shortest code doesn't matter. But the length of your code does still have an impact. To prevent the duplication of sequences, your bytecount must be unique. This means that no other program submitted here can be the same length in bytes as yours.

If there isn't a sequence for then length of the last post, then the sequence for your post is the lowest unused sequence. This means that the sequences used also have to be unique, and that the sequence cannot be the same as your bytecount.

After an answer has been posted and no new answers have been posted for more than a week, the answer before the last posted (the one who didn't break the chain) will win.

Input and Output

Generic input and output rules apply. Input must be an integer or a string representation of an integer and output must be the correct value in the sequence.

Formatting

As with most answer-chaining questions, please format your answer like this

# N. language, length, [sequence](link)

`code`

[next sequence](link)

*anything else*

Rules

• You must wait for at least 1 hour before posting an answer, after having posted.
• You may not post twice (or more) in a row.
• The index number of a sequence is the number after the A part, and with leading zeros removed (e.g. for A000040 the index number is 40)
• You can assume that neither the input nor the required output will be outside your languages numerical range, but please don't abuse this by choosing a language that can only use the number 1, for example.
• If the length of your submission is greater than 65536 characters long, please provide a link to a way to access the code (pastebin for example).
• n will never be larger than 1000, or be out of bounds for the sequence, simply to prevent accuracy discrepancies from stopping a language from competing.
• Every 150 (valid) answers, the number of times a language may be used increases. So after 150 solutions have been posted, every language may be used twice (with all previous answers counting towards this). For instance, when 150 answers have been posted, Python 3 may be used twice, but due to the fact that it has already been used once, this means it can only be used once more until 300 answers have been posted.
• Please be helpful and post a link to the next sequence to be used. This isn't required, but is a recommendation.
• Different versions of languages, e.g. Python 2 and Python 3 are different languages. As a general rule, if the different versions are both available on Try It Online, they are different languages, but keep in mind that this is a general rule and not a rigid answer.
• It is not banned, but please try not to copy the code from the OEIS page, and actually try to solve it.
• Hardcoding is only allowed if the sequence is finite. Please note that the answer that prompted this (#40) is the exception to the rule. A few answers early in the chain hardcode, but these can be ignored, as there is no good in deleting the chain up to, say, #100.

Answer chain snippet

var QUESTION_ID=133754,OVERRIDE_USER=66833;function shareUrl(i){return"https://codegolf.stackexchange.com/a/"+i}function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getTemplate(s){return jQuery(jQuery("#answer-template").html().replace("{{PLACE}}",s.index+".").replace("{{NAME}}",s.user).replace("{{LANGUAGE}}",s.language).replace("{{SEQUENCE}}",s.sequence).replace("{{SIZE}}",s.size).replace("{{LINK}}",s.link))}function search(l,q){m=jQuery("<tbody id='answers'></tbody>");e.forEach(function(s){if(!q||(l==0&&RegExp('^'+q,'i').exec(s.lang_name))||(l==1&&q===''+s.size)){m.append(jQuery(getTemplate(s)))}});jQuery("#answers").remove();jQuery(".answer-list").append(m)}function sortby(ix){t=document.querySelector('#answers');_els=t.querySelectorAll('tr');els=[];for(var i=0;i<_els.length;i++){els.push(_els[i]);}els.sortBy(function(a){a=a.cells[ix].innerText;return ix==0||ix==4?Number(a):a.toLowerCase()});for(var i=0;i<els.length;i++)t.appendChild(els[i]);}function checkSize(x){if(!x)return jQuery("#size-used").text("");var i=b.indexOf(+x);if(i<0)return jQuery("#size-used").text("Available!");var low=+x,high=+x;while(~b.indexOf(low))low--;while(~b.indexOf(high))high++;jQuery("#size-used").text(("Not available. The nearest are "+low+" and "+high).replace("are 0 and","is"))}function checkLang(x){}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.answer_id;answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return (e.owner.user_id==OVERRIDE_USER?"<span id='question-author'>"+e.owner.display_name+"</span>":e.owner.display_name)}function process(){b=[];c=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);if(a){e.push({user:getAuthorName(s),size:+a[4],language:a[2],lang_name:a[3],index:+a[1],sequence:a[5],link:shareUrl(s.answer_id)});if(b.indexOf(+a[4])>=0&&c.indexOf(+a[4])<0){c.push(+a[4])};b.push(+a[4])}else{jQuery('#weird-answers').append('<a href="'+shareUrl(s.answer_id)+'">This answer</a> is not formatted correctly. <b>Do not trust the information provided by this snippet until this message disappears.</b><br />')}}),e.sortBy(function(e){return e.index});e.forEach(function(e){jQuery("#answers").append(getTemplate(e))});var q="A"+("000000"+e.slice(-1)[0].size).slice(-6);jQuery("#next").html("<a href='http://oeis.org/"+q+"'>"+q+"</a>");c.forEach(function(n){jQuery('#weird-answers').append('The bytecount '+n+' was used more than once!<br />')})}Array.prototype.sortBy=function(f){return this.sort(function(a,b){if(f)a=f(a),b=f(b);return(a>b)-(a<b)})};var ANSWER_FILTER="!*RB.h_b*K(IAWbmRBLe",COMMENT_FILTER="!owfmI7e3fd9oB",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page,e=[];getAnswers();var SCORE_REG=/<h\d>\s*(\d+)\.\s*((?:<a [^>]+>\s*)?((?:[^\n,](?!<\/a>))*[^\s,])(?:<\/a>)?),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*, ((?:<a[^>]+>\s*)?A\d+(?:\s*<\/a>)?)\s*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important;font-family:Roboto,sans-serif}#answer-list,#language-list{padding:10px;/*width:290px*/;float:left;display:flex;flex-wrap:wrap;list-style:none;}table thead{font-weight:700}table td{padding:5px}ul{margin:0px}#board{display:flex;flex-direction:column;}#language-list li{padding:2px 5px;}#langs-tit{margin-bottom:5px}#byte-counts{display:block;margin-left:15px;}#question-author{color:purple;text-shadow: 0 0 15px rgba(128,0,128,0.1);}#label-info{font-weight: normal;font-size: 14px;font-style: italic;color: dimgray;padding-left: 10px;vertical-align: middle; }

<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/codegolf/all.css?v=83c949450c8b"><p id="weird-answers"></p><p>Currently waiting on <span id="next"></span></p><span>Search by Byte Count: <input id="search" type="number" min=1 oninput="checkSize(this.value);search(1,this.value)" onclick="document.getElementById('search2').value='';!this.value&&search(0,'')"/> <span id="size-used"></span></span><br><span>Search by Language: <input id="search2" oninput="checkLang(this.value);search(0,this.value)" onclick="document.getElementById('search').value='';!this.value&&search(0,'')"/> <span id="language-used"></span></span><h2>Answer chain <span id="label-info">click a label to sort by column</span></h2><table class="answer-list"><thead><tr><td  onclick="sortby(0)">#</td><td onclick="sortby(1)">Author</td><td onclick="sortby(2)">Language</td><td onclick="sortby(3)">Sequence</td><td onclick="sortby(4)">Size</td></tr></thead><tbody id="answers"></tbody></table><table style="display: none"><tbody id="answer-template"><tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SEQUENCE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table><table style="display: none"><tbody id="language-template"><tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SEQUENCE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table>

Answer 1

76. Pygmy, 4147 bytes, A000036

globaln: 0                                                                                           

Pi:: 3.141592653589793                                                                               

floor:: (number) {                                                                                   
    floatPart: number % 1                                                                            
    number >= 0 =>                                                                                   
    number - floatPart                                                                               
    number - floatPart - 1                                                                           
}                                                                                                    

fsqrt:: (number) {                                                                                   
    floor| number ^ 0.5                                                                              
}                                                                                                    

summation:: (f i imax) {                                                                             
    i > imax => 0                                                                                    
    (f| i) + summation| f, i + 1, imax                                                               
}                                                                                                    

absoluteValue:: (number) {                                                                           
    number < 0 => -number                                                                            
    number                                                                                           
}                                                                                                    

A:: (number) {                                                                                       
    globaln~: number                                                                                 
    1 + 4 * (fsqrt| number)                                                                          
       + 4 * (fsqrt| number / 2) ^ 2                                                                 
       + 8 * summation| (j){ fsqrt| globaln - j * j }, (fsqrt| number / 2) + 1, (fsqrt| number)      
}                                                                                                    

V:: (number) {                                                                  
    Pi * number                                                                      
}                                                                                    

P:: (number) {                                             
    (A| number) - (V| number)                               
}                                                           

recordMax: 0                                           
findRecord:: (searchIndex record recordCount) {                                    
    x: absoluteValue| P| searchIndex                                               
    (x > record && recordCount = recordMax - 1) => searchIndex                     
    x > record => findRecord| searchIndex + 1, x, recordCount + 1                  
    findRecord| searchIndex + 1, record, recordCount                               
}                                                                                  

A000099:: (number) {                                                                 
    recordMax~: number                                                              
    findRecord| 1, 0, 0                                                              
}                                                                               

A000035:: (number) {                                                                       
    floor| (P| (A000099| number)) + 0.5                                         
}                                                                               

Next Sequence

You can run the code on this page. For example, you can get the 10th number in the sequence by copying the code above and adding:

alert| A000035| 10

Answer 2

191. Haskell, 1824 bytes, A000725

import Data.List (sort, group, permutations)
import Control.Monad (replicateM)
import qualified Data.Set as S
import qualified Data.Map.Strict as M

type V = [Bool]

parts :: Int -> [[Int]]
parts n = partsm n n
  where partsm 0 _ = [[]]
        partsm n m = [ v:p | v <- [1 .. min n m], p <- partsm (n-v) v ]

fact :: Int -> Integer
fact n = product [1 .. fromIntegral n]

centralizerSize :: [Int] -> Integer
centralizerSize cyclens =
  product [ l^m * fact m | ll <- group (sort cyclens),
                           let l = fromIntegral $ head ll,
                           let m = length ll             ]

ccSize :: [Int] -> Integer
ccSize cyclens = fact (sum cyclens) `div` centralizerSize cyclens

repr :: [Int] -> [Int]
repr cyclens = reprh cyclens 0
  where reprh []     _ = []
        reprh (l:ls) m = [m+1 .. m+l-1] ++ [m] ++ reprh ls (m+l)

act_it :: [Int] -> V -> V
act_it p v = [ v!!i | i <- p ]

act_ot :: V -> [Int] -> V -> V
act_ot neg p = zipWith (/=) neg . act_it p

orbit :: ( V -> V ) -> V -> [V]
orbit act x = x : takeWhile (x /=) (iterate act (act x))

orbitLengths :: S.Set V -> ( V -> V ) -> [Int]
orbitLengths o act = sort $ orblens o act
  where orblens o act
          | S.null o  = []
          | otherwise = let orb = orbit act (S.findMin o)
                        in length orb :
                           orblens (S.difference o (S.fromList orb)) act

oeis725 :: Int -> Integer
oeis725 n =
  let v = replicateM n [False,True]
      o = S.fromList v
      m = M.fromListWith (+)
          [ (pcls, centralizerSize pcls * ccSize cls) |
            cls <- parts n,
            let pcls = orbitLengths o (act_it $ repr cls) ]
  in sum [ M.findWithDefault 0 (orbitLengths o (act_ot neg p)) m |
           p <- permutations [0..n-1], neg <- v ]
     `div` ( (fact n)^2 * 2^n )

f n = oeis725 (n+1)

Next sequence

Try it online!

The math behind it

Let V be the set of the 2^n boolean vectors of length n (which is also a group under component-wise xor), and P be the group with the (2^n)! permutations of V. Let S be the symmetric group on n points of size n!. S acts on V by permuting the components, thus embedding S in P. Let IT (for input transformations) be this subgroup of P. For the output transformations OT < P, we combine the action of S and the xor-ing action of V on itself. (Abstractly, it is a semidirect product of V and S. It's order is n!*2^n)

Now let the direct product OT*IT act on P by p(ot,it)=ot^-1*p*it (ot is inverted for formal reasons that are not important here). We want to know how many orbits this action has. To use Burnside's lemma, we need to know how many elements of P are fixed under the action of a particular (ot,it), that is, how many satisfy ot^-1*p*it=p, which is equivalent to p*it*p^-1=ot. So there are only solutions if it and ot are conjugate in P, which means they need to have the same cycle lengths. Then, the number of solutions is the size of the centralizer of it (or ot) in P, which can be computed from the cycle lengths.

Instead of running over all elements of OT*IT and summing the corresponding number of fixed elements, we can run only over OT and sum the product of the number of conjugate elements in IT and the centralizer size. These products can be precomputed for each conjugacy class of IT represented by the cycle lengths.

In GAP I would only run over the conjugacy classes of OT, but here I'm too lazy. This program is already good enough to compute more values than OEIS has.

Answer 3

229. FMSLogo, 1147 bytes, A000361

Number of byte: 1132 (code) + 15 (flags) = 1147. Avoid confusing the code snippet.

Need parameter -h 8200 -w 8200 to enlarge the canvas size.

to size ; Constant. Must be power of 2
    op 4096
end

to draw :halfedge :maincol :altcol
    if :halfedge < 4 [stop] ; all fractals need base case
    draw :halfedge / 2 :maincol :altcol
    fd :halfedge rt 60
    fd :halfedge rt 60
    draw :halfedge / 2 :altcol :maincol
    rt 60
    drawtria :halfedge :maincol
    rt 60
    draw :halfedge / 2 :altcol :maincol
    fd :halfedge rt 120 bk :halfedge
end

to drawtria :edge :col
    if :edge <> 4 [stop]
    setpc :col
    pd
    repeat 3 [fd :edge rt 120]
    pu
    rt 30 fd :edge/2
    setfc :col
    fill
    bk :edge/2 lt 30
end

to main :index
    make "index :index + 1 ; Must be 0-based
    pu home ht
    bk size rt 90 bk size lt 60
    if not namep "drawn [
        draw size "purple "gray
        make "drawn "
    ]
    fd 8 * :index
    rt 150
    fd 4 * (sqrt 3) / 2 * (4 / 3) ; Go to the centroid of the next triangle
    localmake "result 0
    while [ycor > -size - 10] [
        if pixel = [128 0 128] [make "result :result * 2 + 1] ; purple
        if pixel = [128 128 128] [make "result :result * 2] ; gray
        fd 8 * (sqrt 3) / 2
    ]
    op :result
end

Testing:

print main 10

Unfortunately, no implementation of the Logo programming language I can find include the function pixel (used to retrieve pixels on the screen), and FMSLogo appear to be limited to Windows. However JSLogo can draw the fractal.

However, this code is likely to take forever to run on FMSLogo. For testing purposes:

• Change the 4096 in size procedure to 128.
• Don't pass that parameter, it is unnecessary in case of size = 128.
• For JSLogo, type to setfc :col end
• Remove the line if :edge <> 4 [stop] so that all triangles are drawn, and not just size-4 ones.

Explanation:

1. What is that sequence: See this image for details. Basically the sequence is binary representation of the columns of congruent triangles. Also the pattern is defined like this (drawn lines indicates symmetry axes of the triangles).
2. Why is Logo useful here: Because Logo has built-in turtle graphics. So draw the fractal at smaller size and rotated is not problem for Logo. After drawing, you just need to read the pixels.

Next Sequence

Answer 4

232. Funky, 326 330 332 bytes, A000938

function gcd (a, b) {
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    };
    return a;
}

function A000938 (n) {
    n = n + 2;
    ans = 0;
    for (m = 2; m <= n; ++m) {
        for (k = 2; k <= n; ++k) {
            ans = ans + (((n - k) + 1) * ((n - m) + 1) * gcd(k - 1, m - 1));
        }
    }
    ans = (2 * ans) - (
        (n*n) *
        ((n*n)-1) / 6
    );
    return ans;
}

Try it online!

Polyglot with Javascript. Try it online!

Next sequence.

---

Use the formula on the OEIS page for O(n^2 log n) complexity, instead of the naive O(n^6).

Quick explanation:

• This code use the formula a[n_] := 2*Sum[(n - k + 1)*(n - m + 1)*GCD[k - 1, m - 1], {m, 2, n}, {k, 2, n}] - n^2*((n^2 - 1)/6) described in the Mathematica code section.

• Formula proof:

  • The formula is equivalent to this.

  • Let the size of the bounding box of three points be m * k. Consider 2 cases:

    • k != 0 and m != 0: There are 2 ways to choose the orientation of the three points (\ or /), gcd(k-1, m-1)-1 ways to choose the point lies between the other 2 points, and (n - k) × (n - m) ways to choose the position of the bounding box.
    • k == 0 or m == 0: There are 2 ways to choose the orientation (| or -), n ways to choose the row/column the points lies on, and Binomial[n, 3] == (n*(n-1)*(n-2)) / 6 ways to choose the points on that row/column.

---

Some polyglot notes:

• Funky doesn't really have keyword return. However, as ATaco explained, [Funky] thinks return is a variable. So it's parsing that expression, which conveniently does nothing, then parses the next expression. And this is used as an output.
• Javascript use ^ as bitwise xor, unlike Funky which use ^ as exponentiation. So n*n have to be used instead of n^2 to ensure Javascript compatibility.
• In Funky, all operator (+, -, *, etc.) have equal precedence and right-associative, so expressions need to be parenthesized properly.

Answer 5

271. Java 6, 10008 bytes, A000103

This program was written entirely by user202729. I am posting this with the creator's explicit permission / request.

/*
Edit: Why must I map from Edge to index, 
and then get edge from index, 
while I can map Edge to Edge? Fixed.
--------
Edit 2: Remove some dependency on ArrayList.get.
--------
Edit 3: Remove a factor of n! because I didn't think
about this efficient graph isomorphism checking.
---------
Ok... the solution turns out to be too short now to
get to 10008 bytes. Therefore I'm going to add some
random things here.

#############################################
#############################################
#############################################
#############################################
#############################################
#############################################
#############################################
#############################################
*/

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.IdentityHashMap;
import java.util.Scanner;

public class Main {
	
	static class Edge {
		Edge next, prev, twin;
		final int node;
		Edge(int node) {
			this.node = node;
		}
		Edge pairNext(Edge e) {
			this.next = e; e.prev = this;
			return this;
		}
		Edge pairTwin(Edge e) {
			this.twin = e; e.twin = this;
			return this;
		}
	}
	
	static class Graph {
		List<Edge> edges;
		int nVertices;
		
		/** 
		 * Initialize to a tetrahedral graph.
		 */
		Graph () {
			nVertices = 3;
			
			edges = new ArrayList<Edge>();
			
			edges.add(new Edge(0));
			edges.add(new Edge(1));
			edges.add(new Edge(2));
			edges.get(0).pairNext(edges.get(1));
			edges.get(1).pairNext(edges.get(2));
			edges.get(2).pairNext(edges.get(0));
			
			edges.add(new Edge(1));
			edges.add(new Edge(2));
			edges.add(new Edge(0));
			edges.get(3).pairTwin(edges.get(0)).pairNext(edges.get(5));
			edges.get(4).pairTwin(edges.get(1)).pairNext(edges.get(3));
			edges.get(5).pairTwin(edges.get(2)).pairNext(edges.get(4));
			
			addVertex(new Edge[] {
				edges.get(0), edges.get(1), edges.get(2)
			});
		}
		
		/** 
		 * Copy the other graph.
		 * Expected time complexity O(n) where n is the number of edges
		 * in the graph.
		 * @param other The other graph.
		 */
		Graph (Graph other) {
			nVertices = other.nVertices;
			edges = new ArrayList<Edge>(other.edges.size()); // initial capacity
			Map<Edge, Edge> map = new IdentityHashMap<Edge, Edge>();
			for (Edge e : other.edges) {
				Edge f = new Edge(e.node);
				edges.add(f);
				map.put(e, f);
			}

			assert other.edges.size() == edges.size();

			for (Map.Entry<Edge, Edge> ef : map.entrySet()) {
				Edge e = ef.getKey(), f = ef.getValue();
				f.prev = map.get(e.prev);
				f.next = map.get(e.next);
				f.twin = map.get(e.twin);
			}
		}
		
		/**
		 * Find circuit from one edge.
		 * Note that if the circuit length is less than {@code n}, {@code null}
		 * is also returned.
		 * @param e The input edge.
		 * @return An edge array of length {@code n} consists of node indices, 
		 * or {@code null} if not found.
		 */
		Edge[] findCircuit (Edge e, int n) {
			
			assert edges.contains(e);
			
			Edge[] circuitEdges = new Edge[n];
			circuitEdges[0] = e;
			for (int i = 1; i < n; ++i) {
				circuitEdges[i] = circuitEdges[i-1].next;
				
				assert circuitEdges[i].prev == circuitEdges[i-1];
			}
			return circuitEdges[n - 1].next == e ? circuitEdges : null;
		}
		
		/**
		 * Add an vertex to the plane bounded by {@code circuit}. <br>
		 * The vertex will be connected to all of the vertices inside the 
		 * circuit. <br>
		 * Time complexity: O({@code circuit.length}).
		 * @param circuit The specified plane. Should be listed in the order
		 * such that {@code circuit[i].next == circuit[(i+1) % nVertices]}
		 * for all valid {@code i}.
		 */
		void addVertex(Edge[] circuit) {
			int n = edges.size(), k = circuit.length;
			
			for (int i = 0; i < k; ++i) {
				assert(circuit[i].next == circuit[(i+1)%k]);
				assert(circuit[(i+1)%k].prev == circuit[i]);
			}
			
			for (int i = 0; i < k; ++i) edges.add(
					new Edge(nVertices)
					.pairNext(circuit[i])
			);
			for (int i = 0; i < k; ++i) edges.add(
					new Edge(circuit[i].node)
					.pairTwin(edges.get(n + i))
					.pairNext(edges.get(n + (i == 0 ? k : i) - 1))
			);
			for (int i = 0; i < k; ++i) 
				circuit[i].pairNext(edges.get(n + (i == k-1 ? i : i + k) + 1));
			
			++nVertices;
		}
		
		/**
		 * Remove an edge from the graph. <br>
		 * Time complexity O({@code edges.size()}).
		 * @param edge The edge to remove.
		 */
		void removeEdge(Edge edge) {

			assert edges.contains(edge);
			
			Edge twin = edge.twin;
			twin.prev.pairNext(edge.next);
			edge.prev.pairNext(twin.next);
			
			// it is possible to implement this in O(1) with LinkedList but I'm lazy...
			boolean success = edges.remove(edge);
			success = edges.remove(twin) && success; 
			assert success;
			
		}
		
		/**
		 * Calculate the minimum degree of any vertex.
		 * @return The minimum degree of any vertex.
		 */
		int minVertexDegree() {
			int[] degree = new int[nVertices];
			for (Edge e : edges) ++degree[e.node];
			
			int ans = degree[0];
			for (int d : degree)
				if (d < ans) ans = d;
			
			return ans;
		}
		
		/**
		 * Check isomorphism between two graphs (reflection does not count).
		 * @param g Other graph.
		 * @return whether the graphs are isomorphic under rotation.
		 */
		boolean isomorphicToWithoutReflection(Graph g) {
			check_edge_equivalence:
			for (Edge e : edges) {
				Map<Edge, Edge> map = new IdentityHashMap<Edge, Edge>();
				map.put(e, g.edges.get(0));
				
				/**
				 * List containing edges which are mapped, but their neighbors 
				 * ({@code next, prev, twin} are not mapped.
				 */
				List<Edge> pending = new ArrayList<Edge>(); 
				pending.add(e);
				
				while (!pending.isEmpty()) {
					Edge f = pending.remove(pending.size() - 1), map_f = map.get(f);
					for (Edge[] adj : new Edge[][]{
						{f.next, map_f.next},
						{f.prev, map_f.prev},
						{f.twin, map_f.twin}
					}) {
						Edge map_adj = map.get(adj[0]);
						if (map_adj == null) {
							map.put(adj[0], adj[1]);
							pending.add(adj[0]);
						} else {
							if (map_adj != adj[1]) 
								continue check_edge_equivalence;
						}
					}
				}
				
				assert map.size() == edges.size(); // the graph is connected
				return true;
			}
			return false;
		}
		
		/**
		 * Reflect this graph.
		 */
		void reflect() {
			for (Edge e : edges) {
				Edge f = e.prev; e.prev = e.next; e.next = f;
			}
		}

		/**
		 * Check isomorphism between two graphs.
		 * Algorithmic complexity: O(n<sup>2</sup>).
		 * @param g The graph to check isomorphism with {@code this}.
		 * @return {@code true} if the graphs are isomorphic,
		 * {@code false} otherwise.
		 */
		boolean isomorphicTo(Graph g) {
			boolean ans = false;
			for (int i = 0; i < 2; ++i) {
				ans = ans || isomorphicToWithoutReflection(g);
				reflect();
			}
			return ans;
		}
	}
	
	/**
	 * Given a graph with length {@code n}, generate all graphs with length 
	 * {@code n+1} using the approach in MishaLavrov's answer to 
	 * HyperNeutrino's question on Math.SE about A000109
	 * @param graph The input graph.
	 * @return A List of graphs.
	 */
	static List<Graph> generateGraph(Graph graph) {
		ArrayList<Graph> result = new ArrayList<Graph>();
		
		// case 1: add vertex to list of 3 edges
		for (int i = 0; i < graph.edges.size(); ++i) {
			Edge edge = graph.edges.get(i);
			
			if (!(edge.node < edge.next.node && edge.node < edge.prev.node))
				continue; // avoid redundancy, for each triangular face 
			// only consider the edge with minimum node index
			
			Graph newgraph = new Graph(graph);
			edge = newgraph.edges.get(i);

			Edge[] circuit = newgraph.findCircuit(edge, 3);
			assert circuit != null; // the graph is supposed to be triangular 
			// decomposition of a sphere.
			
			newgraph.addVertex(circuit);
			result.add(newgraph);
			
		}
		
		// case 2: add vertex to 2 adjacent triangular faces
		for (int i = 0; i < graph.edges.size(); ++i) {
			Edge edge = graph.edges.get(i);

			Edge twin = edge.twin;
			if (edge.node > twin.node) continue;
			
			assert graph.findCircuit(edge, 3) != null;
			assert graph.findCircuit(twin, 3) != null;
			

			Graph newgraph = new Graph(graph);
			edge = newgraph.edges.get(i);

			Edge next = edge.next;
			newgraph.removeEdge(edge);
			Edge[] circuit = newgraph.findCircuit(next, 4);
			assert(circuit != null);
			newgraph.addVertex(circuit);

			result.add(newgraph);
		}
		
		// case 3: add vertex to 3 adjacent triangular faces
		for (int i = 0; i < graph.edges.size(); ++i) {

			Edge edge = graph.edges.get(i);
			if (edge.twin.next.twin == edge.prev.twin.prev) continue;
			
			Graph newgraph = new Graph(graph);

			edge = newgraph.edges.get(i);
			Edge next = edge.next, prev = edge.prev;
			assert newgraph.findCircuit(edge, 3) != null;
			
			newgraph.removeEdge(edge); newgraph.removeEdge(prev); 
			Edge[] circuit = newgraph.findCircuit(next, 5);
			assert(circuit != null);
			newgraph.addVertex(circuit);

			result.add(newgraph);
			
		}
		
		return result;
	}
	
	/**
	 * Evolve the graphs with number of node {@code n} to get graphs with 
	 * number of node {@code n+1}.
	 * @param graphs The list of graphs with {@code n} nodes.
	 * @return A list of graphs with {@code n+1} nodes.
	 */
	static List<Graph> evolve(List<Graph> graphs) {
		List<Graph> result = new ArrayList<Graph>();
		
		for (Graph graph : graphs) {
			outer: for (Graph g0 : generateGraph(graph)) {
				
				assert(g0.nVertices == graph.nVertices + 1);
				
				for (Graph g1 : result) {
					if (g0.isomorphicTo(g1))
						continue outer;
				}
				result.add(new Graph(g0));
			}
		}
		
		return result;
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		
		List<Graph> graphs = new ArrayList<Graph>();
		graphs.add(new Graph());
		
		for (int i = 0; i < n; ++i) graphs = evolve(graphs);
		
		int ans = 0;
		for (Graph g : graphs) {
			if (g.minVertexDegree() >= 4) ++ans;
		}
		
		System.out.println(ans);
	}
}

Try it online!

Note: TIO runs the program on Java 9, but I've tested running the program on Java 6u45 - Windows 32 bit locally, and it also works. Input 5 gives output 5 in about 21 seconds now, and input 6 gives output 12 in 7 minutes 14 seconds.

Next Sequence

Answer 6

265. brainfuck, 636 Bytes, A000102

[-]>[-]+[[-]>[-],[+[-----------[>[-]++++++[<------>-]<--<<[->>++++++++++<<]>>[-<<+>>]<+>]]]<]<

<<<<<+<++<+++++>>>>>>>

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

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

>>>>>>>>-]

<<[-]<[-]<[-]<[-]<[-]<[-]>>>>>>

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

Input is a normal decimal number.

Note that the result is calculated modulo the cell size, so for TIO 256, but it works for other cell sizes as well.

Try it online!

---

Explanation:

Relies on the recursive definition a(n) = 2*a(n-1) + a(n-2) - 2*a(n-4) - 3*a(n-5) - 2*a(n-6) - a(n-7)

[-]>[-]+[[-]>[-],[+[-----------[>[-]++++++[<------>-]<--<<[->>++++++++++<<]>>[-<<+>>]<+>]]]<]<

takes input (decimal value in ASCII) and write actual decimal number in a cell. Taken from the esolang site listing BF algorithms.

<<<<<+<++<+++++>>>>>>> 

initialize first seven values (0, 0, 0, 0, 1, 2, 5)

Then comes the main block. Basically the seven cells to the left of the input represent a(n) a(n-1) a(n-2) a(n-3) a(n-4) a(n-5) a(n-6) and the input represents how many 'window shifting' operations have to be performed still, where a window shifting operation consists of a(n-6)=a(n-5), a(n-5)=a(n-4) etc. and the calculation of the new a(n)(so a(n+1) in terms of our old labels) as described above. The former (a-6) is dropped.

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

Move a value seven cells left, do this for all sequence terms. Then we move to the former a(n) with value x and execute

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

which increases the new value of a(n) by 2*x and the value of a(n-1) by x. Repeat the same for the other sequence values with the corresponding factor for a(n).

Finally, move back to the input, decrease it by 1. If input is zero, we're done with the main block. If not, execute another window shift operation.

<<[-]<[-]<[-]<[-]<[-]<[-]>>>>>>

Zero all the sequence numbers not required for the final output. (This is not necessary, but I like to do it anyway to make sure it does not interfere with the output function.

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

Lastly, output the number left to the input which started as a(0), so it is a(n)after n window shifts. The algorithm for this is again taken from the esolangs site linked above.

---

This window shifting algorithm is generally quite efficient, but this implementation can be optimized a lot.

For some input n, we do n window shifts, but after that our lowest stored value is a(n), which means we already calculated a(n+6). This is obviously inefficient but saves the special handling required for inputs <7, so it saves some characters and mainly nerves of the programmer.

Second, it is not necessary to copy the whole sequence. It'd be sufficient to copy one value, but this way it's more convenient to write and understand.

Here is a solution implementing the second optimization. Only the old a(n) is moved. The other values move one spot to the right and their corresponding multiple is added/subtracted in one loop. This actually saves more time then I expected for larger values with unbounded cell size.

---

Next sequence: A000636

Answer 7

184. CJam, 142 bytes, A000061

{_,@f*\f%1\{)1$f-@+:*\}h;g}:J;
{)_mF{~2/#}%:*:M_*/:B_4%1={_2/,f{)_2$J@@4*-*}}{_,{1&},f{1$1$J@@-*}}?1b0.5e|M3#*Mmf{2>},_&{_2#_@B\J-@*\/}/0.5+i}

Online test suite. This is an anonymous block (function) with an auxiliary named block (function) to calculate the Jacobi symbol.

Note: the formulae given in OEIS as it currently stands (revision 39) are badly transcribed from the Shanks paper. They miss an exponent and one special case and give a different special case incorrectly. I shall propose amendments.

Also note that for the Jacobi symbol I'm using the Zolotarev-style approach I mentioned in an earlier answer of calculating the Levi-Civita symbol of a linear map. The implementation of J above is not the same as the one I previously proposed: it's the same length, but I think it's less wasteful.

The next sequence is a nice easy one, so maybe someone can bring the lowest uncovered sequence, A000017, into play. That should make the hard-coders happy.

Answer 8

345. brainfuck, 162 bytes, A000301

+<<,[>>[>]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]<[<]<-]>>[>]+<[-]++<[>[>>+>+<<<-]>>>[<<<+>>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>[-]>[<<+>>-]<<<<-]>>too golfy.

Try it online!

Next sequence!

This takes as input the character with code point n (by BF's specs) and outputs in the same way. To see the numbers, I suggest using @Timwi's EsotericIDE.

Explanation:

+<<,                                  Initialize the tape with the first two Fibonacci numbers. Take loop counter from input.
[                                     n times:
  >>[>]                                 Move to the end of the tape. 
  <<[>>+>+<<<-]>>>[<<<+>>>-]            Add fib(n-2)...
  <<[>+>+<<-]>>[<<+>>-]                 and fib(n-1). Store on the end of the tape.
  <[<]<-                                Move back to start of tape. Update loop counter.
]                                     End loop.
>>[>]+<[-]++<                         Delete the extra Fibonacci number and prepare for exponentiation. 
[                                     fib(n) times:
  >[>>+>+<<<-]>>>[<<<+>>>-]<<           Copy the base (2) to preserve it.
  [>[>+>+<<-]>>[<<+>>-]<<<-]            Multiply what started as a 1 by the base.
  >[-]>[<<+>>-]<<<<-                    Clean up and update loop counter.
]                                     End loop.
>>too golfy.                          Add some bytes, for all sequences <162 had been used. Print result. 

Since this stores all Fibonacci numbers up to the important one, it will fail for REALLY big input on a bounded tape.

This could be shortened significantly by hardcoding the base (2), but golfiness isn't an issue at all.

Answer 9

7. Brain-Flak, 70 bytes, A000071

({}[<>((()))<>]){({}[()])<>({}<>)<>(({})<>({}<>))<>}<>{}{}({}<>{}[()])

Try it online!

Next sequence

Explanation

({}[<>((()))<>]) #{ place a one on the off stack and subtract 1 from the input (to zero index)}
                {({}[()])                          } #{n times}
                         <>({}<>)<>(({})<>({}<>))<>  #{Add the top two numbers in place}
                                                    <>{}{}({}<>{}[()]) #{Clean up and subtract 1}

Answer 10

5. Python 3, 72 bytes, A000002

n=int(input())
l=[1,2,2]
for i in range(2,n):l+=[1+i%2]*l[i]
print(l[n])

Try it online!

Next Sequence

Answer 11

17. Stacked, 18 bytes, A000069

[bits  sum odd]nth

Try it online!

Next sequence. Pretty simple. Computes the number of bits, calculates the sum, then checks for odd parity. Then takes the nth such number. Hehehe good luck.

In retrospect, I could have made it 16 bytes instead of 17 or 18:

[bits sum 2%]nth

But oh well

Answer 12

25. eta, 183 bytes, A000033

f x = sum $ map f [2..n]
  where f k = g k `div` h k
        g k = (-1)^k * n * v (2*n-k-1) * v (n-k)
        h k = v (2*n-2*k) * v (k-2)
        v n = product [1..n]
        n = x+1

Try it online

Next sequence

Answer 13

31. Joy, 172 bytes, A001112

DEFINE acf == [20 <] [[0 1 1 3 4 11 136 283 419 1121 1540 38081 39621 117323 156944 431211 5331476 11094163 16425639 43945441] of] [10 - dup 10 -] [[39202 *] dip -] binrec.

Try it online!

Next sequence

Answer 14

50. Japt, 26 bytes, A000074

1o2pU 2 èÈo f_¬v1Ãd_nX ¬v1

Try it online!

Next sequence (I was quite tempted to ungolf it by 1 byte to get A000027, but this one should be fine)

Explanation

1o2pU 2 èÈ  o f_  ¬ v1à d_  nX ¬ v1
1o2pU 2 èX{Xo fZ{Zq v1} dZ{ZnX q v1}}   Ungolfed
                                        Implicit: U = input integer
  2pU                                   Yield 2 ** U.
1o    2                                 Create the range [1, 3, 5, ..., 2**U - 1].
        èX{                         }   Find the number of items X where this is true:
           Xo                             [0, 1, ..., X - 1]
              fZ{     }                   filtered to only items Z where
                 Zq v1                      sqrt(Z) is divisible by 1 (Z is square)
                                          (this gives a list of the squares less than X)
                        dZ{        }      contains an item Z where
                           ZnX              X - Z
                               q v1         is also square.
                                          In other words, assert that an integer solution
                                          to X = a**2 + b**2 exists.
                                        This gives the number of odd integers less than 2**U
                                        that can be represented as the sum of two squares.
                                        Implicit: output result of last expression

Answer 15

69. GAP, 333 bytes, A000761

dirs:=[[1,0,0],[0,1,0],[0,0,1]];
dirs:=Concatenation(dirs,-dirs);

count:=function(pos,seen,n)
  local newseen;
  if (pos in seen) or AbsInt(pos[1]-2)>n then
    return 0;
  fi;
  if n=0 then
    return 1;
  fi;
  newseen:=Concatenation(seen,[pos]);
  return Sum(dirs,d->count(pos+d,newseen,n-1));
end;

f:=n->count([0,0,0],[],n+2);

Next sequence

Answer 16

80. Mathics, 140 Bytes, A000013

EulerPhi[x_] := Sum[If[CoprimeQ[i,x], 1, 0], {i, 1, x}]
OEIS[x_] := Sum[If[IntegerQ[x/d], (EulerPhi[2d]*2^(x/d))/(2x), 0], {d,1,x}]
OEIS[#]&

Try it Online!

Next Sequence

Answer 17

116. Kotlin, 1156 bytes, A000273

import java.math.BigInteger;

fun main(args: Array<String>) {
    val n = Integer.valueOf(args[0]);
    var a = accum(n, n, Array(n, { x -> 0 }), Array(n, { x -> 0 }), 0, BigInteger.ONE, n);
    println(a.first / a.second);
}

fun accum(n: Int, m: Int, part: Array<Int>, freq: Array<Int>, off: Int, c: BigInteger, omega: Int): Pair<BigInteger, BigInteger> {
    if (n == 0) return Pair(BigInteger.ONE.shiftLeft(omega), c);
    if (m == 0) return Pair(BigInteger.ZERO, BigInteger.ONE);

    var sum = accum(n, m - 1, part, freq, off, c, omega);
    part[off] = m;
    freq[off] = 0;
    var c1 = c;
    var omega2 = omega;

    var delta = -1;
    var j = 0;
    while (j < off) delta += 2 * freq[j] * gcd(part[j++], m);

    var im = m;
    while (im <= n) {
        freq[off]++;
        c1 = c1 * BigInteger.valueOf(im.toLong());
        omega2 = omega2 + 2 * (im - m) + delta;
        val term = accum(n - im, m - 1, part, freq, off + 1, c1, omega2);
        sum = Pair(sum.first * term.second + sum.second * term.first, sum.second * term.second);
        im += m;
    }

    return sum;
}

fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

Online demo

Next sequence is a nice easy partition sequence.

Notes

This implementation follows J. Qian, Enumeration of unlabeled directed hypergraphs, Electronic Journal of Combinatorics, 20(1) (2013), and in particular exploits corollary 6. Although it may not look it, it's much simpler than the Maple implementation listed in OEIS.

Answer 18

123. Emojicode, 278 bytes, A002057

🐋🚂🍇
 🐖🅱️➡🚂🍇
  🍮p 1.0
  🔂k⏩2➕1🐕🍇
   🍮✖p➕➗🚀🐕🚀k 1
  🍉
  🍎🏇p
 🍉
 🐖🅰️➡🚂🍇
  🍎➗✖🅱️➕🐕1✖2🐕➕3🐕
 🍉
🍉

🏁🍇
 😀🔡🅰️➕1🍺🚂🔷🔡😯🔤🔤10 10
🍉

Try it online!

Next sequence! (have an easy one)

This is Emojicode 0.5, which is currently the newest version, but I'm mentioning it because of the major changes that are planned for 0.6.

Explaination:

Note: a lot of emoji choice doesn't make much sense in Emojicode 0.5. It's 0.x, after all. 0.6 will fix this, so if you want to learn this (because who wouldn't want to), I recommend waiting a moment.

Emojicode is an object-oriented programming language featuring generics, protocols, optionals and closures, but this program uses no closures and all generics and protocols can be considered implicit, while the only optional appears in the I/O part.

The program operates on only a few types: 🚂 is the integer type, 🚀 is the floating-point type, 🔡 is the string type and ⏩ is the range type (yes, a range is a type in Emojicode).

There are currently no operators in Emojicode, so addition, comparsions and other operations that are normally operators are implemented as functions, effectively making the expressions use prefix notation. Operators are also planned in 0.6.

🐋🚂🍇 ... 🍉

Extend the 🚂 type. This is a feature that is not commonly found in programming languages. Instead of creating a new class with 🚂 as the superclass, 🐋 modifies 🚂 directly. Grapes and watermelons declare code blocks in Emojicode.

🐖🅱️➡🚂🍇 ... 🍉

🅱️ is a method that returns 🚂. 🅱️ calculates A000108 using the Product_{k=2..n} (1 + n/k). The OEIS states that the formula is only valid for n > 1, but this method will only be called with n >= 1 and the value is ignored in the n = 1 case because of a multiplication by 0, so no special case is present.

🍮p 1.0

Create a variable named p and set it to 1.0. This automatically makes the type 🚀. This is necessary because fractions are present in the product.

🔂k⏩2➕1🐕🍇 ... 🍉

🔂 iterates over anything that implements the 🔂🐚⚪️ protocol, while ⏩ is a range literal that happens to implement 🔂🐚🚂. A range has a start value, a stop value and a step value, which is assumed to be 1 if start < stop, or -1 otherwise. One can also specify the step value by using the ⏭ to create the range literal. The start value is inclusive, while the stop value is exclusive, so this is equivalent to for k in range(2, ➕1🐕). ➕ is a method of the 🚂 type that adds numbers together and 🐕 refers to the object the method was called on, so ➕1🐕 means n + 1. This corresponds to the range of Product_{k=2..n} from the formula, since the stop value is not included in the range.

🍮✖p ...

This is an assignment by call, which means "call ✖ on p with the arguments (...) and set p to the return value". ✖ is a method of 🚀 that multiplies numbers together. This can sound familiar, because it's similar to the operators like +=, *= or >>= in some popular emoji-free (and therefore inferior) languages.

➕➗🚀🐕🚀k 1

🚀, in addition to being a type, is a method of the 🚂 type, that returns a 🚀 of the same value as 🚂 - by convention, methods that share the name with a type are used to convert to that type. Therefore this expression represents (n / k) + 1, which is then multiplied by, and stored in p.

🍎🏇p

🍎 is used to return values from methods, while 🏇 is a method of the 🚀 type that returns the nearest 🚂. Whether one uses an equivalent of round, floor or ceil shouldn't matter since the formula always results in integers, but using 🏇 makes the code more immune to floating-point inaccuracies.

🐖🅰️➡🚂🍇 ... 🍉

This creates a method named 🅰️ that returns 🚂. This method implements A002057.

🍎➗✖🅱️➕🐕1✖2🐕➕3🐕

This is a return statement with the formula "encoded" in prefix notation. If you decipher it, you'll see 🅱️ being called on n + 1, the result multiplied by 2 * n and divided by n + 3, resulting in the formula 2*n*A000108(n+1)/(n+3) from the OEIS.

🏁🍇 ... 🍉

🏁 marks the equivalent of a main function.

😀🔡🅰️➕1🍺🚂🔷🔡😯🔤🔤10 10

Let's break it down.

🔷🔡😯🔤🔤

🔤 marks the beginning and end of a 🔡 literal. 🔷 is used for constructing objects, so this creates a 🔡 with the constructor 😯 called with a single argument of an empty string. 😯 is used to read a line of input from the user, and the argument is used as a prompt.

🚂🔷🔡😯🔤🔤10

🚂 is a method of the 🔡 type, and as you might guess, it converts the string into an integer. It takes one argument, the number base to use.

🍺🚂🔷🔡😯🔤🔤10

🚂 returns an optional, 🍬🚂. Optionals can contain a value of the base type or nothingness, ⚡. When the string doesn't contain a number, ⚡ is returned. To use the value of an optional, one has to unwrap it using 🍺, which raises a runtime error if the value is ⚡. Normally it is bad practice to unwrap an optional without checking, but this is codegolf.SE, we don't care. If you want to see an example with error checking, see my answer at this challenge.

➕1🍺🚂🔷🔡😯🔤🔤10

The formula used for A002057 appears to have an off-by-one error, so 1 is added to the input to make the offset correct.

🅰️➕1🍺🚂🔷🔡😯🔤🔤10

🅰️ is called on the corrected input, calculating the sequence.

🔡🅰️➕1🍺🚂🔷🔡😯🔤🔤10 10

You guessed it. 🔡 is a method of the 🚂 type that converts it to a 🔡, taking the base as an argument.

😀🔡🅰️➕1🍺🚂🔷🔡😯🔤🔤10 10

Finally, 😀 is used to print the result.

Answer 19

178. GAP, 933 bytes, A000214

Luckily GAP wasn't taken for No. 167 (A000638)!

AG := function( n )
  local b, sw, sh, xr, tr, gens;
  b := BasisVectors(Basis(FullRowSpace(GF(2),n+1)));
  gens := [];
  if n>1 then
    sw := ShallowCopy(b);
    sw{[2,3]} := sw{[3,2]};
    sh := ShallowCopy(b);
    sh{[2..n+1]} := sh{Concatenation([n+1],[2..n])};
    xr := ShallowCopy(b);
    xr[2] := xr[2]+xr[3];
    gens := [ sw, sh, xr ];
  fi;
  tr := ShallowCopy(b);
  tr[2] := tr[1]+tr[2];
  Add(gens, tr);
  return Group(List(gens,TransposedMat));
end;

Fix := function( g )
  local o, h, s, i, k;
  o := One(g);
  s := 2^(Size(g)-1);
  i := 1;
  h := g;
  while not IsOne(h) do
    k := NullspaceMat( h-o );
    if ForAny( k, v -> IsOne(v[1]) ) then
      s := s + 2^(Size(k)-1);
    fi;
    i := i+1;
    h := h*g;
  od;
  return 2^(s/i);
end;

f := function( n )
  local grp;
  grp := AG(n+1); # zero based
  return Sum( ConjugacyClasses(grp),
              cc -> Size(cc)*Fix(Representative(cc)) ) / Order(grp);
end;

This is using somewhat advanced group theory (Burnside's lemma, twice), but no deep knowledge of the affine group. Still it is good enough to compute the 9th and 10th value (and more), which are:

3743090921588631997590183810292071781042846067942809230428008257901850006463197026597863697259931801933484260185559925420090026
479084991876032922658580043148767307553909132799686744495116429395794360341231625183693228836152593000430870733973647565874325953529940377811130038575926765372370447759627109606902989971984053705702177123141099357638755205930373003087364483930095902877678789627725054625735636

Next sequence

How does it work?

There are 2^(2^n) Boolean functions of n variables. The affine group AG(n,2) acts on these functions by transforming the input. An affine transformation can permute the input, xor one input to another, and negate an input. (xor is addition in the field with two elements, negation is addition of one.)

If a Boolean functions can be transformed in this way into an other, we consider them equivalent. The equivalence classes are called orbits. We want to know how many orbits there are.

Burnside's lemma tells us that the number of orbits of an action of a group G on a set X equals the sum of the number of elements of X that are fixed by g (the sum is over each element g of G) divided by the order (size) of the group G.

Since the affine group is big for moderate sizes of n, we want to avoid summing over all its elements. Conjugated elements fix the same number of elements of X, so we can sum instead over conjugacy classes and multiply with the size of the conjugacy class. There are not that much conjugacy classes, and GAP can compute them in reasonable time. (I wasn't sure about this when I started programming.) This is what the main function f does, using helper functions AG to create the affine group and Fix to determine the number of boolean functions that are fixed by an affine transformation.

An affine transformation can be given by an invertible matrix A and an translation vector b, it maps x to Ax+b. This can be brought into the realm of linear algebra by embedding it into n+1 dimensional space. The affine transformation is represented by [[1, 0], [b, A]] (GAP wouldn't accept this). To see where the n dimensional x is mapped to, add a first component of 1, multiply with the matrix, and drop the first component of the result (which will be 1). You can think of adding an extra input that is always 1 and can not be changed by the transformation, but can be added (xor-ed) to other inputs. The AG function creates the affine group as matrix group using this representation.

We create the affine group using four generators, the first three are only meaningful for n>1. The first swaps the first two inputs, the second cyclically shifts the inputs. (For n=2 they are the same, but that is no problem.) Together they generate all permutations of inputs. The third xors the second input to the first. By conjugation with a permutation, this gives all needed xor operations. Together, these three matrices generate the general (or special, that's the same in this case) linear group GL(n,2). The last generator negates the first input. Again, conjugation with a permutation gives the other negations, so all matrices together generate the affine group AG(n,2). You may have noted that my thinking, explaining and constructing has been in terms of right multiplying a column vector to a matrix. GAP however uses row vectors and left multiplication. Since I will use GAP's linear algebra functionality later, I compensate by transposing the generating matrices before construction the group.

Now to the function Fix. We are given an affine transformation g and want to calculate the number of Boolean functions that it fixes. A function is fixed by g if it gives the same result to some input and to this input transformed by g (or g^2 etc). If an input can not be transformed into an other by a power of g, then the function may give different results for them. So the result is 2 to the number of classes of inputs that may get different results. We can get this number by another application of Burnside's lemma! This time the group is the cyclic group generated by g, and it is acting on the set of inputs of size 2^n. We really sum over all elements of the group now. The identity fixes all inputs, so we start the sum s with this number. Now assume we have a power h of g and want to know how many inputs it fixes. That means we want to know how many n+1 dimensional vectors with first component 1 are fixed by the matrix h, or how many are mapped to zero by h-1. So we use NullspaceMat to compute a basis of the kernel of h-1. If that contains no element with a 1 at the first component, then there are no solutions, otherwise there are half as many as the kernel size. In the end i contains the number of elements of the cyclic group, by which we divide the sum s as Burnside's lemma tells us.

The last time I wrote similar code I used it to compute some numbers which I could use to find the series on OEIS and then find a better way to compute them there...

I guess that the algorithm could be improved a lot without very complicated math. For example, I think it should be useful that the affine group is a semidirect product, but we give it to GAP as if it were any random matrix group.

Now I hope this was useful or interesting for someone. I never know how much detail I should give in an explanation here.

Answer 20

226. Java 7, 4903 bytes, A000080

Originally programmed by HyperNeutrino.

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

abstract interface BooleanCombiner {
	abstract boolean combine(boolean left, boolean right);
}

class Main {
	static void print(boolean[][] matrix) {
		for (boolean[] row : matrix) {
			for (boolean e : row) {
				System.out.print(e ? 1 : 0);
				System.out.print(' ');
			}
			System.out.println();
		}
	}

	static boolean[] combine(boolean[] left, boolean[] right, BooleanCombiner f) {
		assert left.length == right.length;
		boolean[] result = new boolean[left.length];
		for (int i = 0; i < result.length; i++) result[i] = f.combine(left[i], right[i]);
		return result;
	}

	static boolean none(boolean[] row) {
		for (boolean element : row) if (element) return false;
		return true;
	}

	static boolean all(boolean[] row) {
		for (boolean element : row) if (!element) return false;
		return true;
	}

	static int weight(boolean[] row) {
		int weight = 0;
		for (boolean element : row) if (element) weight++;
		return weight;
	}

	static boolean[] DFS(boolean[][] matrix, int node, boolean[] visited) {
		assert visited.length == matrix.length;
		if (visited[node]) return visited;
		visited[node] = true;
		for (int neighbor = 0; neighbor < visited.length; ++neighbor) {
			if (matrix[node][neighbor]) DFS(matrix, neighbor, visited);
		}
		return visited;
	}

	static boolean isConnected(boolean[][] matrix) {
		return all(DFS(matrix, 0, new boolean[matrix.length]));
	}

	static int[][] triples(int length) {
		int[][] triples = new int[length * ~-length * ~-~-length / 6][];
		int index = 0;
		for (int i = 0; i < length; i++) {
			for (int j = i + 1; j < length; j++) {
				for (int k = j + 1; k < length; k++) {
					triples[index++] = new int[] { i, j, k };
				}
			}
		} return triples;
	}

	static boolean isomorphic(boolean[][] a, boolean[][] b) {
		int[] permutation = new int[a.length];
		for (int i = 0; i < permutation.length; ++i) permutation[i] = i;
		while (true) {
			// check here
			boolean maybe_valid = true;
			for (int i = 0; i < permutation.length && maybe_valid; ++i) {
				for (int j = 0; j < permutation.length; ++j) {
					if (a[i][j] != b[permutation[i]][permutation[j]]) {
						maybe_valid = false;
						break;
					}
				}
			}
			if (maybe_valid) {
				return true; // actually valid!
			}
			
			// advance the permutation here. Implement C++'s std::next_permutation
			int j = permutation.length - 1;
			while (j != 0) {
				if (permutation[j - 1] > permutation[j]) --j;
				else break;
			}
			if (j == 0) break; // reached last permutation
			// reverse [j, permutation.length) segment
			for (int k = j, l = permutation.length - 1; k < l; ++k, --l) {
				int tmp = permutation[k]; permutation[k] = permutation[l]; permutation[l] = tmp;
			}
			// find smallest element in [j, permutation.length) that is still larger than permutation[j-1]
			int k = j; // sorry, meaningless variable name;
			while (permutation[k] < permutation[j-1]) ++k;
			int tmp = permutation[j-1]; permutation[j-1] = permutation[k]; permutation[k] = tmp;
		};
		return false;
	}

	static boolean[][] construct (int size, boolean[] mask, int[][] triples_table) {
		assert triples_table.length == mask.length;
		boolean[][] matrix = new boolean[size][size];
		for (int index = 0; index < mask.length; ++index) {
			if (mask[index]) {
				int[] triple = triples_table[index];
				int i = triple[0], j = triple[1], k = triple[2];
				matrix[i][j] = matrix[j][i] = matrix[i][k] = matrix[k][i] = matrix[j][k] = matrix[k][j] = true;
			}
		}
		return matrix;
	}

	
	static List<boolean[][]> calculate (int size) {
		List<boolean[][]> matrices = new ArrayList<>();
		int[][] triples_table = triples(size);
		boolean[] mask = new boolean[triples_table.length];
		while (true) {
			boolean[][] matrix = construct(size, mask, triples_table);
			process_matrix:
			if (isConnected(matrix)) {
				// check if matrix is isomorphic to any existing matrix
				for (boolean[][] existing_matrix : matrices) {
					if (isomorphic(matrix, existing_matrix)) break process_matrix;
				}
				// check if the matrix is minimal
				for (int delete_triple = 0; delete_triple < mask.length; ++delete_triple) {
					if (! mask[delete_triple]) continue;
					mask[delete_triple] = false; // temporarily set to false
					if (isConnected(construct(size, mask, triples_table))) {
						// it is not minimal
						mask[delete_triple] = true; // remember to restore it ... 
						break process_matrix;
					}
					mask[delete_triple] = true; // ... in any condition
				}
				/* it is both minimal and not counted now, */ matrices.add(matrix);
			}
			
			int i = mask.length - 1;
			while (i >= 0 && mask[i]) mask[i--] = false;
			if (i == -1) return matrices; // considered all <mask> possible.
			mask[i] = true;
		}
	}
	
	public static void main(String[] args) {
		System.out.println(calculate(Integer.parseInt(args[0]) + 3).size());
	}
}

Try it online!

Next sequence.

Answer 21

241. Trefunge-98 (PyFunge), 230 bytes, A000256

       v   >51>R1-:v>RRO:8*'+-*'9+*O3*9-2Pv
>4      (&:|  \    >|v   ;>v;      <:R: -4<
^"FRTH"<@.1<  +  @.$<>R1-:|>\1-RO*\^
 ^ useful     1     v\0\$$< A000256
 library      \     >:1-:v >\:v
O:8*'3-*'Q+/4/^     ^    _$^ *_$/7*\-

Try it online!

Next sequence!

To understand this monstrosity, you first need a quick primer on Funge:

• All variants of Funge are primarily stack based.
• The stack can only contain numbers.
• Befunge is a 2D language. While Trefunge is 3D, this code would work fine without the third dimension.
• <^>v are used to redirect execution exactly like you would expect.
• +-*/ do addition, subtraction, multiplication and division.
• Digits push the corresponding number on the stack
• The instruction pointer starts in the upper left corner pointing right.
• Space is a no-op
• " toggles stringmode. In stringmode, the ASCII code of each character is pushed on the stack

       v
>4      (
^"FRTH"<

You can see that immediately the execution is redirected on the string "FRTH". Because the execution goes right to left, 70 (F) is on the top of the stack. Then the number 4 is pushed and ( loads the fingerprint.

Fingerprints are similar to libraries from other languages, except they are not created in Funge, which would make them more of a language extension. Fingerprints change the semantics of the commands A through Z, which normally all act like r (reflect). You can load fingerprints using (, which more or less pops the number of characters the fingerprint code takes and then pops the characters themselves.

The FRTH fingerprint stands for FORTH, because it includes some useful stack manipulation primitives that originated from FORTH. This program uses the following of them:

• R - rotate. (... a b c) -> (... b c a)
• O - over. (... a b) -> (... a b a). Equivalent to 1P.
• P - push. Takes a number n and copies the element buried n elements deep to the top. For example, 2P would change the stack like this:
  (... a b c) -> (... a b c a)

   >51>R1-
(&:|  \
@.1<  +

After loading the fingerprint, & inputs a number and pushes it on the stack. : is used to duplicate it because | consumes one copy. | is the vertical conditional. If the number it consumed is zero, it's equivalent to v. Otherwise, it acts like ^.

It is used here because the input of zero needs to be a special case - the loop counter would immediately go negative making the loop infinite and OEIS claims that the formula only works for n > 4. If zero is passed, 1 is pushed, . is used to output it and @ ends the program.

You can also see here the beginning of the main loop of the program. The loop begins with R1- and ends with +\. The stack at the beginning of each iteration looks like this: i n a(n-1). i-1 is the number of repetitions the program will do, since it is decremented and compared at the beginning of the loop. n is the index in the sequence of the value we will be computing, while a(n-1) is the previous value. We implement this formula from the OEIS:

a(n) = (1/4)*(7*binomial(3*n-9, n-4)-(8*n^2-43*n+57)*a(n-1)) / (8*n^2-51*n+81)

Let's tackle the main loop itself:

R1-:v>RRO:
    >|
  @.$<

R brings i to the top. Funge doesn't have a decrement instruction, so we subtract 1 explicitly with -. We duplicate the new i with : for testing with |. If we're finished, we will hit the < and execute the following linear code:

$.@    The stack is now: n a(n-1) i
$      Discard i
 .     Output a(n-1)
  @    Exit.

In most cases, however, | will act like ^, which will make the interpreter execute this long stretch of linear code (ignoring the line wrap):

RRO:8*'+-*'9+*O3*9-2P4- The stack is now: n a(n-1) i
RR                      Bury i where it belongs. Stack: i n a(n-1)
  O:                    Copy n to the top and duplicate. Stack: i n a(n-1) n n
    8*                  Multiply by 8. Stack: i n a(n-1) n 8n
      '+                Use the ASCII value of + to push 43 on the stack
        -               Subtract 43. Stack: i n a(n-1) n 8n-43
         *              Multiply. Stack: i n a(n-1) 8n^2-43n
          '9+           Add 57. Stack: i n a(n-1) 8n^2-43n+57
             *          Multiply. Stack: i n (8n^2 - 43n + 57)*a(n-1)
              O         Copy n to the top. Stack: i n (...)*a(n-1) n
               3*9-     Compute 3n-9. Stack: i n (...)*a(n-1) 3n-9
                   2P4- Copy n to the top, compute n-4.
                        Stack: i n (...)*a(n-1) 3n-9 n-4. Notice how the top two
                        elements are the arguments for the binomial.

We will now compute the binomial(n, k) using the following algorithm which I've come up with myself a few sequences before, but it's probably not anything innovative, since it is obvious when you look at the formula. You can also see it in my Boo answer above.

• Multiply k numbers starting with n, going down
• Divide by the factorial of k

Let's only consider the very top of the stack when considering the algorithm.

v   ;>v;      <:R:
>R1-:|>\1-RO*\^
  \$$<

This is the part before computing the factorial. After :R:, the ; is a bridge, which skips the >v part.

   v   ;>v;      <
:R:>R1-:|>\1-RO*\^ Stack: n k
:                  Duplicate. Stack: n k k
 R                 Rotate. Stack: k k n
  :                Duplicate. Stack: k k n n. The bottommost k is used later.
                   The other k is the loop counter. The topmost n is the number
                   we're multiplying by, while the other n is the partial product.
   >               The loop starts here. Let's rename the variables and ignore
                   the bottom k. Stack: k product n
    R1-            Decrement k. Stack: product n k-1
       :|>         Exit the loop if k-1 is zero. Uses the >v part that is skipped
                   using a bridge
          \1-      Bring n to the top and decrement. Stack: product k-1 n-1
             R     Rotate. Stack: k-1 n-1 product
              O    Over. Stack: k-1 n-1 product n-1
               *   Multiply - extend the partial product.
                   Stack: k-1 n-1 (product)(n-1)
                \  Swap, restoring the stack to the order from the start of the
                   loop. Stack: k-1 (product)(n-1) n-1
                 ^ Jump to the beginning.

When the loop ends, we execute this:

$$\                Stack: k p n-k 0
$$                 Discard the top two elements, we only need the product
  \                Bring k to the top for computing the factorial. Stack: p k

Let's consider the factorial code:

v\0
>:1-:v >\:v
^    _$^ *_$

It consists of two loops. Let's consider the factorial of 4.

0\>:1-:v_$ Stack: 4
0\         Push the marker used in the second loop, swap. Stack: 0 4
  >        The loop starts here
   :1-     Duplicate and decrement. Stack: 0 4 3
      :v_  Duplicate for the comparsion, loop if not 0.
  >        Consider the loop again, with stack: 0 4 3 2 1
   :1-     Duplicate and decrement. Stack: 0 4 3 2 1 0
      :v_  Duplicate for the comparsion and exit the loop.
         $ Discard the top 0. Stack: 0 4 3 2 1

The second loop multiplies the numbers together, while 0 is marking the end.

>\:v_*  Stack: 0 4 3 2 1
>       The loop starts here
 \      Swap. Stack: 0 4 3 1 2
  :v_   If the top element is 0, end the loop
     *  Multiply. Stack: 0 4 3 2
>       Consider the loop again, with stack: 0 4 6
 \      Swap. Stack: 0 6 4
  :v_   (doesn't end the loop)
     *  Multiply. Stack: 0 24
>       Finally, let's see how the loop terminates.
 \      Swap. Stack: 24 0
  :v_   Ends the loop. Stack: 24 0

Let's finish the main loop, since it now consists of only linear code. It is useful to see the formula while following the code:

a(n) = (1/4)*(7*binomial(3*n-9, n-4)-(8*n^2-43*n+57)*a(n-1)) / (8*n^2-51*n+81)

Let's mark the numerator x and the denominator y, to simplify the description.

a(n) = (1/4)*x/y

Keep it mind that when the instruction pointer hits the edge of the Fungespace, it wraps around.

$/7*\-O:8*'3-*'Q+/4/\1+\ Stack: i-1 n (...)*a(n-1) p k! 0
$                        Discard the 0 marker from the factorial loop.
 /                       Divide to compute the binomial.
                         Stack: i-1 n (...)*a(n-1) binomial(3n-9 n-4)
  7*                     Multiply by 7. Stack: i-1 n (...)*a(n-1) 7*binomial
    \-                   Swap and subtract. Stack: i-1 n 7*binomial-(...)*a(n-1)
      O:                 Over, duplicate. Stack: i-1 n x n n
        8*               Multiply by 8. Stack: i-1 n x n 8n
          '3-            Subtract 51. Stack: i-1 n x n 8n-51
             *           Multiply. Stack: i-1 n x 8n^2-51n
              'Q+        Add 81. Stack i-1 n x 8n^2-51n+81
                 /       Divide. Stack: i-1 n x/y
                  4/     Divide by 4. Stack: i-1 n a(n)
                    \1+\ Increment n. Stack: i-1 n+1 a(n), or as the next
                         iteration would call it: i n a(n-1)

Answer 22

253. MIT/GNU Scheme, 1516 bytes, A000251

(define (add f g)
  (stream-map + f g) )

(define (sub f g)
  (stream-map - f g) )

(define (scale c f)
  (stream-map (lambda (v) (* c v)) f) )

(define (adddiag sf)
  (let ((f0 (stream-first sf)))
    (cons-stream (stream-first f0)
                 (add (stream-rest f0) (adddiag (stream-rest sf))) ) ) )

(define (mult f g)
  (adddiag (stream-map (lambda (v) (scale v g)) f)) )

(define (prependzeros n f)
  (if (= 0 n) f (cons-stream 0 (prependzeros (-1+ n) f))) )

(define (intersperse f n)
  (cons-stream (stream-first f)
               (prependzeros n (intersperse (stream-rest f) n)) ) )

(define (iterate fun init)
  (cons-stream init (iterate fun (fun init))) )

(define (from n)
  (iterate 1+ n) )

(define (scanl fun init s)
  (cons-stream init (scanl fun (fun init (stream-first s)) (stream-rest s))) )

(define (expx f)
  (cons-stream 1
               (adddiag (stream-map (lambda (s g) (scale (/ 1 s) g))
                                    (scanl * 1 (from 2))
                                    (iterate (lambda (g) (mult f g)) f) )) ) )

(define (eu f)
  (expx (adddiag (stream-map (lambda (n) (scale (/ 1 n)
                                                (intersperse f (-1+ n)) ))
                             (from 1) ))) )


(define ones
  (cons-stream 1 ones) )

(define s
  (iterate eu ones) )

(define r
  (stream-map sub (stream-rest s) s) )

(define t6
  (sub (stream-ref r 1)
       (cons-stream 0 (mult (stream-first r) (stream-ref s 1))) ) )

(define (f n)
  (stream-ref t6 (+ 6 n)) )

Next sequence

Use like this:

$ scheme -load t6.scm
MIT/GNU Scheme running under GNU/Linux
[...]
1 ]=> (f 49)

;Value: 1110994054004

This answer is based on generating functions given in J. Riordan's paper The Enumeration of Trees by Hight and Diameter mentioned at the OEIS entry of the sequence. Equation numbers will refer to this paper.

First, let s_h(x) be the counting generation function of rooted trees with height at most h by number of nodes, i.e. the coefficient of x^n will give the number of such trees with n nodes. All our generating functions will count by number of nodes in this way.

We can get one such function from the previous by eq. (1):

s_{h+1}(x)=x*exp(s_h(x)+s_h(x^2)/2+s_h(x^3)/3+...)

This is a shifted Euler transformation, which makes sense: the transformation takes a series a_0=0, a_1, a_2... where the a_i tell in how many ways you can get a thing of size/weight/whatever i and gives a series b_0=1, b_1, b_2... where b_j tells in how many ways you can get a multiset of such things with total size/weight/... of j. A rooted tree of height at most h+1 corresponds to a bunch (multiset) of rooted trees of hight at most h, with all their roots connected to a new root, which explains the shifting (multiplication with x).

My function eu (I'm reusing a big part of my solution No. 122) to compute the Euler transformation takes a sequence starting with a_1 and returns a sequence starting with b_0. If we keep our sequences starting with the coefficient of x, we just need to iterate the eu function and the shifting is automatic. The code defines s as infinite stream of s_h (the highest we need is s_3, but it is still simpler like this), where we could start with s_0(x)=x, or even s_{-1}(x)=0, but we start with s_1(x)=x/(1-x)=x+x^2+x^3+.... BTW, s_2 is almost the generating function for the partition numbers, just shifted.

Next, let r_h(x) be the generating function for rooted trees with height exactly h. Obviously, we have r_h(x)=s_h(x)-s_{h-1}(x). The code defines r to be the stream of these r_h, starting with r_2.

Finally, let t_d(x) be the generating function for trees of diameter d. For even d, thos can be expressed by eq. (6a) as

t_{2d}(x) = r_d(x) - r_{d-1}(x)*s_{d_1}(x)

The paper derives this formula algebraically from some other, but it can also be seen directly by comparing coefficients. For fixed d and n it claims that there are as many rooted trees of height d and with n nodes, as there are elements in the disjoint union of (1) trees of diameter 2d and with n nodes, and (2) pairs of rooted trees of height d-1 and of rooted trees of height at most d-1, where the pair has a total number of n nodes. This can be shown by a bijection: given a rooted tree of height d, remove the root and look at the multiset of subtrees you get. At least one of them has height d-1. If there are more than that, then the original tree was of diameter 2d. So forget the root and map it to this tree. Otherwise, form a pair with the one subtree of size d-1, and a tree of size at most d-1 that is created by rejoining the other subtrees with a new root. (Details are left as an exercise to the reader...)

The code directly defines t_6 according to this formula. Since we kept the generating functions starting with x while the multiplication function expects series starting with the constant term, the result must be interpreted as starting with the coefficient of x^2. To compensate, we put a 0 in front of it.

And if you ever need to enumerate trees with odd diameter, their generating function is given by eq. (5) as

t_{2d+1}(x) = (r_d^2(x)+r_d(x^2))/2

Answer 23

259. Hy, 1333 bytes, A000329

(setv precision 80)

(import decimal)

(setv ctx (.getcontext decimal))
(setv ctx.prec precision)
(setv Decimal decimal.Decimal)

(defn approx-pi [series-terms]
  (sum
    (list-comp
      (/ (- (/ 4 (Decimal (+ 1 (* 8 n))))
            (/ 2 (Decimal (+ 4 (* 8 n))))
            (/ 1 (Decimal (+ 5 (* 8 n))))
            (/ 1 (Decimal (+ 6 (* 8 n)))))
         (** 16 n))
      (n (range series-terms)))))

(setv pi (approx-pi precision))

(defn cos [x series-terms]
  (cond
    [(>= x (* 2 pi))
     (cos (- x (* 2 pi)) series-terms)]
    [(neg? x)
     (cos (- x) series-terms)]
    [(>= x (/ (* 3 pi) 2))
     (cos (- (* 2 pi) x) series-terms)]
    [(>= x pi)
     (- (cos (- x pi) series-terms))]
    [(>= x (/ pi 2))
     (- (cos (- pi x) series-terms))]
    [True
     (sum
       (list-comp
         (*
           (if (even? n) 1 -1)
           (reduce *
             (list-comp
               (/ x (inc i))
               (i (range (* 2 n))))
             1))
         (n (range series-terms))))]))

(defn tan [x series-terms]
  (/
    (cos (- x (/ pi 2)) series-terms)
    (cos x series-terms)))

(setv bvalues {0 (Decimal 1)})

(defn b [n]
  (try
    (get bvalues n)
    (except [KeyError]
      (do
        (assoc bvalues n (tan (b (dec n)) precision))
        (get bvalues n)))))

(defn A000329 [n]
  (int (round (b n))))

Next sequence

The difficulty with this sequence is that it's an iterated function, which means that small floating-point errors are magnified as n increases. So we need very accurate numbers. Enter Python's decimal module, which supports arbitrary-precision decimal arithmetic!

Because the decimal module doesn't seem to have trig functions, I reimplemented pi and cos. To calculate pi, I used the series approximation here, which converged pretty fast. For cosine, I used the MacLaurin series. Then I implemented tan as sine over cosine, with sin(x) = cos(x - pi/2).

Finally, I used the definition of A000329 from OEIS: "Nearest integer to b(n), where b(n) = tan(b(n-1)), b(0) = 1." I memoized the definition of b--not really necessary, but speeds up the generation of tables of values. Some experimentation showed that a decimal precision of 80 was sufficient to correctly compute n = 1000.

Now, of course, Python itself has already been used in this challenge, so the next task was to find a Python-based language that hadn't been used yet. I found Hy, which is basically Python with Lisp syntax. One translation, new Ubuntu VM, and language installation later, and voilà!

Answer 24

233. Hexagony, 141 bytes, A000332

    ? } = & \
   . . @ } ( .
  ( . . . _ . .
 . } . . 2 & . .
. . * . 4 . { . .
 . . ' \ ' \ * . 
  . . ( . : . "
   . . { ! . .
    . . * . .

Try it online!

Next sequence!

Note: due to problems with remembering to check whether a bytecount was used before (to be clear: in this case, not by me), this answer has changed 2 times in total, with each of the 3 programs having a full explanation. Check the revision history if you want.

Explanation

There's practically no control flow here. The code has one, constant execution path. It starts at the top left corner going right, gets reflected by multiple mirrors, wraps around a few times and passes through unrelated instructions after printing the result to end at the @ (I'm sorry) in the second row. For reference, here's a picture of the execution path, with a color change every time it hits a mirror. I also changed the color during a long stretch of instructions on the bottom left to make the wraparound clear.

The code operates on 3 memory edges: let's call the one we start on A, the one to the left of it - L, and the one to the right of A - R. binomial(n, 4) can be evaluated with the formula n(n-1)(n-2)(n-3)/24, which is imminent if you think about it, and a similar one could be created for every constant value of the bottom argument. Let's consider the linear path the code takes:

?}=&(}=*{('*}("*{&24':!*=@
?                          Input integer. A = n
 }=&                       Move to the R edge and copy the value of n. R = n
    (                      Decrement. R = n - 1
     }=                    Move to the L edge.
       *                   L = A * R = n(n-1)
        {(                 Move to the R edge and decrement. R = n - 2
          '                Equivalent to ={=, move to the A edge.
           *               A = L * R = n(n-1)(n-2)
            }(             Move to the R edge and decrement. R = n - 3
              "            Equivalent to =}=, move to the L edge.
               *           L = A * R = n(n-1)(n-2)(n-3)
                {&         Move to the R edge and set it to 0 using an edge that
                           hasn't been used before
                  24       Set the value of the R edge to 24. A digit in Hexagony
                           multiplies the edge value by 10 and adds its value to
                           it, which allows chaining them to create multi-digit
                           numbers, but requires the value of the edge to be 0
                    '      Equivalent to ={=, move to the A edge
                     :     A = L / R = n(n-1)(n-2)(n-3)/24 = a(n)
                      !    Print the result
                       *=  Instructions that happen to be in the execution path
                           and not disrupt it
                         @ End the program

Answer 25

81. Röda, 290 bytes, A000140

fact n {
  b = 2
  x = 0
  while [ n > 0 ] do
    x += n % b
    n = floor(n / b)
    b += 1
  done
  return x
}

A000140 n {
  x = 1; q = n; while [ q > 0 ] do x *= q; q -= 1; done
  t = 0
  while [ x > 0 ] do
    x -= 1
    t += 1 if [ fact(x) = floor(n * (n-1) / 4) ]
  done
  return t
}

Try it online!

Next sequence

Each item in A000140 is the largest number of permutations of a length-n array all having the same inversion count. This may sound daunting, but it's really not. Here's the table of possible inversions for n = 3:

    [inv. table]  [permutation]  inversion count
0:     [ 0 0 ]      [ 0 1 2 ]    0
1:     [ 1 0 ]      [ 1 0 2 ]    1
2:     [ 0 1 ]      [ 0 2 1 ]    1
3:     [ 1 1 ]      [ 2 0 1 ]    2
4:     [ 0 2 ]      [ 1 2 0 ]    2
5:     [ 1 2 ]      [ 2 1 0 ]    3

1 permutation has zero inversions, 2 permutations have one inversion each, 2 others have two inversions each, and 1 has three. The maximal number of permutations with x inversions is 2, shared by x = 1 and x = 2, so the output is 2.

Now don't get concerned; we don't have to calculate all permutations of a length-n array. You may have noticed that each inversion table (in the second-to-left column) sums to the number of inversions of that permutation. Also, it turns out calculating the sum of the inversion table for a permutation index k is remarkably simple: just convert k to the factorial base and sum the digits. Examples:

 k: [fact. digits]  sum
 0: [          0 ]  0
 1: [          1 ]  1
 2: [        1 0 ]  1
 3: [        1 1 ]  2
 4: [        2 0 ]  2
 5: [        2 1 ]  3
 6: [      1 0 0 ]  1
 7: [      1 0 1 ]  2
 8: [      1 1 0 ]  2
...
22: [      3 2 0 ]  5
23: [      3 2 1 ]  6
24: [    1 0 0 0 ]  1
25: [    1 0 0 1 ]  2
...

This sequence itself is A034968. So to calculate the n-th term in A000140, all you have to do is find the x that appears the most often in the first n! terms of the factorial digit sum sequence, then return how many times x appears. And you don't even have to find x manually: the OEIS page mentions that it's always floor(n(n-1)/4).

After I made all of these realizations, implementing it was a piece of cake. The hardest part was learning how Röda itself works, but that was a fun challenge in itself. Thanks @fergusq for the nice language :-)

Answer 26

344. Proton, 301 bytes, A000382

p = a => {
	if len(a) == 1 return [a]
	values = []
	for i : 0 .. len(a)
		for j : p(a[to i] + a[i + 1 to])
			values.append([a[i]] + j)
	return values
}

a = n => {
	total = 0
	n += 4
	for j : p(0 .. n)
		if all((j[i] - i) % n < 4 for i : 0 .. n)
			total++
	return total
}

print(a(int(input())) / 4)

Try it online!

Next sequence.

This code takes a long time on n = 2 and I don't want to try testing it on larger cases :P In theory, it works for all cases; the code is an exact implementation of the sequence description, so no fancy math stuff that could break.

Inefficient Coding 101 with hyper-neutrino \o/

(this is intentionally posted from my bot account. someone downvoted one of my posts and now I only have 19 reputation, which isn't enough to chat. and also I'm not going to go upvote it with my main account because that's evil, so I'm making a new post to earn some reputation, hopefully)

Answer 27

336. Pip, 159 bytes, A000620

b:[1]
c:[1]
Fi1,a+1{
 d:0
 e:2*(i%3%2)*c@(i/3)
 Fj,i{
  Fk,i-j{
   Ij=k{ d+:b@j * b@(i-j-k-1) }
   e+:c@j * c@k * c@(i-j-k-1)
  }
 }
 bAE:d
 cAE:e//3
}
c@v-b@v

Online demo

Next sequence

---

Basically this uses A000620 = A000625 - A000621 and the generating function relations for A000625 and A000621. I'm no chemist, but by the power of species theory I think I can reverse engineer the logic behind the g.f. relations, at least for one interpretation of the sequences. We're interested in monosubstituted alkanes, which correspond to graphs which are trees where every node has valence 4 (carbon atom) or 1 (either hydrogen atom or the substituted part, X).

In other words, modulo the trivial cases, we have a marked carbon atom which is attached to X:

   X
   |
a--C--b
   |
   d

The 3D geometry is relevant to the symmetries. The carbon atom is at the centre of a tetrahedron, and the other four elements are at the four vertices. Rotating around the axis CX doesn't change the molecule, so we'll need to avoid double-counting.

Note that if we consider the diagram from the perspective of e.g. a, the rest of the diagram (CXbd) can be considered as an X, and that's the heart of the recurrence logic.

If we ignore all restrictions and symmetry then by elementary species theory we have a generating function with recurrence \$F(x) = 1 + xF(x)^3\$. The \$1\$ corresponds to the special case that there's one molecule with 0 carbon atoms (X); the \$xF(x)^3\$ says that a molecule with \$n\$ carbon items can be identified with a molecule with one (\$x^1\$) identified carbon atom and then the remaining \$n-1\$ carbons are supplied by three smaller instances of the same type of object (a, b, d).

A000621 counts the non-stereoisomeric molecules. That means that they're symmetric: a = b, and all of a, b, d are non-stereoisomeric¹. That gives generating function \$G(x) = 1 + xG(x)G(x^2)\$. The \$x\$ corresponds to the identified carbon atom C; the \$G(x)\$ corresponds to d; and the \$G(x^2)\$ corresponds to a and b being equal. (It uses \$x^2\$ to count each carbon atom in a twice).

A000625 counts all molecules under the rotational symmetry about the axis CX. If a, b, d are all different then there are three rotational positions, so we need to divide by 3; if two of them are the same then there are still three rotational positions; if all three are the same then there is only one rotational position, so we don't want to divide by three. We have g.f. \$H(x) = 1 + \frac13 xH(x)^3 + \frac23 xH(x^3)\$ where the final term is to bring the weight of the case where a=b=d back up from \$\frac13\$ to \$1\$.

---

¹ Actually the choice that a = b is arbitrary, but works out nicely. We could alternatively consider the cases a = d and b = d as well, but then we have to divide by 3 to account for the symmetry.

Answer 28

4. Jelly, 2 bytes, A000038

ṆḤ

Try it online!

Next Sequence

Answer 29

19. Curry, 45 bytes, A000037

f n=[x|x<-[1..],notElem x [y*y|y<-[1..x]]]!!n

Try it online

Next sequence

Answer 30

20. cQuents, 15 bytes, A000045

$0=0,1:z+y)))))

$0 means 0-indexed, =0,1 means it starts with 0,1, : means if given n it returns the nth item in the sequence, z+y means each item is the previous two added together. ))))) are no-ops due mostly to interpreter bugs.

Try it online!

Next sequence