# One OEIS after another

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:

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.

code

*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.

• 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
• @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
• @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
• Chat room – user202729 Dec 22 '17 at 12:45

# 250. Coconut, 711 bytes, A000171

from collections import Counter
from math import gcd, factorial

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

def ccSize(l) =
centSize = [ val**mult * factorial(mult)
{)_mF{~2/#}%:*:M_*/:B_4%1={_2/,f{)_2$J@@4*-*}}{_,{1&},f{1$1$J@@-*}}?1b0.5e|M3#*Mmf{2>},_&{_2#_@B\J-@*\/}/0.5+i} Online test suite. This is an anonymous block (function) with an auxiliary named block (function) to calculate the Jacobi symbol. Note: the formulae given in OEIS as it currently stands (revision 39) are badly transcribed from the Shanks paper. They miss an exponent and one special case and give a different special case incorrectly. I shall propose amendments. Also note that for the Jacobi symbol I'm using the Zolotarev-style approach I mentioned in an earlier answer of calculating the Levi-Civita symbol of a linear map. The implementation of J above is not the same as the one I previously proposed: it's the same length, but I think it's less wasteful. The next sequence is a nice easy one, so maybe someone can bring the lowest uncovered sequence, A000017, into play. That should make the hard-coders happy. • minor nit: you can always make the next sequence the lowest uncovered one by adding 300,000 bytes of padding. – pppery Sep 26 '17 at 20:48 # 318. Funciton, 1688 bytes, A000652 ╔═══╗ ┌─────────╖ ┌─┐ ┌───╖ ╔═══╗ ║ ╟──┤ str→int ╟──┤ └─┤ ↑ ╟──╢ 2 ║ ╚═══╝ ╘═════════╝ │ ╘═╤═╝ ╚═══╝ ┌─────────────────┘ │ ┌─┴┐ │ │┌─┴─╖ ┌───┴───┐ ││ ♭ ║ ┌─┴─╖ ┌─┴─╖ │╘═╤═╝┌───╖ ╔═══╗│ ♭ ║ │ ! ║ │ └──┤ ↑ ╟────╢ 2 ║╘═╤═╝ ╘═╤═╝ │ ╘═╤═╝ ╚═╤═╝ │ │ │ ┌──┴─┐ │ └───┐ │ │ ┌─┴─╖ │┌───╖ │ ┌───╖ │ │ │ │ ! ║ └┤ ↑ ╟─┴──┤ ↑ ╟─┘ │ │ ╘═╤═╝ ╘═╤═╝ ╘═╤═╝ │ │ │ ┌───╖ │ ┌───╖│ │ │ └─┤ × ╟─┘ ┌─┤ × ╟┘ │ │ ╘═╤═╝ │ ╘═╤═╝ ┌───╖ │ │ ╔═══╗ └─────┘ └───┤ + ╟──┘ │ ║ 2 ╟┐ ╘═╤═╝ │ ╚═╤═╝│ ┌───╖ │ │ │ └──┐ ┌─┤ ÷ ╟───┘ │ └──┐┌─┴─╖ │ ╘═╤═╝┌─────────╖ │ ┌───╖ ││ ↑ ╟─┘ └──┤ int→str ╟─ └─┤ × ╟─┘╘═╤═╝ ╘═════════╝ ╘═╤═╝ │ └──────┘ Next Sequence Calculates the formula from the OEIS page. I'm sure there's a more compact way to do this, without multiple 2 constants, but this took me long enough. Try it online! # 5. Python 3, 72 bytes, A000002 n=int(input()) l=[1,2,2] for i in range(2,n):l+=[1+i%2]*l[i] print(l[n]) Try it online! Next Sequence • Gosh darn it, I was playing around with f=lambda n,r=1:n*(n<3)or 3-f(n-f(r),r+1) for around 40 bytes (works except f(3) is omitted), but my internet decided to bug out while I was playing around on TIO – ETHproductions Jul 21 '17 at 15:46 • I don't get what this sequence is about at all. Could someone explain it simply? – geokavel Jul 21 '17 at 15:47 • @geokavel See this challenge – Mr. Xcoder Jul 21 '17 at 15:49 # 17. Stacked, 18 bytes, A000069 [bits sum odd]nth Try it online! Next sequence. Pretty simple. Computes the number of bits, calculates the sum, then checks for odd parity. Then takes the nth such number. Hehehe good luck. In retrospect, I could have made it 16 bytes instead of 17 or 18: [bits sum 2%]nth But oh well • Next sequence is...? – Mr. Xcoder Jul 21 '17 at 19:20 • How are we supposed to do an erroneous sequence? – MD XF Jul 21 '17 at 19:20 • C'mon, you left us with the broken one??? – HyperNeutrino Jul 21 '17 at 19:21 • Fixing........... – Conor O'Brien Jul 21 '17 at 19:21 • Please change this one's byte cont, because the next one is broken – Mr. Xcoder Jul 21 '17 at 19:21 # 31. Joy, 172 bytes, A001112 DEFINE acf == [20 <] [[0 1 1 3 4 11 136 283 419 1121 1540 38081 39621 117323 156944 431211 5331476 11094163 16425639 43945441] of] [10 - dup 10 -] [[39202 *] dip -] binrec. Try it online! Next sequence • How does it work? – Leaky Nun Jul 22 '17 at 4:25 • @LeakyNun a(0)=0, a(1)=1, ..., a(19)=43945441. For n>19, a(n)=39202*a(n-10)+a(n-20). It is based on the MAGMA code on OEIS. – alephalpha Jul 22 '17 at 4:39 # 39. Add++, 1 byte, A000004 O Try it online! Next sequence # 50. Japt, 26 bytes, A000074 1o2pU 2 èÈo f_¬v1Ãd_nX ¬v1 Try it online! Next sequence (I was quite tempted to ungolf it by 1 byte to get A000027, but this one should be fine) ### Explanation 1o2pU 2 èÈ o f_ ¬ v1Ã d_ nX ¬ v1 1o2pU 2 èX{Xo fZ{Zq v1} dZ{ZnX q v1}} Ungolfed Implicit: U = input integer 2pU Yield 2 ** U. 1o 2 Create the range [1, 3, 5, ..., 2**U - 1]. èX{ } Find the number of items X where this is true: Xo [0, 1, ..., X - 1] fZ{ } filtered to only items Z where Zq v1 sqrt(Z) is divisible by 1 (Z is square) (this gives a list of the squares less than X) dZ{ } contains an item Z where ZnX X - Z q v1 is also square. In other words, assert that an integer solution to X = a**2 + b**2 exists. This gives the number of odd integers less than 2**U that can be represented as the sum of two squares. Implicit: output result of last expression ## 69. GAP, 333 bytes, A000761 dirs:=[[1,0,0],[0,1,0],[0,0,1]]; dirs:=Concatenation(dirs,-dirs); count:=function(pos,seen,n) local newseen; if (pos in seen) or AbsInt(pos[1]-2)>n then return 0; fi; if n=0 then return 1; fi; newseen:=Concatenation(seen,[pos]); return Sum(dirs,d->count(pos+d,newseen,n-1)); end; f:=n->count([0,0,0],[],n+2); Next sequence • The partitions don't stop, do they? – tomsmeding Jul 23 '17 at 15:47 • Solution to the next one – BlackCap Jul 23 '17 at 16:29 • I'd just let g x n|x<0=0 | otherwise =1+sum(takeWhile(>0)([g(x-sqrt k)k|k<-[n..]])) and call g(n+1)1 - 1. BTW, I wonder how to do it without relying on floating point arithmetics. – Christian Sievers Jul 23 '17 at 16:55 # 80. Mathics, 140 Bytes, A000013 EulerPhi[x_] := Sum[If[CoprimeQ[i,x], 1, 0], {i, 1, x}] OEIS[x_] := Sum[If[IntegerQ[x/d], (EulerPhi[2d]*2^(x/d))/(2x), 0], {d,1,x}] OEIS[#]& Try it Online! Next Sequence • Wellp, I'll be waiting for 81 oeis.org/A000140 hah. – Magic Octopus Urn Jul 24 '17 at 19:26 • @MagicOctopusUrn It's actually not that hard. If you understand Jelly, it's just !ḶÆ!S€ĠL€Ṁ – ETHproductions Jul 24 '17 at 20:53 • @ETHproductions was looking to do an 05AB1E entry :P. – Magic Octopus Urn Jul 24 '17 at 21:07 # 116. Kotlin, 1156 bytes, A000273 import java.math.BigInteger; fun main(args: Array<String>) { val n = Integer.valueOf(args[0]); var a = accum(n, n, Array(n, { x -> 0 }), Array(n, { x -> 0 }), 0, BigInteger.ONE, n); println(a.first / a.second); } fun accum(n: Int, m: Int, part: Array<Int>, freq: Array<Int>, off: Int, c: BigInteger, omega: Int): Pair<BigInteger, BigInteger> { if (n == 0) return Pair(BigInteger.ONE.shiftLeft(omega), c); if (m == 0) return Pair(BigInteger.ZERO, BigInteger.ONE); var sum = accum(n, m - 1, part, freq, off, c, omega); part[off] = m; freq[off] = 0; var c1 = c; var omega2 = omega; var delta = -1; var j = 0; while (j < off) delta += 2 * freq[j] * gcd(part[j++], m); var im = m; while (im <= n) { freq[off]++; c1 = c1 * BigInteger.valueOf(im.toLong()); omega2 = omega2 + 2 * (im - m) + delta; val term = accum(n - im, m - 1, part, freq, off + 1, c1, omega2); sum = Pair(sum.first * term.second + sum.second * term.first, sum.second * term.second); im += m; } return sum; } fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b) Online demo Next sequence is a nice easy partition sequence. ### Notes This implementation follows J. Qian, Enumeration of unlabeled directed hypergraphs, Electronic Journal of Combinatorics, 20(1) (2013), and in particular exploits corollary 6. Although it may not look it, it's much simpler than the Maple implementation listed in OEIS. # 123. Emojicode, 278 bytes, A002057 🐋🚂🍇 🐖🅱️➡🚂🍇 🍮p 1.0 🔂k⏩2➕1🐕🍇 🍮✖p➕➗🚀🐕🚀k 1 🍉 🍎🏇p 🍉 🐖🅰️➡🚂🍇 🍎➗✖🅱️➕🐕1✖2🐕➕3🐕 🍉 🍉 🏁🍇 😀🔡🅰️➕1🍺🚂🔷🔡😯🔤🔤10 10 🍉 Try it online! Next sequence! (have an easy one) This is Emojicode 0.5, which is currently the newest version, but I'm mentioning it because of the major changes that are planned for 0.6. # Explaination: Note: a lot of emoji choice doesn't make much sense in Emojicode 0.5. It's 0.x, after all. 0.6 will fix this, so if you want to learn this (because who wouldn't want to), I recommend waiting a moment. Emojicode is an object-oriented programming language featuring generics, protocols, optionals and closures, but this program uses no closures and all generics and protocols can be considered implicit, while the only optional appears in the I/O part. The program operates on only a few types: 🚂 is the integer type, 🚀 is the floating-point type, 🔡 is the string type and ⏩ is the range type (yes, a range is a type in Emojicode). There are currently no operators in Emojicode, so addition, comparsions and other operations that are normally operators are implemented as functions, effectively making the expressions use prefix notation. Operators are also planned in 0.6. 🐋🚂🍇 ... 🍉 Extend the 🚂 type. This is a feature that is not commonly found in programming languages. Instead of creating a new class with 🚂 as the superclass, 🐋 modifies 🚂 directly. Grapes and watermelons declare code blocks in Emojicode. 🐖🅱️➡🚂🍇 ... 🍉 🅱️ is a method that returns 🚂. 🅱️ calculates A000108 using the Product_{k=2..n} (1 + n/k). The OEIS states that the formula is only valid for n > 1, but this method will only be called with n >= 1 and the value is ignored in the n = 1 case because of a multiplication by 0, so no special case is present. 🍮p 1.0 Create a variable named p and set it to 1.0. This automatically makes the type 🚀. This is necessary because fractions are present in the product. 🔂k⏩2➕1🐕🍇 ... 🍉 🔂 iterates over anything that implements the 🔂🐚⚪️ protocol, while ⏩ is a range literal that happens to implement 🔂🐚🚂. A range has a start value, a stop value and a step value, which is assumed to be 1 if start < stop, or -1 otherwise. One can also specify the step value by using the ⏭ to create the range literal. The start value is inclusive, while the stop value is exclusive, so this is equivalent to for k in range(2, ➕1🐕). ➕ is a method of the 🚂 type that adds numbers together and 🐕 refers to the object the method was called on, so ➕1🐕 means n + 1. This corresponds to the range of Product_{k=2..n} from the formula, since the stop value is not included in the range. 🍮✖p ... This is an assignment by call, which means "call ✖ on p with the arguments (...) and set p to the return value". ✖ is a method of 🚀 that multiplies numbers together. This can sound familiar, because it's similar to the operators like +=, *= or >>= in some popular emoji-free (and therefore inferior) languages. ➕➗🚀🐕🚀k 1 🚀, in addition to being a type, is a method of the 🚂 type, that returns a 🚀 of the same value as 🚂 - by convention, methods that share the name with a type are used to convert to that type. Therefore this expression represents (n / k) + 1, which is then multiplied by, and stored in p. 🍎🏇p 🍎 is used to return values from methods, while 🏇 is a method of the 🚀 type that returns the nearest 🚂. Whether one uses an equivalent of round, floor or ceil shouldn't matter since the formula always results in integers, but using 🏇 makes the code more immune to floating-point inaccuracies. 🐖🅰️➡🚂🍇 ... 🍉 This creates a method named 🅰️ that returns 🚂. This method implements A002057. 🍎➗✖🅱️➕🐕1✖2🐕➕3🐕 This is a return statement with the formula "encoded" in prefix notation. If you decipher it, you'll see 🅱️ being called on n + 1, the result multiplied by 2 * n and divided by n + 3, resulting in the formula 2*n*A000108(n+1)/(n+3) from the OEIS. 🏁🍇 ... 🍉 🏁 marks the equivalent of a main function. 😀🔡🅰️➕1🍺🚂🔷🔡😯🔤🔤10 10 Let's break it down. 🔷🔡😯🔤🔤 🔤 marks the beginning and end of a 🔡 literal. 🔷 is used for constructing objects, so this creates a 🔡 with the constructor 😯 called with a single argument of an empty string. 😯 is used to read a line of input from the user, and the argument is used as a prompt. 🚂🔷🔡😯🔤🔤10 🚂 is a method of the 🔡 type, and as you might guess, it converts the string into an integer. It takes one argument, the number base to use. 🍺🚂🔷🔡😯🔤🔤10 🚂 returns an optional, 🍬🚂. Optionals can contain a value of the base type or nothingness, ⚡. When the string doesn't contain a number, ⚡ is returned. To use the value of an optional, one has to unwrap it using 🍺, which raises a runtime error if the value is ⚡. Normally it is bad practice to unwrap an optional without checking, but this is codegolf.SE, we don't care. If you want to see an example with error checking, see my answer at this challenge. ➕1🍺🚂🔷🔡😯🔤🔤10 The formula used for A002057 appears to have an off-by-one error, so 1 is added to the input to make the offset correct. 🅰️➕1🍺🚂🔷🔡😯🔤🔤10 🅰️ is called on the corrected input, calculating the sequence. 🔡🅰️➕1🍺🚂🔷🔡😯🔤🔤10 10 You guessed it. 🔡 is a method of the 🚂 type that converts it to a 🔡, taking the base as an argument. 😀🔡🅰️➕1🍺🚂🔷🔡😯🔤🔤10 10 Finally, 😀 is used to print the result. • Wow, what's that? So colourful! – Christian Sievers Sep 1 '17 at 14:09 • This is Emojicode, the only serious programming language that's bursting with emoji! Stay tuned for the explaination. – NieDzejkob Sep 1 '17 at 14:15 • @ChristianSievers I just thought I'd notify you that now you can learn this beautiful, superior language on my example. – NieDzejkob Sep 1 '17 at 14:53 # 178. GAP, 933 bytes, A000214 Luckily GAP wasn't taken for No. 167 (A000638)! AG := function( n ) local b, sw, sh, xr, tr, gens; b := BasisVectors(Basis(FullRowSpace(GF(2),n+1))); gens := []; if n>1 then sw := ShallowCopy(b); sw{[2,3]} := sw{[3,2]}; sh := ShallowCopy(b); sh{[2..n+1]} := sh{Concatenation([n+1],[2..n])}; xr := ShallowCopy(b); xr[2] := xr[2]+xr[3]; gens := [ sw, sh, xr ]; fi; tr := ShallowCopy(b); tr[2] := tr[1]+tr[2]; Add(gens, tr); return Group(List(gens,TransposedMat)); end; Fix := function( g ) local o, h, s, i, k; o := One(g); s := 2^(Size(g)-1); i := 1; h := g; while not IsOne(h) do k := NullspaceMat( h-o ); if ForAny( k, v -> IsOne(v[1]) ) then s := s + 2^(Size(k)-1); fi; i := i+1; h := h*g; od; return 2^(s/i); end; f := function( n ) local grp; grp := AG(n+1); # zero based return Sum( ConjugacyClasses(grp), cc -> Size(cc)*Fix(Representative(cc)) ) / Order(grp); end; This is using somewhat advanced group theory (Burnside's lemma, twice), but no deep knowledge of the affine group. Still it is good enough to compute the 9th and 10th value (and more), which are: 3743090921588631997590183810292071781042846067942809230428008257901850006463197026597863697259931801933484260185559925420090026 479084991876032922658580043148767307553909132799686744495116429395794360341231625183693228836152593000430870733973647565874325953529940377811130038575926765372370447759627109606902989971984053705702177123141099357638755205930373003087364483930095902877678789627725054625735636 Next sequence ### How does it work? There are 2^(2^n) Boolean functions of n variables. The affine group AG(n,2) acts on these functions by transforming the input. An affine transformation can permute the input, xor one input to another, and negate an input. (xor is addition in the field with two elements, negation is addition of one.) If a Boolean functions can be transformed in this way into an other, we consider them equivalent. The equivalence classes are called orbits. We want to know how many orbits there are. Burnside's lemma tells us that the number of orbits of an action of a group G on a set X equals the sum of the number of elements of X that are fixed by g (the sum is over each element g of G) divided by the order (size) of the group G. Since the affine group is big for moderate sizes of n, we want to avoid summing over all its elements. Conjugated elements fix the same number of elements of X, so we can sum instead over conjugacy classes and multiply with the size of the conjugacy class. There are not that much conjugacy classes, and GAP can compute them in reasonable time. (I wasn't sure about this when I started programming.) This is what the main function f does, using helper functions AG to create the affine group and Fix to determine the number of boolean functions that are fixed by an affine transformation. An affine transformation can be given by an invertible matrix A and an translation vector b, it maps x to Ax+b. This can be brought into the realm of linear algebra by embedding it into n+1 dimensional space. The affine transformation is represented by [[1, 0], [b, A]] (GAP wouldn't accept this). To see where the n dimensional x is mapped to, add a first component of 1, multiply with the matrix, and drop the first component of the result (which will be 1). You can think of adding an extra input that is always 1 and can not be changed by the transformation, but can be added (xor-ed) to other inputs. The AG function creates the affine group as matrix group using this representation. We create the affine group using four generators, the first three are only meaningful for n>1. The first swaps the first two inputs, the second cyclically shifts the inputs. (For n=2 they are the same, but that is no problem.) Together they generate all permutations of inputs. The third xors the second input to the first. By conjugation with a permutation, this gives all needed xor operations. Together, these three matrices generate the general (or special, that's the same in this case) linear group GL(n,2). The last generator negates the first input. Again, conjugation with a permutation gives the other negations, so all matrices together generate the affine group AG(n,2). You may have noted that my thinking, explaining and constructing has been in terms of right multiplying a column vector to a matrix. GAP however uses row vectors and left multiplication. Since I will use GAP's linear algebra functionality later, I compensate by transposing the generating matrices before construction the group. Now to the function Fix. We are given an affine transformation g and want to calculate the number of Boolean functions that it fixes. A function is fixed by g if it gives the same result to some input and to this input transformed by g (or g^2 etc). If an input can not be transformed into an other by a power of g, then the function may give different results for them. So the result is 2 to the number of classes of inputs that may get different results. We can get this number by another application of Burnside's lemma! This time the group is the cyclic group generated by g, and it is acting on the set of inputs of size 2^n. We really sum over all elements of the group now. The identity fixes all inputs, so we start the sum s with this number. Now assume we have a power h of g and want to know how many inputs it fixes. That means we want to know how many n+1 dimensional vectors with first component 1 are fixed by the matrix h, or how many are mapped to zero by h-1. So we use NullspaceMat to compute a basis of the kernel of h-1. If that contains no element with a 1 at the first component, then there are no solutions, otherwise there are half as many as the kernel size. In the end i contains the number of elements of the cyclic group, by which we divide the sum s as Burnside's lemma tells us. The last time I wrote similar code I used it to compute some numbers which I could use to find the series on OEIS and then find a better way to compute them there... I guess that the algorithm could be improved a lot without very complicated math. For example, I think it should be useful that the affine group is a semidirect product, but we give it to GAP as if it were any random matrix group. Now I hope this was useful or interesting for someone. I never know how much detail I should give in an explanation here. # 226. Java 7, 4903 bytes, A000080 Originally programmed by HyperNeutrino. import java.util.Arrays; import java.util.List; import java.util.ArrayList; abstract interface BooleanCombiner { abstract boolean combine(boolean left, boolean right); } class Main { static void print(boolean[][] matrix) { for (boolean[] row : matrix) { for (boolean e : row) { System.out.print(e ? 1 : 0); System.out.print(' '); } System.out.println(); } } static boolean[] combine(boolean[] left, boolean[] right, BooleanCombiner f) { assert left.length == right.length; boolean[] result = new boolean[left.length]; for (int i = 0; i < result.length; i++) result[i] = f.combine(left[i], right[i]); return result; } static boolean none(boolean[] row) { for (boolean element : row) if (element) return false; return true; } static boolean all(boolean[] row) { for (boolean element : row) if (!element) return false; return true; } static int weight(boolean[] row) { int weight = 0; for (boolean element : row) if (element) weight++; return weight; } static boolean[] DFS(boolean[][] matrix, int node, boolean[] visited) { assert visited.length == matrix.length; if (visited[node]) return visited; visited[node] = true; for (int neighbor = 0; neighbor < visited.length; ++neighbor) { if (matrix[node][neighbor]) DFS(matrix, neighbor, visited); } return visited; } static boolean isConnected(boolean[][] matrix) { return all(DFS(matrix, 0, new boolean[matrix.length])); } static int[][] triples(int length) { int[][] triples = new int[length * ~-length * ~-~-length / 6][]; int index = 0; for (int i = 0; i < length; i++) { for (int j = i + 1; j < length; j++) { for (int k = j + 1; k < length; k++) { triples[index++] = new int[] { i, j, k }; } } } return triples; } static boolean isomorphic(boolean[][] a, boolean[][] b) { int[] permutation = new int[a.length]; for (int i = 0; i < permutation.length; ++i) permutation[i] = i; while (true) { // check here boolean maybe_valid = true; for (int i = 0; i < permutation.length && maybe_valid; ++i) { for (int j = 0; j < permutation.length; ++j) { if (a[i][j] != b[permutation[i]][permutation[j]]) { maybe_valid = false; break; } } } if (maybe_valid) { return true; // actually valid! } // advance the permutation here. Implement C++'s std::next_permutation int j = permutation.length - 1; while (j != 0) { if (permutation[j - 1] > permutation[j]) --j; else break; } if (j == 0) break; // reached last permutation // reverse [j, permutation.length) segment for (int k = j, l = permutation.length - 1; k < l; ++k, --l) { int tmp = permutation[k]; permutation[k] = permutation[l]; permutation[l] = tmp; } // find smallest element in [j, permutation.length) that is still larger than permutation[j-1] int k = j; // sorry, meaningless variable name; while (permutation[k] < permutation[j-1]) ++k; int tmp = permutation[j-1]; permutation[j-1] = permutation[k]; permutation[k] = tmp; }; return false; } static boolean[][] construct (int size, boolean[] mask, int[][] triples_table) { assert triples_table.length == mask.length; boolean[][] matrix = new boolean[size][size]; for (int index = 0; index < mask.length; ++index) { if (mask[index]) { int[] triple = triples_table[index]; int i = triple[0], j = triple[1], k = triple[2]; matrix[i][j] = matrix[j][i] = matrix[i][k] = matrix[k][i] = matrix[j][k] = matrix[k][j] = true; } } return matrix; } static List<boolean[][]> calculate (int size) { List<boolean[][]> matrices = new ArrayList<>(); int[][] triples_table = triples(size); boolean[] mask = new boolean[triples_table.length]; while (true) { boolean[][] matrix = construct(size, mask, triples_table); process_matrix: if (isConnected(matrix)) { // check if matrix is isomorphic to any existing matrix for (boolean[][] existing_matrix : matrices) { if (isomorphic(matrix, existing_matrix)) break process_matrix; } // check if the matrix is minimal for (int delete_triple = 0; delete_triple < mask.length; ++delete_triple) { if (! mask[delete_triple]) continue; mask[delete_triple] = false; // temporarily set to false if (isConnected(construct(size, mask, triples_table))) { // it is not minimal mask[delete_triple] = true; // remember to restore it ... break process_matrix; } mask[delete_triple] = true; // ... in any condition } /* it is both minimal and not counted now, */ matrices.add(matrix); } int i = mask.length - 1; while (i >= 0 && mask[i]) mask[i--] = false; if (i == -1) return matrices; // considered all <mask> possible. mask[i] = true; } } public static void main(String[] args) { System.out.println(calculate(Integer.parseInt(args[0]) + 3).size()); } } Try it online! Next sequence. • Nice! @HyperNeutrino Did you find out what was the problem with the lean fish graph? – J. Sallé Oct 18 '17 at 14:05 • @J.Salle user202729 pointed it out to me; my isValid function didn't work because one of the cycles didn't have any vertices with order 2 because rather than disconnecting a single node, it split the graph. Credit goes to them, not me :) – HyperNeutrino Oct 18 '17 at 14:08 • abstract interface makes me sad... and now it's immortalized here since you aren't allowed to change it... – Socratic Phoenix Oct 18 '17 at 14:09 • @SocraticPhoenix Originally programmed by HyperNeutrino. – user202729 Oct 18 '17 at 14:11 • I'm confused about how, for the next sequence, 0 is a sum of any NONZERO 10th powers, unless I'm totally misreading it... – Giuseppe Oct 18 '17 at 14:13 # 241. Trefunge-98 (PyFunge), 230 bytes, A000256 v >51>R1-:v>RRO:8*'+-*'9+*O3*9-2Pv >4 (&:| \ >|v ;>v; <:R: -4< ^"FRTH"<@.1< + @.$<>R1-:|>\1-RO*\^
^ useful     1     v\0$< A000256 library \ >:1-:v >\:v O:8*'3-*'Q+/4/^ ^ _^ *_/7*\- Try it online! Next sequence! To understand this monstrosity, you first need a quick primer on Funge: • All variants of Funge are primarily stack based. • The stack can only contain numbers. • Befunge is a 2D language. While Trefunge is 3D, this code would work fine without the third dimension. • <^>v are used to redirect execution exactly like you would expect. • +-*/ do addition, subtraction, multiplication and division. • Digits push the corresponding number on the stack • The instruction pointer starts in the upper left corner pointing right. • Space is a no-op • " toggles stringmode. In stringmode, the ASCII code of each character is pushed on the stack v >4 ( ^"FRTH"< You can see that immediately the execution is redirected on the string "FRTH". Because the execution goes right to left, 70 (F) is on the top of the stack. Then the number 4 is pushed and ( loads the fingerprint. Fingerprints are similar to libraries from other languages, except they are not created in Funge, which would make them more of a language extension. Fingerprints change the semantics of the commands A through Z, which normally all act like r (reflect). You can load fingerprints using (, which more or less pops the number of characters the fingerprint code takes and then pops the characters themselves. The FRTH fingerprint stands for FORTH, because it includes some useful stack manipulation primitives that originated from FORTH. This program uses the following of them: • R - rotate. (... a b c) -> (... b c a) • O - over. (... a b) -> (... a b a). Equivalent to 1P. • P - push. Takes a number n and copies the element buried n elements deep to the top. For example, 2P would change the stack like this: (... a b c) -> (... a b c a) >51>R1- (&:| \ @.1< + After loading the fingerprint, & inputs a number and pushes it on the stack. : is used to duplicate it because | consumes one copy. | is the vertical conditional. If the number it consumed is zero, it's equivalent to v. Otherwise, it acts like ^. It is used here because the input of zero needs to be a special case - the loop counter would immediately go negative making the loop infinite and OEIS claims that the formula only works for n > 4. If zero is passed, 1 is pushed, . is used to output it and @ ends the program. You can also see here the beginning of the main loop of the program. The loop begins with R1- and ends with +\. The stack at the beginning of each iteration looks like this: i n a(n-1). i-1 is the number of repetitions the program will do, since it is decremented and compared at the beginning of the loop. n is the index in the sequence of the value we will be computing, while a(n-1) is the previous value. We implement this formula from the OEIS: a(n) = (1/4)*(7*binomial(3*n-9, n-4)-(8*n^2-43*n+57)*a(n-1)) / (8*n^2-51*n+81) Let's tackle the main loop itself: R1-:v>RRO: >| @.< R brings i to the top. Funge doesn't have a decrement instruction, so we subtract 1 explicitly with -. We duplicate the new i with : for testing with |. If we're finished, we will hit the < and execute the following linear code: .@ The stack is now: n a(n-1) i  Discard i . Output a(n-1) @ Exit. In most cases, however, | will act like ^, which will make the interpreter execute this long stretch of linear code (ignoring the line wrap): RRO:8*'+-*'9+*O3*9-2P4- The stack is now: n a(n-1) i RR Bury i where it belongs. Stack: i n a(n-1) O: Copy n to the top and duplicate. Stack: i n a(n-1) n n 8* Multiply by 8. Stack: i n a(n-1) n 8n '+ Use the ASCII value of + to push 43 on the stack - Subtract 43. Stack: i n a(n-1) n 8n-43 * Multiply. Stack: i n a(n-1) 8n^2-43n '9+ Add 57. Stack: i n a(n-1) 8n^2-43n+57 * Multiply. Stack: i n (8n^2 - 43n + 57)*a(n-1) O Copy n to the top. Stack: i n (...)*a(n-1) n 3*9- Compute 3n-9. Stack: i n (...)*a(n-1) 3n-9 2P4- Copy n to the top, compute n-4. Stack: i n (...)*a(n-1) 3n-9 n-4. Notice how the top two elements are the arguments for the binomial. We will now compute the binomial(n, k) using the following algorithm which I've come up with myself a few sequences before, but it's probably not anything innovative, since it is obvious when you look at the formula. You can also see it in my Boo answer above. • Multiply k numbers starting with n, going down • Divide by the factorial of k Let's only consider the very top of the stack when considering the algorithm. v ;>v; <:R: >R1-:|>\1-RO*\^$$< This is the part before computing the factorial. After :R:, the ; is a bridge, which skips the >v part. v ;>v; < :R:>R1-:|>\1-RO*\^ Stack: n k : Duplicate. Stack: n k k R Rotate. Stack: k k n : Duplicate. Stack: k k n n. The bottommost k is used later. The other k is the loop counter. The topmost n is the number we're multiplying by, while the other n is the partial product. > The loop starts here. Let's rename the variables and ignore the bottom k. Stack: k product n R1- Decrement k. Stack: product n k-1 :|> Exit the loop if k-1 is zero. Uses the >v part that is skipped using a bridge \1- Bring n to the top and decrement. Stack: product k-1 n-1 R Rotate. Stack: k-1 n-1 product O Over. Stack: k-1 n-1 product n-1 * Multiply - extend the partial product. Stack: k-1 n-1 (product)(n-1) \ Swap, restoring the stack to the order from the start of the loop. Stack: k-1 (product)(n-1) n-1 ^ Jump to the beginning. When the loop ends, we execute this: $$\ Stack: k p n-k 0$$ Discard the top two elements, we only need the product \ Bring k to the top for computing the factorial. Stack: p k Let's consider the factorial code: v\0 >:1-:v >\:v ^ _$^ *_$It consists of two loops. Let's consider the factorial of 4. 0\>:1-:v_$ Stack: 4
0\         Push the marker used in the second loop, swap. Stack: 0 4
>        The loop starts here
:1-     Duplicate and decrement. Stack: 0 4 3
:v_  Duplicate for the comparsion, loop if not 0.
>        Consider the loop again, with stack: 0 4 3 2 1
:1-     Duplicate and decrement. Stack: 0 4 3 2 1 0
:v_  Duplicate for the comparsion and exit the loop.
$Discard the top 0. Stack: 0 4 3 2 1 The second loop multiplies the numbers together, while 0 is marking the end. >\:v_* Stack: 0 4 3 2 1 > The loop starts here \ Swap. Stack: 0 4 3 1 2 :v_ If the top element is 0, end the loop * Multiply. Stack: 0 4 3 2 > Consider the loop again, with stack: 0 4 6 \ Swap. Stack: 0 6 4 :v_ (doesn't end the loop) * Multiply. Stack: 0 24 > Finally, let's see how the loop terminates. \ Swap. Stack: 24 0 :v_ Ends the loop. Stack: 24 0 Let's finish the main loop, since it now consists of only linear code. It is useful to see the formula while following the code: a(n) = (1/4)*(7*binomial(3*n-9, n-4)-(8*n^2-43*n+57)*a(n-1)) / (8*n^2-51*n+81) Let's mark the numerator x and the denominator y, to simplify the description. a(n) = (1/4)*x/y Keep it mind that when the instruction pointer hits the edge of the Fungespace, it wraps around.$/7*\-O:8*'3-*'Q+/4/\1+\ Stack: i-1 n (...)*a(n-1) p k! 0
Discard the 0 marker from the factorial loop. / Divide to compute the binomial. Stack: i-1 n (...)*a(n-1) binomial(3n-9 n-4) 7* Multiply by 7. Stack: i-1 n (...)*a(n-1) 7*binomial \- Swap and subtract. Stack: i-1 n 7*binomial-(...)*a(n-1) O: Over, duplicate. Stack: i-1 n x n n 8* Multiply by 8. Stack: i-1 n x n 8n '3- Subtract 51. Stack: i-1 n x n 8n-51 * Multiply. Stack: i-1 n x 8n^2-51n 'Q+ Add 81. Stack i-1 n x 8n^2-51n+81 / Divide. Stack: i-1 n x/y 4/ Divide by 4. Stack: i-1 n a(n) \1+\ Increment n. Stack: i-1 n+1 a(n), or as the next iteration would call it: i n a(n-1) • "nominator"? Should it be "numerator"? – user202729 Oct 28 '17 at 12:29 • @user202729 You are right. That's what you get when you don't learn math in English... :P – NieDzejkob Oct 28 '17 at 12:30 • Also can you add an explanation what is the sequence? – user202729 Oct 28 '17 at 12:58 • @user202729 I totally would if my current understanding of this sequence aligned with the values given by the OEIS. – NieDzejkob Oct 28 '17 at 13:40 # 253. MIT/GNU Scheme, 1516 bytes, A000251 (define (add f g) (stream-map + f g) ) (define (sub f g) (stream-map - f g) ) (define (scale c f) (stream-map (lambda (v) (* c v)) f) ) (define (adddiag sf) (let ((f0 (stream-first sf))) (cons-stream (stream-first f0) (add (stream-rest f0) (adddiag (stream-rest sf))) ) ) ) (define (mult f g) (adddiag (stream-map (lambda (v) (scale v g)) f)) ) (define (prependzeros n f) (if (= 0 n) f (cons-stream 0 (prependzeros (-1+ n) f))) ) (define (intersperse f n) (cons-stream (stream-first f) (prependzeros n (intersperse (stream-rest f) n)) ) ) (define (iterate fun init) (cons-stream init (iterate fun (fun init))) ) (define (from n) (iterate 1+ n) ) (define (scanl fun init s) (cons-stream init (scanl fun (fun init (stream-first s)) (stream-rest s))) ) (define (expx f) (cons-stream 1 (adddiag (stream-map (lambda (s g) (scale (/ 1 s) g)) (scanl * 1 (from 2)) (iterate (lambda (g) (mult f g)) f) )) ) ) (define (eu f) (expx (adddiag (stream-map (lambda (n) (scale (/ 1 n) (intersperse f (-1+ n)) )) (from 1) ))) ) (define ones (cons-stream 1 ones) ) (define s (iterate eu ones) ) (define r (stream-map sub (stream-rest s) s) ) (define t6 (sub (stream-ref r 1) (cons-stream 0 (mult (stream-first r) (stream-ref s 1))) ) ) (define (f n) (stream-ref t6 (+ 6 n)) ) Next sequence Use like this: scheme -load t6.scm
MIT/GNU Scheme running under GNU/Linux
[...]
1 ]=> (f 49)

;Value: 1110994054004

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

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

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

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

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

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

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

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

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

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

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

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

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

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

# 259. Hy, 1333 bytes, A000329

(setv precision 80)

(import decimal)

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

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

(setv pi (approx-pi precision))

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

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

(setv bvalues {0 (Decimal 1)})

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

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

Next sequence

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

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

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

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

# 233. Hexagony, 141 bytes, A000332

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

Try it online!

Next sequence!

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

## Explanation

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

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

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

# 81. Röda, 290 bytes, A000140

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

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

Try it online!

Next sequence

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

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

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

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

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

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

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

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

# 7. Brain-Flak, 70 bytes, A000071

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

Try it online!

Next sequence

## Explanation

({}[<>((()))<>]) #{ place a one on the off stack and subtract 1 from the input (to zero index)}
{({}[()])                          } #{n times}
<>({}<>)<>(({})<>({}<>))<>  #{Add the top two numbers in place}
<>{}{}({}<>{}[()]) #{Clean up and subtract 1}
• @cairdcoinheringaahing I don't know. Is that not allowed? – Wheat Wizard Jul 21 '17 at 15:46
• no its fine. I just thought that it could help the next answerer – caird coinheringaahing Jul 21 '17 at 15:51

# 4. Jelly, 2 bytes, A000038

ṆḤ

Try it online!

Next Sequence

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

# 19. Curry, 45 bytes, A000037

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

Try it online

Next sequence

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

# 20. cQuents, 15 bytes, A000045

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

Try it online!

Next sequence

# 25. eta, 183 bytes, A000033

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

Try it online

Next sequence

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

## 29. JavaScript (SpiderMonkey), 46 bytes, A000009

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

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

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

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

# 35. dc, 67 bytes, A000168

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

Try it online!

Next Sequence