94
\$\begingroup\$

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

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

1. NieDzejkob - 41 answers

2. KSmarts - 30 answers

3. Hyper Neutrino - 26 answers


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

This answer chaining question will work in the following way:

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

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

However!

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

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

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

Input and Output

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

Formatting

As with most questions, please format your answer like this

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

`code`

[next sequence](link)

*anything else*

Rules

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

Answer chain snippet

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

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

346 Answers 346

3
\$\begingroup\$

154. Verilog, 262 bytes, A001344

module OEIS1344 (input c, input [99:0] n, output reg [99:0] r=0, output reg v=1'b1);
reg [99:0] i,f;
always @ (posedge c) if(v)begin f=n-((n>0)?1:0);v=(f==0);i=f-1;r=(n*(n+3))+((n==0)?2:1);end else begin v=(i==0)||(i==-1);f=v?f:f*i;i=i-1;r=v?r*f:r;end 
endmodule

Next sequence!

The Verilog module above calculates OEIS A001344.

The code below is the same code but prettified, and a testbench module added to allow you to run the code in a Verilog simulator such as modelsim.

I have verified inputs up to the 22nd element in the sequence, beyond which OEIS runs out of examples, and shortly afterwards the numbers start overflowing 100bit arithmetic. I believe that is allowed as per the rules about assuming input and output numbers will never overflow the language. Originally I had used 32bit arithmetic which caused overflow at 13, but without changing the byte count (just 3 numbers from 31 to 99) we can get up to 22-ish.

When simulating, the input number is clocked in on the rising edge. v may go low if it is going to take more than one clock cycle to calculate. Once v is high after the clock edge that loaded the number, the output r can be considered a valid number of the OEIS A001344 sequence.

The code is actually making use of the related OEIS sequence, A028387 which calculates n + (n+1)^2. By multiplying the n+1'th element of that sequence by n! we arrive at the A001344 sequence. All that is required is a little fiddling around with the value of n to make it 0-indexed as per the requirements and we have our result.

To do this in Verilog is a little bit of a pain as it requires a factorial. The simplest approach is to use an iterative approach over n clock cycles to calculate the factorial and output the final result.

I should probably point out that both the OEIS1344 module and its testbench are very naïve approaches to get the job done. But since joining PPCG I've wanted to be able to use Verilog in an answer, and I found a way to shoehorn it into this one.


The following is an example output from ModelSim:

Testbench Output Example

The following is the testbench code:

module OEIS1344_test;

reg c = 0;
always begin
    #10 c = !c;
end

reg  [99:0] n;
wire [99:0] r;
wire v;

OEIS1344 dut (
    .c(c),
    .n(n),
    .r(r),
    .v(v)
);

reg  [99:0] i;
initial begin
    for (i = 0; i < 23; i=i+1) begin
        n = i;
        @(posedge c);
        while (!v) @(posedge c);
    end
end

endmodule

module OEIS1344 (
    input c,
    input [99:0] n,
    output reg [99:0] r = 0,
    output reg v = 1'b1
);

reg [99:0] i,f;
always @ (posedge c) begin
    if (v) begin
        f = n - ((n > 0) ? 1 : 0);
        v = (f == 0);
        i = f - 1;
        r = (n * (n + 3)) + ((n == 0) ? 2 : 1);
    end else begin
        v = (i == 0) || (i == -1);
        f = v ? f : f * i;
        i = i - 1;
        r = v ? r * f : r;
    end
end
endmodule
\$\endgroup\$
3
\$\begingroup\$

160. Bash, 315 bytes, A000778

#!/bin/bash

array=()
array[0]=1
i=1
read n

while [ $i -le $(expr 2 * $n + 2) ]
do
    let array[$i]=array[$(expr $i - 1)]*$i
    let i=i+1
done

echo $(expr ${array[$(expr 2 * $n)]} / ${array[$n]} / ${array[$(expr $n + 1)]} + ${array[$(expr 2 * $n + 2)]} / ${array[$(expr $n + 1)]} / ${array[$(expr $n + 2)]} - 1)

Try it online!

A000315

\$\endgroup\$
  • \$\begingroup\$ It'll take a moment to figure this out, but I can already see that this is related to sudoku. \$\endgroup\$ – NieDzejkob Sep 19 '17 at 10:34
3
\$\begingroup\$

166. Scratch 2, 638 bytes, A000114

code as image

Or, when written as text in the ScratchBlocks2 format:

when green flag clicked
ask [] and wait
set [a v] to ((answer) + (2))
if <(a) = [2]> then 
  say [3]
else 
  set [b v] to (((a) * (a)) / (2))
  set [d v] to [2]
  repeat until <(d) = (a)> 
    if <((a) mod (d)) = [0]> then 
      set [c v] to [2]
      set [prime v] to [1]
      repeat until <<(prime) = [0]> or <(c) > ([sqrt v] of (d))>> 
        if <((d) mod (c)) = [0]> then 
          set [prime v] to [0]
        end
        set [c v] to ((c) + (1))
      end
      if <(prime) = [1]> then 
        set [b v] to ((b) * ((1) - ((1) / ((d) * (d)))))
      end
    end
    set [d v] to ((d) + (1))
  end
  say ((b) - ((b) mod (1)))
end

Next sequence

\$\endgroup\$
  • 2
    \$\begingroup\$ Note for next sequence: as with previous similar sequences, you cannot hardcode. You must compute, since it has to theoretically work for ns up to 1000. \$\endgroup\$ – Stephen Sep 19 '17 at 21:02
  • 1
    \$\begingroup\$ Also good resource for future things vixra.org/abs/1409.0048 \$\endgroup\$ – Husnain Raza Sep 19 '17 at 23:30
  • 1
    \$\begingroup\$ When everyone gives up we can always "use" Magma (totally no copy-paste from OEIS) \$\endgroup\$ – Grzegorz Puławski Sep 20 '17 at 12:07
  • 1
    \$\begingroup\$ @GrzegorzPuławski alernatively, we can reverse engineer Magma and copy the necessary functions to some other language \$\endgroup\$ – NieDzejkob Sep 20 '17 at 12:53
  • 1
    \$\begingroup\$ I wonder, if I got another function in Magma other than SubgroupLatices() that produces the same sequence, would that still be considered copy from OEIS? (after packaging into a function) \$\endgroup\$ – Grzegorz Puławski Sep 20 '17 at 13:50
3
\$\begingroup\$

167. Magma, 101 bytes, A000638

a000638:=function(n);if n eq 0 then return 1;else return#SubgroupClasses(Sym(n));end if;end function;

Next sequence

You're probably thinking "This is taken from the OEIS site!", but hold on. While checking Magma documentation, I found something interesting here. One of OEIS descriptions of this sequence is number of conjugacy classes of subgroups of symmetric group S_n, and the documentation speaks of a build-in! And it's a different one than the one used on OEIS SubgroupLattice(), this one is SubgroupClasses(). So it happens that both functions create the same amount of subgroups (possibly how the math of this works - I'm not sure), but SubgroupClasses() is actually THE correct way. Thus I felt that this answer is eligible.

You can try it here

Code usage:

Just paste the function and then call it by a000638(5); or any other number instead of 5 (note, anything higher than 11 will time out). You can also use this to output 11 first integers in the sequence:

for i := 0 to 10 by 1 do a000638(i); end for;

Code explanation:

a000638 := function(n);           // Create a function taking one argument
    if n eq 0 then                // If argument is 0
        return 1;                 //     Then return 1
    else                          // Otherwise
        return #                  //     Count and return the number of
               SubgroupClasses(   //         Conjugacy classes of subgroups of
                   Sym(n)         //             Symmetric group of order n
               );
    end if;
end function;
\$\endgroup\$
3
\$\begingroup\$

171. TrumpScript, 541 bytes, A000204

Putin hears all your life
Putin is safe because its Putin
Trump is, 1000001 minus 1000000; great
Our beautiful America is, 1000003 minus 1000000; the greatest
Of course everything is, Trump plus Trump;
Every million is for Trump;
If you want, Putin is Trump?;:
Say Putin!
Otherwise: if for you, Putin is Everything?;:
Say America!
Otherwise:
Money is Everything
As long as, our Money less than Putin;:
Russia is America
America is, Trump plus America;
Trump is Russia
Money is, Money plus Million;!
Say America with force!!
America is great.

Try it online!

Next sequence

Pseudocode for explanation:

var Putin = int(input())
var Trump = 1
var America = 3
var Everything = Trump + Trump
var Million = Trump
if(Putin == Trump)
    print(Putin)
else if(Putin == Everything)
    print(America)
else
    var Money = Everything
    while(Money < Putin)
        var Russia = America
        America = Trump + America
        Trump = Russia
        Money = Money + Million
    print(America)
America is great.
\$\endgroup\$
3
\$\begingroup\$

190. COBOL (GNU), 725 bytes, A001182

       IDENTIFICATION DIVISION.
       PROGRAM-ID.  A001182.
       AUTHOR.  KSmarts.

       DATA DIVISION.

       WORKING-STORAGE SECTION.
       01  Num1                                PIC 999   VALUE ZEROS.
       01  Num2                                PIC 999   VALUE ZEROS.
       01  Iterator                            PIC 999   VALUE ZEROS.
       01  Result                              PIC 9(6)  VALUE ZEROS.

       PROCEDURE DIVISION.

       ACCEPT Num1.
       MOVE Num1 TO Iterator
       ADD 1 TO Num1
       MOVE 1 TO Num2
       PERFORM Summing Iterator TIMES
       DISPLAY Result.
       STOP RUN.

       Summing.
           COMPUTE Result = Result + (Num1**2 - Num2**2)**.5
           ADD 1 TO Num2.

Next Sequence

Try it online!

COBOL was originally designed with ease-of-use as the goal. We've come a long way since then.

\$\endgroup\$
  • 1
    \$\begingroup\$ Does anybody know what the symbols in the rightmost column of the table here mean? 'Cause A000722 is easy to solve but I don't know how to narrow it down to A000725... \$\endgroup\$ – totallyhuman Sep 27 '17 at 15:56
  • 1
    \$\begingroup\$ @icrieverytim I think it's the same as the comments: Equivalence classes "under action of permutation of variables on the domain and permutation and complementation of the range." \$\endgroup\$ – KSmarts Sep 27 '17 at 16:35
  • 1
    \$\begingroup\$ Why are there like three different sequences around the next one with the exact same description? \$\endgroup\$ – Husnain Raza Sep 28 '17 at 3:34
  • 1
    \$\begingroup\$ @HusnainRaza They all have the same title, but different descriptions in the comments. It looks like they are equivalence classes under different transformations \$\endgroup\$ – KSmarts Sep 28 '17 at 13:42
  • \$\begingroup\$ Is this impossible \$\endgroup\$ – Husnain Raza Sep 29 '17 at 3:25
3
\$\begingroup\$

195. ><>, 210 bytes, A000589

5+::6+}2*}5 -{2[\]b*$,n;
//?={:{:/?= 0:  /
:\      >    ~~1v
\{:}-12[v   /~]{ 22[v/~]*$32[v
v       <           <        >
            /:2=    ?/\
            ?
>:?\~11>*l2\
-1:/ v$\?- /
     >  :1) ^   v,$]~ /

Try it here - input given as initial stack
Next sequence

Fixed previous version. Byte count changed so I decided to delete and repost.
For some reason, doesn't work on TIO.

The code has 3 parts:
enter image description here
Red - computing main sequence;
Orange - computing binomial using factorial;
Blue - computing factorial;

\$\endgroup\$
3
\$\begingroup\$

196. Java (OpenJDK 9), 56 bytes, A000210

int f(int n) {return (int)Math.floor((n+1)*(Math.E-1));}

Try it online!

Next Sequence

\$\endgroup\$
  • \$\begingroup\$ Not like it matters very much, but I think you should say this is Java 9. \$\endgroup\$ – NieDzejkob Oct 2 '17 at 18:41
  • \$\begingroup\$ @NieDzejkob EDIT oh I thought that Java 9 was all taken and that Java 8 was still available mb \$\endgroup\$ – Stephen Oct 2 '17 at 18:50
3
\$\begingroup\$

204. Positron, 53 bytes, A000096

f = function {
      return ( $1 * ( $1 + 3 ) ) / 2
}

Try it online!

Next Sequence

shout out to all the New Yorkers here! xD

N.B. The next one can be hardcoded because it is a finite sequence

\$\endgroup\$
  • \$\begingroup\$ I'm a new yorker :D \$\endgroup\$ – Giuseppe Oct 2 '17 at 23:30
  • \$\begingroup\$ Is there a Mathematica built-in for the next one? \$\endgroup\$ – KSmarts Oct 2 '17 at 23:33
  • \$\begingroup\$ @KSmarts TrackStops@"NewYorkBroadway" (jk idk but I wouldn't be surprsed :P) \$\endgroup\$ – HyperNeutrino Oct 2 '17 at 23:35
  • \$\begingroup\$ If I find the Mathematica built-in, would you guys be okay with me using Mathematica for this? :P \$\endgroup\$ – totallyhuman Oct 3 '17 at 0:58
  • 1
    \$\begingroup\$ I'm afraid we might need you to save the challenge again... \$\endgroup\$ – NieDzejkob Oct 8 '17 at 11:18
3
\$\begingroup\$

211. 05AB1E, 78 bytes, A000076

2sm©ÝDâεDDн2m4*sP4*+sθ2m5*+}Ùʒ®›1s-}gqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq

Try it online!

Explanation

2sm©ÝDâεDDн2m4*sP4*+sθ2m5*+}Ùʒ®›1s-}gqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq  5
2                                                                               5, 2
 s                                                                              2, 5
  m                                                                             32
   ©                                                                            32 [Copy to register]
    Ý                                                                           [0, ..., 32]
     D                                                                          [0, ..., 32], [0, ..., 32]
      â                                                                         [[0, 0], [0, 1], ..., [32, 31], [32, 32]]
       ε                   }                                                    For each pair [x, y]
        D                                                                       [x, y], [x, y]
         D                                                                      [x, y], [x, y], [x, y] # yes I realize I can triplicate
          н                                                                     [x, y], [x, y], x
           2                                                                    [x, y], [x, y], x, 2
            m                                                                   [x, y], [x, y], x^2
             4                                                                  [x, y], [x, y], x^2, 4
              *                                                                 [x, y], [x, y], 4x^2
               s                                                                [x, y], 4x^2, [x, y]
                P                                                               [x, y], 4x^2, xy
                 4                                                              [x, y], 4x^2, xy, 4
                  *                                                             [x, y], 4x^2, 4xy
                   +                                                            [x, y], 4x^2+4xy
                    s                                                           4x^2+4xy, [x, y]
                     θ                                                          4x^2+4xy, y
                      2                                                         4x^2+4xy, y, 2
                       m                                                        4x^2+4xy, y^2
                        5                                                       4x^2+4xy, y^2, 5
                         *                                                      4x^2+4xy, 5y^2
                          +                                                     4x^2+4xy+5y^2
                            Ù                                                   Now we have a list of all numbers formed by this; uniquify
                             ʒ     }                                            Keep numbers `n` where the result of the codeblock is 1
                              ®                                                 n, 32
                               ›                                                n > 32
                                1                                               n > 32, 1
                                 s                                              1, n > 32
                                  -                                             1 - (n > 32)
                                    g                                           Length; final number of numbers formed
                                     qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq  `q` terminates the program

Next Sequence

\$\endgroup\$
  • \$\begingroup\$ wait, x to the power y is m in 05AB1E? Why? \$\endgroup\$ – caird coinheringaahing Oct 10 '17 at 19:45
  • \$\begingroup\$ @cairdcoinheringaahing \$\endgroup\$ – totallyhuman Oct 10 '17 at 21:16
  • \$\begingroup\$ @icrieverytim yeah? What? \$\endgroup\$ – caird coinheringaahing Oct 10 '17 at 21:18
  • \$\begingroup\$ @cairdcoinheringaahing Good question. I don't know either lol \$\endgroup\$ – HyperNeutrino Oct 10 '17 at 23:28
3
\$\begingroup\$

210. Pyth, 76 bytes, A000100

 "This is dummy text. Can be replaced with whatever you want!"l{s.pMfq3eST./

See the first few terms.

Next Sequence.

Explanation

  • (leading space) : Makes the interpreter ignore the next command.

  • "This is dummy text.... !" : Pushes a dummy String, which is ignored.

  • l{s.pMfq3eST./ : The thing which does the actual job.

    ./     @ Integer partitions.
    fq3eST @ Filter the partitions with maximal integer `3`.
    .pM    @ Get all the permutations of each.
    s      @ Flattens.
    {      @ Deduplicate.
    l      @ Length.
    
\$\endgroup\$
  • \$\begingroup\$ lol the next sequence is almost the same as the previous :P \$\endgroup\$ – Uriel Oct 10 '17 at 13:02
3
\$\begingroup\$

217. Mathematica, 174 bytes, A000411

L[a_, s_] := Sum[JacobiSymbol[-a, 2k + 1] / (2k + 1)^s, {k, 0, Infinity}]
d[a_, n_] := L[-a, 2n] * (2a / Pi)^(2n) / Sqrt[a] * (2n - 1)!
A000411[n_] := Round @ N @ d[6, n + 1]

Try it online!

Next sequence.

Note that this takes 30 seconds for n = 2 on TIO. Paper that was both useful and useless at the same time.

\$\endgroup\$
  • \$\begingroup\$ I found that paper very useful in creating the solution that I just now finished, more than 20 minutes late. It defines a recursive relationship, so you don't have to use infinite sums or Jacobi symbols at all. I'll have to save it in case another "Generalized Triangular Numbers" sequence comes up. \$\endgroup\$ – KSmarts Oct 10 '17 at 18:12
  • \$\begingroup\$ Might want to add a version number \$\endgroup\$ – Stephen Oct 10 '17 at 18:19
  • \$\begingroup\$ Rather than struggling with the paper you could just have looked at my Python code on OEIS. \$\endgroup\$ – Peter Taylor Oct 10 '17 at 19:18
  • \$\begingroup\$ @PeterTaylor Unfortunately all versions of Python have been used (cough i cri everytim) \$\endgroup\$ – HyperNeutrino Oct 10 '17 at 20:06
  • \$\begingroup\$ (though actually the logic there would've been really helpful nvm) \$\endgroup\$ – HyperNeutrino Oct 10 '17 at 20:06
3
\$\begingroup\$

218. ExtraC, 702 bytes, A000174

long N be readint
long R be 0
for(long A be 0 AND not(A times A greater N) AND increment A)do
  for(long B be A AND not(A times A plus B times B greater N) AND increment B)do
    for(long C be B AND not(A times A plus B times B plus C times C greater N) AND increment C)do
      for(long D be C AND not(A times A plus B times B plus C times C plus D times D greater N) AND increment D)do
        for(long E be D AND not(A times A plus B times B plus C times C plus D times D plus E times E greater N) AND increment E)do
          if(A times A plus B times B plus C times C plus D times D plus E times E equals N)do
            increment R
          end
        end
      end
    end
  end
end

print(R)

Try it online!

Next sequence!

\$\endgroup\$
  • \$\begingroup\$ Oh god this verbosity \$\endgroup\$ – HyperNeutrino Oct 11 '17 at 13:39
  • \$\begingroup\$ BTW, I think sorta(less) is supposed to work as <=, but it doesn't, so I had to use not(... greater ...). Also, I didn't bother removing the repeating expressions, because I would rather have simplicity and this is not codegolf. \$\endgroup\$ – NieDzejkob Oct 11 '17 at 14:45
3
\$\begingroup\$

208. Befunge 93, 75 bytes, A000389

&:5-v
vp00<v`g00<
    v_:v
    >1 >/v:
>:1-:v v*<^_$5432***/.@
^    _$> \:^

Try it online!

Next sequence

Since it has been pointed out that MATLAB might be is overkill for such a simple sequence I decided to give Befunge a try, and free MATLAB for future use.

Hoping it's not against the rules I'm changing the language of my answer maintaining the same bytecount.

\$\endgroup\$
  • 1
    \$\begingroup\$ You used MATLAB for a sequence that could've been done in 23 bytes of Befunge. I think that's a little bit wasteful. \$\endgroup\$ – NieDzejkob Oct 10 '17 at 10:27
  • \$\begingroup\$ @NieDzejkob Erik using jelly for 2,0,0,0,0,0,0... though xD also i cri everytim using all the pythons lol \$\endgroup\$ – HyperNeutrino Oct 10 '17 at 11:59
  • 1
    \$\begingroup\$ @Cinaski The point is that using such a useful language for something trivial enough to be solved in a short Befunge program is wasteful of MATLAB. \$\endgroup\$ – HyperNeutrino Oct 10 '17 at 12:24
  • 1
    \$\begingroup\$ @HyperNeutrino the point is to starve useful languages off in trivial sequences so people have to use languages no one has ever heard of in the last 15 or so, which is fun :P \$\endgroup\$ – Stephen Oct 10 '17 at 15:47
  • 1
    \$\begingroup\$ @KSmarts, it's even more frustrating when people change history unnecessarily. IMO the edit to change the language is against the spirit of answer-chaining, and OP should revert it. Also, everyone should stop complaining when someone else uses a language they wanted, or leaves a next sequence they don't like. The challenge is designed to die. If you don't like it, don't play. \$\endgroup\$ – Peter Taylor Oct 11 '17 at 18:02
3
\$\begingroup\$

221. Pony, 670 bytes, A000107

fun b(n: U128): U128 =>
  if n == 0 then
    return 0
  elseif n == 1 then
    return 1
  else
    var result: U128 = 0
    var j: U128 = 1
    
    while j < n do
      var d: U128 = 1
      var t: U128 = 0
      while d <= j do
        if (j % d) == 0 then
          t = t + (d * b(d))
        end
        d = d+1
      end
      result = result + (t * b(n-j))
      j = j+1
    end
    return result / (n-1)
  end

fun a(n: U128): U128 =>
  if n == 0 then
    return 0
  elseif n == 1 then
    return 1
  else
    var result: U128 = 0
    var i: U128 = 1
    while i < n do
      result = result + (a(n-i) * b(i))
      i = i+1
    end
    return result + b(n)
  end

Next Sequence

Try it online!

\$\endgroup\$
3
\$\begingroup\$

223. GolfScript, 88 bytes, A000110

{
 # Recurrence a(n+1) = sum a(k) * binomial(n, k)
 [1]{..,({[.(;\);]zip{~+}%}*+}@*-1=
}

Online demo

Next sequence

\$\endgroup\$
  • \$\begingroup\$ Does anyone have an idea what the O(...) mean in the first two formulas for the next seq? \$\endgroup\$ – NieDzejkob Oct 12 '17 at 7:50
  • \$\begingroup\$ @NieDzejkob Big O notation \$\endgroup\$ – Christian Sievers Oct 12 '17 at 9:41
  • \$\begingroup\$ @ChristianSievers have you seen that formula? The Big O notation is used for describing computational complexity, this was in the middle of a formula, which would obviously make no sense. \$\endgroup\$ – NieDzejkob Oct 12 '17 at 10:42
  • 1
    \$\begingroup\$ @NieDzejkob See the introduction and the section "Matters of notation"/"Other arithmetic operators" in the wikipedia article. It means there is a missing term of order O(...). \$\endgroup\$ – Christian Sievers Oct 12 '17 at 11:10
  • \$\begingroup\$ @ChristianSievers Oh that's right, sorry. That would also mean the formula is not usable for computing the sequence. Not that it matters anymore. \$\endgroup\$ – NieDzejkob Oct 12 '17 at 13:34
3
\$\begingroup\$

224. Racket, 1232 bytes, A000088

#lang racket

(define (partsm n m)
  (if (= n 0)
      '(())
      (for*/list ([k (range 1 (add1 (min n m)))]
                  [r (partsm (- n k) k)] )
        (cons k r) ) ) )

(define (parts n)
  (partsm n n) )

(define (fact n)
  (for/product ([i (range 1 (add1 n))]) i) )

(define (c2 n) ; ways to choose 2 elements from n
  (* n (sub1 n) 1/2) )

(define (cycHash cl)
  (let ([h (make-hash)])
     (for ([i cl])
       (hash-update! h i add1 0) )
   h ) )

(define (halfes ch)
  (for/hash ([(l m) ch]
             #:when (even? l) )
    (values (/ l 2) m) ) )

(define (centralizerSize ch)
  (for/product ([(l m) ch])
    (* (expt l m) (fact m)) ) )

(define (fixp ch n)
  (for/sum ([(l m) ch]
            #:when (= (remainder n l) 0) )
    (* l m) ) )

(define (s2orb hch n)
  (for/sum ([(hl m) hch]
            #:when (let-values ([(q r) (quotient/remainder n hl)])
                     (and (= 0 r) (odd? q)) ) )
    (* hl m) ) )

(define (edgeOrbs ch)
  (let* ([hch (halfes ch)]
         [order (apply lcm (hash-keys ch))])
    (/ (for/sum ([k order])
         (+ (c2 (fixp ch k)) (s2orb hch k)) )
       order ) ) )

(define (f n)
  (for/sum ([ch (map cycHash (parts n))])
    (/ (expt 2 (edgeOrbs ch)) (centralizerSize ch)) ) )

Try it online!

Next sequence

Yes, it was Burnside's lemma time again! Symmetric group acts on n nodes, inducing an action on the possible edges and on the possible graphs. Count the orbits of the last action, yada yada. Run through the elements by conjugacy classes represented by partitions of n. Number of graphs fixed by an element g is 2 to the number of orbits of edges under the action of the cyclic group generated by g. So use Burnside's lemma again and find the number of edges fixed by each g^k. An edge is fixed if its endpoints are on fixed points or on points that are interchanged by the group element. Feel free to ask for more details!

\$\endgroup\$
3
\$\begingroup\$

228. Hodor, 361 bytes, A000861

HoDoRHoDoR HODOR 000861(HODOR? ) {
  $HODOR: Hodor? = 0;
  $HODOR: HODOR?! = 0;
  hodor............ (Hodor? < HODOR? ) {
    HODOR?! = HODOR?! +1;
    $HODOR: d = HODOR?! % 10;
    $HODOR: h = HODOR?! % 100;
    HOdor!!! ( h==12 || ((h>20 || h<10) && ((d==1) || (d==2) || (d==3) || (d==5) || (d==9)))) {
      Hodor? = Hodor? +1;
    }
  }
  HODOR:: HODOR?! ;
}

Next Sequence

Hodor!

\$\endgroup\$
  • \$\begingroup\$ NOOOO.... I was ninja'd.... \$\endgroup\$ – Mr. Xcoder Oct 18 '17 at 17:37
  • \$\begingroup\$ @Mr.Xcoder Hodor. \$\endgroup\$ – KSmarts Oct 18 '17 at 17:38
  • \$\begingroup\$ @Mr.Xcoder same rip \$\endgroup\$ – Stephen Oct 18 '17 at 17:38
  • 1
    \$\begingroup\$ If you read the title of the next sequence out loud, I'd assume you're having a stroke.... \$\endgroup\$ – Grzegorz Puławski Oct 18 '17 at 20:06
3
\$\begingroup\$

227. C++ (clang), 861 bytes, A004903

Thanks to user202729 for C++ help :)

# include <iostream>
# include <algorithm>
# include <vector>
# include <math.h>

std::vector<int> getsums(std::vector<int> values, int times) {
	if (times == 1) {
		return values;
	} else {
		std::vector<int> results;
		for (int i = 0; i < values.size(); i++) {
			std::vector<int> subs = getsums(values, times - 1);
			for (int j = 0; j < subs.size(); j++) {
				results.push_back(subs[j] + values[i]);
			}
		} return results;
	}
}

// This method is O(log_8(n)) I think.

int main() {
	int input; std::cin >> input;
	int size = (int) pow(input / 8, 0.1) + 1;
	std::vector<int> values;
	for (int i = 0; i <= size; i++) values.push_back(pow(i, 10));
	std::vector<int> sums = getsums(values, 8);
	std:sort(sums.begin(), sums.end());
	sums.erase(std::unique(sums.begin(), sums.end()), sums.end());
	for (int i = 0; i < input; i++) std::cout << sums[i] << " ";
}

Try it online!

My first C++ program that actually does something interesting \o/

Next Sequence

\$\endgroup\$
  • \$\begingroup\$ very nice. I picked Gaia at random from TIO and saw your solution right as I was wrapping up! 4…10*¦8*Σ¦uȯ= if anyone is interested. \$\endgroup\$ – Giuseppe Oct 18 '17 at 17:17
  • \$\begingroup\$ note that y is not a vowel for the next sequence (otherwise 20 would be in it) \$\endgroup\$ – Giuseppe Oct 18 '17 at 17:18
  • \$\begingroup\$ @Giuseppe Cool, nice answer! Sorry for ninja'ing you haha \$\endgroup\$ – HyperNeutrino Oct 18 '17 at 17:18
  • \$\begingroup\$ If A000086 shows up, I'd be glad if ninjas let me post my Shakespeare-esque masterpiece. \$\endgroup\$ – NieDzejkob Oct 18 '17 at 17:20
  • \$\begingroup\$ @NieDzejkob Quick, now's your chance! \$\endgroup\$ – HyperNeutrino Oct 20 '17 at 14:48
3
\$\begingroup\$

237. M, 89 bytes, A000341

‘ḤŒ!s€2Ṣ€Ṣ$€QS€ÆPa/$$ÐfL                                                                 

Try it online!

Explanation

‘ḤŒ!s€2Ṣ€Ṣ$€QS€ÆPa/$$ÐfL  Main Link
‘                         Increment (for 0-indexing)
 Ḥ                        Double
  Œ!                      All permutations of {1 .. 2n} (implicit range)
    s€2                   Slice each permutation into subslices of length 2
          $€              For each subconfiguration
       Ṣ€                 Sort each pair
         Ṣ                Then sort the entire thing
            Q             Then remove duplicates
                   $$Ðf   Filter pairings using the last three links as a condition
                 a/       All (reduce over logical AND because M doesn't have the ALL builtin)
             S€           Sums
               ÆP         Are Prime
                       L  How many pairings are there?

There are a bunch of spaces at the end

Next Sequence

\$\endgroup\$
  • \$\begingroup\$ Does M not have an identity function? \$\endgroup\$ – caird coinheringaahing Oct 27 '17 at 14:15
  • \$\begingroup\$ @cairdcoinheringaahing Maybe it does but spaces are better because they don't clutter the end \$\endgroup\$ – HyperNeutrino Oct 27 '17 at 14:15
  • \$\begingroup\$ I'd say that you add those spaces to avoid A000087. \$\endgroup\$ – user202729 Oct 27 '17 at 14:25
  • \$\begingroup\$ @user202729 A87 is at the edge of feasibility in Shakespeare. \$\endgroup\$ – NieDzejkob Oct 27 '17 at 14:27
  • \$\begingroup\$ @user202729 I chose 89 because it looked nicer lol. Sometimes I decide to be nicer and sometimes I decide to make it a bit more challenging. In this case though, honestly 87 isn't really hard and I probably should've chosen it to keep a contiguous block of unoccupied bytecounts on the low end :P \$\endgroup\$ – HyperNeutrino Oct 27 '17 at 14:30
3
\$\begingroup\$

242. FriCAS, 111 bytes, A000230

a: (Integer) -> Integer
a(n) ==
 i:=2
 repeat
  j:=nextPrime(i)
  if j-i = 2*n or n = 0 then
   return i
  i:=j

Try it online here

Next Sequence

Pretty straightforward.

\$\endgroup\$
  • 2
    \$\begingroup\$ Ack, I spent too long testing my Pip solution! \$\endgroup\$ – DLosc Oct 28 '17 at 16:57
  • \$\begingroup\$ @DLosc This seems to be the theme of this challenge... \$\endgroup\$ – NieDzejkob Oct 30 '17 at 6:24
3
\$\begingroup\$

243. Ly, 112 bytes, A000111

1<<<<111<n2-0G*
[
 >&s0>l>lr>1>&s>lp
 [
  sp<l+sp<l>>
 ]
 <p<1&s>l<
 [
  sp<l*sp<l*sp<l+>>>
 ]
 <p<p<<,
]
p>u&p;

Try it online!

Next sequence

This uses the recurrence a(n) = Sum_{i=0..n-2} binomial(n-2,i)*a(i)*a(n-1-i).

Using the recurrence for one value needs all the binomials from one row in Pascal's tringle, and then the next value needs the next row, so we compute one row from the previous one by addition, avoiding factorials and divisions, so Ly will stay in the realm of integers and not switch to floats.

Ly uses an infinite strip of stacks, of which we're using seven. For reference, let's call them, from left to right: count, vals, oldvals, oldvalsR, bins, oldbins, and oldbinsT. The stack that we are at in the beginning will be used as oldbins, just because this is the rightmost that needs initialisation. We can move between the stacks with < and >.

We initialise oldbins with 1, the first row of Pascal's triangle. Then we initialise vals with the first three values, which are all 1. Next, we read the input into count and subtract 2, then 0G* will turn that into 0 if it was negative.

Now count tells us how many more values we need. Next we'll have a loop with this loop invariant: vals contains some initial values of the series, we are at count which holds one nonnegative number that tells how many more values are needed, oldbins contains the row of Pascal's triangle that was used for the last value, and the other stacks are empty.

(We didn't really use the first row of the triangle, but we would have needed it if we had computed a(2) from the recurrence. We don't start with only two values, because there is no 0th row from which we can compute the first without complicating the algorithm. We could also store the row we need next, but then we would needlessly compute one row more than needed.)

The looping construct [...] loops while the stack is not empty and its top element isn't zero. The outer loop will be terminated when count is zero, all other loops will be terminated by empty stacks.

To prepare for the work in the loop, we copy the vals stack to the backup cell using &s, then add a zero to this stack as initial value for the sum. Then we store the value of the backup cell to oldvals (with l) and also to oldvalsR, where we reverse it with r. Then we push the first value 1 of the new row of Pascal's triangle to bins, copy oldbins to oldbinsT and drop its first element there (with p).

We can think of the computation of bins as equivalent to this Haskell computation:

[1] ++ zipWith(+) oldbins oldbinsT ++ [1]   where oldbinsT = tail oldbins

The inner loop then copies (s) the top element from oldbinsT to the backup cell and drops it from the stack (p), and puts it on top of the oldbins stack, where it is added to the former top element. This sum is then moved (again with sp<l) to the bins stack. The loop body is completed by going back to the oldbinsT stack. (Note that at the first iteration of the outer loop, this loop will terminate immediately.)

After this loop, the remaining value from oldbins is dropped, and the final 1 value appended to bins. Then bins is copied to oldbins.

The second inner loop is like this Haskell code:

sum ( zipWith3 (\a b c->a*b*c) oldvals oldvalsR bins )

Note that bins has one value less than the two other stacks, so we use this to control the loop. In it, we move the top value to oldvalsR and multiply, then move the result to oldvals and multiply again. This product is moved to vals and added to the accumulated sum on its top. (Remember that we already pushed a zero here.)

When the loop is done, we drop the remaining values from oldvalsR and oldvals and decrement count (with ,).

When the outer loop is done, we needlessly drop the zero from count and output (and drop) the top element from vals. Finally, we delete this whole stack with &p and explicitely end the program with ;. We don't need both, but if we didn't do either, implicit output would print all values from vals.

\$\endgroup\$
  • \$\begingroup\$ Oh yes, I was late for 4 hours this time... Anyway my Enlist code: Try it online! (try on Python because Dennis hasn't pull latest version of Enlist, or at least I guess so) \$\endgroup\$ – user202729 Oct 31 '17 at 13:53
  • 1
    \$\begingroup\$ @user202729 503 Backend fetch failed. \$\endgroup\$ – Christian Sievers Oct 31 '17 at 14:01
  • 1
    \$\begingroup\$ @user202729 All those formulas and generating functions listed on the OEIS page, with sample programs in five different languages, and you decided to brute-force it. Good job. \$\endgroup\$ – KSmarts Oct 31 '17 at 14:32
  • 1
    \$\begingroup\$ @KSmarts Confusingly many formulas, not that easy to find one that is useful. (Otherwise someone would have answered earlier.) If you like brute-forcing, that may be the way to go for the next sequence. \$\endgroup\$ – Christian Sievers Oct 31 '17 at 14:42
  • 1
    \$\begingroup\$ @ChristianSievers Well, the first one E.g.f.: (1+sin(x))/cos(x) = tan(x) + sec(x) is pretty easy to understand, imo, but tough to implement in most languages. \$\endgroup\$ – KSmarts Oct 31 '17 at 15:25
3
\$\begingroup\$

245. Java 7, 1272 bytes, A001524

import java.util.*;

public class Main {
	public static List<List<Long>> partitions(long val) {
		List<List<Long>> list = new ArrayList<>();
		if (val == 0) {
			List<Long> sublist;
			list.add(sublist = new ArrayList<>());
		} else {
			for (int i = 1; i <= val; i++) {
				for (List<Long> ext : partitions(val - i)) {
					List<Long> sublist;
					list.add(sublist = new ArrayList<>());
					sublist.add((long) i);
					sublist.addAll(ext);
				}
			}
		} return list;
	}

	public static List<List<Long>> filter(List<List<Long>> partitions) {
		List<List<Long>> list = new ArrayList<>();
		outerloop: for (List<Long> sublist : partitions) {
			for (int i = 0; i < sublist.size() - 1; i++) {
				if (sublist.get(i) <= sublist.get(i + 1)) continue outerloop;
			} list.add(sublist);
		} return list;
	}

	public static long variants(List<Long> stack) {
		int variants = 1;
		for (int i = 0; i < stack.size() - 1; i++) {
			variants *= stack.get(i) - stack.get(i + 1);
		} return variants;
	}

	public static long A001524(long val) {
		long out = 0;
		for (List<Long> stack : filter(partitions(val))) out += variants(stack);
		return out;
	}

	public static void main(String[] args) {
		for (long i = 0; i < 10; i++) {
			System.out.println(i + ": " + A001524(i));
		}
	}
}

Try it online!

This isn't too slow though it probably could be improved. This sequence was fairly simple but 1272 bytes because Java.

Next Sequence

\$\endgroup\$
  • \$\begingroup\$ The only reason I didn't beat you to this is that my Python-based solution was too slow. It took more than a minute for A(3)... \$\endgroup\$ – KSmarts Nov 6 '17 at 15:03
  • \$\begingroup\$ @KSmarts Can I see your solution? How was it that slow D: \$\endgroup\$ – HyperNeutrino Nov 6 '17 at 15:05
  • \$\begingroup\$ Lots of recursion. \$\endgroup\$ – KSmarts Nov 6 '17 at 15:17
  • \$\begingroup\$ @KSmarts ಠ_ಠ that much recursion is 0/10 but regardless, nice :P \$\endgroup\$ – HyperNeutrino Nov 6 '17 at 15:23
  • \$\begingroup\$ @KSmarts You might want to try memoization \$\endgroup\$ – Christian Sievers Nov 6 '17 at 16:01
3
\$\begingroup\$

246. Coconut, 240 bytes, A001272

import math

def p(a): return not (a < 2 or any(a % x == 0 for x in range(2, int(a**0.5) + 1)))

def A(n):
 m=n+1
 i=k=0
 while k<m:
  i= i + 1
  x=0
  for j in range(1,i+1):
   x = x+(-1)**(i-j)*math.factorial(j)
  if p(x): k=k+1
 return i

Next Sequence

Try it online!

\$\endgroup\$
  • \$\begingroup\$ My Enlist code was late again. Partial code \$\endgroup\$ – user202729 Nov 6 '17 at 15:51
  • \$\begingroup\$ Since Coconut can execute nearly any Python code, there are now six Pythons to choose from ... :p \$\endgroup\$ – Jonathan Frech Nov 7 '17 at 19:55
  • \$\begingroup\$ @JonathanFrech According to their homepage (linked in the header), all valid Python is valid Coconut. Have fun! \$\endgroup\$ – KSmarts Nov 7 '17 at 20:00
  • \$\begingroup\$ @KSmarts The only annoying thing from a golfing perspective is that this is not entirely true, as -- for example -- the piece of code linked to can be considered valid Python 2 code. \$\endgroup\$ – Jonathan Frech Nov 7 '17 at 20:04
3
\$\begingroup\$

247. Enlist, 87 bytes, A000240

RṖ†eṢS=1§€S                                                                            

Try it online!

Next sequence.


Explanation:

 Ṗ           All permutations of
R            the ranges from 1 to n.
  †     §€   For each of them
   eṢ        Calculate the equality of that list with the sorted list (which is the range from 1 to n)
     S       Sum. Now the value is the number of fixed point of that permutation.
      =1     Return 1 if the number of fixed point is 1, and 0 otherwise.
         S   Sum of the values -> number of permutations such that number of fixed point is 1.
\$\endgroup\$
  • \$\begingroup\$ What is the next sequence? Definitely not A000011. Code snippet need to be changed. \$\endgroup\$ – user202729 Nov 6 '17 at 16:02
  • \$\begingroup\$ According to OP's snippet, it's A000087. (Not sure how accurate that is, though) \$\endgroup\$ – J. Sallé Nov 6 '17 at 16:04
  • 1
    \$\begingroup\$ "your bytecount must be unique." Please change this to match that requirement. \$\endgroup\$ – caird coinheringaahing Nov 6 '17 at 16:50
  • \$\begingroup\$ @cairdcoinheringaahing Oh yes. Sorry. I thought the rule was "if the sequence is already used then the next sequence is the lowest unused one". \$\endgroup\$ – user202729 Nov 7 '17 at 0:25
  • 1
    \$\begingroup\$ :DD :DDDD Enlist got used for something cool :D +1 \$\endgroup\$ – HyperNeutrino Nov 7 '17 at 13:20
3
\$\begingroup\$

248. Huginn, 904 bytes, A000087

import Algorithms as alg;

gcd( a_, b_ ) {
 u = integer( a_ );
 v = integer( b_ );
 while ( v > 0 ) {
    t = u;
    u = v;
    v = t % v;
  }
  return( u );
}

eulerPhi( n_ ) {
 n = integer( n_ );
 x = 0;
 for ( i : alg.range( 1, n + 1 ) ) {
  if ( gcd( i, n ) == 1 ) {
   x += 1;
  }
 }
 return ( x );
}

binomial( n_, k_ ) {
 n = integer( n_ );
 k = integer( k_ );
 x = 1;
 for ( i : alg.range( 1, k + 1 ) ) {
  x = x * (n - i + 1) / i;
 }
 return ( x );
}

A000087( n_ ) {
 n = integer( n_ ) + 1;
 z = 0.0 ;
 for ( k : alg.range( 1, n ) ) {
  if ( n % k == 0 ) {
   z += real( eulerPhi( n / k ) * binomial( 3 * k, k ) );
  }
 }
 z += real( ( n + 2 ) * binomial( 3 * n, n ) ) / real( ( 3 * n - 2 ) * ( 3 * n - 1 ) );
 z = z / real( 3 * n );
 if ( n % 2 == 1 ) {
  z += real( 2 * ( n + 1 ) * binomial( 3 * ( n + 1 ) / 2, ( n + 1 ) / 2 ) ) / real( 3 * ( 3 * n - 1 ) * ( 3 * n + 1 ) );
 }
 return( z );
}

Next Sequence

Try it online!

This uses the formula from the OEIS page, which is a little complicated, but not too hard once you break it down.

\$\endgroup\$
3
\$\begingroup\$

251. C (tcc), 269 bytes, A000711

long p(int k,int n,int*a,int l){long s=1;if(n<1)return!l;a[l]=n;for(int i=1,c,j;i<=k;i++){for(j=0,c=1;j<=l;j++)if(a[j]==i)c++;s*=(i<5)?((c)*(c+1)/2):c;}for(int i=(l==0)?1:a[l-1];i<=n/2;i++)a[l]=i,s+=p(k,n-i,a,l+1);return s;}long a(int n){int a[1000];return p(n,n,a,0);}

Try it online!

Next sequence!

Explanation

// Takes a partition a of the number k and returns how many different
// partitions it represents if the numbers can have many kinds, according
// to the specification of the sequence. For example:
// [1 1 1] =>
//    [1  1  1 ]
//    [1  1  1']
//    [1  1' 1']
//    [1' 1' 1']
//    [1' 1' 1"]
//    [1' 1" 1"]
//    [1" 1" 1"]
// Each different number in the partition can be processed separately,
// and the "score" will be the product of the scores of each number.
long score(int k, int length, int * a){
    long product = 1;

    for(int i = 1;i <= k;i++){ // A partition of k can contain numbers [1,k]
        int count = 0; // Count how many times the number i appears
        for(int j = 0;j <= length;j++){
            if(a[j] == i) c++;
        }

        if(i < 5){
            // i has 3 kinds. If you sort all the cases in ascending
            // "kind numbers", then the first Kind 2 (') can be in
            // (number of Kind >= 1, i. e. the variable c) + 1 positions:
            //    1  1  1
            //    1  1  1'
            //    1  1' 1'
            //    1' 1' 1'
            // Then, the first Kind 3 (") can be in (number of Kind >= 2) + 1
            // positions:
            //    1' 1' 1'
            //    1' 1' 1"
            //    1' 1" 1"
            //    1" 1" 1"
            // If you think about it, you'll get the sum of natural numbers
            // from 1 to (c + 1), for which there is a nice closed form
            // formula (look at sequence of answer number 1, don't forget
            // to rate the language choice 😉) (one problem Emoji solved
            // is ending a parenthesis with an emoticon).
            product *= ((c + 1) * (c + 2)) / 2;
        }else{
            product *= (c + 1);
        }
    }

    return product;
}

// A recursive function that enumerates all partitions of n, scores each
// and returns the sum of all scores. The partitions are generated at
// (a + level)
// Pseudocode algorithm:
// def partitions(n):
//     yield [n]
//     for i in range(1, n):
//         for p in partitions(n - i):
//             yield [n] + p
// Notice how we don't really need to check the whole range of [1, n)
// k is only relevant for scoring
// the partitions are generated at (a + level)
long partitions(int k, int n, int * a, int level){
    if(n < 1){
        if(l == 0){
            return 1; // l == 0 => this is the top level call, so include
            // the case of []
        }else{
            return 0; // doesn't happen, but I think this is the best
            // way to handle this edge case
        }
    }

    a[l] = n;
    long score_sum = score(k, l + 1, a);

    int start;

    if(l == 0){
        start = 1;
    }else{
        start = a[l - 1];
    }

    for(int i = start;i <= n/2;i++){
        a[l]=i;
        score_sum += partitions(k,n-i,a,l+1);
    }

    return score_sum;
}

long a(int n){
    // the longest partition of k is [1]*k, speaking Python,
    // so let's not bother with dynamic allocation
    int a[1000];
    return partitions(n, n, a, 0);
}
\$\endgroup\$
  • \$\begingroup\$ My Jelly code: chat.stackexchange.com/transcript/message/41118715#41118715 \$\endgroup\$ – user202729 Nov 13 '17 at 14:14
  • \$\begingroup\$ Please don't golf your answer, make it readable instead. This isn't even code-golf. \$\endgroup\$ – user202729 Nov 13 '17 at 14:36
  • 1
    \$\begingroup\$ @user202729 but it's fun! OK, I'll add a readable version \$\endgroup\$ – NieDzejkob Nov 13 '17 at 14:46
  • \$\begingroup\$ My Jelly code is even more efficient than yours, and only at number of bytecount ~ 8.2% of yours. \$\endgroup\$ – user202729 Nov 13 '17 at 14:52
  • \$\begingroup\$ @user202729 But is it more readable? \$\endgroup\$ – Christian Sievers Nov 13 '17 at 15:05
3
\$\begingroup\$

252. Pari/GP, 251 bytes, A000269

A000081(n) = if( n<3, if(n<1,0,1) , 1/(n-1)*sum(k=1,n-1,sumdiv(k,d,d*A000081(d))*A000081(n-k) ) );

gfA81(n) = sum( i=0, n, A000081(i)*x^i, O(x^(n+1)) );

gfA269(n) = {Bx = gfA81(n); Bx^3 * (3-2*Bx) / (1-Bx)^3}

A000269(n) = polcoeff(gfA269(n+3), n+3)

Next Sequence

Try it online!

This uses the generating function formula, by directly computing values of the sequence A000081.

\$\endgroup\$
  • \$\begingroup\$ Does anyone have access to that paper? I don't see how we're supposed that in less than O(silly(n))... \$\endgroup\$ – NieDzejkob Nov 16 '17 at 8:48
  • \$\begingroup\$ @NieDzejkob I have it now. I can implement the sequence in Haskell with the usual stuff for handling generating functions plus three one-line definitions. \$\endgroup\$ – Christian Sievers Nov 16 '17 at 23:12
  • \$\begingroup\$ @NieDzejkob It doesn't have to be efficient. \$\endgroup\$ – KSmarts Nov 17 '17 at 14:13
  • \$\begingroup\$ @KSmarts if it's fast enough for small n that you can convince yourself that it works... \$\endgroup\$ – NieDzejkob Nov 17 '17 at 18:04
  • \$\begingroup\$ Rip challenge :( \$\endgroup\$ – Husnain Raza Nov 20 '17 at 3:53
3
\$\begingroup\$

267. Erlang (escript), 338 bytes, A002572


h(N,A,_) when A > N -> 0;
h(N,A,_) when A == N -> 1;
h(N,A,B) -> case erlang:get({N,A,B}) of
	F when is_integer(F) -> F;
	'undefined' -> 
		F = lists:sum(lists:map(
			fun(I) -> h(N-I, (A-I)*2, B+1) end,
		lists:seq(0, A-1))),
		erlang:put({N,A,B}, F),
		F
	end.

main([])-> {ok, [N]} = io:fread("", "~d"),
io:fwrite("~p", [h(N+1,1,0)]).

Try it online!

Next sequence!

I first wrote this in Python, and then I had decided to find a language with bignums, because this sequence grows pretty quickly. I hope this will explain it pretty well:

cache = {}
# Calculate the number of partitions of a/(2^b) into n powers of (1/2), with
# the exponent of at least b. You need at least a powers of (1/2) for the
# trivial solution of a*(1/2)^b, and you cannot write any of the fractions
# in that solution as a sum of smaller fractions if a = n.
def B(n, a, b):
    if a > n:
        return 0

    if a == n:
        return 1

    if (n, a, b) not in cache:
# We need more fractions - use 1/(2^b) from 0 to (a-1) times, and fill
# the rest with the recursive call of this function

        s = 0
        for i in range(a):
            s += B(n - i, # we used i fractions
                   (a - i) * 2, # use a higher power of (1/2)
                   b + 1)
        cache[(n, a, b)] = s

    return cache[(n, a, b)]

def A(n):
    return B(n, 1, 0)

for n in range(1, 2000):
    print(n, A(n))

Memoization in Erlang from this SO answer

\$\endgroup\$
  • 1
    \$\begingroup\$ +1 from me. I really don't understand your ability to port stuff that easily to new languages. \$\endgroup\$ – Mr. Xcoder Nov 30 '17 at 18:57
3
\$\begingroup\$

268. Pyke, 99 bytes, A000338

9 2/Q2+X*15 2/Q2+*-BQ1>*Q0q5*Q1q18*++                                                              

Try it here!

Next sequence. (quite tendious, yet doable I think)

\$\endgroup\$
  • 1
    \$\begingroup\$ The next sequence is definitely doable. It looks more tedious than hard to me. \$\endgroup\$ – KSmarts Nov 30 '17 at 19:38

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.