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

4
\$\begingroup\$

51. Burlesque, 8 bytes, A000026

fCf:FLpd

Try it online!

Next sequence

\$\endgroup\$
  • 1
    \$\begingroup\$ I swear we've already done the "partitions of N into 1,2,5,10" sequence... perhaps an answer got deleted though \$\endgroup\$ – ETHproductions Jul 22 '17 at 16:08
  • \$\begingroup\$ I thought so too @ETHproductions but I don't see it, probably a similar sequence \$\endgroup\$ – Stephen Jul 22 '17 at 16:13
4
\$\begingroup\$

52. Ceylon, 484 bytes, A000008

Integer f(Integer n) {
	variable Integer coin1 = 0;
	variable Integer coin2 = 0;
	variable Integer coin5 = 0;
	variable Integer coinT = 0;
	variable Integer count = 0;
	while (coin1 <= n) {
		while (coin2 <= n / 2) {
			while (coin5 <= n / 5) {
				while (coinT <= n / 10) {
					if (n == coin1 + 2 * coin2 + 5 * coin5 + 10 * coinT) {
						count++;
					}
					coinT++;
				}
				coin5++;
				coinT = 0;
			}
			coin2++;
			coin5 = 0;
		}
		coin1++;
		coin2 = 0;
	}
	return count; 
}

Try it online!

huehue I'm a Ceylon noob

Next Sequence (c'mon this is so easy)

\$\endgroup\$
4
\$\begingroup\$

55. ><>, 41 bytes, A000196

:1>::*$@(?vv
  ^ +1@@:$ <
          \1-n;

Try it online!

Next sequence

\$\endgroup\$
  • 1
    \$\begingroup\$ f=function(n,q=1){return n?n>=q?f(n-q,q)+f(n,q+1):0:1} solves A000041 in Node.JS, but it's an extremely trivial modification of another answer of mine so I don't know if I really want to post it... (also, A000054 is "Local stops on New York City A line subway", so...) \$\endgroup\$ – ETHproductions Jul 22 '17 at 16:54
4
\$\begingroup\$

57. Desmos, 119 bytes, A000138

f\left(n\right)=n!\sum _{i=0}^{\operatorname{floor}\left(\frac{n}{4}\right)}\frac{\left(-1\right)^i}{i!\cdot 4^I}

Try It Online!

Next Sequence

\$\endgroup\$
  • \$\begingroup\$ \operatorname? \$\endgroup\$ – BlackCap Jul 22 '17 at 17:49
  • \$\begingroup\$ Gosh darn it, ninja'd again... I had come up with q=n=>n?n*q(n-4)+(-n/4%2||1):1;f=n=>n?f(n-1)*(n%4?n:q(n)/q(n-4)):1 in JS which uses a similar technique \$\endgroup\$ – ETHproductions Jul 22 '17 at 17:50
  • \$\begingroup\$ @ETHproductions That seems to be a common theme with this challenge. I've had 3 other Desmos answers that just got beat out. \$\endgroup\$ – Scott Milner Jul 22 '17 at 17:50
  • \$\begingroup\$ @BlackCap Desmos auto-formats while you type. When you copy-paste, you get a bunch of TEX-like code, but it won't necessarily work in TEX. \$\endgroup\$ – Scott Milner Jul 22 '17 at 17:52
  • \$\begingroup\$ Pasting the equation directly in still works with f(n)=n!\sum _{i=0}^{floor(n/4)}(-1)^i/i!/4^i. Not that you should golf it now, but... \$\endgroup\$ – ETHproductions Jul 22 '17 at 18:09
4
\$\begingroup\$

21. M, 24 bytes, A000015

Ṫ*Ḣ
l2Rp²ÆR$µÇ€<³$ÐḟṂ
‘Ç

Try it online!

Next Sequence

Sorry for changing the next sequence; I had to fix my indexing.

Explanation

Ṫ*Ḣ                !!!!!!! Helper Link
Ṫ                  Last element
 *                 To the power of
  Ḣ                First element
l2Rp²ÆR$µÇ€<³$ÐḟṂ  !!!!!!! Main Link
l2R                Range up to log_2(input); this is the largest power we need to handle because 2**k will be at least `input` this way
   p               Cartesian Product with
    ²ÆR$           All primes up to `input squared`
        µ          New Monadic Link
         ǀ        Call the last link on each element (all prime powers)
              Ðḟ   Filter to discard
           <³$                       elements smaller than the input
                Ṃ  Minimum Value
‘Ç                 !!!!!!! Called Link
‘                  Decrement
 Ç                 Call the Main Link
\$\endgroup\$
4
\$\begingroup\$

58. 2sable, 11 bytes, A000119

<DÅFÙïæOrQO

Try it online!

<DÅFÙïæOrQO  Program
<            Decrement for 0-indexing
 D           Duplicate top of stack (for later use)
  ÅF         List of fibonacci numbers up to the current number
    Ù        Remove duplicates
     ï       Convert each element to an integer (they become strings for whatever reason ;_;)
      æ      Powerset
       O     Sum of each subset in the powerset
        r    Reverse stack (I don't think this is necessary, but 10 bytes isn't allowed anyway)
         Q   Equality check; vectorizes
          O  Gives number of occurrences; done

Next Sequence

\$\endgroup\$
  • \$\begingroup\$ Have we not had A11 already? \$\endgroup\$ – BlackCap Jul 22 '17 at 18:24
  • \$\begingroup\$ @BlackCap We had A46, which is similar, but is slightly different (they're very similar; you may remember me raging last night about not being able to get the definitions lol) \$\endgroup\$ – HyperNeutrino Jul 22 '17 at 18:25
4
\$\begingroup\$

62. S.I.L.O.S, 57 bytes, A000005

readIO
n=i
lblb
r=n%i
r/r
r=1-r
s+r
i-1
if i b
printInt s

Try it online!

Next Sequence


*LeakyNun asked me to post this, again.

\$\endgroup\$
4
\$\begingroup\$

68. Pascal (FPC), 761 bytes, A000837

function Mobius(n: integer): integer;
type
	iarray = array of integer;
var
	result: iarray;
	i, j, sum: integer;
begin
	setlength(result,n+1);
	result[1] := 1;
	for i := 2 to n do
	begin
		sum := 0;
		for j := 1 to i-1 do
			if (i mod j = 0) then
				sum := sum + result[j];
		result[i] := -sum;
	end;
	Mobius := result[n];
end;

function A000837(n: integer): integer;
type
	iarray = array of integer;
var
	partitions: iarray;
	i, j, sum: integer;
begin
	setlength(partitions,n+1);
	partitions[0] := 1;
	for i := 1 to n do
		for j := i to n do
			partitions[j] := partitions[j] + partitions[j-i];
	sum := 0;
	for i := 1 to n do
		if (n mod i = 0) then
			sum := sum + partitions[i] * Mobius(n div i);
	if (n = 0) then
		A000837 := 1
	else
		A000837 := sum;
end;

Try it online!

Next sequence

How it works

It generates the partitions using the trivial gf:

prod(q=[1,infty], 1/(1-x^q))

and then uses the Möbius Transform.

\$\endgroup\$
  • \$\begingroup\$ Anyone having the feeling that A000761(3) should be 464 instead of 468? \$\endgroup\$ – yoann Jul 23 '17 at 11:27
4
\$\begingroup\$

74. Racket, 77 bytes, A000363

(define(a n)(/(-(expt 5 n)(*(sub1(* 2 n))(expt 3 n))(* 2 n)2(-(* 2 n n)))16))

Try it online!

Next sequence

\$\endgroup\$
4
\$\begingroup\$

75. GolfScript, 36 bytes, A000077

~2\?):P.*,{.P/.*\P%.*6*+}%.&{P<},0-,

Online demo

Next sequence

\$\endgroup\$
  • \$\begingroup\$ This is similar to the GolfScript answer I was working on when an earlier answer was changed for no good reason. \$\endgroup\$ – Peter Taylor Jul 24 '17 at 6:19
4
\$\begingroup\$

82. Cubix, 14 bytes, A000290

....I:*....u@O

Try it online!

Next sequence

\$\endgroup\$
  • 1
    \$\begingroup\$ Finally Cubix gets in here :-) \$\endgroup\$ – ETHproductions Jul 24 '17 at 20:54
  • \$\begingroup\$ @ETHproductions I was in the midst of editing this one! thanks. As a note, this is actually a 6-byter but 6 was already taken. \$\endgroup\$ – Giuseppe Jul 24 '17 at 20:56
  • \$\begingroup\$ Dang, too slow for me \$\endgroup\$ – Brian J Jul 24 '17 at 21:00
4
\$\begingroup\$

95. Taxi, 478 bytes, A000027

Go to Post Office:w 1 l 1 r 1 l.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery:s 1 l 1 r.
Pickup a passenger going to Addition Alley.
1 is waiting at Starchild Numerology.
Go to Starchild Numerology:n 1 l 1 l 1 l 2 l.
Pickup a passenger going to Addition Alley.
Go to Addition Alley:w 1 r 1 l 1 r 3 r 1 r.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery:n 1 r 1 r.
Pickup a passenger going to Post Office.
Go to Post Office:n 1 l 1 r.

Adds 1 to the input, since this has to be 0-based.

Try it online!

Next Sequence

\$\endgroup\$
4
\$\begingroup\$

102. Perl 5, 158 bytes, A000335

@b[0]=1;
while($n++<=$ARGV[0]){
  for($d=1;$d<=$n;$d++){
    for($k=$d;$k<=$n;$k+=$d){@b[$n]+=$d*$d*($d+1)*($d+2)/6*@b[$n-$k]}
  }
  @b[$n]/=$n
}
print @b[-1]

Online demo. This is a full program which takes input as a command-line parameter.

Next Sequence

\$\endgroup\$
4
\$\begingroup\$

104. Vala, 267 bytes, A000713

static int main(string[] args) {
	int n = int.parse(stdin.read_line());
	int[] a = new int[n+1];
	a[0] = 1;
	for(int i=1;i<=n;i++){
		int iter = i==1?3:2;
		for(int j=0;j<iter;j++)
			for(int k=i;k<=n;k++) a[k] += a[k-i];
	}
	stdout.printf("%d\n", a[n]);
	return 0;
}

Try it online!

Next sequence.

Explanation

Uses the g.f. 1/[(1-x)^3 (1-x^2)^2 (1-x^3)^2 (1-x^4)^2 ...].

\$\endgroup\$
  • \$\begingroup\$ {a={s=[];b(it,it,s);return s.size()};b={n,m,p->if(!n){p<<0;return;};for(int i=Math.min(m,n);i>=1;i--){b(n-i, i, p);}};(0..it).sum{d->(0..d).sum{a(it)*a(d-it)}}} - so much wasted effort on my part :(. \$\endgroup\$ – Magic Octopus Urn Aug 14 '17 at 15:10
  • \$\begingroup\$ I implemented A000041 to implement A000712 to implement A000713 xD. \$\endgroup\$ – Magic Octopus Urn Aug 14 '17 at 15:12
4
\$\begingroup\$

114. Crystal, 1560 bytes, A000228

Dirs = [0,1,-1].permutations.to_a

def addhp(a,b)
  (0..2).map{ |i| a[i]+b[i] }
end

def hexh(n,use,seen,possible)
  if n==0
    testhex(use) ? 1 : 0
  else
    if possible.empty?
      0
    else
      elem = possible[0]
      remain = possible[1..-1]
      newseen = [elem]+seen
      c = hexh(n,use,newseen,remain)
      newpossible = Dirs.map{ |d| addhp(elem,d) }
      newpossible = newpossible.select \
         { |p| ! ((seen.includes? p) || (remain.includes? p)) }
      c + hexh(n-1,use+[elem],newseen,remain+newpossible)
    end
  end
end

def hex(n)
  empty = [] of Array(Int32)
  hexh(n,empty,empty,[[0,0,0]])
end

def rot(hl)
  hl.map{ |h| h.rotate }
end

def neg(hl)
  hl.map{ |h| h.map{ |v| -v } }
end

def mirr(hl)
  hl.map{ |h| [0,2,1].map{ |i| h[i] } }
end

def normhex(hl)
  x = hl.map{ |h| h[0] }.min 
  hl = hl.map{ |h| addhp(h,[-x,0,x]) }
  x = hl.map{ |h| h[1] }.min
  hl.map{ |h| addhp(h,[0,-x,x]) }
end

def check(shl,chl)
  ( shl <=> chl.sort ) == 1
end

def testonesided(hl,ohl)
  return false if check(hl,ohl)
  nhl = normhex(rot(ohl))
  return false if check(hl,nhl)
  nhl = normhex(rot(nhl))
  return false if check(hl,nhl)
  nhl = normhex(neg(ohl))
  return false if check(hl,nhl)
  nhl = normhex(rot(nhl))
  return false if check(hl,nhl)
  nhl = normhex(rot(nhl))
  return false if check(hl,nhl)
  true
end

def testhex(hl)
  hl = normhex(hl)
  return false if hl[0] != hl.min
  hl.sort!
  mhl = normhex(mirr(hl))
  testonesided(hl,hl) && testonesided(hl,mhl)
end

n = ARGV.size==1 ? ARGV[0].to_i : 7
puts "f(#{n}) = #{hex(n)}"

Next sequence

Try it online!

This is a full program that takes input from the command line and computes the value for n=7 if no argument was given, because that has a nice value. I don't really know this language, it may show. And I don't know how to give command line arguments to TIO, you may just replace the assignment to n in the line before the last one instead.

Strangely, it compiles fine (on old debian jessie using crystal's external debian repository) with crystal build hex.cr, but the optimizing call crystal build hex.cr --release fails with what seems to be an internal error.

\$\endgroup\$
  • 1
    \$\begingroup\$ partitions ಠ_ಠ \$\endgroup\$ – Business Cat Aug 18 '17 at 18:33
  • 2
    \$\begingroup\$ It seems to always output f(7) = 333 regardless of the input. (by the way, Crystal is on TIO) \$\endgroup\$ – Business Cat Aug 18 '17 at 18:36
  • \$\begingroup\$ Do you run it locally? I can use command line arguments just fine. But I have no idea how to give them with TIO. And I wonder how I did not see the language there. \$\endgroup\$ – Christian Sievers Aug 18 '17 at 18:50
  • \$\begingroup\$ @ChristianSievers I don't have it installed (and I'm on my work computer right now so I can't). I was trying to get it to work on TIO but I couldn't figure it out either, best I could tell it kept trying to open files named 6 or whatever I input. \$\endgroup\$ – Business Cat Aug 18 '17 at 18:53
  • \$\begingroup\$ @ChristianSievers see this comment from Dennis \$\endgroup\$ – Stephen Aug 18 '17 at 18:59
4
\$\begingroup\$

168. Python 2 (PyPy), 261 bytes, A000101

import sympy

def A000101(n):
  i = 0
  p = 2
  max_difference = 0
  while i <= n:
    next_p = sympy.nextprime(p)
    if next_p-p > max_difference:
      max_difference = next_p - p
      i = i + 1
    p = next_p    
  return p

print A000101(int(raw_input()))

Next Sequence

Try it online!

Others want to starve the challenge of the use of Python, so I'll help.

\$\endgroup\$
  • \$\begingroup\$ Might want to note that you use sympy somewhere. It's not in the standard library... \$\endgroup\$ – totallyhuman Sep 21 '17 at 16:43
4
\$\begingroup\$

174. C++ (gcc), 54 bytes, A000257

int f(int n){return n?~-~-~-~-(n<<3)*f(~-n)/-~-~n:01;}
  • Try it online!
  • Next sequence: A000054 :P
  • Alternative C solution (as C (clang) and C (gcc) are not considered to be different languages, even if Python interpreters are, I switched to C++)
\$\endgroup\$
  • 3
    \$\begingroup\$ What the hell is this next sequence... Wonder if Mathematica has a built-in \$\endgroup\$ – Grzegorz Puławski Sep 22 '17 at 12:19
  • \$\begingroup\$ Wasn't C already used before? \$\endgroup\$ – NieDzejkob Sep 22 '17 at 12:21
  • \$\begingroup\$ @NieDzejkob Every 150 (valid) answers, the number of times a language may be used increases. It was used once before my answer. \$\endgroup\$ – Jonathan Frech Sep 22 '17 at 12:22
  • 1
    \$\begingroup\$ @NieDzejkob The OP said C (gcc) and C (clang) are considered to be the same language, so I switched to C++. \$\endgroup\$ – Jonathan Frech Sep 22 '17 at 14:07
  • 1
    \$\begingroup\$ Given that CPython and PyPy are considered different languages, I have reverted that decision and am going to say that clang and gcc are different languages. Please don't change this answer however, this is just for future reference. \$\endgroup\$ – caird coinheringaahing Sep 22 '17 at 17:43
4
\$\begingroup\$

185. Octave, 17 bytes, A000142

@(n)factorial(n);

Try it online!

Next sequence

\$\endgroup\$
  • 3
    \$\begingroup\$ Next sequence just asks for some funky language. Malbolge anyone? \$\endgroup\$ – Grzegorz Puławski Sep 26 '17 at 12:12
  • \$\begingroup\$ Next sequence is uncomputable and erroneous. I'm editing your bytecount (no code changes) to give us an actual sequence to use :) Nothing personal; we've run into this problem before edit never mind \$\endgroup\$ – HyperNeutrino Sep 26 '17 at 12:20
  • \$\begingroup\$ If A000017 just an erroneous version of A032522 does that mean it's not really even a sequence? Would hard-coding the 19 values on OEIS count as outputting it in its entirety, then? \$\endgroup\$ – Engineer Toast Sep 26 '17 at 12:23
  • 2
    \$\begingroup\$ I believe hardcoding is permissible in this case since it's not computable / a finite sequence. \$\endgroup\$ – Giuseppe Sep 26 '17 at 13:04
  • 3
    \$\begingroup\$ Just hardcoding is lame. You could compute the real sequence and add a "correction" for the error. If we knew how the wrong result was obtained, we could even try to redo that... \$\endgroup\$ – Christian Sievers Sep 26 '17 at 13:57
4
\$\begingroup\$

199. Kotlin, 92 bytes, A000466

fun main(args: Array<String>){
    val n = Integer.valueOf(args[0]);
    println(4*n*n-1);
}

Try it online!

Next Sequence

\$\endgroup\$
4
\$\begingroup\$

207. ARBLE, 389 bytes, A003275

coprime = eq(max((#table.unpack)(where(range(1,max(a,b)),eq(d%first(a,b,c,d,e),0)*eq(e%a,0),a,b))),1)
phi = len(where(range(1,n),coprime(a,first(n,b,c)),n))
A003275 = list()
local A003275_n = 0
return function(n)
	while(#A003275 < n)do
		A003275_n = A003275_n + 1
		if(phi(A003275_n) == phi(A003275_n+1))then
			A003275[#A003275+1] = phi(A003275_n)
		end
	end
	return A003275[#A003275]
end

Try it online!

Next Sequence

\$\endgroup\$
4
\$\begingroup\$

225. VBA, 80 bytes, A001232

Sub s(n)
While k<n+1
i=i+1
If i*9=StrReverse(i) Then k=k+1
Wend
MsgBox i
End Sub

Next sequence

Output is a popup message. A not-very-exciting sequence deserves a not-very-exciting solution, I think.

\$\endgroup\$
  • \$\begingroup\$ I hate the fact that can't see that a new answer showed up without scrolling to the top or reloading the page... At least I learned the basics of a new language. \$\endgroup\$ – NieDzejkob Oct 12 '17 at 13:59
  • 1
    \$\begingroup\$ C for next seq \$\endgroup\$ – NieDzejkob Oct 12 '17 at 14:03
  • \$\begingroup\$ @NieDzejkob Same here. I (sort of) know Perl now. \$\endgroup\$ – KSmarts Oct 12 '17 at 14:54
4
\$\begingroup\$

235. Pascal (FPC), 3295 bytes, A000512

4 days passed without anyone answered.

Type
	int = LongInt; // Can be changed to Integer

Var
	n, n_column, matrices_len, i, j, k: int;
	row_values, matrices: Array of array of int;
	row_id, column_sum: Array of int;
	valid: Boolean;

Function next_permutation (var A : Array of int): Boolean;
var x, y, z, temp: int;
begin
	if Length(A) <> n then writeln('Error!!');
	x := Length(A) - 1; // or High(A)
	z := x;
	while (x > 0) and (A[x-1] > A[x]) do Dec(x);
	y := x;
	while y < z do
	begin
		temp := A[z]; A[z] := A[y]; A[y] := temp;
		Inc(y); Dec(z);
	end;
	if (x = 0) then
		Exit(false);
	y := x; temp := A[x-1];
	while A[y] < temp do Inc(y);
	A[x-1] := A[y]; A[y] := temp;
	Exit(true);
end;

Function equivalent (mat1, mat2: int): Boolean;
{ Use highly sub-optimal solution, O(n!^2 x n^2).
  O( n! x n^2 x log(n) ) solution is possible by trying all row permutation
  and sort the columns, and check if the matrices are equal.
  Sort the rows and the columns alternatively does not work, though.
}
var
	xP, yP: Array of int;
	x, y: int;
	different: Boolean;
begin
	SetLength(xP, n);
	SetLength(yP, n);
	for x := 0 to n-1 do
	begin
		xP[x] := x;
		yP[x] := x;
	end;
	repeat
		repeat
			different := false;
			for x := 0 to n-1 do
			begin
				for y := 0 to n-1 do
				begin
					if row_values[matrices[mat1, x], y] <>
					row_values[matrices[mat2, xP[x]], yP[y]] then
					begin
						different := true;
						break;
					end;
				end;
				if different then break;
			end;
			if not different then Exit(true);
		until not next_permutation(xP);
	until not next_permutation(yP);
	Exit(false);
end;

Begin
	Read(n); Inc(n);
	If n < 3 then
	begin
		Writeln(0);
		Halt;
	end;
	SetLength(row_values, (n * (n - 1) * (n - 2)) div 6);
	n_column := 0;
	for i := 0 to n-1 do
		for j := i+1 to n-1 do
			for k := j+1 to n-1 do
			begin
				SetLength(row_values[n_column], n);
				row_values[n_column, i] := 1;
				row_values[n_column, j] := 1;
				row_values[n_column, k] := 1;
				Inc(n_column);
			end;
	// Dynamic array in FP is 0-based
	if n * (n - 1) * (n - 2) <> 6 * n_column then
	begin
		WriteLn('Error!');
		exit();
	end;

	matrices_len := 0;
	SetLength(matrices, 4);

	SetLength(row_id, n);
	SetLength(column_sum, n);
	while true do
	begin
		for i := 0 to n-1 do column_sum[i] := 0;

		for i := 0 to n-1 do
		begin
			for j := 0 to n-1 do
				Inc(column_sum[j], row_values[row_id[i], j]);
		end;

		valid := true;
		for i := 0 to n-1 do
		begin
			if column_sum[i] <> 3 then // column_sum[i] = sum of all values on column i
			begin
				valid := false;
				break;
			end;
		end;
		if valid then
		begin
			if matrices_len = length(matrices) then
				SetLength(matrices, 2 * length(matrices));
			matrices[matrices_len] := copy(row_id, 0, n);
			Inc(matrices_len);
		end;

		i := n - 1;
		while (i <> -1) and (row_id[i] = n_column - 1) do
			Dec(i);
		if i = -1 then
			Break;
		Inc(row_id[i]); Inc(i);
		while i < n do
		begin
			row_id[i] := row_id[i-1];
			Inc(i);
		end;
	end;

	row_id := nil; column_sum := nil;

	k := 0;
	for i := 0 to matrices_len-1 do
	begin
		valid := true;
		for j := 0 to i-1 do
		begin
			if matrices[j, 0] <> -1 then
			begin
				if equivalent(i, j) then
				begin
					valid := false;
					break;
				end;
			end;
		end;
		if valid then
			inc(k)
		else
			matrices[i, 0] := -1;
	end;
	Writeln(k);
End.

Try it online!

Next sequence.

I can easily delete a byte to get this sequence instead (which seems to be much easier to understand), but I didn't do that.

\$\endgroup\$
4
\$\begingroup\$

236. Axiom, 341 bytes, A003295

qpc(n,k) ==  -- inspired by 3rd PARI code for A010815
  qr := divide(n,k)
  if qr.remainder>0 then return 0
  sq := perfectSqrt(24*qr.quotient+1)
  sq case "failed" => 0
  jacobi(12,sq)

qp(k) == series(n+->qpc(n,k),'q=0)

q := series q

F := q*qp(3)*(qp(33)/(qp(1)*qp(11)))

s := q*(-11+(1+3*F)^2*(1/F+1+3*F))

f(n) == coefficients(s).(n+1)

Next sequence.

Put it in a file called a003295.input and, at the axiom prompt, type )read a003295. Now you can for example call f 25. The first time it will give a warning before still giving the correct result. Here it is computing the first values:

(9) -> [f n for n in 0..20]
   Cannot compile map: f 
   We will attempt to interpret the code.

   (9)
   [1, - 5, 17, 46, 116, 252, 533, 1034, 1961, 3540, 6253, 10654, 17897, 29284,
    47265, 74868, 117158, 180608, 275562, 415300, 620210]
                                              Type: List(Expression(Integer))

qp(k) computes the series of the q-Pochhammer symbol for q^k. The definition of F and s follows the Mathematica code.

\$\endgroup\$
  • \$\begingroup\$ could have used coefficient(s,n) \$\endgroup\$ – Christian Sievers Oct 27 '17 at 13:59
  • \$\begingroup\$ I wonder if I should upvote or downvote this answer. \$\endgroup\$ – user202729 Oct 27 '17 at 14:00
  • 1
    \$\begingroup\$ @user202729 why would you downvote? \$\endgroup\$ – Christian Sievers Oct 27 '17 at 14:01
  • \$\begingroup\$ Can you add an explanation what is the sequence? \$\endgroup\$ – user202729 Oct 29 '17 at 14:03
  • \$\begingroup\$ @user202729 I hardly understand the basics of what is said in the OEIS entry, so I'm not sure what I can explain. But I like that it is related to the fascinating phenomenon of monstrous moonshine. \$\endgroup\$ – Christian Sievers Oct 29 '17 at 18:31
4
\$\begingroup\$

262. Cubically, 91 bytes, A000115

$:7*1+4/1**1+55/1RFD'/2%:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

Try it online!

Next sequence.

Use the formula

a(n) = round((n+4)^2/20).

listed on the OEIS page.

Originally I intended to format the code as a cube, something like

  $:7*1
 +    4
/1**1 +
5   5 /
1   RF
D'/2%

but it does not work out too well, because Cubically does not have comments and it is not allowed to put spaces between command and parameters, unfortunately.

More explanation later.

\$\endgroup\$
  • \$\begingroup\$ The Cubically interpreter now allows arbitrary whitespace in source code. Thanks for prompting me to redo the interpreter, I've been trying to get around to that for months :) \$\endgroup\$ – MD XF Nov 25 '17 at 23:52
4
\$\begingroup\$

261. Alice, 115 bytes, A000504

/
 i                            >'Qa*:\ o
  /.!.h*?2Ea*?a5+*+2+*?2*3+.!w=
                              >?*?2-.!K @

Try it online!

Next sequence.

Uses the formula used by the Mathematica snippet on OEIS:

a[n_] := n (n+1) (10n^2+15n+2) (2n+3)!! / 810

In detail:

/      Switch to Ordinal mode.
i      Read all input as a string.
/      Switch back to Cardinal mode.
.!     Implicitly convert the input to an integer N and store a copy on the tape.
.h*    Multiply N by (N+1).
?2E    Retrieve a copy of N and square it.
a*     Multiply by 10.
?a5+*  Retrieve another copy of multiply it by 15.
+      Add the last two results.
2+     Add 2.
*      Multiply the initial value by this, giving N*(N+1)*(10N^2+15N+2)
?2*3+  Retrieve another copy of N and compute 2N+3, which will be our
       iterator for the double factorial.
.!     Store a copy of this on the tape.
w      Push the current IP address to the return address stack. This starts
       a loop.
  =      Sign junction. Pops the current value of the double factorial iterator.
         If it's positive, turn right (continuing the loop). If it's negative,
         turn left (exiting the loop).
  >      Redirect the IP eastward again.
  ?*     Multiply our result by the current value of the iterator.
  ?2-    Retrieve another copy of the iterator and subtract 2.
  .!     Store a copy on the tape to update the iterator.
K      Jump back to the w to get to the next iteration.

       Once we exit the loop, we continue here:
>      Redirect the IP eastward again.
'Qa*:  Divide the result by 810 (computed as 81*10).
\      Switch to Ordinal mode.
o      Implicitly convert the result to a string and print it.
@      Terminate the program.
\$\endgroup\$
4
\$\begingroup\$

260. Brain-Flak, 504 bytes, A001333

<>       # switch to another stack
(())(()) # push two 1s. Assuming top = a n-1, second top = a n-2 apart from the input
<>({}<>) # transfer the input to this stack
{        # repeat input times
    ({}[()]<     # subtract 1, ignore 
      (
        ({}<>)   # move top a n-1 to another stack
        ({})     # + top a n-1
        <>{}<>   # add to a n-2 on the other stack
      )          # and push 2 * a n-1 + a n-2
    >)           # and push back again
}
{}{}     # remove redundant values on top 

Try it online!

Next sequence.

The actual code is only 52 bytes: Try it online!

Use the recurrence relation

a(n) = 2a(n-1) + a(n-2)

described on the OEIS page.


The mathematical information about that sequence is pretty simple and elementary, and not worth the effort I write the explanation, so I decide to not write explanation for this sequence.

\$\endgroup\$
  • 1
    \$\begingroup\$ Huh, using the explanation as the actual program. Original, +1 \$\endgroup\$ – caird coinheringaahing Nov 24 '17 at 8:00
  • \$\begingroup\$ Note that 503 is already used. I switch to 504. \$\endgroup\$ – user202729 Nov 24 '17 at 8:01
4
\$\begingroup\$

194. ALGOL 68 (Genie), 589 bytes, A000160

BEGIN
  LONG LONG INT n   := read int + 4;
  LONG LONG INT r   := 0;
  LONG LONG REAL ma := ( n / 4.0 ) ** 1.5;
  LONG LONG REAL mb := ( n / 3.0 ) ** 1.5;
  LONG LONG REAL mc := ( n / 2.0 ) ** 1.5;
  LONG LONG REAL x  := 2.0 / 3;
  INT a             := 1;
  WHILE a <= ma DO
    INT b := a;
    WHILE b <= mb DO
      INT c := b;
      WHILE c <= mc DO
        INT d := c;
        WHILE a ** x + b ** x + c ** x + d ** x <= n DO
          r := r + 1;
          d := d + 1
        OD;
        c := c + 1
      OD;
      b := b + 1
    OD;
    a := a + 1
  OD;
  print ( whole ( r , 0 ))
END

Try it online!

Next Sequence.

Based on the comments of the sequence, counts the solutions to the inequality

a(2/3)+b(2/3)+c(2/3)+d(2/3) ≤ n

for any four integers 1 ≤ a ≤ b ≤ c ≤ d.

I also gave a fairly straightforward next sequence, to make up for last time.

Edit: This was originally written for Java 8, but I missed that there were already two Java 8 answers when I wrote this. Probably because one was labeled "Java (OpenJDK 8)" and the other was just "Java 8". Whatever the reason, this answer was invalid. I re-wrote it in a different language, with the same byte count, to fix this.

\$\endgroup\$
  • \$\begingroup\$ Note that this is valid because You can assume that neither the input nor the required output will be outside your languages numerical range \$\endgroup\$ – Stephen Oct 2 '17 at 14:07
  • \$\begingroup\$ @Stephen You could get picky and say that it doesn't count because Java has the "long" type, but that's an easy fix. All of the test cases on the OEIS page fit in 32-bit integers anyway. \$\endgroup\$ – KSmarts Oct 2 '17 at 14:20
  • \$\begingroup\$ Oh, right, I forgot about that. It needs to work for n=0 to 1000 then or it is invalid (since you also have BigInteger) \$\endgroup\$ – Stephen Oct 2 '17 at 14:22
  • 1
    \$\begingroup\$ @Stephen Fixed (Byte count unchanged). \$\endgroup\$ – KSmarts Oct 2 '17 at 14:47
4
\$\begingroup\$

256. Pygmy Forth, 562 bytes, A000454

CODE PICK  dpush(_stack[~dpop()]) END-CODE
: COEFFICIENT-A(N-1) 2 * 5 - 2 * ;
: COEFFICIENT-A(N-2) DUP 6 - * 6 * 55 + ;
: COEFFICIENT-A(N-3) DUP DUP 7 - * 2 * 25 + SWAP 2 * 7 - * ;
: COEFFICIENT-A(N-4) 4 - DUP * DUP * ;
: ADVANCE DUP COEFFICIENT-A(N-1) 2 PICK * OVER COEFFICIENT-A(N-2) 4 PICK * - OVER COEFFICIENT-A(N-3) 5 PICK * + OVER COEFFICIENT-A(N-4) 6 PICK * - SWAP 1 + ;
CODE ADVANCE-LOOP  for i in range(dpop()): ADVANCE() END-CODE
CODE CLEAN-STACK  global _stack; _stack = [_stack[-1]] END-CODE
: A000454 0 0 0 1 5 5 PICK ADVANCE-LOOP DROP CLEAN-STACK ;

Next sequence!

Nice, round number of answers! Computes up to 16 A454 on 64-bit Forths, and you can Try It Online! on gforth with some modifications. However, Pygmy Forth is arbitrary precision and it can compute n=1000 in a blink of an eye.

Explanation

Forth is a stack-based language, like 05AB1E or Actually, but it was not designed that way to be esoteric. Forth was designed in 1970, and being stack based allowed the interpreter to fit in extremely small space - even now, an x86 interpreter could fit in the MBR and VBR (two 512 byte sectors) of a hard disk, with the code loaded from a FAT32 filesystem (first-hand experience). The most important consequences of the stack-oriented design are the postfix notation in which all calculations are described, and having to keep the words ("functions") small so you don't get lost. Breaking up a word into smaller chunks is called factoring.

ADVANCE expects the last 4 numbers of the sequence on the stack, with a cherry the sequence index n on top, and calculates the next number in the sequence as well as increments n. The sequence can start as 0, 0, 0, 1, and the next number will be assigned the index of 5, so you can calculate a specific element of the sequence like this:

0 0 0 1 5 ADVANCE ADVANCE ADVANCE ADVANCE ADVANCE
DROP ( the index )
. ( print )

Now we only need to loop ADVANCE a given number of times, and this is exactly what A454 does. The 0 0 0 1 5 at the beginning initializes the stack, then 5 PICK brings the argument this word was given to the top. Normally in Forth, one would do limit start ?DO stuff LOOP, which is a construct equivalent to Python's for i in range(start, limit): stuff. However, Pygmy Forth is missing a lot of words, so I have to make up for it with CODE, which is used to define words in Python. At the end of A454, DROP is used to remove the sequence index, leaving the result at the top of the stack.

\$\endgroup\$
4
\$\begingroup\$

124. ArnoldC, 796 bytes, A000278

IT'S SHOWTIME

HEY CHRISTMAS TREE input
YOU SET US UP @I LIED
HEY CHRISTMAS TREE result
YOU SET US UP @I LIED
HEY CHRISTMAS TREE x
YOU SET US UP @I LIED
HEY CHRISTMAS TREE y
YOU SET US UP @NO PROBLEMO
HEY CHRISTMAS TREE temp1
YOU SET US UP @I LIED

GET YOUR ASS TO MARS input
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY

STICK AROUND input

GET TO THE CHOPPER temp1
HERE IS MY INVITATION x
ENOUGH TALK

GET TO THE CHOPPER x
HERE IS MY INVITATION x
GET UP y
ENOUGH TALK

GET TO THE CHOPPER y
HERE IS MY INVITATION temp1
YOU'RE FIRED temp1
ENOUGH TALK

GET TO THE CHOPPER input
HERE IS MY INVITATION input
GET DOWN 1
ENOUGH TALK

CHILL

GET TO THE CHOPPER result
HERE IS MY INVITATION x
ENOUGH TALK

TALK TO THE HAND result
YOU HAVE BEEN TERMINATED

Try it Online!

Next Sequence

\$\endgroup\$
  • 1
    \$\begingroup\$ useful for the next person, perhaps? \$\endgroup\$ – Giuseppe Sep 1 '17 at 15:16
  • \$\begingroup\$ I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY: How does this work? \$\endgroup\$ – NieDzejkob Sep 1 '17 at 15:16
  • \$\begingroup\$ @NieDzejkob GET YOUR ASS TO MARS assigns a variable from a method call, DO IT NOW calls the method, and I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY reads an integer input. \$\endgroup\$ – KSmarts Sep 1 '17 at 15:33
  • \$\begingroup\$ @Giuseppe Of course, lots of math software have built-ins for arbitrary precision pi, too. \$\endgroup\$ – KSmarts Sep 1 '17 at 15:35
  • \$\begingroup\$ @KSmarts sure, but I'm having trouble picking one that hasn't been used yet, so I provided that link as at least one example of a "roll your own" algorithm \$\endgroup\$ – Giuseppe Sep 1 '17 at 15:36
4
\$\begingroup\$

309. Haskell, 699 bytes, A003025

import Control.Monad
import Data.List

-- (n, es) has n nodes; es is a list of (i,j) where 1 <= i < j <= n.
type Dag = (Int, [(Int, Int)])

both f (a,b) = (f a, f b)
powerset = filterM (const [True, False])

-- All dags with n nodes.
dags :: Int -> [Dag]
dags n = map ((,) n) $ powerset [(i,j) | i <- [1..n], j <- [i+1..n]]

-- Is there only one node with no exits?
ok :: Dag -> Bool
ok (n, es) = not $ any (\i -> not $ any ((==i) . fst) es) [1..n-1]

-- All ways to relabel the given dag.
rewrites :: Dag -> [Dag]
rewrites (n, es) = [(n, sort $ map (both ((p!!) . pred)) es) | p <- permutations [1..n]]

-- A003025
f :: Int -> Integer
f = genericLength . nub . concatMap rewrites . filter ok . dags

Try it online!

Enumerates the n-node labeled acyclic digraphs with 1 out-point.

print (f 5) produces the correct output (16885) after 20 seconds when compiled with -O3.

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.