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

2
\$\begingroup\$

299. Unefunge-98 (PyFunge), 137 bytes, A001008

&1+3p01p12p2g3g::/1-:/d*j:0p%0g\0f-8-j$:3g\/:1g*1p\2g\/1g+1p2g*2p1g2g::/1-:/d*j:0p%0g\0f-8-j$:1g\/1p2g\/2p3g1-:3p:/0ab*-3-*j1g.@ unefunge

Try it online!

Next sequence!

Due to the way PyFunge handles input, the input to this program has to be followed by at least one newline.

Explanation

I'm calculating GCD twice, both times using the Euclidean algorithm, which is a simple one-liner in Python: while b: a, b = b, a % b (the result is left in a). Here is it implemented in Unefunge:

::/1-:/d*j:0p%0g\0f-8-j$ Stack: a b
::/1-:/d*j               If b is equal to 0, skip to the $ at the end
          :0p            Save b in a temporary variable
             %           Stack: a%b
              0g\        Recall b and swap. Stack: b a%b
                 0f-8-j  Jump to the beginning
                       $ Drop b, which is now equal to 0.

In the explanation of the whole program, I'll replace this snippet with a G. The program uses its first 4 bytes as variables, since the programs in Unefunge can easily modify themselves.

Byte no    Letter   Purpose
    0               A temporary variable used in the GCD algorithm
    1         n     The numerator of the partial sum
    2         d     The denominator of the partial sum
    3         i     The loop counter

This should be enough to understand the whole program.

&1+3p       i = int(input()) + 1
01p         n = 0
12p         d = 1
            The main loop starts here
2g3gG:      gcd = GCD(d, i) # Stack: gcd, gcd
3g\/:                       # Stack: gcd, i // gcd, i // gcd
1g*1p       n *= i // gcd   # Stack: gcd, i // gcd
\2g\/1g+1p  n += d // gcd   # Stack: i // gcd
2g*2p       d *= i // gcd   # Stack empty
1g2gG:      gcd = GCD(n, d) # Stack: gcd, gcd
1g\/1p      n //= gcd
2g\/2p      d //= gcd
3g1-:3p     i -= 1
:/0ab*-3-*j If i is not 0, loop
1g.@        print(n)
\$\endgroup\$
  • 1
    \$\begingroup\$ Note that there must be a trailing newline after input. \$\endgroup\$ – user202729 Jan 3 '18 at 16:21
  • \$\begingroup\$ I recall Hyper asking about Series parallel numbers on Math.SE, are you sure it hasn't occurred before? \$\endgroup\$ – Mr. Xcoder Jan 3 '18 at 16:25
  • \$\begingroup\$ @Mr.Xcoder the snippet doesn't complain, and you know it would. An ill-formatted answer is also out of the question. \$\endgroup\$ – NieDzejkob Jan 3 '18 at 16:27
  • \$\begingroup\$ @Mr.Xcoder The related sequence A000084 has been done before. And maybe this one came up in a now-deleted answer? \$\endgroup\$ – KSmarts Jan 3 '18 at 22:30
  • \$\begingroup\$ @KSmarts Issue already solved \$\endgroup\$ – user202729 Jan 4 '18 at 0:52
2
\$\begingroup\$

300. C# (.NET Core), 2407 bytes, A000137

using System;
using System.Numerics;

public class A000137 {

 // Expands the polynomial (1 / x^k)
 public static BigInteger[] ExpandReciprocalPowerK(int k, int max) {
  BigInteger[] result = new BigInteger[max + 1];
  for (int i = 0; i <= max; i++) {
   if (i % k == 0)
    result[i] = new BigInteger(1);
   else
    result[i] = new BigInteger(0);
  }
  return result;
 }

 // Calculates p1(x) * p2(x)
 public static BigInteger[] PolynomialMultiply(BigInteger[] x, BigInteger[] y, int max) {
  BigInteger[] result = new BigInteger[max + 1];
  for (int i = 0; i <= max; i++) {
   for (int j = 0; j <= max - i; j++) {
    if (result[i + j] == null)
     result[i + j] = new BigInteger(0);
    result[i + j] += x[i] * y[j];
   }
  }
  return result;
 }

 // Calculates (p(x))^n
 public static BigInteger[] PolynomialPower(BigInteger[] x, BigInteger n, int max) {
  BigInteger[] result = x;
  if (BigInteger.Compare(n, new BigInteger(0)) == 0) {
   result = new BigInteger[max + 1];
   result[0] = new BigInteger(1);
   for (int i = 1; i <= max; i++)
    result[i] = new BigInteger(0);
  }
  if (BigInteger.Compare(n, new BigInteger(2)) < 0)
   return result;

  BigInteger counter = new BigInteger(1);
  while (BigInteger.Compare(counter, n >> 2) <= 0)
   counter <<= 1;
  
  while (BigInteger.Compare(counter, new BigInteger(0)) > 0) {
   result = PolynomialMultiply(result, result, max);
   if (BigInteger.Compare(n & counter, new BigInteger(0)) != 0)
    result = PolynomialMultiply(result, x, max);
   counter >>= 1;
  }
  return result;
 }
 
 public static void Main(string[] args) {
  try {
   // Get Input
   int n = int.Parse(args[0]);
   BigInteger[] x1 = ExpandReciprocalPowerK(1, n);
   for (int i = 2; i <= n; i++) {
    BigInteger coeff = x1[i];
    x1 = PolynomialMultiply(x1, PolynomialPower(ExpandReciprocalPowerK(i, n), coeff, n), n);
   }

   BigInteger[] x2 = new BigInteger[n + 1], x3 = new BigInteger[n + 1], x4 = new BigInteger[n + 1];
   x3[0] = x2[0] = new BigInteger(1) - x1[0]; 
   x4[0] = new BigInteger(1);
   for (int i = 1; i <= n; i++)
    x4[i] = x3[i] = x2[i] = x1[i];
   for (int i = 2; i <= n; i++) {
    x3 = PolynomialMultiply(x3, x2, n);
    for (int j = 0; j <= n; j++)
     x4[j] += x3[j];
   }
   BigInteger[] x5 = PolynomialMultiply(x1, x4, n);

   Console.WriteLine(x5[n]); // A000137 is not zero-offset
  }
  catch (Exception e) {
   Console.WriteLine(e);
  }
 }

}

Try it online!

Next sequence: A002407, Cuban primes

Second .NET Core C# answer in the first 300 (Since TIO shows both .NET Core and Visual C# Compiler so I assume the two to be different).

Implementation of the algorithm(Mathematica) in the A000137 page in C#, courtesy to Jean-François Alcover (2016).

I tried to find the pattern, but failed to arrive an algorithm that solves it. Used Maclaurin series to calculate the expansion of 1/(1-p(x)) where p is a polynomial of x.

Added some lines so that it points to a nice one

\$\endgroup\$
2
\$\begingroup\$

303. APL (Dyalog), 203 bytes, A000135

{n←1+⍵⋄++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++≢⊃{{(n≥⍵)/⍵},⍵,⍺+0,⍵}/(2÷3)*⍨1+⍳⌊1.5*⍨n}

Try it online!

using ⎕IO←0. After removing fillers (+, conjugate in Dyalog APL but it doesn't change the result becuase we're dealing real numbers here):

{n←1+⍵⋄≢⊃{{(n≥⍵)/⍵},⍵,⍺+0,⍵}/(2÷3)*⍨1+⍳⌊1.5*⍨n}

Next sequence

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to the site, and nice first post! \$\endgroup\$ – caird coinheringaahing Jan 7 '18 at 19:17
2
\$\begingroup\$

304. Clojure, 143 bytes, A000203

(defn sigma
   [num]
   (reduce +
      (filter
         (comp zero?
            (partial rem num))
         (range 1
            (+ 1 num)))))

Try it online!

Next sequence

\$\endgroup\$
2
\$\begingroup\$

305. JavaScript (Node.js), 145 bytes, A000143

p=Math.pow
a=(n)=>{q=!n/16;
for(i=1;i<=n;i++){if(!(n%i))q+=p(-1,i)*p(i,3)}return q*16*p(-1,n)}
//Filing out characters to get to nearest empty ch

Try it online!

Next sequence

If you by chance consider comments cheating here's the same code ungolfed with the same length

a = function(n) {
	q=!n/16;
	for (i = 1; i <= n; i++) {
		if (n%i==0) q += Math.pow(-1, i) * Math.pow(i, 3)
	}
	return q * 16 * Math.pow(-1, n)
}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Why would anyone consider this cheating? \$\endgroup\$ – NieDzejkob Jan 8 '18 at 13:53
  • \$\begingroup\$ @NieDzejkob Because comments simplifies changing the length of the code. I myself don't think it's that important but you never know. \$\endgroup\$ – IQuick 143 Jan 8 '18 at 16:00
2
\$\begingroup\$

310. Pyth, 148 bytes, A000699

L?>b1*tbsm*y-bdydtUb1;*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1yh

Try it here!

Next Sequence.

I am going to regret using Pyth that soon. Implements a recursive function y that:

  • Checks if its argument, b, is higher than 1.
  • If that is true, then it returns (b-1) * Σd=1b-1 y(d) * y(b-d).
  • Otherwise, it just returns 1.
\$\endgroup\$
2
\$\begingroup\$

316. Pascal (FPC), 1808 bytes, A000147

{ ''' }
Type
	Num = Integer; // may change this to LongInt or big integer.
Const
	maxN = 1010; // Why using dynamic array?
Var
	ans, i, n, m, n0: Num;
	a: Array [1..maxN, 1..maxN] of Num;
Begin
	read(n0);
	inc(n0); // because input is 0-indexing.
	if n0 > maxN then
	begin
		writeln('Input too large!');
		halt;
	end;
	{ Let a[i, j] (a[i][j] in other languages. Pascal multidimensional
	array indexing looks nicer) be the number of rooted tree with
	(i) nodes, height at most 2 and all rooted subtree with its
	root being a child of the root has at least (j) nodes. }
	for m := 1 to n0 do
		a[1, m] := 1;
	{ Because if the tree only have a node, there is no rooted subtree.
	BTW, Sublime Text doesn't support Pascal well. }
	for n := 2 to n0 do
	begin
		a[n, n-1] := 1;
		for m := n-2 downto 1 do
			a[n, m] :=
			// When there is no rooted subtree of size (m).
			{ (line comment is FP's extension. TP doesn't have this)
			(TP = Turbo Pascal) }
			a[n, m+1]
			{ When there is a subtree of size (m), the remaining
			part is a tree of order (n-m) and each rooted subtree
			has at least (m) nodes. }
			+ a[n-m, m];
	end;
	{ From OEIS page: A tree of diameter 5 is formed from two rooted trees 
	of height 2, with their roots joined. }
	ans := 0;
	for i := 1 to (n0-1) div 2 do
		{ Assume one of the tree has order (i), then the other 
		has order (n0-i), where (n0) is the input. }
		ans += (a[i, 1] - 1) * (a[n0-i, 1] - 1);
		{ -1 because there is exactly one tree of height < 2
		and order = i. }
	if n mod 2 = 0 then
	begin // Assume both of the rooted subtrees has order (n div 2).
		i := a[n div 2, 1] - 1;
		ans += i * (i+1) div 2;
	end;
	writeln(ans); // ln = line.
End.
{ ''',



print(__import__('base64').b64decode(b'Tm90aGluZyBpbnRlcmVzdGluZy4uLiB0aGlzIGlzIG5vdCBQeXRob24u').decode('ascii')) }

Try it online!

Next sequence! Easy, just implement generating function.

\$\endgroup\$
2
\$\begingroup\$

317. Python 3 (Cython), 652 bytes, A001808

from itertools import zip_longest

def mul(a, b):
	return list(map(sum, zip_longest(*[[0] * i + [e * f for j, f in enumerate(b)] for i, e in enumerate(a)], fillvalue = 0)))

# a(x) - b(x)
def sub(a,b):
	return list(map(lambda v: v[0] - v[1], zip_longest(a, b, fillvalue = 0)))

# a'(x)
def polyderiv(a):
	return[i*x for i,x in enumerate(a)][1:]

# (f(x)/g(x))', first n terms
def fracderiv(f,g):
	return sub(mul(polyderiv(f),g),mul(f,polyderiv(g))),mul(g,g)

f = [1]
g = [1,-11,54,-154,275,-297,132,132,-297,275,-154,54,-11,1]
F = 1

n = int(input())
for i in range(n):
	f, g = fracderiv(f, g)
	f = f[:n]
	g = g[:n]
	F*= i + 1

print(f[0] // g[0] // F)

Try it online!

Next sequence!

\$\endgroup\$
2
\$\begingroup\$

320. Java 7, 308 bytes, A000292

class Main{
  public static void main(String[] args){
    System.out.println(new Main().BinomialCoefficient(new Long(args[0])+2, 3));
  }

  static long BinomialCoefficient(long n, long k){
    return n==k || k<1?
        1
      :
        BinomialCoefficient(n-1, k) + BinomialCoefficient(n-1, k-1);
  }
}

Easy enough; calculates the Binomial Coefficient of n+2 and 3 as stated in the OEIS sequence.

Try it online.

Next sequence

\$\endgroup\$
2
\$\begingroup\$

319. C (8cc), 292 bytes, A001688

#include <math.h>

unsigned long factorial(unsigned long f) {
    if ( f == 0 ) 
        return 1;
    return(f * factorial(f - 1));
}

unsigned long long a(int n) {
    return factorial(n) * (pow(n,4) + (6*pow(n,3)) + (17*pow(n,2)) + (20*n) + 9);
}

int main(void) {
    printf("%d",a(4));
}

Next sequence

\$\endgroup\$
2
\$\begingroup\$

321. Racket, 249 bytes, A000308

#lang racket/base
(define sub-one (λ (n) (+ n -1)))
(define sub-two (compose sub-one sub-one))
(define sub-thr (compose sub-one sub-two))
(define A000308 (λ (n) (if (< n 4) n (* (A000308 (sub-one n)) (A000308 (sub-two n)) (A000308 (sub-thr n))))))
\$\endgroup\$
2
\$\begingroup\$

323. Common Lisp, 238 bytes, A000150

(defun catalan (n)
  (if (zerop n) 1 (/ (* 2 (+ n n -1) (catalan (1- n))) (1+ n))))
(let ((n (read)))
  (if (= n 0) (print 0)
    (if (evenp n)
      (print (/ (catalan n) 2))
      (print (/ (- (catalan n) (catalan (/ (- n 1) 2))) 2)))))

Try it online!

Next Sequence

\$\endgroup\$
2
\$\begingroup\$

325. Perl 6, 385 bytes, A000559

my $n = get+3;
my @s = 0..$n;
my $result = 0;

for @s -> $k {
  $result = $result + stirling($n,$k)*stirling($k,3);
}

say $result;

sub stirling ($n, $k) {
  my @a = 0..$k;
  my $s = 0;
  for @a -> $j {
    $s = $s + ((-1)**($k-$j) * binom($k, $j) * $j**$n);
  }
  return $s / ([*] 1..$k);
}

sub binom ($n, $k) {
  my $l = $n-$k;
  return ([*] 1..$n) / ( ([*] 1..$k)*([*] 1..$l) );
}

An operator in square brackets is a reduction operator over a list. So [*] 1..$k is $k factorial.

Try it online!

Next Sequence

\$\endgroup\$
2
\$\begingroup\$

324. Pyon, 559 bytes, A000238

import fractions,itertools
global fractions,k,R,itertools;# ugh
R=[0,1]
p=lambda a:[i*x for i,x in enumerate(a)][1:]
A=lambda a,b:list(map(sum,itertools.zip_longest(a,b,fillvalue=0)))
m=lambda p,q,n:[sum((p+k*[0])[i]*(q+k*[0])[k-i]for i in range(k+1))for k in range(len(p+q)-1)][:n]
for n in range(len(R),int(input())+2):
	P=[]
	for k in range(1, n):P=A(P,[fractions.Fraction(x,k)for x in[0if i%k else R[i//k]for i in range(n)]])
	f=[0,1];F=1
	for i in range(n):f=A(p(f),m(f,p([x*2for x in P]),n));F*=i+1
	R+=[f[0].numerator//F]
print(R[-1]-m(R,R,len(R))[-1])

Try it online!

Next sequence!

I initially wrote an answer that calculated A000150 in Befunge, then KSmarts answered, before Christian Sievers noticed that I've made that mistake. I took my code from this answer, added a call to mul to calculate a different sequence, and golfed it all a lot.

\$\endgroup\$
  • \$\begingroup\$ TIO doesn't seem to like the # ugh \$\endgroup\$ – Christian Sievers Jan 27 '18 at 15:17
  • \$\begingroup\$ @ChristianSievers ugh, fixed \$\endgroup\$ – NieDzejkob Jan 27 '18 at 15:18
  • \$\begingroup\$ Is that a bug in Pyon? \$\endgroup\$ – Christian Sievers Jan 27 '18 at 15:22
  • \$\begingroup\$ @ChristianSievers There are many bugs in Pyon that I don't intend to fix. The language was made in about half an hour and I don't plan to spend more time on it because it's not really worth it. \$\endgroup\$ – HyperNeutrino Jan 27 '18 at 18:06
2
\$\begingroup\$

327. tinylisp, 439 bytes, A000205

(load library)

(def x^2+3*y^2
 (lambda (x y)
  (add2
   (mul2 x x)
   (* y y 3))))

(def _sum-of-squares?
 (lambda (n x y)
  (if (equal? n (x^2+3*y^2 x y))
   1
   (if (less? n (x^2+3*y^2 x y))
    (if x
     (_sum-of-squares? n 0 (inc y))
     0)
    (_sum-of-squares? n (inc x) y)))))

(def sum-of-squares?
 (lambda (n)
  (_sum-of-squares? n 1 0)))

(def A000205
 (lambda (n)
  (length
   (filter sum-of-squares?
    (1to (pow 2 n))))))

Try it online!

Next sequence!

This is pretty slow, but it should work for any input, given enough time and memory.

The main function, A000205, generates all integers from 1 to 2^n; filters the list, keeping numbers of the form x^2+3*y^2; and returns the length of the resulting list.

There's probably a better way to check whether a number is of the form x^2+3*y^2. Here's the algorithm I used (see the function _sum-of-squares):

  • Start checking at x=1, y=0. At any point, if x^2+3*y^2 == n, stop and return 1 (truthy).
  • If x^2+3*y^2 is less than n, increment x.
  • If x^2+3*y^2 is greater than n, reset x to 0 and increment y.
  • If, when x is 0, x^2+3*y^2 is still greater than n, then there are no x and y that will make the equation work. Return 0 (falsey).
\$\endgroup\$
2
\$\begingroup\$

328. MY-BASIC, 222 bytes, A000439

def lin(n):return     n        :enddef
def sqr(n):return lin(n)*lin(n):enddef
def cub(n):return sqr(n)*lin(n):enddef
def hyp(n):return sqr(n)*sqr(n):enddef
def seq(n):return(hyp(n)+18*cub(n)+83*sqr(n)+114*lin(n))/24:enddef
\$\endgroup\$
  • \$\begingroup\$ is the first line just to make the bytecount work? :P \$\endgroup\$ – HyperNeutrino Jan 29 '18 at 2:25
  • \$\begingroup\$ @HyperNeutrino ... functionally relevant code formatting! \$\endgroup\$ – Jonathan Frech Jan 29 '18 at 13:33
2
\$\begingroup\$

329. Yacas, 155 bytes, A000222

/* compute the series A000222 with yacas */
f(n) := Sum(k,2,n,Bin(2*n-k,k) * (n-k)! * (-1)^k * Bin(k,2));
/* only the space between ! and * is necessary */

Put it in a file and load it with Load("a000222"); - alternatively, there is an online demo of yacas here, you can paste the definition, press Shift+Enter, then input something like f(10); followed again by Shift+Enter.

Next sequence

I can explain the series and the formula, but there is a big gap between these explanations:

The crossrefs entry of A000222 says it is a diagonal of A058057.

The comments of that series describe n*n matrices where the main diagonal from (1,1) to (n,n) and the diagonal below from (2,1) to (n,n-1) have x entries and the remaining entries are 1.

The permanents of these matrices are polynomials in x. A058057 gives their coefficients. A bit of experimentation shows that A000222 consists of the coefficients of x^2.

It follows that A000222 gives the number permutations of {1,...,n} that have exactly two positions i that are mapped to i or (if i>1) to i-1.

That doesn't seem to help efficiently computing the series, I rather feel I have reconstructed the problem to which the permanent is the answer.

I had exciting ideas how to compute the permanent in the quotient ring Z[x]/(x^3), because doing it in Z[x] is unnecessary work, but there is an easier way.

The maple code for A058057 starts with a definition that expresses the polynomial as the sum of k from 0 to n of an integer expresssion in n and k times (x-1)^k. I don't know where this comes from, it might be explained in Riordan's book mentioned in the references. This book has come up often, I think I want it!

Anyway, the coefficient of x^2 of the last term is (-1)^k*binomial(k,2) for k>=2 and 0 otherwise, which leads to the formula used in the program.

\$\endgroup\$
  • \$\begingroup\$ The expression of the polynomial as a sum is related to the ménage problem. Judging from the permutations that come up, I think it might have to do with the variations that allow for some (in this case, two) couples to sit together. \$\endgroup\$ – KSmarts Jan 30 '18 at 15:38
  • \$\begingroup\$ @KSmarts Yes, if there is a meeting of the heterosexual binary couples' society with n couples sitting at one side of a long (not round) table where the women sit first at the odd numbered chairs, there are that many ways for the men to sit such that exactly two couples sit together. \$\endgroup\$ – Christian Sievers Jan 30 '18 at 17:15
  • \$\begingroup\$ Now I see why the formula is true. I thought it was somehow derived from the permanent, but it can be obtained in exactly this form by simple combinatorical arguments. The fact that it is a polynomial in x-1 already suggests that is might have come from an application of the principle of inclusion and exclusion. \$\endgroup\$ – Christian Sievers Jan 31 '18 at 2:05
2
\$\begingroup\$

331. Coconut, 766 bytes, A001854

# grow all roted trees on n labeled nodes
def grow(nodes, tree = (), r = ()):
	used_nodes = tuple(j for j in nodes |> range if any(j in k for k in tree)) or (0,)
	available_nodes = tuple(j for j in nodes |> range if j not in used_nodes)
	if not available_nodes: return tree |> sorted |> tuple,
	for node in used_nodes:
		for new_node in available_nodes: r += grow(nodes, (tree, ((node, new_node),)) |*> (+))
	return r |> set |> sorted |> tuple

# calculate a tree's height
def tree_height(tree):
	tree, lengths = tree |> list, {0: 0}
	while tree:
		for v in tree:
			if v[0] in lengths: lengths[v[1]] = lengths[v[0]]+1; tree.remove(v)
	return lengths.values() |> max

# implement A001854
def A001854(nodes): return (nodes, sum(map(tree_height, grow(nodes)))) |*> (*)
\$\endgroup\$
  • \$\begingroup\$ Oh and I tried doing it the way that required nth derivative of some crazy function \$\endgroup\$ – IQuick 143 Feb 3 '18 at 19:17
  • 1
    \$\begingroup\$ @IQuick143 Brute. Force. \$\endgroup\$ – Jonathan Frech Feb 3 '18 at 19:28
  • \$\begingroup\$ @IQuick143 f=\sum_{k>=1}k*(s_k-s_{k-1}) where s_0(x)=x and s_{h+1}(x)=x*exp(x) is not that crazy... \$\endgroup\$ – Christian Sievers Feb 3 '18 at 21:48
2
\$\begingroup\$

333. Swift 3, 219 bytes, A000852

import Foundation
{typealias N=NumberFormatter;var i=$0+1,k=0;while i>0 {k+=1;let F=N();F.numberStyle=N.Style.spellOut;if "eo".contains("\(F.string(from:NSNumber(value:k))![" ".startIndex])"){i-=1}};print(k)}as(Int)->()

My previous Physica submission was invalid, because it didn't handle numbers like 14000. This is also compatible with Swift 4, and var f= needn't be included in the byte count.

Try it online!

Next sequence.

\$\endgroup\$
  • \$\begingroup\$ You seem to have forgotten your chain number (probably 333). \$\endgroup\$ – Jonathan Frech Feb 10 '18 at 18:41
  • \$\begingroup\$ @JonathanFrech Whoops sorry fixed. \$\endgroup\$ – Mr. Xcoder Feb 10 '18 at 18:43
2
\$\begingroup\$

338. Triangularity, 287 bytes, A000154

...........)...........
..........1)1..........
.........)2)7).........
........35)228)........
.......1834)1738.......
......2)195866)24......
.....87832)3549957.....
....6)562356672)979....
...4156448)186025364...
..016)3826961710272)8..
.4775065603888)2011929.
826983504W)IEsm........

Try it online!

Next Sequence

The previous sequence is erroneous, so hardcoding the terms listed in OEIS should be allowed as far as I am aware.

\$\endgroup\$
2
\$\begingroup\$

340. x86_64 assembly (nasm), 206 bytes, A000209

extern printf
section .data
fmt: db "%d", 10, 0
section .text
global f
f:
    push rdi
    fild qword [rsp]
    fptan
    fstp st0
    fistp qword [rsp]
    pop rsi
    lea rdi, [rel fmt]
    mov rax, 0
    call printf wrt ..plt
    ret

Try it online!

Next Sequence

The only reason I'm printing instead of returning the result is that I needed to get a higher byte count.

To test save the code below in a206.asm and run

$ nasm -f elf64 a206.asm
$ gcc a206.o -o a206
$ ./a206 11
-226

Test code:

extern printf
section .data
fmt: db "%d", 10, 0
section .text
global f
f:
    push rdi
    fild qword [rsp]
    fptan
    fstp st0
    fistp qword [rsp]
    pop rsi
    lea rdi, [rel fmt]
    mov rax, 0
    call printf wrt ..plt
    ret

extern atoi
global main
main:
    mov rdi, [rsi+8]
    call atoi wrt ..plt

    mov rdi, rax
    call f

    mov rax, 0
    ret
\$\endgroup\$
1
\$\begingroup\$

108. Proton, 32 bytes, A001589

a => ((4&(**),(**)&4) + *(+))(a)

Try it online!

Next Sequence

The shortest working solution would probably be a=>a**4+4**a :P

\$\endgroup\$
1
\$\begingroup\$

111. Ceres, 42 bytes, A000442

!3*@                                      

Try it online!

Spacing is to get an unused easy sequence. Many trailing spaces...

Note that this works for very large values because Python and sympy, though it doesn't look like it because of printing...

Next Sequence

\$\endgroup\$
1
\$\begingroup\$

112. Retina, 49 bytes, A000042

.+
$*
$(Let's just add some padding here, yes)?
1

The extra part at the end is for it to be 0-indexed, to comply with the spec.

Try it online!

Next Sequence

\$\endgroup\$
  • \$\begingroup\$ That next sequence looks familiar... \$\endgroup\$ – NieDzejkob Aug 15 '17 at 20:15
  • 1
    \$\begingroup\$ @NieDzejkob I'm considering making a programming language that finds the number of positive integers less than 2^n in the form Ax^2+By^2 :P I swear this kind of sequence comprises at least 25% of all OEIS :P they should make a keyword for this \$\endgroup\$ – HyperNeutrino Aug 15 '17 at 20:17
  • \$\begingroup\$ @HyperNeutrino Index entries for sequences related to populations of quadratic forms, perhaps? \$\endgroup\$ – Brian J Aug 15 '17 at 20:22
  • \$\begingroup\$ @HyperNeutrino According to their indexing, there are 53 distinct sequences like that. \$\endgroup\$ – KSmarts Aug 15 '17 at 20:22
  • 3
    \$\begingroup\$ waited a day for the OEIS to not be Ax^2+By^2, but it came full circle \$\endgroup\$ – Magic Octopus Urn Aug 16 '17 at 2:06
1
\$\begingroup\$

127. Alice, 58 bytes, A000156

/o
\i@/1!&w]!k4Pt&wwh..*.&[?~&].hn6*&#2*?+!K;;[q$KW;e)[k[?

Try it online!

This uses a dynamic programming approach to compute the number of ways to compute m with k squares for all m <= n+1. Using n+1 instead of n allows me to avoid using a conditional when n=0.

Next sequence

\$\endgroup\$
1
\$\begingroup\$

129. ExtraC, 482 bytes, A000082

import math

int isprime(long n)do
	if(n equals 1) return 0
	if(n equals 2) return 1
	if(not(n modulus 2)) return 0
	long max be sqrt(n)
	for(long i be 2 AND i less max AND increment i)do
		if(not(n modulus (2 times i plus 1))) return 0
	end
	return 1
end

long n be readint plus 1
double r be 1
for(long p be 1 AND p minus 1 less n AND increment p)do
	if(not(n modulus p))do
		if(isprime(p))do
			r be r times (F(1) divide p plus 1)
		end
	end
end
print((int)(r times (n times n)))

Try it online!

Next sequence!

\$\endgroup\$
1
\$\begingroup\$

131. Bean, 116 bytes, A000090

00000000: a64d a048 8040 a06a 52a0 6acc a06a 8d53  ¦M H.@ jR jÌ j.S
00000010: a048 4ca0 6a8c 253a 253a a64d a062 8050   HL j.%:%:¦M b.P
00000020: 80a0 1f20 803c a64d a05e 8053 a062 4ca0  . . .<¦M ^.S bL 
00000030: 438e 253c a64d a05f 804c d3a0 4820 5e8d  C.%<¦M _.LÓ H ^.
00000040: 53d0 80a0 1f20 8046 a53c 205e 264c ccd3  SÐ. . .F¥< ^&LÌÓ
00000050: a048 2043 8d53 a062 4ccc a05f 8e53 d080   H C.S bLÌ _.SÐ.
00000060: a01f 2080 3b4c a53a 8e25 3c8b 2581 008e   . .;L¥:.%<.%...
00000070: 205f ae35                                 _®5

Try it online!

Next sequence!

\$\endgroup\$
  • \$\begingroup\$ If I read the haskell for the next sequence right, A000116(n) = A000013(2*n), which is confirmed in comments of A00013. \$\endgroup\$ – NieDzejkob Sep 3 '17 at 8:50
1
\$\begingroup\$

133. CHICKEN Scheme, 643 bytes, A000903

(define (g x) 
(cond ((= x 0) 1) (else x)))
(define (div4 x)
(/ (- x (remainder x 4)) 4))
(define (factorial x)
(cond ((< x 3) (g x)) 
(else (* x (factorial (- x 1))))))
(define (a37223 x)
(define y (/ (- x (remainder x 2)) 2))
(* (factorial y) (expt 2 y)))
(define (a37224 x) 
(define y (div4 x))
(cond ((> (remainder x 4) 1) 0) ((= x 1) 1) (else (/ (* 2 (factorial (- (* 2 y) 1))) (factorial (- y 1))))))
(define (a85 x)
(cond ((< x 2) 1) (else (+ (a85 (- x 1)) (* (- x 1) (a85 (- x 2)))))))
(define (a00000000000000000000000000000000000000903 x)
(cond ((= x 1) 1) (else (/ (+ (factorial x) (+ (a37223 x) (* 2 (+ (a37224 x) (a85 x))))) 8))))

Try it online!

Next Sequence

\$\endgroup\$
  • \$\begingroup\$ It's 627 bytes, not 526, and the Next Sequence link does not point to any of these sequences. I just finished writing a program for A000643... \$\endgroup\$ – NieDzejkob Sep 4 '17 at 8:17
1
\$\begingroup\$

138. Chapel, 689 bytes, A000701

proc sigma(n: int): int { // A000203
	var sum: int = 0;
	for d in 1..n {
		if n % d == 0 {
			sum += d;
		}
	}

	return sum;
}

proc sumodd(n: int): int { // A000593
	var sum: int = 0;
	for d in 1..n {
		if (n % d == 0) & (d % 2 == 1) {
			sum += d;
		}
	}

	return sum;
}

proc part(n: int): int { // A000041
	if n == 0 { return 1; }

	var sum: int = 0;
	for k in 0..(n-1) {
		sum += sigma(n-k) * part(k);
	}

	return sum / n;
}

proc helper(n: int): int { // A000700
	if n == 0 { return 1; }

	var sum: int = 0;
	for k in 1..n {
		sum += (if k % 2 == 0 then -1 else 1) * sumodd(k) * helper(n-k);
	}

	return sum / n;
}

var n: int;
n = stdin.read(int);

write((part(n) - helper(n)) / 2);

Should be pretty self-explanatory. I'm surprised such a nice language was available for so long.

Try it online!

Next sequence!

\$\endgroup\$
1
\$\begingroup\$

139. Perl 6, 52 bytes, A000689

my $n=get();
$n= 2**$n;
print substr($n,$n.chars-1);

Try it online!

Next Sequence

\$\endgroup\$
  • \$\begingroup\$ The next sequence would be a lot easier if it weren't for the teens. \$\endgroup\$ – KSmarts Sep 6 '17 at 16:38
  • \$\begingroup\$ @KSmarts well, there is a Mathematica program, and Mathematica 11 hasn't been used yet... \$\endgroup\$ – Stephen Sep 6 '17 at 16:59
  • 1
    \$\begingroup\$ If you'll give me $300, I'll do it in Mathematica. Or give me $240, and I'll do it in Maple. \$\endgroup\$ – KSmarts Sep 6 '17 at 18:43

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.