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>

  • Comments are not for extended discussion; this conversation has been moved to chat. – Dennis Oct 31 '17 at 2:49
  • 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? – NieDzejkob Nov 21 '17 at 15:15
  • 1
    @Giuseppe No, as you're generating the numbers by doing the maths, rather than just placing them into an array/string – caird coinheringaahing Dec 15 '17 at 22:14
  • 2
    @cairdcoinheringaahing In my opinion that's hardcoding the gamma constant. It doesn't work "in theory" for larger numbers. – user202729 Dec 22 '17 at 12:44
  • 6
    Chat room – user202729 Dec 22 '17 at 12:45

346 Answers 346

up vote 4 down vote accepted

345. brainfuck, 162 bytes, A000301

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

Try it online!

Next sequence!

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

Explanation:

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

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

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

  • As the next answer (#346) broke the chain, your answer is the winner! – caird coinheringaahing Mar 14 at 16:58
  • 1
    @cairdcoinheringaahing Thank you for this amazing challenge. It saddens me that it should end now, but as do all good things in the world, end it did. Now to golf this poor excuse for code, for it's now the first answer anyone will see, and it must be impressively short... – Scrooble Mar 14 at 18:23
  • @Scrooble you can't really change the length... – NieDzejkob Mar 15 at 14:22
  • @NieDzejkob Yeah, but I can golf and add some more padding, to keep the same length. – Scrooble Mar 15 at 15:25
  • @cairdcoinheringaahing "broke the chain"? What does that mean? – Magic Octopus Urn Aug 2 at 20:02

22. FiM++, 982 bytes, A000024

Note: if you are reading this, you might want to sort by "oldest".

Dear PPCG: I solved A000024!

I learned how to party to get a number using the number x and the number y.
Did you know that the number beers was x?
For every number chug from 1 to y,
  beers became beers times x!
That's what I did.
Then you get beers!
That's all about how to party.

Today I learned how to do math to get a number using the number n.
Did you know that the number answer was 0?
For every number x from 1 to n,
  For every number y from 1 to n,
    Did you know that the number tmp1 was how to party using x and 2?
    Did you know that the number tmp2 was how to party using y and 2?
    Did you know that the number max was how to party using 2 and n?
    tmp2 became tmp2 times 10!
    tmp1 became tmp1 plus tmp2!
    If tmp1 is more than max then: answer got one more.
  That's what I did.
That's what I did.
Then you get answer!
That's all about how to do math.

Your faithful student, BlackCap.

PS:  This is the best answer
PPS: This really is the best answer

Next sequence

  • 10
    Hahaha, laughed so hard through the whole thing. +1 for choice of language :-) – ETHproductions Jul 22 '17 at 13:49
  • Amazing, take my upvote – downrep_nation Jul 23 '17 at 11:11

1. Triangular, 10 bytes, A000217

$\:_%i/2*<

Try it online!

Next Sequence

How it works

The code formats into this triangle

   $
  \ :
 _ % i
/ 2 * <

with the IP starting at the $ and moving South East (SE, heh), works like this:

$            Take a numerical input (n);     STACK = [n]
 :           Duplicate it;                   STACK = [n, n]
  i          Increment the ToS;              STACK = [n, n+1]
   <         Set IP to W;                    STACK = [n, n+1]
    *        Multiply ToS and 2ndTos;        STACK = [n(n+1)]
     2       Push 2;                         STACK = [n(n+1), 2]
      /      Set IP to NE;                   STACK = [n(n+1), 2]
       _     Divide ToS by 2ndToS;           STACK = [n(n+1)/2]
        \    Set IP to SE (heh);             STACK = [n(n+1)/2]
         %   Output ToS as number;           STACK = [n(n+1)/2]
          *  Multiply ToS by 2ndToS (no op); STACK = [n(n+1)/2]
  • 13
    1. Triangular, 10 bytes, A000217. *follows link* A000217 Triangular numbers ... – MD XF Jul 23 '17 at 3:39

73. Starry, 363 bytes, A000252

, +      + *     '.     `
 + + + +  *  *  *  +     
 +`      +*       +    ` 
 + +   +  + +   + *  '   
   +   '  ####`  + +   + 
 + +    ####  +*   +    *
    '  #####  +      + ' 
  `    ######+  + +   +  
+ +   + #########   * '  
 +   +  + #####+ +      +
*  +      + * +  *  *   +
   +  *  + + + +  *  *   
+   +  +   *   + `  + +  
 +  + +   + *'    +    +.

Try it online!

Next sequence

Uses the formula "a(n) = n^4 * product p^(-3)(p^2 - 1)*(p - 1) where the product is over all the primes p that divide n" from OEIS.

The moon's a no-op, but hey, this isn't code-golf.

  • stars in moon? hmmm – betseg Jan 1 at 14:45
up vote 19 down vote
+100

97. Python 3 (PyPy), 1772 bytes, A000236

First of all, many thanks to Dr. Max Alekseyev for being patient with me. I'm very fortunate that I was able to contact him by email to understand this challenge. His Math.SE answer here helped me out a lot. Thanks to Wheat Wizard for helping me as well. :)

plist = []

def primes(maximal = -1): # Semi-efficient prime number generator with caching up to a certain max.
	index = plist and plist[-1] or 2
	for prime in plist:
		if prime <= maximal or maximal == -1: yield prime
		else: break
	while index <= maximal or maximal == -1:
		composite = False
		for prime in plist:
			if index % prime == 0:
				composite = True
				break
		if not composite:
			yield index
			plist.append(index)
		index += 1

def modinv(num, mod): # Multiplicative inverse with a modulus
	index = 1
	while num * index % mod != 1: index += 1
	return index

def moddiv(num, dnm, mod):
	return num * modinv(dnm, mod) % mod

def isPowerResidue(num, exp, mod):
	for base in range(mod):
		if pow(base, exp, mod) == num:
			return base
	return False

def compute(power, prime):
	for num in range(2, prime):
		if isPowerResidue(moddiv(num - 1, num, prime), power, prime):
			return num - 1
	return -1

# file = open('output.txt', 'w')

def output(string):
	print(string)
	# file.write(str(string) + '\n')

def compPrimes(power, count):
	maximum = 0
	index = 0
	for prime in getValidPrimes(power, count):
		result = compute(power, prime)
		if result > maximum: maximum = result
		index += 1
		# output('Computed %d / %d = %d%% [result = %d, prime = %d]' % (index, count, (100 * index) // count, result, prime))
	return maximum

def isValidPrime(power, prime):
	return (prime - 1) % power == 0

def getValidPrimes(power, count):
	collected = []
	for prime in primes():
		if isValidPrime(power, prime):
			collected.append(prime)
		if len(collected) >= count:
			return collected
		# output('Collected %d / %d = %d%% [%d]' % (len(collected), count, (100 * len(collected)) // count, prime))

power = int(input()) + 2

output(compPrimes(power, 100))

# file.close()

Try it online!

If it gives the wrong result, just increase the 100 to something larger. I think 10000 will work for 4 but I'll leave my computer running overnight to confirm that; it may take a couple of hours to finish.

Note that the (PyPy) part is just so that I can use Python again. I really don't know many other languages and I'm not going to try to port this to Java and risk not finishing in time.

Next Sequence (Also please don't do any more crazy math stuff; I don't have any Python versions left so someone else will have to save this challenge D:)

  • well there's always pypy3 – ASCII-only Aug 6 '17 at 4:29
up vote 15 down vote
+100

107. TrumpScript, 1589 bytes, A000047

My cat hears everything really well
because with me every cat is a safe cat
Everybody knows that one is 1000001 minus 1000000
but only most of you that two is, one plus one;
As always nothing is, one minus one;
My dog is one year old.
I promise you that as long as you vote on me, nothing will be less cool than a cat;:
Much dog is, dog times two;
Dead cat is, cat minus one;!
I will make dog feel good, food for dog plus one;
Roads can be made using different things. Asphalt is one of them.
As long as Hillary jailed, I love asphalt less than my dog;:
Roads are, always made using asphalt plus one of other things;
I promise my roadways are, two times asphalt than you want;
My roadways are great, always roadways plus one;
Vladimir is nothing more than my friend.
Name of Putin is Vladimir.
As long as, Putin eat less roadways;:
China is nothing interesting.
We all know people speaking Chinese are from China.
As long as, Chinese makes less roads;:
I will make economy, for Putin - Chinese will love me;
If it will mean, economy is asphalt in Russia?;:
I will make cat feel good, cat plus one dollar on food;
Make Vladimir roadways to help Russia economy.
Never make china roads!
I show you how great China is, China plus one; You can add numbers to China.
Like Chinese is, China times China makes sense;
Like Chinese is, two times Chinese letter;!
Make Vladimir happy, Vladimir plus one million dollars;
I also show you how great Putin is, Vladimir times Vladimir; You can do number stuff to Putin too!
I will make asphalt roads a lot!
Everybody say cat. You did it? America is great.

Try it online!

First time programming in TrumpScript, it is possible that I reinvented the wheel a few times - 4 lines are dedicated to calculating 2 ^ n. I tried to make it look like something that (drunk) Trump could say. As a bonus, here is a Python script I wrote to verify that I'm doing everything right. There are some differences to the above program, but much of it is directly equivalent.

cat = int(input())
dog = 2 ** cat + 1
asphalt = 1
cat = 0
while asphalt < dog:
    roads = asphalt + 1
    roadways = 2 * asphalt + 1
    vladimir = 0
    putin = vladimir
    while putin < roadways:
        china = 0
        chinese = china
        while chinese < roads:
            chair = putin - chinese
            if chair == asphalt:
                cat += 1
                vladimir = roadways
                china = roads
            china += 1
            chinese = 2 * china * china
        vladimir += 1
        putin = vladimir * vladimir
    asphalt = roads
print(cat)

Next sequence!

  • 3
    I will make cat feel good O_O – Business Cat Aug 15 '17 at 16:20
  • Sadly I will make Business Cat feel good won't work... – NieDzejkob Aug 15 '17 at 16:26

30. Python 1, 1112 bytes, A000046

def rotations(array):
	rotations = []
	for divider_index in range(len(array)):
		rotations.append(array[divider_index:] + array[:divider_index])
	return rotations

def next(array):
	for index in range(len(array) - 1, -1, -1):
		array[index] = 1 - array[index]
		if array[index]: break
	return array

def reverse(array):
	reversed = []
	for index in range(len(array) - 1, -1, -1):
		reversed.append(array[index])
	return reversed

def primitive(array):
	for index in range(1, len(array)):
		if array == array[:index] * (len(array) / index): return 1
	return 0

def necklaces(size):
	previous_necklaces = []
	array = [0] * size
	necklaces = 0
	for iteration in range(2 ** size):
		if not primitive(array) and array not in previous_necklaces:
			necklaces = necklaces + 1
			for rotation in rotations(array):
				complement = []
				for element in rotation:
					complement.append(1 - element)
				previous_necklaces.append(rotation)
				previous_necklaces.append(complement)
				previous_necklaces.append(reverse(rotation))
				previous_necklaces.append(reverse(complement))
		array = next(array)
	return necklaces

Try it online!

Not even going to bother to golf this. Hey, it's not my longest Python answer on this site!

Next sequence

  • 1
    Congratulations on decoding the maths :D – Leaky Nun Jul 22 '17 at 4:27
  • 2
    313 bytes, lol – Leaky Nun Jul 22 '17 at 4:57
  • @LeakyNun As I was saying, I didn't bother to golf this lol. Besides, it's not my longest Python answer on this site so idc :P but nice – HyperNeutrino Jul 22 '17 at 15:16
  • @LeakyNun And thanks :D It took me a while to understand all of it lol – HyperNeutrino Jul 22 '17 at 16:22
  • @LeakyNun 309 bytes because the actual value of _ is irrelevant; we just need to repeat that many times – HyperNeutrino Sep 24 '17 at 1:36

2. Haskell, 44 bytes, A000010

f k|n<-k+1=length.filter(==1)$gcd n<$>[1..n]

Try it online!

Next Sequence

  • 11
    The name of the next sequence though... – not not totallyhuman Jul 21 '17 at 15:16
  • @totallyhuman poor rabbits... – Erik the Outgolfer Jul 21 '17 at 15:17
  • Should we link to the previous post? – Leaky Nun Jul 21 '17 at 15:17
  • It pains me that I cannot golf it now. I had to be first you see – BlackCap Jul 21 '17 at 15:20
  • What is that next sequence? I don't understand the three ones :P – Beta Decay Jul 21 '17 at 15:20

9. Pyth, 19 bytes, A000025

?>Q0sm@_B1-edld./Q1

Test suite.

Next sequence

a(n) = number of partitions of n with even rank minus number with odd rank. The rank of a partition is its largest part minus the number of parts.

  • For those who know Pyth, I deliberately used >Q0 instead of Q in order to, you know, have the next sequence to be A000019. – Leaky Nun Jul 21 '17 at 16:41
  • 1
    From the OEIS page Keywords: easy,nice – BlackCap Jul 21 '17 at 16:46
  • @LeakyNun Yeah since otherwise I'd have to solve A000017...gross. – Erik the Outgolfer Jul 21 '17 at 16:56

8. Mathematica (10.1), 25 bytes, A000070

Tr@PartitionsP@Range@#+1&

Next sequence

  • The perfect sequence to use Mathematica for. – Leaky Nun Jul 21 '17 at 15:52
  • 1
    A000025 is an incredibly difficult one. You should add a byte to get A000026 instead. :P – MD XF Jul 21 '17 at 16:29

206. Proton, 3275 bytes, A000109

# This took me quite a while to write; if it's wrong, please tell me and I'll try to fix it without changing the byte count..

permutations = x => {
	if len(x) == 0 return [ ]
	if len(x) == 1 return [x]
	result = []
	for index : range(len(x)) {
		for permutation : permutations(x[to index] + x[index + 1 to]) {
			result.append([x[index]] + permutation)
		}
	}
	return result
}

adjacency = cycles => {
	cycles = cycles[to]
	size = cycles.pop()
	matrix = [[0] * size for i : range(size)]
	for cycle : cycles {
		i, j, k = cycle[0], cycle[1], cycle[2]
		matrix[i][j] = matrix[i][k] = matrix[j][i] = matrix[j][k] = matrix[k][i] = matrix[k][j] = 1
	}
	return matrix
}

transform = a => [[a[j][i] for j : range(len(a[i]))] for i : range(len(a))]

isomorphic = (a, b) => {
	return any(sorted(b) == sorted(transform(A)) for A : permutations(transform(a)))
}

intersection = (a, b) => [x for x : a if x in b]

union = (a, b) => [x for x : a if x not in b] + list(b)

validate = graph => {
	matrix = adjacency(graph)
	rowsums = map(sum, matrix)
	r = 0
	for s : rowsums if s + 1 < graph[-1] r++
	return 2 || r
}

graphs = nodes => {
	if nodes <= 2 return []
	if nodes == 3 return [[(0, 1, 2), 3]]
	result = []
	existing = []
	for graph : graphs(nodes - 1) {
		graph = graph[to]
		next = graph.pop()
		for index : range(len(graph)) {
			g = graph[to]
			cycle = g.pop(index)
			n = g + [(cycle[0], cycle[1], next), (cycle[1], cycle[2], next), (cycle[2], cycle[0], next), next + 1]
			N = sorted(adjacency(n))
			if N not in existing {
				existing += [sorted(transform(a)) for a : permutations(transform(adjacency(n)))]
				result.append(n)
			}
			for secondary : index .. len(graph) - 1 {
				g = graph[to]
				c1 = g.pop(index)
				c2 = g.pop(secondary)
				q = union(c1, c2)
				g = [k for k : g if len(intersection(k, intersection(c1, c2))) <= 1]
				if len(intersection(c1, c2)) == 2 {
					for i : range(3) {
						for j : i + 1 .. 4 {
							if len(intersection(q[i, j], intersection(c1, c2))) <= 1 {
								g.append((q[i], q[j], next))
							}
						}
					}
				}
				g.append(next + 1)
				N = sorted(adjacency(g))
				if N not in existing {
					existing += [sorted(transform(a)) for a : permutations(transform(adjacency(g)))]
					result.append(g)
				}
				for tertiary : secondary .. len(graph) - 2 {
					g = graph[to]
					c1 = g.pop(index)
					c2 = g.pop(secondary)
					c3 = g.pop(tertiary)
					q = union(union(c1, c2), c3)
					g = [k for k : g if len(intersection(k, intersection(c1, c2))) <= 1 and len(intersection(k, intersection(c2, c3))) <= 1]
					if len(q) == 5 and len(intersection((q1 = intersection(c1, c2)), (q2 = intersection(c2, c3)))) <= 1 and len(q1) == 2 and len(q2) == 2 {
						for i : range(4) {
							for j : i + 1 .. 5 {
								if len(intersection(q[i, j], q1)) <= 1 and len(intersection(q[i, j], q2)) <= 1 {
									g.append((q[i], q[j], next))
								}
							}
						}
						g.append(next + 1)
						N = sorted(adjacency(g))
						if N not in existing {
							existing += [sorted(transform(a)) for a : permutations(transform(adjacency(g)))]
							result.append(g)
						}
					}
				}
			}
		}
	}
	return [k for k : result if max(sum(k[to -1], tuple([]))) + 1 == k[-1] and validate(k)]
}

x = graphs(int(input()) + 3)
print(len(x))

Try it online!

Next Sequence

  • Wait, you actually did it? If you don't write a paper with these freaking programs and go talk to some professor, you're passing up on something cool :P – Stephen Oct 10 '17 at 2:54
  • @Stephen Currently bugfixing lol – HyperNeutrino Oct 10 '17 at 2:58
  • Is this the approach of splitting triangles, squares, and pentagons as per plantri? Looks like it might be, but some of the syntax is unfamiliar. – Peter Taylor Oct 10 '17 at 6:50
  • 1
    @PeterTaylor Assuming I understand the approach you're describing, yes, it looks for triangles and places a vertex adjacent to all 3 vertices, or two adjacent cycles and deletes the common edge and places a vertex adjacent to all 4, same for 3 triangles on a pentagon. I think that's one you're describing. – HyperNeutrino Oct 10 '17 at 12:01
  • 1
    @ChristianSievers math.stackexchange.com/a/2463430/457091 – HyperNeutrino Oct 10 '17 at 15:06

308. ENIAC (simulator), 3025 bytes, A006060

Pseudocode:

repeat{
    M←input
    N←-M
    A←1
    B←253
    while(N<0){
        C←60
        C←C-A
        repeat(194){
            C←C+B
        }
        A←B
        B←C
        N←N+1
    }
    output←A
}

No online simulator, execution result: Card reader input Punch card output

Registers and constants:

A: 1-2
B: 3-4
C: 5-6
M: 7
N: 8

input: const. A
253: const. J
60: const. K
194: Master programmer decade limit 1B

Program signal flow and data flow: Program signal flow and data flow chart

Full "code" on pastebin or in HTML comments in the markup of this answer, to prevent linkrot and a quite long answer to scroll through at the same time. This is fun!

Next sequence

  • Could you add a link to the next sequence please – Zacharý Jan 8 at 16:52
  • @Zacharý The link is in the post. I'll move it to the end of the post so it's easier to find. – leo3065 Jan 8 at 17:02

67. LOLCODE, 837 bytes, A000043

HAI 1.2
  CAN HAS STDIO?

  I HAS A CONT ITZ 0
  I HAS A ITRZ ITZ 1
  I HAS A NUMBAH
  GIMMEH NUMBAH
  NUMBAH R SUM OF NUMBAH AN 1

  IM IN YR GF
    ITRZ R SUM OF ITRZ AN 1

    I HAS A PROD ITZ 1
    IM IN YR MOM UPPIN YR ASS WILE DIFFRINT ITRZ AN SMALLR OF ITRZ AN ASS
      PROD R PRODUKT OF PROD AN 2
    IM OUTTA YR MOM
    PROD R DIFF OF PROD AN 1

    I HAS A PRAIME ITZ WIN
    I HAS A VAR ITZ 1
    IM IN YR MOM
      VAR R SUM OF VAR AN 1
      BOTH SAEM VAR AN PROD, O RLY?
        YA RLY, GTFO
      OIC
      BOTH SAEM 0 AN MOD OF PROD AN VAR, O RLY?
        YA RLY
          PRAIME R FAIL
          GTFO
      OIC
    IM OUTTA YR MOM

    BOTH SAEM PRAIME AN WIN, O RLY?
      YA RLY, CONT R SUM OF CONT AN 1
    OIC

    BOTH SAEM NUMBAH AN CONT, O RLY?
      YA RLY, GTFO
    OIC
  IM OUTTA YR GF

  VISIBLE ITRZ
KTHXBYE

My capslock key is bound to escape, so I wrote this entire thing while holding shift ..

Try it online!

Next sequence

  • +1 for using PRAIME – Leaky Nun Jul 23 '17 at 9:07
  • 3
    You're a programmer, you could have written this and then run it through a Python script that upper'd it -.- – Stephen Jul 23 '17 at 12:25
  • 5
    @StepHen Or simply gggUG in vim where I wrote it, but I am not that clever – BlackCap Jul 23 '17 at 12:36

15. CJam, 85 bytes, A000060

{ee\f{\~\0a*@+f*}:.+}:C;2,qi:Q,2f+{_ee1>{~2*\,:!X*X<a*~}%{CX<}*W=+}fX_0a*1$_C.- .+Q)=

Online demo

Next sequence

Dissection

OEIS gives

G.f.: S(x)+S(x^2)-S(x)^2, where S(x) is the generating function for A000151. - Pab Ter, Oct 12 2005

where

$$\begin{eqnarray*}S(x) & = & x \prod_{i \ge 1} \frac{1}{(1 - x^i)^{2s(i)}} \\ & = & x \prod_{i \ge 1} (1 + x^i + x^{2i} + \ldots)^{2s(i)}\end{eqnarray*}$$

{           e# Define a block to convolve two sequences (multiply two polynomials)
  ee\f{     e#   Index one and use the other as an extra parameter for a map
    \~\0a*  e#     Stack manipulations; create a sequence of `index` 0s
    @+f*    e#     Shift the extra parameter poly and multiply by the coefficient
  }
  :.+       e#   Fold pointwise add to sum the polys
}:C;        e# Assign the block to C (for "convolve")
2,          e# Initial values of S: S(0) = 0, S(1) = 1
qi:Q        e# Read integer and assign it to Q
,2f+{       e# For X = 2 to Q+1
  _ee1>     e#   Duplicate accumulator of S, index, and ditch 0th term
  {         e#   Map (over notional variable i)
    ~2*\    e#     Double S(i) and flip i to top of stack
    ,:!     e#     Create an array with a 1 and i-1 0s
    X*X<    e#     Replicate X times and truncate to X values
            e#     This gives g.f. 1/(1-x^i) to the first X terms
    a*~     e#     Create 2S(i) copies of this polynomial
  }%
  {CX<}*    e#   Fold convolution and truncation to X terms
  W=+       e#   Append the final coefficient, which is S(X), to the accumulator
}fX
_0a*        e# Pad a copy to get S(X^2)
1$_C        e# Convolve two copies to get S(X)^2
.-          e# Pointwise subtraction
 .+         e# Pointwise addition. Note the leading space because the parser thinks
            e# -. is an invalid number
Q)=         e# Take the term at index Q+1 (where the +1 adjusts for OEIS offset)
  • 1 minute and 33 seconds ahead of me... while I was typing the explanation – Leaky Nun Jul 21 '17 at 19:05

10. Magma, 65 bytes, A000019

f:=function(n);return NumberOfPrimitiveGroups(n+1);end function;

Try it here

lol builtin

Next sequence

  • @ETHproductions :) no problem, thank the OEIS page though cuz it has the exact builtin there lol – HyperNeutrino Jul 21 '17 at 17:20
  • 4
    ;_; I solved A000064 and you changed it. Downvoted. – Leaky Nun Jul 21 '17 at 17:26
  • My gosh, so many partition sequences – ETHproductions Jul 21 '17 at 17:27
  • I accidentally solved A007317 while trying to do this in Python (TIO) :P – ETHproductions Jul 21 '17 at 17:36
  • Re-upvoted! \o/ – Leaky Nun Jul 21 '17 at 17:38

24. Julia 0.5, 33 bytes, A000023

Expansion of e.g.f. exp(−2*x)/(1−x).

!x=foldl((a,b)->a*b+(-2)^b,1,1:x)

Try it online!

Next sequence.

121. Pip, 525 bytes, A000022

n:(a+1)//2
t:[[0]RL(3*a+3)PE1]
Fh,n{
  m:([0]RL(3*a+3))
  Fi,(a+1){
    Fj,(a+1){
      Fk,(a+1)m@(i+j+k)+:(t@h@i)*(t@h@j)*(t@h@k)
      m@(i+2*j)+:3*(t@h@i)*(t@h@j)
    }
    m@(3*i)+:2*(t@h@i)
  }
  t:(tAE(m//6PE1))
}
k:t@n
o:0
Fh,aFi,aFj,aI(h+i+j<a)o+:(k@h)*(k@i)*(k@j)*k@(a-1-h-i-j)
Fh,((a+1)//2){
  Fi,aI(2*h+i<a){o+:6*(k@h)*(k@i)*(k@(a-1-2*h-i))}
  I(a%2=1)o+:3*(k@h)*(k@((a-1-2*h)//2))
}
Fh,((a+2)//3)o+:8*(k@h)*(k@(a-1-3*h))
I(a%4=1)o+:6*k@(a//4)
o//:24
Ia(o+:t@n@a)
Fh,nFj,(a+1)o-:(t@(h+1)@j-t@h@j)*(t@(h+1)@(a-j))
o

Online demo

Next sequence

Fun fact: when the challenge was first posted, I drew up a list of small nasty sequence numbers that I wanted to aim for with CJam, and A000022 was at the top of the list.

This implements the generating function described in E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), Journal of Integer Sequences, Vol. 2 (1999), taking the sum for Ck to as many terms as a necessary for the nth coefficient to be fixed and then telescoping three quarters of the sum. In particular, telescoping the first half means that the cycle index of S4 only has to be applied to one of the Th rather than to all of them.

The code breaks down as

; Calculate the relevant T_h
t:[[0]RL(3*a+3)PE1]
Fh,n{
  m:([0]RL(3*a+3))
  Fi,(a+1){
    Fj,(a+1){
      Fk,(a+1)m@(i+j+k)+:(t@h@i)*(t@h@j)*(t@h@k)
      m@(i+2*j)+:3*(t@h@i)*(t@h@j)
    }
    m@(3*i)+:2*(t@h@i)
  }
  t:(tAE(m//6PE1))
}

; Calculate the cycle index of S_4 applied to the last one
k:t@n
o:0
Fh,aFi,aFj,aI(h+i+j<a)o+:(k@h)*(k@i)*(k@j)*k@(a-1-h-i-j)
Fh,((a+1)//2){
  Fi,aI(2*h+i<a){o+:6*(k@h)*(k@i)*(k@(a-1-2*h-i))}
  I(a%2=1)o+:3*(k@h)*(k@((a-1-2*h)//2))
}
Fh,((a+2)//3)o+:8*(k@h)*(k@(a-1-3*h))
I(a%4=1)o+:6*k@(a//4)
o//:24

; Handle the remaining convolution,
; pulling out the special case which involves T_{-2}
Ia(o+:t@n@a)
Fh,nFj,(a+1)o-:(t@(h+1)@j-t@h@j)*(t@(h+1)@(a-j))

Note that this is my first ever Pip program, so is probably not very idiomatic.

  • Comments are not for extended discussion; this conversation has been moved to chat. – Dennis Aug 31 '17 at 12:28

156. C# (Mono), 2466 bytes, A000083

Note: the score is 2439 bytes for the code and 27 for the compiler flag -reference:System.Numerics.

using Num = System.Numerics.BigInteger;
namespace PPCG
{
    class A000083
    {
        static void Main(string[] a)
        {
            int N = int.Parse(a[0]) + 1;

            var phi = new int[N + 1];
            for (int i = 1; i <= N; i++)
                phi[i] = 1;
            for (int p = 2; p <= N; p++)
            {
                if (phi[p] > 1) continue;
                for (int i = p; i <= N; i += p)
                    phi[i] *= p - 1;
                int pa = p * p;
                while (pa <= N)
                {
                    for (int i = pa; i <= N; i += pa)
                        phi[i] *= p;
                    pa *= p;
                }
            }

            var aik = new Num[N + 1, N + 1];
            var a035350 = new Num[N + 1];
            var a035349 = new Num[N + 1];
            aik[0, 0] = aik[1, 1] = a035350[0] = a035350[1] = a035349[0] = a035349[1] = 1;
            for (int n = 2; n <= N; n++)
            {
                // A000237 = EULER(A035350)
                Num nbn = 0;
                for (int k = 1; k < n; k++)
                    for (int d = 1; d <= k; d++)
                        if (k % d == 0) nbn += d * a035350[d] * aik[1, n - k];
                aik[1, n] = nbn / (n - 1);

                // Powers of A000237 are used a lot
                for (int k = 2; k <= N; k++)
                    for (int i = 0; i <= n; i++)
                        aik[k, n] += aik[k - 1, i] * aik[1, n - i];

                // A035350 = BIK(A000237)
                Num bn = 0;
                for (int k = 1; k <= n; k++)
                {
                    bn += aik[k, n];
                    if (k % 2 == 1)
                        for (int i = n & 1; i <= n; i += 2)
                            bn += aik[1, i] * aik[k / 2, (n - i) / 2];
                    else if (n % 2 == 0)
                        bn += aik[k / 2, n / 2];
                }
                a035350[n] = bn / 2;

                // A035349 = DIK(A000237)
                Num dn = 0;
                for (int k = 1; k <= n; k++)
                {
                    // DIK_k is Polyà enumeration with the cyclic group D_k
                    // The cycle index for D_k has two parts: C_k and what Bower calls CPAL_k
                    // C_k
                    Num cikk = 0;
                    for (int d = 1; d <= k; d++)
                        if (k % d == 0 && n % d == 0)
                            cikk += phi[d] * aik[k / d, n / d];
                    dn += cikk / k;

                    // CPAL_k
                    if (k % 2 == 1)
                        for (int i = 0; i <= n; i += 2)
                            dn += aik[1, n - i] * aik[k / 2, i / 2];
                    else
                    {
                        Num cpalk = 0;
                        for (int i = 0; i <= n; i += 2)
                            cpalk += aik[2, n - i] * aik[k / 2 - 1, i / 2];
                        if (n % 2 == 0)
                            cpalk += aik[k / 2, n / 2];
                        dn += cpalk / 2;
                    }
                }
                a035349[n] = dn / 2;
            }

            // A000083 = A000237 + A035350 - A000237 * A035349
            var a000083 = new Num[N + 1];
            for (int i = 0; i <= N; i++)
            {
                a000083[i] = aik[1, i] + a035349[i];
                for (int j = 0; j <= i; j++) a000083[i] -= aik[1, j] * a035350[i - j];
            }

            System.Console.WriteLine(a000083[N - 1]);
        }
    }
}

Online demo. This is a full program which takes input from the command line.

Next sequence

Dissection

I follow Bowen's comment in OEIS that the generating function A000083(x) = A000237(x) + A035349(x) - A000237(x) * A035350(x) where the component generating functions are related by transforms as

  • A000237(x) = x EULER(A035350(x))
  • A035350(x) = BIK(A000237(x))
  • A035349(x) = DIK(A000237(x))

I use the definitions of BIK and DIK from https://oeis.org/transforms2.html but the formulae seem to have a number of typos. I corrected LPAL without much difficulty, and independently derived a formula for DIK based on applying Pólya enumeration to the cycle index of the dihedral group. Between #121 and #156 I'm learning a lot about Pólya enumeration. I have submitted some errata, which may prove useful to other people if these transforms come up again in the chain.

3. JavaScript (ES6), 38 bytes, A000044

f=n=>n<0?0:n<3?1:f(n-1)+f(n-2)-f(n-13)

Try it online!

Next sequence (should be an easy one :P)

13. VB.NET (.NET 4.5), 1246 bytes, A000131

Public Class A000131
    Public Shared Function Catalan(n As Long) As Long
        Dim ans As Decimal = 1
        For k As Integer = 2 To n
            ans *= (n + k) / k
        Next
        Return ans
    End Function
    Shared Function Answer(n As Long) As Long

        n += 7

        Dim a As Long = Catalan(n - 2)

        Dim b As Long = Catalan(n / 2 - 1)
        If n Mod 2 = 0 Then
            b = Catalan(n / 2 - 1)
        Else
            b = 0
        End If

        Dim c As Long = Catalan(n \ 2 - 1) ' integer division (floor)

        Dim d As Long
        If n Mod 3 = 0 Then
            d = Catalan(n / 3 - 1)
        Else
            d = 0
        End If

        Dim e As Long = Catalan(n / 4 - 1)
        If n Mod 4 = 0 Then
            e = Catalan(n / 4 - 1)
        Else
            e = 0
        End If

        Dim f As Long = Catalan(n / 6 - 1)
        If n Mod 6 = 0 Then
            f = Catalan(n / 6 - 1)
        Else
            f = 0
        End If

        Return (
                    a -
                    (n / 2) * b -
                    n * c -
                    (n / 3) * d +
                    n * e +
                    n * f
                ) /
                (2 * n)
    End Function
End Class

A001246

Try it Online!

91. Python 2 (PyPy), 1733 bytes, A000066

import itertools

girth = int(input()) + 3

v = 4

r = range

def p(v):
	a = [0 for i in r(v)]
	k = int((v * 2) ** .5)
	a[k - 1] = a[k - 2] = a[k - 3] = 1
	j = len(a) - 1
	for i in r(1, 3):
		a[j] = 1
		j -= i
	yield [x for x in a]
	while not all(a):
		for index in r(len(a) - 1, -1, -1):
			a[index] ^= 1
			if a[index]: break
		yield [x for x in a]

def wrap_(p, v):
	m = [[0 for j in r(v)] for i in r(v)]
	k = 0
	for i in r(0, v - 1):
		for j in r(i + 1, v):
			m[i][j] = m[j][i] = p[k]
			k += 1
	return m

def completes_cycle(edgelist):
	if not edgelist or not edgelist[1:]: return False
	start = edgelist[0]
	edge = edgelist[0]
	e = [x for x in edgelist]
	edgelist = edgelist[1:]
	while edgelist:
		_edges = [_edge for _edge in edgelist if _edge[0] in edge or _edge[1] in edge]
		if _edges:
			edgelist.remove(_edges[0])
			if _edges[0][1] in edge: _edges[0] = (_edges[0][1], _edges[0][0])
			edge = _edges[0]
		else:
			return False
	flat = sum(e, ())
	for i in flat:
		if flat.count(i) != 2: return False
	return edge[1] in start

def powerset(a):
	return sum([list(itertools.combinations(a, t)) for t in r(len(a))], [])

while True:
	ps = (v * (v - 1)) // 2
	skip = False
	for Q in p(ps):
		m = wrap_(Q, v)
		output = [row + [0] for row in m]
		output.append([0 for i in r(len(m[0]))])
		for i in r(len(m)):
			output[i][-1] = sum(m[i])
			output[-1][i] = sum(row[i] for row in m)
		if all(map(lambda x: x == 3, map(sum, m))):
			edges = []
			for i in r(v):
				for j in r(i, v):
					if m[i][j]: edges.append((i, j))
			for edgegroup in powerset(edges):
				if completes_cycle(list(edgegroup)):
					if len(edgegroup) == girth:
						print(v)
						exit(0)
					else:
						skip = True
						break
		if skip: break
	v += 1

Try it online!

I hope using Python 2 PyPy counts as another major version. If someone could get me a Python 0 interpreter, I could use that too, but I hope this is valid.

This starts at 1 vertex and works up, creating the adjacency matrix representation of every possible undirected graph with that many vertices. If it is trivalent, then it will look through the powerset of the edges, which will be sorted by length. If the first cycle it finds is too short, then it will move on. If the first cycle it finds matches the input (offset by 3) then it will output the correct vertex count and terminate.

Next Sequence <-- have an easy one as a break from all this math nonsense :D

EDIT: I added some optimizations to make it a bit faster (still can't compute the third term within TIO's 60 second limit though) without changing the bytecount.

  • ... and I was seriously thinking the chain would end with answer 90 – ppperry Jul 31 '17 at 0:04
  • 1
    @ppperry :) I like doing hard challenges because most people can't even make a solution so I don't have to worry about getting outgolfed :) (e.g. the carbon chain namer problem) – HyperNeutrino Jul 31 '17 at 0:25
  • Unless someone takes your solution and converts it into a terser language – ppperry Jul 31 '17 at 0:26
  • @ppperry that too o_O :P – HyperNeutrino Jul 31 '17 at 0:26
  • 1
    @HyperNeutrino Congrats on solving that! I was worried I had broken the chain, and was considering padding the byte count to point to a different sequence. Good job! – Scott Milner Jul 31 '17 at 22:27

232. Funky, 326 330 332 bytes, A000938

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

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

Try it online!

Polyglot with Javascript. Try it online!

Next sequence.


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

Quick explanation:

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

    • The formula is equivalent to this.

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

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

Some polyglot notes:

  • Funky doesn't really have keyword return. However, as ATaco explained, [Funky] thinks return is a variable. So it's parsing that expression, which conveniently does nothing, then parses the next expression. And this is used as an output.
  • Javascript use ^ as bitwise xor, unlike Funky which use ^ as exponentiation. So n*n have to be used instead of n^2 to ensure Javascript compatibility.
  • In Funky, all operator (+, -, *, etc.) have equal precedence and right-associative, so expressions need to be parenthesized properly.
  • 1
    +1 was not expecting a polyglot. – ATaco Oct 21 '17 at 3:11
  • There's no Pentagony, but Hexagony fits well. – NieDzejkob Oct 21 '17 at 5:24
  • This bytecount was used already... link – NieDzejkob Dec 5 '17 at 14:22
  • So, to fix the bytecount problem, could you please pad this answer to 330 bytes? I'll handle the rest. – NieDzejkob Dec 5 '17 at 17:41
  • [Answer padded to 332 bytes because of bytecount conflicting issues, see this chat message] – user202729 Dec 8 '17 at 0:50

11. Pari/GP, 64 bytes, A000065

{a(n) = if( n<0, 0, polcoeff ( 1 / eta(x + x*O(x^n) ), n) - 1)};

Try it online!

Next sequence

  • Is that valid input? – Leaky Nun Jul 21 '17 at 17:35
  • Didya have to get 64 bytes? :P – not not totallyhuman Jul 21 '17 at 17:40
  • @totallyhuman yes: ;_; I solved A000064 and you changed it. Downvoted. – Stephen Jul 21 '17 at 17:41
  • @totallyhuman compromises lol. see chat – HyperNeutrino Jul 21 '17 at 17:41
  • Dang – Mr. Xcoder Jul 21 '17 at 17:42

281. Java 5, 11628 bytes, A000947

// package oeis_challenge;

import java.util.*;
import java.lang.*;

class Main {

//  static void assert(boolean cond) {
//      if (!cond)
//          throw new Error("Assertion failed!");
//  }

    /* Use the formula a(n) = A000063(n + 2) - A000936(n).
    It's unfair that I use the formula of "number of free polyenoid with n
    nodes and symmetry point group C_{2v}" (formula listed in A000063)
    without understanding why it's true...
    */

    static int catalan(int x) {
        int ans = 1;
        for (int i = 1; i <= x; ++i)
            ans = ans * (2*x+1-i) / i;
        return ans / -~x;
    }

    static int A63(int n) {
        int ans = catalan(n/2 - 1);
        if (n%4 == 0) ans -= catalan(n/4 - 1);
        if (n%6 == 0) ans -= catalan(n/6 - 1);
        return ans;
    }

    static class Point implements Comparable<Point> {
        final int x, y;
        Point(int _x, int _y) {
            x = _x; y = _y;
        }

        /// @return true if this is a point, false otherwise (this is a vector)
        public boolean isPoint() {
            return (x + y) % 3 != 0;
        }

        /// Translate this point by a vector.
        public Point add(Point p) {
            assert(this.isPoint() && ! p.isPoint());
            return new Point(x + p.x, y + p.y);
        }

        /// Reflect this point along x-axis.
        public Point reflectX() {
            return new Point(x - y, -y);
        }

        /// Rotate this point 60 degrees counter-clockwise.
        public Point rot60() {
            return new Point(x - y, x);
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Point)) return false;
            Point p = (Point) o;
            return x == p.x && y == p.y;
        }

        @Override
        public int hashCode() {
            return 21521 * (3491 + x) + y;
        }

        public String toString() {
            // return String.format("(%d, %d)", x, y);
            return String.format("setxy %d %d", x * 50 - y * 25, y * 40);
        }

        public int compareTo(Point p) {
            int a = Integer.valueOf(x).compareTo(p.x);
            if (a != 0) return a;
            return Integer.valueOf(y).compareTo(p.y);
        }

        /// Helper class.
        static interface Predicate {
            abstract boolean test(Point p);
        }

        static abstract class UnaryFunction {
            abstract Point apply(Point p);
        }

    }

    static class Edge implements Comparable<Edge> {
        final Point a, b; // guarantee a < b
        Edge(Point x, Point y) {
            assert x != y;
            if (x.compareTo(y) > 0) { // y < x
                a = y; b = x;
            } else {
                a = x; b = y;
            }
        }

        public int compareTo(Edge e) {
            int x = a.compareTo(e.a);
            if (x != 0) return x;
            return b.compareTo(e.b);
        }
    }

    /// A graph consists of multiple {@code Point}s.
    static class Graph {
        private HashMap<Point, Point> points;

        public Graph() {
            points = new HashMap<Point, Point>();
        }

        public Graph(Graph g) {
            points = new HashMap<Point, Point>(g.points);
        }

        public void add(Point p, Point root) {
            assert(p.isPoint());
            assert(root.isPoint());
            assert(p == root || points.containsKey(root));
            points.put(p, root);
        }

        public Graph map(Point.UnaryFunction fn) {
            Graph result = new Graph();
            for (Map.Entry<Point, Point> pq : points.entrySet()) {
                Point p = pq.getKey(), q = pq.getValue();
                assert(p.isPoint()) : p;
                assert(q.isPoint()) : q;
                p = fn.apply(p); assert(p.isPoint()) : p;
                q = fn.apply(q); assert(q.isPoint()) : q;
                result.points.put(p, q);
            }
            return result;
        }

        public Graph reflectX() {
            return this.map(new Point.UnaryFunction() {
                public Point apply(Point p) {
                    return p.reflectX();
                }
            });
        }

        public Graph rot60() {
            return this.map(new Point.UnaryFunction() {
                public Point apply(Point p) {
                    return p.rot60();
                }
            });
        }

        @Override
        public boolean equals(Object o) {
            if (o == null) return false;
            if (o.getClass() != getClass()) return false;
            Graph g = (Graph) o;
            return points.equals(g.points);
        }

        @Override
        public int hashCode() {
            return points.hashCode();
        }

        Graph[] expand(Point.Predicate fn) {
            List<Graph> result = new ArrayList<Graph>();

            for (Point p : points.keySet()) {
                int[] deltaX = new int[] { -1, 0, 1, 1,  0, -1};
                int[] deltaY = new int[] {  0, 1, 1, 0, -1, -1};
                for (int i = 6; i --> 0;) {
                    Point p1 = new Point(p.x + deltaX[i], p.y + deltaY[i]);
                    if (points.containsKey(p1) || !fn.test(p1)
                        || !p1.isPoint()) continue;

                    Graph g = new Graph(this);
                    g.add(p1, p);
                    result.add(g);
                }
            }

            return result.toArray(new Graph[0]);
        }

        public static Graph[] expand(Graph[] graphs, Point.Predicate fn) {
            Set<Graph> result = new HashSet<Graph>();

            for (Graph g0 : graphs) {
                Graph[] g = g0.expand(fn);
                for (Graph g1 : g) {
                    if (result.contains(g1)) continue;
                    result.add(g1);
                }
            }

            return result.toArray(new Graph[0]);
        }

        private Edge[] edges() {
            List<Edge> result = new ArrayList<Edge>();
            for (Map.Entry<Point, Point> pq : points.entrySet()) {
                Point p = pq.getKey(), q = pq.getValue();
                if (p.equals(q)) continue;
                result.add(new Edge(p, q));
            }
            return result.toArray(new Edge[0]);
        }

        /**
         * Check if two graphs are isomorphic... under translation.
         * @return {@code true} if {@code this} is isomorphic
         * under translation, {@code false} otherwise.
         */
        public boolean isomorphic(Graph g) {
            if (points.size() != g.points.size()) return false;
            Edge[] a = this.edges();
            Edge[] b = g.edges();
            Arrays.sort(a);
            Arrays.sort(b);

            // for (Edge e : b)
                // System.err.println(e.a + " - " + e.b);
            // System.err.println("------- >><< ");

            assert (a.length > 0);
            assert (a.length == b.length);
            int a_bx = a[0].a.x - b[0].a.x, a_by = a[0].a.y - b[0].a.y;
            for (int i = 0; i < a.length; ++i) {
                if (a_bx != a[i].a.x - b[i].a.x || 
                    a_by != a[i].a.y - b[i].a.y) return false;
                if (a_bx != a[i].b.x - b[i].b.x || 
                    a_by != a[i].b.y - b[i].b.y) return false;
            }

            return true;
        }

        // C_{2v}.
        public boolean correctSymmetry() {

            Graph[] graphs = new Graph[6];
            graphs[0] = this.reflectX();
            for (int i = 1; i < 6; ++i) graphs[i] = graphs[i-1].rot60();
            assert(graphs[5].rot60().isomorphic(graphs[0]));
            int count = 0;
            for (Graph g : graphs) {
                if (this.isomorphic(g)) ++count;
                // if (count >= 2) {
                    // return false;
                // }
            }
            // if (count > 1) System.err.format("too much: %d%n", count);
            assert(count > 0);
            return count == 1; // which is, basically, true
        }

        public void reflectSelfType2() {
            Graph g = this.map(new Point.UnaryFunction() {
                public Point apply(Point p) {
                    return new Point(p.y - p.x, p.y);
                }
            });

            Point p = new Point(1, 1);
            assert (p.equals(points.get(p)));

            points.putAll(g.points);

            assert (p.equals(points.get(p)));
            Point q = new Point(0, 1);
            assert (q.equals(points.get(q)));
            points.put(p, q);
        }

        public void reflectSelfX() {
            Graph g = this.reflectX();
            points.putAll(g.points); // duplicates doesn't matter
        }

    }

    static int A936(int n) {
        // if (true) return (new int[]{0, 0, 0, 1, 1, 2, 4, 4, 12, 10, 29, 27, 88, 76, 247, 217, 722, 638, 2134, 1901, 6413})[n];

        // some unreachable codes here for testing.
        int ans = 0;

        if (n % 2 == 0) { // reflection type 2. (through line 2x == y)
            Graph[] graphs = new Graph[1];
            graphs[0] = new Graph();

            Point p = new Point(1, 1);
            graphs[0].add(p, p);

            for (int i = n / 2 - 1; i --> 0;)
                graphs = Graph.expand(graphs, new Point.Predicate() {
                    public boolean test(Point p) {
                        return 2*p.x > p.y;
                    }
                });

            int count = 0;
            for (Graph g : graphs) {
                g.reflectSelfType2();
                if (g.correctSymmetry()) {
                    ++count;

                    // for (Edge e : g.edges())
                        // System.err.println(e.a + " - " + e.b);
                    // System.err.println("------*");

                    }
                // else System.err.println("Failed");
            }

            assert (count%2 == 0);

            // System.err.println("A936(" + n + ") count = " + count + " -> " + (count/2));

            ans += count / 2;

        }

        // Reflection type 1. (reflectX)

        Graph[] graphs = new Graph[1];
        graphs[0] = new Graph();

        Point p = new Point(1, 0);
        graphs[0].add(p, p);

        if (n % 2 == 0) graphs[0].add(new Point(2, 0), p);

        for (int i = (n-1) / 2; i --> 0;)
            graphs = Graph.expand(graphs, new Point.Predicate() {
                public boolean test(Point p) {
                    return p.y > 0;
                }
            });

        int count = 0;
        for (Graph g : graphs) {
            g.reflectSelfX();
            if (g.correctSymmetry()) {
                ++count;
                // for (Edge e : g.edges())

                    // System.err.printf(

                // "pu %s pd %s\n"
                // // "%s - %s%n"

                // , e.a, e.b);
                // System.err.println("-------/");

            }
            // else System.err.println("Failed");
        }

        if(n % 2 == 0) {
            assert(count % 2 == 0);
            count /= 2;
        }
        ans += count;

        // System.err.println("A936(" + n + ") = " + ans);

        return ans;
    }

    public static void main(String[] args) {

        // Probably
        if (! "1.5.0_22".equals(System.getProperty("java.version"))) {
            System.err.println("Warning: Java version is not 1.5.0_22");
        }

        // A936(6);

        for (int i = 0; i < 20; ++i)
            System.out.println(i + " | " + (A63(i+9) - A936(i+7)));
        //A936(i+2);
    }
}

Try it online!


Side note:

  1. Tested locally with Java 5. (such that the warning is not printed - see TIO debug tab)
  2. Don't. Ever. Use. Java. 1. It's more verbose than Java in general.
  3. This may break the chain.
  4. The gap (7 days and 48 minutes) is no more than the gap created by this answer, which is 7 days and 1 hours 25 minutes later than the previous one.
  5. New record on large bytecount! Because I (mistakenly?) use spaces instead of tabs, the bytecount is larger than necessary. On my machine it's 9550 bytes. (at the time of writing this revision)
  6. Next sequence.
  7. The code, in its current form, only prints the first 20 terms of the sequence. However it's easy to change so that it will prints first 1000 items (by change the 20 in for (int i = 0; i < 20; ++i) to 1000)

Yay! This can compute more terms than listed on the OEIS page! (for the first time, for a challenge I need to use Java) unless OEIS has more terms somewhere...


Quick explanation

Explanation of the sequence description.

The sequence ask for the number of free nonplanar polyenoid with symmetry group C2v, where:

  • polyenoid: (mathematical model of polyene hydrocarbons) trees (or in degenerate case, single vertex) with can be embedded in hexagonal lattice.

For example, consider the trees

      O                O           O      O       (3)
      |                 \         /        \
      |                  \       /          \
O --- O --- O             O --- O            O --- O
      |                                             \
      |                    (2)                       \
 (1)  O                                               O

The first one cannot be embedded in the hexagonal lattice, while the second one can. That particular embedding is considered different from the third tree.

  • nonplanar polyenoid: embedding of trees such that there exists two overlapping vertices.

(2) and (3) tree above are planar. This one, however, is nonplanar:

   O---O O
  /       \
 /         \
O           O
 \         /
  \       /
   O --- O

(there are 7 vertices and 6 edges)

  • free polyenoid: Variants of one polyenoid, which can be obtained by rotation and reflection, is counted as one.

  • C2v group: The polyenoid are only counted if they have 2 perpendicular planes of reflection, and no more.

For example, the only polyenoid with 2 vertices

O --- O

has 3 planes of reflection: The horizontal one -, the vertical one |, and the one parallel to the computer screen . That's too much.

On the other hand, this one

O --- O
       \
        \
         O

has 2 planes of reflection: / and .


Explanation of the method

And now, the approach on how to actually count the number.

First, I take the formula a(n) = A000063(n + 2) - A000936(n) (listed on the OEIS page) for granted. I didn't read the explanation in the paper.

[TODO fix this part]

Of course, counting planar is easier than counting nonplanar. That's what the paper does, too.

Geometrically planar polyenoids (without overlapping vertices) are enumerated by computer programming. Thus the numbers of geometrically nonplanar polyenoids become accessible.

So... the program counts the number of planar polyenoid, and subtract it from the total.

Because the tree is planar anyway, it obviously has the plane of reflection. So the condition boils down to "count number of tree with an axis of reflection in its 2D representation".

The naive way would be generate all trees with n nodes, and check for correct symmetry. However, because we only want to find the number of trees with an axis of reflection, we can just generate all possible half-tree on one half, mirror them through the axis, and then check for correct symmetry. Moreover, because the polyenoids generated are (planar) trees, it must touch the axis of reflection exactly once.

The function public static Graph[] expand(Graph[] graphs, Point.Predicate fn) takes an array of graphs, each have n nodes, and output an array of graph, each has n+1 nodes, not equal to each other (under translation) - such that the added node must satisfy the predicate fn.

Consider 2 possible axes of reflection: One that goes through an vertex and coincide with edges (x = 0), and one that is the perpendicular bisector of an edge (2x = y). We can take only one of them because the generated graphs are isomorphic, anyway.

So, for the first axis x = 0, we start from the base graph consists of a single node (1, 0) (in case n is odd) or two nodes with an edge between (1, 0) - (2, 0) (in case n is even), and then expand nodes such that y > 0. That's done by the "Reflection type 1" section of the program, and then for each generated graph, reflect (mirror) itself through the X axis x = 0 (g.reflectSelfX()), and then check if it has the correct symmetry.

However, note that if n is divisible by 2, by this way we counted each graph twice, because we also generate its mirror image by the axis 2x = y + 3.

(note the 2 orange ones)

Similar for the axis 2x = y, if (and only if) n is even, we start from the point (1, 1), generate graphs such that 2*x > y, and reflect each of them over the 2x = y axis (g.reflectSelfType2()), connect (1, 0) with (1, 1), and check if they have correct symmetry. Remember to divide by 2, too.

  • Given that I was asleep when this (and the other one) were posted, I'll give you the benefit of the doubt and not accept an answer yet. – caird coinheringaahing Dec 24 '17 at 6:21
  • 2
    @cairdcoinheringaahing You were online 3 minutes before the deadline... – user202729 Dec 24 '17 at 6:23
  • Uh oh, the next sequence can be hard-coded... (although it's infinite) if I read it correctly. The calculation itself is ---pretty--- very easy, so don't do it. – user202729 Dec 24 '17 at 12:39

6. R, 71 bytes, A000072

function(n)length(unique((t<-outer(r<-(0:2^n)^2,r*4,"+"))[t<=2^n&t>0]))

Try it online!

Next sequence

  • 1
    For the love of God, I didn't check the next sequence before I posted this answer. – Leaky Nun Jul 21 '17 at 15:38
  • Isn't an easy next sequence a strategic advantage? – BlackCap Jul 21 '17 at 15:39
  • @BlackCap They can't answer twice in a row or less than 1 hour after they last answered. – Erik the Outgolfer Jul 21 '17 at 15:41
  • @EriktheOutgolfer the answer before the last posted (the one who didn't break the chain) will win – BlackCap Jul 21 '17 at 15:41
  • @BlackCap at this point that isn't going to happen – Stephen Jul 21 '17 at 15:42

14. Python 2, 60 bytes, A001246

f=lambda x:x<1or x*f(x-1)
c=lambda n:(f(2*n)/f(n)/f(n+1))**2

Try it online!

Next sequence.

  • 3
    Wow you ninja'd by 2 seconds – Business Cat Jul 21 '17 at 18:13

26. TI-BASIC, 274 bytes, A000183

.5(1+√(5→θ
"int(.5+θ^X/√(5→Y₁
"2+Y₁(X-1)+Y₁(X+1→Y₂
{0,0,0,1,2,20→L₁
Prompt A
Lbl A
If A≤dim(L₁
Then
Disp L₁(A
Else
1+dim(L₁
(~1)^Ans(4Ans+Y₂(Ans))+(Ans/(Ans-1))((Ans+1))-(2Ans/(Ans-2))((Ans-3)L₁(Ans-2)+(~1)^AnsY₂(Ans-2))+(Ans/(Ans-3))((Ans-5)L₁(Ans-3)+2(~1)^(Ans-1)Y₂(Ans-3))+(Ans/(Ans-4))(L₁(Ans-4)+(~1)^(Ans-1)Y₂(Ans-4→L₁(Ans
Goto A
End

Evaluates the recursive formula found on the OEIS link.

Next Sequence

34. Prolog (SWI), 168 bytes, A000073

tribonacci(0,0).
tribonacci(1,0).
tribonacci(2,1).
tribonacci(A,B):-
	C is A-1,
	D is A-2,
	E is A-3,
	tribonacci(C,F),
	tribonacci(D,G),
	tribonacci(E,H),
	B is F+G+H.

Try it online!

Next sequence

49. SageMath, 74 bytes, A000003

lambda n: len(BinaryQF_reduced_representatives(-4*n, primitive_only=True))

Try it online!

Next sequence

  • And I just spent an hour trying to work this sequence out using JavaScript... oh well, I'll just have to move on to the next one... – ETHproductions Jul 22 '17 at 15:20

76. Pygmy, 4147 bytes, A000036

globaln: 0                                                                                           

Pi:: 3.141592653589793                                                                               

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

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

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

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

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

V:: (number) {                                                                  
    Pi * number                                                                      
}                                                                                    

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

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

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

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

Next Sequence

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

alert| A000035| 10
  • 4
    ... the next sequence is uncomputable... – HyperNeutrino Jul 24 '17 at 16:14
  • 1
    @HyperNeutrino I know :P I did this on purpose – Peter Olson Jul 24 '17 at 16:18
  • Evil... >.< But anyway, I'll just hardcode the 4 elements in the sequence. Easy enough xD OP approves of it apparently ¯\_(ツ)_/¯ – HyperNeutrino Jul 24 '17 at 16:20

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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