94
\$\begingroup\$

As of 13/03/2018 16:45 UTC, the winner is answer #345, by Scrooble. 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 , 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 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>

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Dennis Oct 31 '17 at 2:49
  • \$\begingroup\$ Is it OK if a program would need a better floating-point accuracy for the builtin float/double type in order to produce values for larger n? \$\endgroup\$ – NieDzejkob Nov 21 '17 at 15:15
  • 1
    \$\begingroup\$ @Giuseppe No, as you're generating the numbers by doing the maths, rather than just placing them into an array/string \$\endgroup\$ – caird coinheringaahing Dec 15 '17 at 22:14
  • 2
    \$\begingroup\$ @cairdcoinheringaahing In my opinion that's hardcoding the gamma constant. It doesn't work "in theory" for larger numbers. \$\endgroup\$ – user202729 Dec 22 '17 at 12:44
  • 6
    \$\begingroup\$ Chat room \$\endgroup\$ – user202729 Dec 22 '17 at 12:45

346 Answers 346

7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

250. Coconut, 711 bytes, A000171

from collections import Counter
from math import gcd, factorial

def sparts(n, m=4):
  if n%2==1:
    return [ [1] + p for p in sparts(n-1) ]
  elif n==0:
    return [ [] ]
  elif n<m:
    return []
  else:
    return [ [m] + p for p in sparts(n-m,m) ] + sparts(n,m+4)

def ccSize(l) =
  centSize = [ val**mult * factorial(mult)
               for val, mult in Counter(l).items() ] |> reduce$(*)
  factorial(sum(l)) // centSize

def edgeorbits(l) =
  samecyc = sum(l) // 2
  diffcyc = sum ([ gcd(l[i],l[j])
                   for i in range(len(l)) for j in range(i) ])
  samecyc + diffcyc

def a(n) =
  sum ([ ccSize(l)*2**edgeorbits(l)
         for l in sparts(n)         ]) // factorial(n)

def f(n) = a(n+1)

Try it online!

Next sequence

This can easily compute more values than the 31 that OEIS has.

Once again we have a symmetric group acting on nodes, inducing an action on the set of possible edges and on graphs. It acts on the set of self-complementary graphs, but I don't see how to count how many of these are fixed by a given permutation to apply the lemma that is often named after Burnside. So instead I use the formula in the comment of the OEIS entry that says that the number of self-complementary graphs with n nodes is equal to the difference of the number of graphs with n nodes with an even number of edges and with an odd number of edges. The symmetric group acts on these sets of graphs as well. Instead of computing both numbers independently, we will consider the cases of an even number and an odd number of edges in parallel, which will turn out to be simpler and allow optimizations. We'll see that "evaluate the graph polynomial at -1" will lead to the same result.

As usual, we take the sum over the group elements in Burnside's lemma conjugacy class wise, and represent the conjugacy classes by partitions of n. For each conjugacy class, we want to know the difference between the numbers of graphs with an even and odd number of edges that is fixed by a permutation from that class.

Assume we are given a concrete permutation g. The group generated by g acts on the set of possible edges and partitions them into orbits. A graph is fixed by g if for each orbit, it contains either all or none of its edges. Let's look at the orbits. Each edge in one orbit has its endpoints in the same two (possibly same) cycles of g.

Let's first assume the endpoints are from the same cycle of length k>=2. If k is odd, then there are (k-1)/2 orbits of length k. If k is even, then there are k/2-1 orbits of length k and one of length k/2 (for example, if g contains the cycle (123456), then the there is an edge orbit of size 3 containing {1,4}). Note that we get all orbits of even size exactly when k is a multiple of four.

Next consider the case that the endpoints are from different cycles of lengths k and l. Then the orbit has size lcm(k,l), and there are gcd(k,l) such orbits.

In order to combine all the possibilities, consider the product, for each edge orbit, of 1+x^r, where r is the size of the corresponding orbit. The coefficient of x^s of the product gives the number of graphs that are fixed by g and have s edges. We want the sum of the coefficients at even exponents minus the sum of them at odd coefficients, which we get by evaluating the polynomial at x=-1.

If we kept the polynomials and added them together, we'd get the graph polynomial. Instead, we don't even create these polynomials, but do the substitution immediately. For an edge orbit of even size, we get a factor of 2, for an odd size we get 0. (There is also a direct combinatorial argument that if there is an edge orbit of odd size then there are as many fixed graphs with an even number of edges as there are with an odd number of edges. And the factor 2 corresponds to the choice of including the edges of one orbit to the fixed graph or not).

So, by the considerations about edges with points from only one cycle, we get a difference of 0 whenever g contains a cycle of odd length greater than one, or a cycle of even length not divisible by four. We also get a difference of 0 whenever g contains at least two fixed points (cycles of length one).

This means we only need to sum over conjugacy classes with at most one fixed point and all other cycle lengths multiples of four. sparts computes the corresponding partitions of n. There are none unless n is of the form 4k or 4k+1, so in the other cases there are no self-complementary graphs, which can also easily seen by noting that in these cases the total number of possible edges is odd. But this observations alone doesn't lead to the optimization of only considering special partitions, of which there are only as much as there are partitions of k.

ccSize computes the size of a conjugacy class with given cycle lengths. edgeorbits computes the number of edge orbits of the action of the group generated by a permutation with the given cycle lengths, assuming they are of the special form. In the general case, samecyc, the number of edge orbits with edges that have both nodes from the same cycle, could not be calculated like this. (When I wrote the code, I didn't notice that it only depends on n in the relevant cases.)

a puts everything together, and f fixes the different indexing.

\$\endgroup\$
  • \$\begingroup\$ This looks like Python with a touch of JavaScript added :P \$\endgroup\$ – caird coinheringaahing Nov 12 '17 at 19:07
  • \$\begingroup\$ @ChristianSievers I'm stupid. Anyway, don't forget that some PPCGers have OEIS accounts and could add more values to A000171 :) \$\endgroup\$ – Stephen Nov 12 '17 at 21:38
  • \$\begingroup\$ @Stephen I consider doing that \$\endgroup\$ – Christian Sievers Nov 12 '17 at 22:11
  • \$\begingroup\$ Can you explain what algorithm are you using and/or what does the abbreviated function names (sparts, ccSize) means? \$\endgroup\$ – user202729 Nov 13 '17 at 14:17
  • \$\begingroup\$ @user202729 I finally added some explanation. \$\endgroup\$ – Christian Sievers Nov 15 '17 at 18:18
7
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Could you please add a link to the next sequence in order to help the next answerer? \$\endgroup\$ – caird coinheringaahing Nov 25 '17 at 1:10
  • \$\begingroup\$ Personally I find the recurrence relation somewhat magical. \$\endgroup\$ – user202729 Nov 25 '17 at 13:39
  • \$\begingroup\$ I think I know how to calculate the next sequence, but I don't know how to enumerate unrooted trees without duplicates, so I'll leave this here: for brevity, let's define a branch as a non-leaf element of a tree. The value of the sequence for the index n is the sum of "scores" of all unrooted ternary trees with n branches. The score of a tree is defined as c² – c + d, where c is the number of branches with at least one leaf, and d is the number of branches with at least two leaves \$\endgroup\$ – NieDzejkob Nov 27 '17 at 7:55
  • \$\begingroup\$ Clarification: the trees are unordered and unlabelled \$\endgroup\$ – NieDzejkob Nov 27 '17 at 9:42
  • \$\begingroup\$ Honestly I didn't look at the next sequence at all. But there's a g.f. in terms of A000642 which in turn has a g.f. in terms of A000598 which can be defined by positive integer solutions for a polynomial. I haven'z checked that, but if it's true, it should be fairly easy to implement in most languages. And I just noticed A000642 has a Mathematica implementation and A000598 has a Maple solution. So it should be definetely possible. \$\endgroup\$ – PattuX Nov 27 '17 at 19:20
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ minor nit: you can always make the next sequence the lowest uncovered one by adding 300,000 bytes of padding. \$\endgroup\$ – pppery Sep 26 '17 at 20:48
7
\$\begingroup\$

318. Funciton, 1688 bytes, A000652

╔═══╗  ┌─────────╖  ┌─┐ ┌───╖  ╔═══╗
║   ╟──┤ str→int ╟──┤ └─┤ ↑ ╟──╢ 2 ║
╚═══╝  ╘═════════╝  │   ╘═╤═╝  ╚═══╝
  ┌─────────────────┘     │
┌─┴┐                      │
│┌─┴─╖                ┌───┴───┐
││ ♭ ║              ┌─┴─╖   ┌─┴─╖  
│╘═╤═╝┌───╖    ╔═══╗│ ♭ ║   │ ! ║  
│  └──┤ ↑ ╟────╢ 2 ║╘═╤═╝   ╘═╤═╝
│     ╘═╤═╝    ╚═╤═╝  │       │
│    ┌──┴─┐      │    └───┐   │
│  ┌─┴─╖  │┌───╖ │  ┌───╖ │   │
│  │ ! ║  └┤ ↑ ╟─┴──┤ ↑ ╟─┘   │
│  ╘═╤═╝   ╘═╤═╝    ╘═╤═╝     │
│    │ ┌───╖ │   ┌───╖│       │
│    └─┤ × ╟─┘ ┌─┤ × ╟┘       │
│      ╘═╤═╝   │ ╘═╤═╝ ┌───╖  │
│  ╔═══╗ └─────┘   └───┤ + ╟──┘
│  ║ 2 ╟┐              ╘═╤═╝
│  ╚═╤═╝│        ┌───╖   │
│    │  └──┐   ┌─┤ ÷ ╟───┘
│    └──┐┌─┴─╖ │ ╘═╤═╝┌─────────╖
│ ┌───╖ ││ ↑ ╟─┘   └──┤ int→str ╟─
└─┤ × ╟─┘╘═╤═╝        ╘═════════╝
  ╘═╤═╝    │
    └──────┘

Next Sequence

Calculates the formula from the OEIS page. I'm sure there's a more compact way to do this, without multiple 2 constants, but this took me long enough.

Try it online!

\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Gosh darn it, I was playing around with f=lambda n,r=1:n*(n<3)or 3-f(n-f(r),r+1) for around 40 bytes (works except f(3) is omitted), but my internet decided to bug out while I was playing around on TIO \$\endgroup\$ – ETHproductions Jul 21 '17 at 15:46
  • \$\begingroup\$ I don't get what this sequence is about at all. Could someone explain it simply? \$\endgroup\$ – geokavel Jul 21 '17 at 15:47
  • 1
    \$\begingroup\$ @geokavel See this challenge \$\endgroup\$ – Mr. Xcoder Jul 21 '17 at 15:49
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Next sequence is...? \$\endgroup\$ – Mr. Xcoder Jul 21 '17 at 19:20
  • \$\begingroup\$ How are we supposed to do an erroneous sequence? \$\endgroup\$ – MD XF Jul 21 '17 at 19:20
  • \$\begingroup\$ C'mon, you left us with the broken one??? \$\endgroup\$ – HyperNeutrino Jul 21 '17 at 19:21
  • \$\begingroup\$ Fixing........... \$\endgroup\$ – Conor O'Brien Jul 21 '17 at 19:21
  • \$\begingroup\$ Please change this one's byte cont, because the next one is broken \$\endgroup\$ – Mr. Xcoder Jul 21 '17 at 19:21
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ How does it work? \$\endgroup\$ – Leaky Nun Jul 22 '17 at 4:25
  • \$\begingroup\$ @LeakyNun a(0)=0, a(1)=1, ..., a(19)=43945441. For n>19, a(n)=39202*a(n-10)+a(n-20). It is based on the MAGMA code on OEIS. \$\endgroup\$ – alephalpha Jul 22 '17 at 4:39
6
\$\begingroup\$

39. Add++, 1 byte, A000004

O

Try it online!

Next sequence

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ The partitions don't stop, do they? \$\endgroup\$ – tomsmeding Jul 23 '17 at 15:47
  • \$\begingroup\$ Solution to the next one \$\endgroup\$ – BlackCap Jul 23 '17 at 16:29
  • 1
    \$\begingroup\$ I'd just let g x n|x<0=0 | otherwise =1+sum(takeWhile(>0)([g(x-sqrt k)k|k<-[n..]])) and call g(n+1)1 - 1. BTW, I wonder how to do it without relying on floating point arithmetics. \$\endgroup\$ – Christian Sievers Jul 23 '17 at 16:55
6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Wellp, I'll be waiting for 81 oeis.org/A000140 hah. \$\endgroup\$ – Magic Octopus Urn Jul 24 '17 at 19:26
  • \$\begingroup\$ @MagicOctopusUrn It's actually not that hard. If you understand Jelly, it's just !ḶÆ!S€ĠL€Ṁ \$\endgroup\$ – ETHproductions Jul 24 '17 at 20:53
  • \$\begingroup\$ @ETHproductions was looking to do an 05AB1E entry :P. \$\endgroup\$ – Magic Octopus Urn Jul 24 '17 at 21:07
6
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wow, what's that? So colourful! \$\endgroup\$ – Christian Sievers Sep 1 '17 at 14:09
  • \$\begingroup\$ This is Emojicode, the only serious programming language that's bursting with emoji! Stay tuned for the explaination. \$\endgroup\$ – NieDzejkob Sep 1 '17 at 14:15
  • \$\begingroup\$ @ChristianSievers I just thought I'd notify you that now you can learn this beautiful, superior language on my example. \$\endgroup\$ – NieDzejkob Sep 1 '17 at 14:53
6
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice! @HyperNeutrino Did you find out what was the problem with the lean fish graph? \$\endgroup\$ – J. Sallé Oct 18 '17 at 14:05
  • \$\begingroup\$ @J.Salle user202729 pointed it out to me; my isValid function didn't work because one of the cycles didn't have any vertices with order 2 because rather than disconnecting a single node, it split the graph. Credit goes to them, not me :) \$\endgroup\$ – HyperNeutrino Oct 18 '17 at 14:08
  • \$\begingroup\$ abstract interface makes me sad... and now it's immortalized here since you aren't allowed to change it... \$\endgroup\$ – Socratic Phoenix Oct 18 '17 at 14:09
  • 1
    \$\begingroup\$ @SocraticPhoenix Originally programmed by HyperNeutrino. \$\endgroup\$ – user202729 Oct 18 '17 at 14:11
  • 1
    \$\begingroup\$ I'm confused about how, for the next sequence, 0 is a sum of any NONZERO 10th powers, unless I'm totally misreading it... \$\endgroup\$ – Giuseppe Oct 18 '17 at 14:13
6
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ "nominator"? Should it be "numerator"? \$\endgroup\$ – user202729 Oct 28 '17 at 12:29
  • \$\begingroup\$ @user202729 You are right. That's what you get when you don't learn math in English... :P \$\endgroup\$ – NieDzejkob Oct 28 '17 at 12:30
  • \$\begingroup\$ Also can you add an explanation what is the sequence? \$\endgroup\$ – user202729 Oct 28 '17 at 12:58
  • \$\begingroup\$ @user202729 I totally would if my current understanding of this sequence aligned with the values given by the OEIS. \$\endgroup\$ – NieDzejkob Oct 28 '17 at 13:40
6
+100
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Cutting it a little close, don't you think? \$\endgroup\$ – KSmarts Nov 20 '17 at 14:09
  • 1
    \$\begingroup\$ Since just using some formula isn't very well recieved, I wanted to give time for other solutions. (But now I mostly understand what I do...) And I had to look for a free language, and initially didn't want to use scheme again. \$\endgroup\$ – Christian Sievers Nov 20 '17 at 14:31
  • \$\begingroup\$ There are reasonable hints towards eq. 5 in OEIS, but nothing towards eq. 6a. Did you find an electronic copy of the paper or did you have to go to a library? Either way, well done. \$\endgroup\$ – Peter Taylor Nov 23 '17 at 13:52
  • \$\begingroup\$ @PeterTaylor I went to a library. \$\endgroup\$ – Christian Sievers Nov 23 '17 at 14:02
6
\$\begingroup\$

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à!

\$\endgroup\$
6
\$\begingroup\$

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.

control flow diagram

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
\$\endgroup\$
6
\$\begingroup\$

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 :-)

\$\endgroup\$
  • \$\begingroup\$ NB for an efficient implementation, the first comment on A000140 points you at A008302, which has a nice recurrence. \$\endgroup\$ – Peter Taylor Jan 20 '18 at 10:26
5
\$\begingroup\$

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}
\$\endgroup\$
  • \$\begingroup\$ @cairdcoinheringaahing I don't know. Is that not allowed? \$\endgroup\$ – Sriotchilism O'Zaic Jul 21 '17 at 15:46
  • \$\begingroup\$ no its fine. I just thought that it could help the next answerer \$\endgroup\$ – caird coinheringaahing Jul 21 '17 at 15:51
5
\$\begingroup\$

4. Jelly, 2 bytes, A000038

ṆḤ

Try it online!

Next Sequence

\$\endgroup\$
  • 2
    \$\begingroup\$ Noo, Kolakoski.... \$\endgroup\$ – Mr. Xcoder Jul 21 '17 at 15:24
  • \$\begingroup\$ @Mr.Xcoder well that's why it's called a "challenge" \$\endgroup\$ – Erik the Outgolfer Jul 21 '17 at 15:24
  • 6
    \$\begingroup\$ I deleted this because I don't want to use Jelly just yet; so much for that \$\endgroup\$ – Stephen Jul 21 '17 at 15:25
  • \$\begingroup\$ And I even had f(x){return!x*2;} in ANSI C... \$\endgroup\$ – LegionMammal978 Jul 21 '17 at 15:26
5
\$\begingroup\$

19. Curry, 45 bytes, A000037

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

Try it online

Next sequence

\$\endgroup\$
  • \$\begingroup\$ ninja'd by 37 seconds >.< \$\endgroup\$ – HyperNeutrino Jul 21 '17 at 20:12
  • \$\begingroup\$ but you were ninja'd by 23 seconds rip \$\endgroup\$ – HyperNeutrino Jul 21 '17 at 20:13
5
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ To quote the OP: You must wait for at least 1 hour before posting an answer, after having posted. This makes your answer invalid; you can ask OP in chat but I believe this invalidates your answer. \$\endgroup\$ – HyperNeutrino Jul 22 '17 at 0:09
  • \$\begingroup\$ @HyperNeutrino My FiM++ answer was posted 22:28, this was posted 23:29 \$\endgroup\$ – BlackCap Jul 22 '17 at 0:13
  • \$\begingroup\$ My bad. It must've rounded down to "1 hour" which is why I thought your FiM++ answer was younger than it was. Sorry for the misunderstanding :) \$\endgroup\$ – HyperNeutrino Jul 22 '17 at 0:15
  • \$\begingroup\$ Reading through all answers here, and wondering how many essentially-haskell answers are coming still :p \$\endgroup\$ – tomsmeding Jul 23 '17 at 8:03
  • \$\begingroup\$ @tomsmeding I still have idris and elm left \$\endgroup\$ – BlackCap Jul 23 '17 at 8:28
5
\$\begingroup\$

29. JavaScript (SpiderMonkey), 46 bytes, A000009

f = function(n,q=1)n?n<q?0:f(n-q,q)+f(n,q+2):1

Try it online! The OEIS page is rather daunting, but after reading it for a while I realized that this boils down to the partitions problem, but using only odd integers. Change the q+2 to q+1 and you have a function that calculates the number of partitions of a number.

Next sequence. I tried hard to leave it off on an easy one, I really did...

\$\endgroup\$
  • \$\begingroup\$ Please put a "29." in your header. I think you're confusing the Stack Snippet. \$\endgroup\$ – Silvio Mayolo Jul 22 '17 at 1:00
  • \$\begingroup\$ @SilvioMayolo Ah sorry. This is my first time since #3, so I've already forgotten how to answer :P \$\endgroup\$ – ETHproductions Jul 22 '17 at 1:01
  • 4
    \$\begingroup\$ @SilvioMayolo he made the stack snippet :P \$\endgroup\$ – Stephen Jul 22 '17 at 2:37
5
\$\begingroup\$

35. dc, 67 bytes, A000168

?sw[1[li*li1-dsi0<o]soli0<o]se3lw^2*lw2*silex*lwsilexlw2+silex*/p0P

Try it online!

Next Sequence

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.