107
\$\begingroup\$

As of 13/03/2018 16:45 UTC, the winner is answer #345, by Khuldraeseth na'Barya. This means the contest is officially over, but feel free to continue posting answers, just so long as they follow the rules.

As well, just a quick shout out to the top three answerers in terms of numbers of answers:

1. NieDzejkob - 41 answers

2. KSmarts - 30 answers

3. Hyper Neutrino - 26 answers


This is an answer chaining question that uses sequences from OEIS, and the length of the previous submission.

This answer chaining question will work in the following way:

  • I will post the first answer. All other solutions must stem from that.
  • The next user (let's call them userA) will find the OEIS sequence in which its index number (see below) is the same as the length of my code.
  • Using the sequence, they must then code, in an unused language, a program that takes an integer as input, n, and outputs the nth number in that sequence.
  • Next, they post their solution after mine, and a new user (userB) must repeat the same thing.

The nth term of a sequence is the term n times after the first, working with the first value being the first value given on its OEIS page. In this question, we will use 0-indexing for these sequences. For example, with A000242 and n = 3, the correct result would be 25.

However!

This is not a , so shortest code doesn't matter. But the length of your code does still have an impact. To prevent the duplication of sequences, your bytecount must be unique. This means that no other program submitted here can be the same length in bytes as yours.

If there isn't a sequence for then length of the last post, then the sequence for your post is the lowest unused sequence. This means that the sequences used also have to be unique, and that the sequence cannot be the same as your bytecount.

After an answer has been posted and no new answers have been posted for more than a week, the answer before the last posted (the one who didn't break the chain) will win.

Input and Output

Generic input and output rules apply. Input must be an integer or a string representation of an integer and output must be the correct value in the sequence.

Formatting

As with most questions, please format your answer like this

# N. language, length, [sequence](link)

`code`

[next sequence](link)

*anything else*

Rules

  • You must wait for at least 1 hour before posting an answer, after having posted.
  • You may not post twice (or more) in a row.
  • The index number of a sequence is the number after the A part, and with leading zeros removed (e.g. for A000040 the index number is 40)
  • You can assume that neither the input nor the required output will be outside your languages numerical range, but please don't abuse this by choosing a language that can only use the number 1, for example.
  • If the length of your submission is greater than 65536 characters long, please provide a link to a way to access the code (pastebin for example).
  • n will never be larger than 1000, or be out of bounds for the sequence, simply to prevent accuracy discrepancies from stopping a language from competing.
  • Every 150 (valid) answers, the number of times a language may be used increases. So after 150 solutions have been posted, every language may be used twice (with all previous answers counting towards this). For instance, when 150 answers have been posted, Python 3 may be used twice, but due to the fact that it has already been used once, this means it can only be used once more until 300 answers have been posted.
  • Please be helpful and post a link to the next sequence to be used. This isn't required, but is a recommendation.
  • Different versions of languages, e.g. Python 2 and Python 3 are different languages. As a general rule, if the different versions are both available on Try It Online, they are different languages, but keep in mind that this is a general rule and not a rigid answer.
  • It is not banned, but please try not to copy the code from the OEIS page, and actually try to solve it.
  • Hardcoding is only allowed if the sequence is finite. Please note that the answer that prompted this (#40) is the exception to the rule. A few answers early in the chain hardcode, but these can be ignored, as there is no good in deleting the chain up to, say, #100.

Answer chain snippet

var QUESTION_ID=133754,OVERRIDE_USER=66833;function shareUrl(i){return"https://codegolf.stackexchange.com/a/"+i}function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getTemplate(s){return jQuery(jQuery("#answer-template").html().replace("{{PLACE}}",s.index+".").replace("{{NAME}}",s.user).replace("{{LANGUAGE}}",s.language).replace("{{SEQUENCE}}",s.sequence).replace("{{SIZE}}",s.size).replace("{{LINK}}",s.link))}function search(l,q){m=jQuery("<tbody id='answers'></tbody>");e.forEach(function(s){if(!q||(l==0&&RegExp('^'+q,'i').exec(s.lang_name))||(l==1&&q===''+s.size)){m.append(jQuery(getTemplate(s)))}});jQuery("#answers").remove();jQuery(".answer-list").append(m)}function sortby(ix){t=document.querySelector('#answers');_els=t.querySelectorAll('tr');els=[];for(var i=0;i<_els.length;i++){els.push(_els[i]);}els.sortBy(function(a){a=a.cells[ix].innerText;return ix==0||ix==4?Number(a):a.toLowerCase()});for(var i=0;i<els.length;i++)t.appendChild(els[i]);}function checkSize(x){if(!x)return jQuery("#size-used").text("");var i=b.indexOf(+x);if(i<0)return jQuery("#size-used").text("Available!");var low=+x,high=+x;while(~b.indexOf(low))low--;while(~b.indexOf(high))high++;jQuery("#size-used").text(("Not available. The nearest are "+low+" and "+high).replace("are 0 and","is"))}function checkLang(x){}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.answer_id;answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return (e.owner.user_id==OVERRIDE_USER?"<span id='question-author'>"+e.owner.display_name+"</span>":e.owner.display_name)}function process(){b=[];c=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);if(a){e.push({user:getAuthorName(s),size:+a[4],language:a[2],lang_name:a[3],index:+a[1],sequence:a[5],link:shareUrl(s.answer_id)});if(b.indexOf(+a[4])>=0&&c.indexOf(+a[4])<0){c.push(+a[4])};b.push(+a[4])}else{jQuery('#weird-answers').append('<a href="'+shareUrl(s.answer_id)+'">This answer</a> is not formatted correctly. <b>Do not trust the information provided by this snippet until this message disappears.</b><br />')}}),e.sortBy(function(e){return e.index});e.forEach(function(e){jQuery("#answers").append(getTemplate(e))});var q="A"+("000000"+e.slice(-1)[0].size).slice(-6);jQuery("#next").html("<a href='http://oeis.org/"+q+"'>"+q+"</a>");c.forEach(function(n){jQuery('#weird-answers').append('The bytecount '+n+' was used more than once!<br />')})}Array.prototype.sortBy=function(f){return this.sort(function(a,b){if(f)a=f(a),b=f(b);return(a>b)-(a<b)})};var ANSWER_FILTER="!*RB.h_b*K(IAWbmRBLe",COMMENT_FILTER="!owfmI7e3fd9oB",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page,e=[];getAnswers();var SCORE_REG=/<h\d>\s*(\d+)\.\s*((?:<a [^>]+>\s*)?((?:[^\n,](?!<\/a>))*[^\s,])(?:<\/a>)?),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*, ((?:<a[^>]+>\s*)?A\d+(?:\s*<\/a>)?)\s*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important;font-family:Roboto,sans-serif}#answer-list,#language-list{padding:10px;/*width:290px*/;float:left;display:flex;flex-wrap:wrap;list-style:none;}table thead{font-weight:700}table td{padding:5px}ul{margin:0px}#board{display:flex;flex-direction:column;}#language-list li{padding:2px 5px;}#langs-tit{margin-bottom:5px}#byte-counts{display:block;margin-left:15px;}#question-author{color:purple;text-shadow: 0 0 15px rgba(128,0,128,0.1);}#label-info{font-weight: normal;font-size: 14px;font-style: italic;color: dimgray;padding-left: 10px;vertical-align: middle; }
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><p id="weird-answers"></p><p>Currently waiting on <span id="next"></span></p><span>Search by Byte Count: <input id="search" type="number" min=1 oninput="checkSize(this.value);search(1,this.value)" onclick="document.getElementById('search2').value='';!this.value&&search(0,'')"/> <span id="size-used"></span></span><br><span>Search by Language: <input id="search2" oninput="checkLang(this.value);search(0,this.value)" onclick="document.getElementById('search').value='';!this.value&&search(0,'')"/> <span id="language-used"></span></span><h2>Answer chain <span id="label-info">click a label to sort by column</span></h2><table class="answer-list"><thead><tr><td  onclick="sortby(0)">#</td><td onclick="sortby(1)">Author</td><td onclick="sortby(2)">Language</td><td onclick="sortby(3)">Sequence</td><td onclick="sortby(4)">Size</td></tr></thead><tbody id="answers"></tbody></table><table style="display: none"><tbody id="answer-template"><tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SEQUENCE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table><table style="display: none"><tbody id="language-template"><tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SEQUENCE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table>

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

385 Answers 385

1 2
3
4 5
13
5
\$\begingroup\$

27. C++, 584 bytes, A000274

#include <map>
#include <functional>
using namespace std;
int f(int i) {
    map<int, int> m;
    function<int(int)> a = [&](int j){
        if (!m.count(j)) {
            switch (j) {
            case -1:
            case 0:
                m[j] = 0;
                break;
            case 1:
                m[j] = 1;
                break;
            case 2:
                m[j] = 3;
                break;
            default:
                m[j] = (1+j)*a(j-1)+(3+j)*a(j-2)+(3-j)*a(j-3)+(2-j)*a(j-4);
            }
        }
        return m[j];
    };
    return a(i - 1);
}

Recursive solution with caching.

Next Sequence (shouldn't be a tricky one)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Since now different compilers are considered different languages, I think you should specify which compiler you are using. \$\endgroup\$
    – NieDzejkob
    Sep 23, 2017 at 12:03
5
\$\begingroup\$

28. Positron, 9 bytes, A000584

->{$1**5}

Try it online!

Finally got Positron in here ^_^

Next sequence

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Gosh darn it, I thought I had a chance to use Cubix, where the linear code is just I:***O@ \$\endgroup\$ Jul 22, 2017 at 0:51
  • \$\begingroup\$ @ETHproductions :) Finally I managed to not get ninja'd... for once... lol \$\endgroup\$
    – hyper-neutrino
    Jul 22, 2017 at 0:52
5
\$\begingroup\$

29. JavaScript (SpiderMonkey), 46 bytes, A000009

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

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

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

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

32. C (gcc), 216 bytes, A000172

#include <stdio.h>

#define cube(x) (x)*(x)*(x)

int main(int a) {
	int n;
	scanf("%d",&n);
	int nCr = 1;
	int sum = 0;
	for(int r=0;r<=n;r++) {
		sum += cube(nCr);
		nCr *= n-r;
		nCr /= r+1;
	}
	printf("%d",sum);
}

Try it online!

Next sequence

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

35. dc, 67 bytes, A000168

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

Try it online!

Next Sequence

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 65 is already used \$\endgroup\$
    – Leaky Nun
    Jul 22, 2017 at 6:00
  • \$\begingroup\$ @LeakyNun Fixed \$\endgroup\$
    – R. Kap
    Jul 22, 2017 at 6:03
5
\$\begingroup\$

36. J, 124 bytes, A000067

squares =: *:@i.@>:@<.@%:
filter =: ] #~ [ >: ]
f =: [: <: (2^]) +/@:>: [: ~.@,/ (2^<:@]) (] +/ 2 * filter) [: squares (2^])

Try it online!

Next sequence

\$\endgroup\$
1
  • \$\begingroup\$ Please make the next sequence in 6 bytes lol \$\endgroup\$
    – Leaky Nun
    Jul 22, 2017 at 6:38
5
\$\begingroup\$

37. 05AB1E, 6 bytes, A000124

The courtesy of Leaky Nun.

D>*2÷>

Try it online!

Next Sequence

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

38. Actually, 4 bytes, A000006

P√LA

Try it online!

Next sequence

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

41. PHP, 503 bytes, A003416

function f ($n) {
  $i=12495; $cnt=0; $used =[];

  while (true) {
    $i++;
    $ns = [];
    $v = $i;
    $sm = $i;

    while (!in_array($v, $ns)) {
      $ns[] = $v;
      $s = 0;

      for ($k=1; $k<=$v/2; $k++)
        if ($v % $k == 0) $s += $k;

      $v = $s;
      if ($s == 1) break;
      $sm = min($sm, $v);
    }

    if ($v < 2) continue;
    if (in_array($sm, $used)) continue;
    if ($cnt == $n) return $sm;
    $cnt++;

    for ($i=0; $i < count($ns); $i++) $used[] = $ns[$i];
  }
}

Try it online!

Next sequence

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

42. Cheddar, 28 bytes, A000503

n->(tan(n)|0)-(tan(n)<0?1:0)

Try it online!

Next sequence

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

44. Maxima, 94 bytes, A000651

f(n):=sum((2*k)!/k!/(k+1)!,k,1,n)+sum((2*binomial(n+k-1,k)-binomial(n+k,k))*f(n-1-k),k,0,n-2);

Try it online!

Next sequence

\$\endgroup\$
1
  • 1
    \$\begingroup\$ ... and we're back to partition \$\endgroup\$
    – Leaky Nun
    Jul 22, 2017 at 12:53
5
\$\begingroup\$

57. Desmos, 119 bytes, A000138

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

Try It Online!

Next Sequence

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

59. Brachylog, 59 bytes, A000011

;2↔^gP~g⟦k;Pz+ᵐḃᵐbᵐ{↔;?T{{;1↔-}ᵐ}ᵐ,T{{~cĊ↔c}ᶠb}ᵐ{∋∋}ᶠo}ᵐ∋ᶜ¹

Try it online!

Next sequence

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

72. SML, 252 bytes, A000401

fun A000401 x =
    let fun helper x y z =
        if z mod 4 = 0 then helper x y (z div 4)
        else if z mod 16 = 14 then helper x (y + 1) (y + 1)
        else if x = 0 then y
        else helper (x - 1) (y + 1) (y + 1)
    in helper x 0 1
    end

Online demo

(Note: those blocks which look like four spaces each are really tabs. I forgot about StackExchange forcing tabs into spaces, and now that I've posted the next sequence it's a bit late to change. If anyone is really fussed then they can be changed to use a single space for indentation).

Next sequence

Dissection

This uses the characterisation given in Dickson's History of the Theory of Numbers:

These are the numbers not of the form 4^k*(16*n + 14)

I could have defined one helper function to test for numbers not in the sequence and another to find the xth number which passes the test, but I think it's more in the spirit of PPCG to use a single helper function with two accumulators. x is the number we still have to discard; y is the number currently under consideration; z is y divided by some power of 4.

There is a small hack in calling it as helper x 0 1: if I called it as helper x 0 0 then there would be an infinite loop because 0 is divisible by 4 yielding 0.

\$\endgroup\$
3
  • \$\begingroup\$ Good to see that you've decided to participate again! \$\endgroup\$ Jul 23, 2017 at 21:25
  • \$\begingroup\$ I was a little nervous about leaving it on this sequence, but I saw the 4^k*(16*n + 14) note in the OEIS comments and knew that would be quite doable. \$\endgroup\$ Jul 24, 2017 at 2:28
  • \$\begingroup\$ @ETHproductions, it would have been easy to do it directly too. In CJam I would have used the definition because it's easier to do a three-way Cartesian product and set union than to do the loop to remove powers of 4. \$\endgroup\$ Jul 24, 2017 at 5:47
5
\$\begingroup\$

101. Fortress, 335 bytes, A000020

relativelyPrime(a,b)=array[\ZZ32\]((a MIN b)-1).fill(fn(n)=>1) EQ array[\ZZ32\]((a MIN b)-1).fill(fn(n)=>if ((a MOD (n+2))+(b MOD (n+2))) NE 0 then 1 else 0 end)
totient(n)= do
 S : ZZ32 = 0
 for i <- 1:n do
  S += if relativelyPrime(i,n) then 1 else 0 end
 end
 S
end
A000020(n) = do
 |\if n = 1 then 2 else totient(2^n-1)/n end/|
end

Next Sequence

Direct download of Fortress

If the language was equivalent to the specification at the time that FOrtress got axed, then this would probably be easy. But sadly, Fortress got the boot, and I'm stuck with this crap >_<.

\$\endgroup\$
2
  • \$\begingroup\$ Link to the language? \$\endgroup\$ Aug 11, 2017 at 22:18
  • \$\begingroup\$ Dead. Very dead. There it is. \$\endgroup\$
    – Adalynn
    Aug 11, 2017 at 22:22
5
\$\begingroup\$

115. shortC, 273 bytes, A001560

pa(m){Fm%2){T-1;}E{T1;}}
pt(m){Ii,p[200],s,j,k,t,kk;p[0]=1;for(i=1;i<=m;i++){j=1;k=1;s=0;Wj>0){kk=k*k;j=i-(3*kk+k)/2;t=pa(k);if(j>=0){s=s-t*p[j];}j=i-(3*kk-k)/2;Fj>=0){s=s-t*p[j];}k=k+1;}p[i]= s;}Ts}
AIi,c;scanf("%d",&c);Oi=0;i<131;i++){Fpt(i)%2==0)c--;Fc==1)break;}R"%d",i

Next sequence and Try it online!

It's surprisingly hard to calculate partitions in a language that doesn't have many math builtins. This could be more golfed, but it could also be a lot less golfed. :P

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Formula: ~ very helpful, I'm glad I can approximate it \$\endgroup\$
    – Stephen
    Aug 18, 2017 at 19:23
  • \$\begingroup\$ @StepHen hey it's not as bad as answer 96 :P \$\endgroup\$
    – MD XF
    Aug 18, 2017 at 19:24
  • \$\begingroup\$ It's not that hard to calculate partitions: you just need some kind of loop and addition. The number of partitions of n is the sum over 1 <= k <= n of the number of partitions of n into k parts, which has recurrence p(n, k) = p(n-1, k-1) + p(n-k, k). Alternatively the number of partitions of n into parts of at most k has recurrence q(n, k) = n == 0 ? 1 : sum(q(n - i*k, k-1), i = 0 to n/k). \$\endgroup\$ Aug 18, 2017 at 20:10
  • \$\begingroup\$ @PeterTaylor I wasn't very clear; I tried this in lots of languages that weren't built to deal with math before I resorted to shortC. \$\endgroup\$
    – MD XF
    Aug 18, 2017 at 20:20
  • 1
    \$\begingroup\$ NO. That's a complete violation of the spirit of the game. \$\endgroup\$ Aug 19, 2017 at 6:12
5
\$\begingroup\$

149. dash, 1993 bytes, A000173

Important: this is a precaution in case the INTERCAL answer for #149 is disqualified, to avoid #148 ending the chain due to the week having expired. It is deliberately the same length in order to preserve following answers.

succ () {
    # The successor is the sum of strictly smaller unitary divisors, where a
    # unitary divisor is a product of some subset of the maximal prime power divisors.
    # In other words, if we factor n as
    #   \prod_i p_i^{a_i}
    # then the successor should be
    #   \prod_i (p_i^{a_i} + 1) - n
    local n=$1
    local m=1
    factor $n | sed "s% %\n%g" | tail -n +2 | uniq -c |
        # Workaround for buggy read on my computer
        sed "s%^ *%%;s% %\n%" |
        while read x
        do
            read y
            z=1
            for i in $( seq $x )
            do
                z=$(( z * y ))
            done
            m=$(( m * (z + 1) ))
            # echo here and take tail because scope problems mean that m loses its
            # value outside this pipeline
            echo $(( m - n ))
        done
}

inseq () {
    local n=$1
    # We detect rhos using the little-step big-step method. If at any point we hit a
    # value less than n, clearly n isn't the smallest element of a cycle
    local k=$( succ $n | tail -1 )
    # If we loop already, it's unitary-perfect
    if test $k -le $n ; then return 1 ; fi

    local m=$( succ $k | tail -1 )
    # Loop already => it's unitary-amicable
    if test $m -le $n ; then return 1 ; fi

    while true
    do
        # Advance k once
        k=$( succ $k | tail -1 )
        # Advance m twice
        m=$( succ $m | tail -1 )
        if test $m -eq $n ; then return 0 ; fi
        if test $m -lt $n -o $m -eq $k ; then return 1 ; fi
        m=$( succ $m | tail -1 )
        if test $m -eq $n ; then return 0 ; fi
        if test $m -lt $n -o $m -eq $k ; then return 1 ; fi
    done
}

idx=$1
# Naive approach: test all values from 2 to see whether they're in the sequence
# until we've found enough that are
j=2
while true
do
    if inseq $j
    then
        if test $idx -eq 0
        then
            echo $j
            return 0
        fi
        idx=$(( idx - 1 ))
    fi

    j=$(( j + 1 ))
done

Online demo

Next sequence

\$\endgroup\$
6
  • \$\begingroup\$ I wonder how the snippet will react to that :P \$\endgroup\$
    – NieDzejkob
    Sep 15, 2017 at 16:35
  • \$\begingroup\$ No, I don't have A000083. I don't have a slightest idea about what is happening. Go ahead and choose some saner next sequence ;) \$\endgroup\$
    – NieDzejkob
    Sep 17, 2017 at 7:38
  • \$\begingroup\$ Uh, @PeterTaylor did you get a notification when I replied? \$\endgroup\$
    – NieDzejkob
    Sep 17, 2017 at 19:00
  • 1
    \$\begingroup\$ @PeterTaylor gogogo \$\endgroup\$ Sep 18, 2017 at 17:20
  • \$\begingroup\$ @cairdcoinheringaahing, I don't understand your request. On the basis of the discussion on meta, where no-one has provided any answer contrary to mine or downvoted it, it's the other 149 which should be deleted and this one remains necessary. \$\endgroup\$ Sep 23, 2017 at 20:28
5
\$\begingroup\$

231. Shakespeare Programming Language, 938 bytes, A000086

The Beautiful Story of Solving Quadratic Equations.
Theseus, the mathematician.
Dogberry, his calculator.
Page, to avoid mistakes caused by imperfect mental math.
Mistress Page, to make Page feel less lonely.

     Act XLII: Introducing modulus arithmetic.
    Scene I: Dogberry as a motivational speaker.
[Enter Dogberry and Page]
 Dogberry:
   Listen to your heart!
[Exeunt]

   Scene II: Complex math without complex numbers.
[Exeunt]
[Enter Theseus and Dogberry]
 Theseus:
   You are the remainder of the quotient between the sum of a cat and
   the product of Mistress Page and the sum of Mistress Page and a
   Microsoft and Page. Are you as big as nothing?
 Dogberry:
   If so, you are the sum of yourself and a cat.
[Exit Dogberry]
[Enter Mistress Page]
 Theseus:
   You are the sum of yourself and an angel. Are you as trustworthy as
   Page? If not, let us return to Scene II.
 Mistress Page:
   If so, open your heart.
[Exeunt]

Try it online!

Next sequence!

It's suprisingly hard to introduce words that mean nothing in the statement, so I didn't. Yes, Microsoft has a meaning - in fact, it's a negative noun so it means -1.

\$\endgroup\$
1
  • \$\begingroup\$ Please note that the bytecount changed in the first 10 or so seconds. \$\endgroup\$
    – NieDzejkob
    Oct 20, 2017 at 15:11
5
\$\begingroup\$

244. UCBLogo, 1524 bytes, A000112

to permutations :list
    if :list = [] [op [[]]]
    op map.se [
        map [[ls] fput ? :ls] permutations (remove ? :list)
    ] :list
end

to dfs :node
    repeat :N [
        if and
        (1 = item :node item repcount :matrix) 
        not(item repcount :visited) 
        [
            setitem repcount :visited "true
            dfs repcount
        ]
    ]
end

to tuples :items :n
    if :n = 1 [op map "list :items]
    op (crossmap "fput :items tuples :items :n-1)
end

to isomorphic :mat1 :mat2 ; they must both have size N*N
    foreach permutations iseq 1 :N [
        catch "failed [
            for [i 1 :N] [
                for [j 1 :N] [
                    if (
                            (item      :i    item       :j    :mat1)  
                            item (item :i ?) item (item :j ?) :mat2
                    ) [throw "failed]
                ]
            ]
            op "true
        ]
    ]
    op "false
end

to solve :N
    if :N = 0 [op 1]

    localmake "visited array :N
    localmake "matrices []
    local "valid

    foreach tuples (tuples [0 1] :N) :N [ [matrix]
        make "valid "true
        for [node 1 :N] [
            repeat :N [
                setitem repcount :visited "false
            ]
            dfs :node

            if (item :node :visited) [
                make "valid "false
                throw "for.catchtag ; FMSLogo-specific way to break for loop
                ; because Logo doesn't have Break command.
            ]
            repeat :N [
                if and (item repcount :visited) (0 = item :node item repcount :matrix) [
                    make "valid "false
                    throw "for.catchtag
                ]
            ]
        ]

        if :valid [
            catch "nextmatrix [
                foreach :matrices [
                    if isomorphic :matrix ? [throw "nextmatrix]
                ]
                make "matrices fput :matrix :matrices
            ]
        ]
    ]
    op count :matrices
end
       

Next sequence.

There are 7 spaces in the last line.

You can try it online here. Just enter the program and append print solve 3 (for example) in the end.

I choose UCBLogo for this sequence because I don't want to use FMSLogo, which I want to keep for a more geometry-related sequence.

So, in the end I gave up and just post my bruteforce solution.

This one takes a long time to calculate for just n=4. The MD5 I mentioned in the chat is for the version with some spaces at the end removed.


Explanation:

First, the program generates all possible N×N matrices tuples (tuples [0 1] :N) :N. Each matrix represent a directed graph with N vertices.

For each matrix (store in variable matrix, it checks whether it represents a poset (Two vertices A and B has the edge A→B connected if and only if A<B) by: for each node, it runs a DFS from that node, and verify that it can't reach that node (there is no cycle in the graph), and there is an edge from the node to every reachable nodes (because < is transitive).

After having checked that the matrix represents a valid poset, the program checks whether it is isomorphic to any existing poset, stored in the matrices variable. If it is not, the program put :matrix to the first of the variable :matrices (make "matrices fput :matrix :matrices).

Then in the end the program output the number of elements of :matrices (op count :matrices).

\$\endgroup\$
8
  • 1
    \$\begingroup\$ I need to stop trying to write efficient code for these tougher sequences. Or at least, I need to start seriously attempting them before there's only a day left. \$\endgroup\$
    – KSmarts
    Nov 6, 2017 at 14:11
  • \$\begingroup\$ You could avoid the poset check by observing that each poset can be obtained from the subset relations among n subsets of {1,...,n}. But I'm not sure if creating all these (which can be optimized) and turning them into the.matrix representation of the graph is easier... \$\endgroup\$ Nov 6, 2017 at 15:56
  • \$\begingroup\$ @ChristianSievers So there would be ${2^n} \choose n$ graphs which is still significantly less than $2^{n^2}$. May be faster. It is not necessary to turn it into matrix representation too, if there is a way to check isomorphism of those. (Is it possible to check isomorphism of posets in polynomial time? Not for general graph, I know.) \$\endgroup\$
    – DELETE_ME
    Nov 7, 2017 at 1:02
  • \$\begingroup\$ You can easily bring the number of relevant matrices down to $3^((n-1)(n-2)/2)$, and my approach with the mentioned optimizations to less than $2^same$. So that seems nice, but my main idea was just to try to simpify the algorithm. I don't know about the isomorphism check, but be careful: graph isomorphism is not known to be NP-complete (subgraph isomorphism is), but has unknown complexity in NP (I mixed that up once myself) \$\endgroup\$ Nov 7, 2017 at 2:51
  • \$\begingroup\$ @ChristianSievers I don't really understand. First, how can I get complexity $3^{(n-1)(n-2) \over 2}$? I find it not obvious. (BTW your LaTeX need curly bracket in necessary places) Second, how is it important that graph isomorphism is NP-unknown? I can just use the fastest-available known algorithm that I can implement. \$\endgroup\$
    – DELETE_ME
    Nov 7, 2017 at 8:07
5
\$\begingroup\$

254. Enlist, 98 bytes, A001516

W F †  0r   ‡ ;@ ±@ ¹ ! :/ §€¹  Ė  ‡ 2* :2 :@ §/€   † ↕ ḥ1 ↕ ×J ḥ1 § † ↕ ḥ1 ↕ ×J ḥ1 §   ;0   S  §€

Try it online!

haha enlist can do a thing :D

Next Sequence

Explanation

WF†0r‡;@±@¹!:/§€¹Ė‡2*:2:@§/€†↕ḥ1↕×Jḥ1§†↕ḥ1↕×Jḥ1§;0S§€  Main Link
W                                                      wrap; x => [x]
 F                                                     flatten (WF is just for test suite purposes lol)
                                                    €  For each (this just returns the first `n` elements if the input is an integer)
  †                                                §   Execute a monadic bracketed chain on each (let's call the argument `z`)
   0r                                                  Range from 0 to `z`, inclusive
               €                                       For each in the range
     ‡        §                                        Execute a dyadic bracketed chain on each (let's call the argument `n`)
      ;@                                               Append `n` to
        ±@¹                                            [z + n, z - n]
           !                                           Factorial (of each)
            :/                                         Reduce over division (this gives (z + n)! / (z - n)! / n! which is what we want as the coefficient)
                ¹                                      Identity as right argument to prevent dyad-monad chaining
                 Ė                                     Enumerate 1-indexed
                           €                           For each enumerated element (let's call the argument [x, y])
                  ‡      §/€                           Reduce over dyadic function (gives `x $ y`)
                   2*                                  2 ^ x
                     :2                                / 2 (floored)
                       :@                              y / (floored)
                                                     (this is y / 2 ^ (x - 1))
                            †        §                 Monadic bracketed expression (derivative step)
                             ↕                         Reverse
                              ḥ1                       All but last 1 element
                                ↕                      Reverse
                                 ×J                    Multiply each with its index
                                   ḥ1                  All but last 1 element
                                      †↕ḥ1↕×Jḥ1§       Derivative again
                                                ;0     Append 0 (to prevent empty-sum errors)
                                                  S    Sum
\$\endgroup\$
5
  • \$\begingroup\$ For the second time. Well, that means Enlist can't be used again till 300th answer. \$\endgroup\$
    – DELETE_ME
    Nov 20, 2017 at 14:16
  • \$\begingroup\$ cough cough bytecount cough \$\endgroup\$
    – NieDzejkob
    Nov 20, 2017 at 14:18
  • \$\begingroup\$ @user202729 oh well, enlist isn't that great for this challenge due to its current lack of functionality. By the time it gets functionality it will probably be in the 300s. \$\endgroup\$
    – hyper-neutrino
    Nov 20, 2017 at 14:22
  • \$\begingroup\$ Shouldn't it return the n-th number instead of a list of all numbers up to n? Anyway, good job \$\endgroup\$
    – NieDzejkob
    Nov 20, 2017 at 14:48
  • \$\begingroup\$ @NieDzejkob eh, technically yes. fine, I'll fix it \$\endgroup\$
    – hyper-neutrino
    Nov 20, 2017 at 14:49
5
\$\begingroup\$

12. Java (OpenJDK 8), 131 bytes, A000064

int f(int n){int[]a=new int[n+1],c={1,2,5,10,1};a[0]=1;for(int i=0,j,k;i<5;i++)for(j=c[i],k=0;j<=n;j++,k++)a[j]+=a[k];return a[n];}

Try it online!

Next sequence

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

277. 2sable, 104 bytes, A000188

Ln¹%1‹Oquery: no rules about unnecessary text?
Nearest available byte count is 104 so this code is on it

Try it online!

Next Sequence

It didn't seem like there was a rule against unnecessary text but if I misinterpreted I will delete.

Explanation

Ln¹%1‹Oq     Only part of the code that gets evaluated
L            [1...n] where n is the input
 n           square: [1,4,9,...n**2]
  ¹          push the input n
   %         mod: [1%n,4%n,...(n**2)%n]
    1        push 1
     ‹       less than 1: [1%n<1,4%n<1,...(n**2)%n<1]
      O      count the ones in the array
       q     terminate the program
uery: no...  not evaluated

Regarding the next sequence, I almost skipped it because it looks hard but then changed my mind. It seems like a high level language would be useful there. I've noticed there are no Maple answers so someone could try it in that. There is also Pyon which from this answer seems like it is essentially just Python so I don't know if we are counting it as a separate language. Fortran is also available for an answer but I don't know if many people use it and it is not so high level.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Unnecessary bytes are allowed (and sometimes forced), mostly because of byte restriction. \$\endgroup\$
    – DELETE_ME
    Dec 8, 2017 at 2:40
  • 1
    \$\begingroup\$ hard? No, this one is easy. \$\endgroup\$
    – DELETE_ME
    Dec 8, 2017 at 6:34
  • \$\begingroup\$ @user202729 good, I was worried a little \$\endgroup\$
    – dylnan
    Dec 8, 2017 at 13:07
  • \$\begingroup\$ For those working on the next one, you may want to look at Donald Knuth's POLYNUM and POLYSLAVE programs. \$\endgroup\$
    – KSmarts
    Dec 8, 2017 at 14:54
  • \$\begingroup\$ BTW Pyon is a superset of Python, kind of like Coconut. Most Python code works in Pyon, and if there's code that doesn't, then it's a bug with Pyon. \$\endgroup\$
    – hyper-neutrino
    Dec 11, 2017 at 14:43
5
\$\begingroup\$

280. Axiom, 947 bytes, A002852

artanh:(Float) -> Float
artanh(x) == 
    y := x 
    k := 1
    for k in 1..precision() repeat
        z := x^(2*k+1) / (2 * k + 1)
        y := z + y
    return y

ln2:() -> Float
ln2() == artanh(0.5) + artanh(1.0 / 7)

gamma:(NonNegativeInteger) -> Float
gamma(e) ==
    precision(2 ^ e + 100)
    n := 2.0 ^ e
    eps := 1.0 / n
    A := - e * ln2()
    B := 1.0
    U := A 
    V := 1.0
    k := 1
    repeat
        B := B * n^2 / k^2
        A := (A * n^2 / k + B) / k
        if (A < eps) /\ (B < eps) then
            return U / V
        U := U + A
        V := V + B
        k := k + 1

fractions:(NonNegativeInteger, Integer) -> List(Integer)
fractions(e, n) ==
    y := gamma(e)
    l : List(Integer) := []
    for i in 0..n repeat
        f := floor(y)
        l := cons(f, l)
        y := y - f
        if y > 0 then 
            y := 1 / y
    reverse(l)

)set messages prompt none
)set messages type off
fractions(12, 1000)
)quit

next sequence

There doesn't seem to be a good way to read input in this system, but called like this (using the fricas fork)

fricas -noht -eval ")read em.input )quiet" 

where em.input contains the source code, will print a table of the first 1001 elements of the sequence.

\$\endgroup\$
8
  • \$\begingroup\$ I don't have Axiom installed on my machine, but is e=12 enough to calculate 1000 terms? Because in that case you have eps = 1 / (2 ^ 12) (I guess ^ is exponentiation?) and the terminating condition is (A < eps) /\ (B < eps) (I guess /\ is conjunction)... \$\endgroup\$
    – DELETE_ME
    Dec 17, 2017 at 3:48
  • \$\begingroup\$ Also, can you explain which series are you using to calculate gamma? It's not entirely obvious from the code. \$\endgroup\$
    – DELETE_ME
    Dec 17, 2017 at 4:02
  • \$\begingroup\$ That should be eps = 10 ^ -n. Odd that it works anyway. Series used is from Brent. There also is an axiom docker image. \$\endgroup\$
    – politza
    Dec 17, 2017 at 9:09
  • 2
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$
    – Riker
    Dec 18, 2017 at 1:04
  • \$\begingroup\$ Does the next series involve group theory \$\endgroup\$ Dec 21, 2017 at 18:23
5
\$\begingroup\$

43. Swift 4, 651 bytes, A000028

func bit_sum_parity(n: Int) -> Int {
    var res = 0;
    var test = n;
    while test > 0 {
        res ^= test%2;
        test /= 2;
    }
    return res;
}

func A000028(n: Int) -> Int {
    var res = 1;
    var iter = n;
    while iter > 0 {
        var clone = res;
        var p = 2;
        var parity = 0;
        while clone > 1 {
            var count = 0;
            while clone % p == 0 {
                clone /= p;
                count += 1;
            }
            parity ^= bit_sum_parity(n: count);
            p += 1;
        }
        if parity == 1 {
            iter -= 1;
        }
        res += 1;
    }
    return res-1;
}

Try it online!

Next Sequence - A000651

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

297. Shakespeare Programming Language, 1460 bytes, A000161

A000161 - Number of partitions of n into 2 squares.
Romeo, the first square.
Juliet, the second square.
Othello, the input.
Macbeth, the counter.
Hamlet, the narrator.
The Ghost, the temporary actor one.

          Act I: Main Program.
       Scene I: Retrieving Input.

[Enter Hamlet and Othello]
 Hamlet:
  Listen to your heart!
[Exeunt]
  
       Scene II: Initialization.

[Enter Romeo and Juliet]
 Juliet:
  You are nothing!
[Exit Juliet]
[Enter Macbeth]
 Romeo:
  You are as good as me!
[Exeunt]

       Scene III: Calculation.

[Exeunt]
[Enter Romeo and The Ghost]
 Romeo:
  You are as bad as the product of me and me!
[Exit The Ghost]
[Enter Juliet]
 Romeo:
  You are as lovely as the square root of the difference between Othello and The Ghost!
 Juliet:
  Is Othello as lovely as the sum of the product of me and me and the product of you and you?
 Romeo:
  If not, let us proceed to Scene V.
[Exeunt]

       Scene IV: Add One.

[Enter Romeo and Macbeth]
 Romeo:
  You are as good as the sum of yourself and a flower.
[Exeunt]

       Scene V: Decision.

[Exeunt]
[Enter Romeo and Hamlet]
 Hamlet:
  You are as good as the sum of yourself and a flower.
 Romeo:
  Am I not better than the square root of Othello?
 Hamlet:
  If so, let us proceed to Scene III.
[Exeunt]

       Scene VI: Ending.

[Enter Hamlet and Macbeth]
 Hamlet:
  You are as good as the quotient between the sum of you and a flower and a beautiful flower. Open your heart!
[Exeunt]

Try it online!

Next sequence: A001460 - just some trivial factorial things

Added some padding bytes so that the next one will not be calculating on the graphs (originally 1429 bytes).

Added more padding so that the sequence points to a 0-indexed array

Translated code (Python):

import math
R, O = 0, input()              # Act I Scene I & II
M = R                          # Act I Scene I & II
while R <= int(math.sqrt(O)):  # Act I Scene V
 G = R * R                     # Act I Scene III
 J = int(math.sqrt(O - G))     # Act I Scene III
 if O == R * R + J * J:        # Act I Scene III
  M = M + 1                    # Act I Scene IV
 R = R + 1                     # Act I Scene V
print (M + 1) // 2             # Act I Scene VI result = ceil(M / 2)
                               #                because all except n=2a² are counted twice
\$\endgroup\$
4
\$\begingroup\$

16. Lua, 69 bytes, A000085

function f(n)
 if n<2 then return 1 end
 return f(n-1)+~-n*f(n-2)
end

Try it online!

Next sequence

\$\endgroup\$
2
  • \$\begingroup\$ Open problem: does Lua have memoization? This should have exponential complexity... \$\endgroup\$
    – Leaky Nun
    Jul 21, 2017 at 19:10
  • \$\begingroup\$ Hold on, you 4 people \o/ \$\endgroup\$
    – Leaky Nun
    Jul 21, 2017 at 19:14
4
\$\begingroup\$

18. APL (Dyalog), 37 bytes, A000018

{+/(1↓∪,∘.{(⍵×⍵)+16×⍺×⍺}⍨⍳1+2*⍵)≤2*⍵}

Try it online!

Next sequence

Warning: this is terribly inefficent

\$\endgroup\$
4
  • \$\begingroup\$ @ETHproductions Yes, forgot the number \$\endgroup\$
    – user41805
    Jul 21, 2017 at 20:03
  • \$\begingroup\$ Note: I changed the bytecount of this solution to make it slightly easier for the next solution. cc @ETHproductions \$\endgroup\$
    – user41805
    Jul 21, 2017 at 20:06
  • 2
    \$\begingroup\$ -1 for changing the next sequence for no good reason \$\endgroup\$ Jul 21, 2017 at 20:09
  • \$\begingroup\$ Oh, that'll probably be solved before I'm back at a computer then \$\endgroup\$ Jul 21, 2017 at 20:09
4
\$\begingroup\$

23. Ruby, 23 bytes, A000982

a=->(n){(n*n/2.0).ceil}

Try it online!

Next sequence

23rd entry uses 23 bytes!

\$\endgroup\$
2
  • \$\begingroup\$ Could you format this as asked in the question please? \$\endgroup\$ Jul 21, 2017 at 22:51
  • \$\begingroup\$ fixed, sorry bout that \$\endgroup\$
    – Justin
    Jul 21, 2017 at 22:52
4
\$\begingroup\$

33. Octave, 73 bytes, A000216

function o=s(x)
if x<2
o=2;
else
o=sum((int2str(s(x-1))-'0').^2);
end
end

Try it online!

Pretty basic recursive formula.

Next sequence

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

45. D, 190 bytes, A000094

int A000094(int n) {
	if (n<4) {
		return 0;
	}
	int[] gf = new int[n+1];
	gf[0] = 1;
	for (int i=1; i<n; i++) {
		for (int j=i; j<=n; j++) {
			gf[j] += gf[j-i];
		}
	}
	return gf[n]-n+1;
}

Try it online!

Next sequence

\$\endgroup\$
1
  • \$\begingroup\$ Never thought I'd see a D answer, nice job making me use Fortress. Grr. \$\endgroup\$
    – Adalynn
    Aug 11, 2017 at 21:49
1 2
3
4 5
13

Your Answer

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

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