110
\$\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
    Commented 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\$
    – Maya
    Commented 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\$ Commented 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
    Commented Dec 22, 2017 at 12:44
  • 6
    \$\begingroup\$ Chat room \$\endgroup\$
    – DELETE_ME
    Commented Dec 22, 2017 at 12:45

407 Answers 407

1
8 9
10
11 12
14
2
\$\begingroup\$

276. MATLAB, 188 bytes, A000113

n=input('')+1;
F=factor(n);
psi = @(x) x*prod(1+1./unique(F))-(x<2);
i=sum(F==2);
j=sum(F==3);
if i > 5
i = 3;
else
i = floor(i./2);
end
if j > 1
j = 1;
else
j = 0;
end
psi(n) ./ (2^i*3^j)

Try it online!

Next Sequence

As this is a carefully written polyglot with Octave, it will run on TIO.

Implements the formula with Dedekind's psi function listed in the notes.

Oddly, there's a dead link for transformation groups on this OEIS wiki page and I'm not entirely sure how to count transformation groups!

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

266. UCBLogo, 2572 bytes, A000636

; ------ helper function ------ (unrelated to the problem)

; minimum of two numbers
to min :x :y
    output ifelse :x<:y [:x] [:y]
end

; clone an array
to clone :arr
    localmake "ans (array (count :arr) (first :arr))
    localmake "offset -1+first :arr
    repeat count :arr [
        setitem (#+:offset) :ans (item (#+:offset) :arr)
    ]
    output :ans
end

; ------ coefficient list manipulators ------

; apply (map binary function)
to ap :func :x :y
    localmake "ans arz min count :x count :y
    for [i 0 [-1+count :ans]] [ 
        setitem :i :ans (invoke :func item :i :x item :i :y)
    ]
    output :ans
end

; zero-indexing zero array : f(x) = 0
to arz :n 
    localmake "ans (array :n 0)
    repeat :n [setitem #-1 :ans 0]
    output :ans
end

; polynomial multiplication
to convolve :x :y [:newsize (count :x)+(count :y)-1]
    localmake "ans arz :newsize
    for [i 0 [-1+count :x]] [
        for [j 0 [min -1+count :y :newsize-:i-1] 1] [
            setitem :i+:j :ans (item :i+:j :ans) + (item :i :x) * (item :j :y)
        ]
    ]
    output :ans
end

; given arr = coefficients of f(x), calculate factor * f(x^n)
to extend :arr :n [:factor 1]
    localmake "ans arz (-1+count :arr)*:n+1
    repeat count :arr [
        setitem (#-1)*:n :ans (:factor*item #-1 :arr)
    ]
    output :ans
end

; calculate :const + :factor * x * p(x)
to shift :p :factor :const [:size 1+count :p]
    localmake "ans (array :size 0)
    setitem 0 :ans :const    ; 1+...
    repeat :size-1 [
        setitem # :ans (item #-1 :p)*:factor
    ]
    output :ans

end

; calculate multiplication inverse (1/p(x))
to inverse :p [:n (count :p)]
    localmake "one arz :n
    setitem 0 :one 1

    localmake "p_1 clone :p
    setitem 0 :p_1 (-1+item 0 :p_1) ; p_1(x) = p(x) - 1

    localmake "q (array 1 0)
    setitem 0 :q (1/item 0 :p) ; q(x) = 1/p(0) (coefficient of x^0)

    repeat :n [
        make "q ap "difference :one (convolve :p_1 :q #)
    ]

    output :q
end

; ------ define functions ------

; calculate r(x) first n coefficients
to r :n
    localmake "ans {1}@0
    repeat :n [
        make "ans (shift (ap "sum ap "sum
            convolve convolve :ans :ans :ans ; r[x]^3
            convolve :ans (extend :ans 2 3)  ; 3*r[x]*r[x^2]
            (extend :ans 3 2)  ; 2 r[x^3]
        ) 1/6 1 #)
    ]
    output :ans
end

; calculate R(x) first n coefficients
to BigR :n
    localmake "rn r :n
    output (extend
        ap "sum
            convolve :rn :rn ; r[x]^2
            extend :rn 2     ; r[x^2]
    1 0.5)  ; /2
end

; main function
to main :n
    localmake "Rx bigR :n+1
    localmake "inv_1_xRx inverse shift :Rx -1 1 ; 1 - x*R[x]
    output item :n+1 (extend (ap "sum
        :inv_1_xRx
        convolve
            (shift :Rx 1 1)   ; 1 + x*R[x]
            (extend :inv_1_xRx 2) ; 1/(1 - x^2 * R[x^2])
    ) 1 0.5)
end

Try it online! (at Anarchy golf performance checker)

Paste the code there, and then append print main 10 at the end.

Although Logo has been used twice, UCBLogo only once and FMSLogo only once. In other word, programming languages that has multiple versions tend to have more advantage in this challenge. Next time it will probably be Elica.


Next sequence.

\$\endgroup\$
2
  • \$\begingroup\$ Probably the next answer is "using the recurrence formula in the Mathematica code". I don't like that, if anyone do that please also include formula proof. \$\endgroup\$
    – DELETE_ME
    Commented Nov 30, 2017 at 15:19
  • \$\begingroup\$ Sorry for "just using the formula"... but I promise I will add mathematical explanation. \$\endgroup\$
    – DELETE_ME
    Commented Nov 30, 2017 at 16:00
2
\$\begingroup\$

275. Whispers, 113 bytes, A001021

> Input
> 12
>> 2*1
>> Output 3
Rather than add a bunch of spaces,
I think it'd be better to actually have
words.

Try it online!

Next sequence

How it works

The parser automatically removes lines that don't match any of the valid regexes, meaning that the code that actually gets executes is

> Input
> 12
>> 2*1
>> Output 3

Which is executed non-linearly way (as most Whispers programs are), and runs as follows:

Output ((12) * (Input))

Where * is exponentiation (raising x to the power y)

\$\endgroup\$
5
  • \$\begingroup\$ What are the rules on using languages newer than the challenge? \$\endgroup\$
    – KSmarts
    Commented Dec 7, 2017 at 20:28
  • \$\begingroup\$ @KSmarts Just so long as it isn't specifically designed for this challenge (or violate any other standard loophole), it's the same as posting an answer with a newer language on any other question. \$\endgroup\$ Commented Dec 7, 2017 at 21:01
  • \$\begingroup\$ What is this sorcery? \$\endgroup\$
    – Maya
    Commented Dec 7, 2017 at 21:29
  • \$\begingroup\$ Does this still work if you change acually to actually and remove the duplicate !? \$\endgroup\$ Commented Dec 8, 2017 at 4:17
  • \$\begingroup\$ This language reminds me of LLVM IR... \$\endgroup\$
    – Maya
    Commented Dec 9, 2017 at 14:22
2
\$\begingroup\$

279. Fortran (GFortran), 2852 bytes, A005692

program beans

integer :: n, first_move, last_move, new_move1, new_move2, turn_count, win_accomplished, cycleq

integer, dimension(270,1000000) :: current_paths, next_paths
integer :: next_path_count, current_path_count, path_iter, move_iter, cycle_iter

read *,n
first_move = 2*n+1
turn_count = 0
win_accomplished = 0


current_paths(1,1)=first_move
current_path_count=1


do while(.true.)
  
  turn_count = turn_count + 1    !current path length

  if (first_move == 1) then
    turn_count = 1
    exit
  end if

  next_path_count = 1


  do path_iter=1,current_path_count
    
    cycleq = 0
    last_move = current_paths(turn_count,path_iter)
    !print *,'prince'
    !print *,last_move
    !print *,'prince'

  
    if (mod(last_move,2)==1)  then
      if (last_move>1) then
        if (mod(turn_count,2) == 0) then
          cycle
        end if
      end if
    end if

    if (last_move==1) then
      if (mod(turn_count,2) == 0) then
        win_accomplished = 1
      end if

    else if (mod(last_move,2)==0) then
      new_move1 = last_move/2

      do cycle_iter = 1,turn_count
        if (current_paths(cycle_iter,path_iter) == new_move1) then
          cycleq=1
        end if
      end do

      if (cycleq == 0) then
        do cycle_iter=1,turn_count
          next_paths(cycle_iter,next_path_count) = current_paths(cycle_iter,path_iter)
        end do 
        next_paths(turn_count+1,next_path_count) = new_move1
        next_path_count = next_path_count + 1
      end if

    else 
      new_move1 = 3*last_move + 1
      new_move2 = 3*last_move - 1

      cycleq=0
      do cycle_iter = 1,turn_count
        if (current_paths(cycle_iter,path_iter) == new_move1) then
          cycleq=1
        end if
      end do 

      if (cycleq == 0) then
        do cycle_iter=1,turn_count
          next_paths(cycle_iter,next_path_count) = current_paths(cycle_iter,path_iter)
        end do 
        next_paths(turn_count+1,next_path_count) = new_move1
        next_path_count = next_path_count + 1
      end if


      cycleq=0
      do cycle_iter = 1,turn_count
        if (current_paths(cycle_iter,path_iter) == new_move2) then
          cycleq=1
        end if
      end do 

      if (cycleq == 0) then
        do cycle_iter=1,turn_count
          next_paths(cycle_iter,next_path_count) = current_paths(cycle_iter,path_iter)
        end do
        next_paths(turn_count+1,next_path_count) = new_move2
        next_path_count = next_path_count + 1
      end if

    end if

  end do 

  if (win_accomplished==1) then
     exit
  end if


  do path_iter=1,next_path_count-1
    do move_iter=1,turn_count+1
      current_paths(move_iter,path_iter) = next_paths(move_iter,path_iter)
      next_paths(move_iter,path_iter) = 0
    end do
  end do
  
  current_path_count = next_path_count-1

end do


print *,turn_count-1

end program beans

Try it online!

Next Sequence

I originally wrote a similar program in Python. It properly compiled in Pyon but I wanted to see if I could write it in Fortran first and save Pyon/Python for harder sequences.

The program relies on the fact that if Jack moves to an odd number then the Giant gains control and will be able to use a never-lose strategy. It starts with a the Giant's fist move [n] then enumerates all the possible games until the first win is found which must be the shortest one since moves are added to each possible game pathway once per iteration of the main loop. If Jack loses in one particular game or if the Giant takes control then that particular game pathway is abandoned which helps save on memory and time.

The first term in the sequence doesn't make any sense to me since it isn't a win for Jack but I hard coded it in anyway.

The paper OEIS references helped me understand the sequence. They suggest an algorithm to us on a computer (they calculated the first 525 terms of the sequence by hand) which I didn't use because it seemed a little more difficult to implement but it would probably be faster and much less memory intensive.

Because of memory limitations, the program won't actually work on all the terms but is fine for terms up to at least 119 (n=109). Note that the two arrays declared at the top have 270x10^6 elements. This allows in the algorithm for 10^6 branches of possible game paths of length 270 moves. None of the first 1000 terms are bigger than 263 so this is still valid for the challenge.

The next sequence (terms in the continued fraction of Eulers constant) looks pretty hard, but maybe that's just because I don't know how to do it of the top of my head. I promise I didn't engineer my byte-count to pick this, it's just what I ended up with.

Edit: It seems calculating the terms doesn't seem too hard once you have the actual constant (which is irrational [edit: apparently this is actually not known]). Here are some resources:

\$\endgroup\$
10
  • \$\begingroup\$ 119 (n=109) Huh? \$\endgroup\$
    – DELETE_ME
    Commented Dec 15, 2017 at 6:06
  • \$\begingroup\$ NOTE There has already been a deleted answer that hardcodes. Don't do this again if you don't want downvotes. \$\endgroup\$
    – DELETE_ME
    Commented Dec 15, 2017 at 6:11
  • \$\begingroup\$ @user202729 Haha sorry to disappoint you. I know what a continued fraction is just didn’t know how to calculate it off the top of my head. I agree the next one isn’t that hard \$\endgroup\$
    – dylnan
    Commented Dec 15, 2017 at 13:14
  • 2
    \$\begingroup\$ @Giuseppe it kind of hardcodes the sequence to get a number from which you can compute the sequence. Don't you think that's a little pointless? \$\endgroup\$
    – Maya
    Commented Dec 15, 2017 at 21:22
  • 1
    \$\begingroup\$ numberworld.org/y-cruncher/internals/formulas.html \$\endgroup\$
    – politza
    Commented Dec 16, 2017 at 8:56
2
\$\begingroup\$

283. Ohm v2, 384 bytes, A000126

³4+ý³-2-                                                                                                                                                                                                                                                                                                                                                                                        

Try it online!

Next Sequence. (This one is trivial, the hexagonal numbers!)

If this were code golf, I could solve this in 6 bytes: 4+ýa‹‹.

This one was really just Fibonacci(N + 4) - N - 2.

\$\endgroup\$
2
  • \$\begingroup\$ Please let me do the next one in Hexagony! \$\endgroup\$
    – Maya
    Commented Dec 24, 2017 at 14:41
  • \$\begingroup\$ Wait, I still need to wait 45 minutes... I'll try anyway \$\endgroup\$
    – Maya
    Commented Dec 24, 2017 at 14:41
2
\$\begingroup\$

287. Scratch 2, 7437 Bytes, A001118

A001118

Try it online

Here is the text version of the full program.

Below is the portion of the program that represents the code blocks in the image. The full text is much longer, dealing with things irrelevant to this challenge.

        "scripts": [[275.8,
                75.2,
                [["procDef", "Power %n %n", ["Base", "exponent"], [1, 1], false],
                    ["setVar:to:", "presult", "1"],
                    ["doRepeat",
                        ["getParam", "exponent", "r"],
                        [["setVar:to:", "presult", ["*", ["readVariable", "presult"], ["getParam", "Base", "r"]]]]]]],
            [539.1,
                73.2,
                [["procDef", "Binomial %n %n", ["a", "b"], [1, 1], false],
                    ["call", "FactLoop %n", ["getParam", "a", "r"]],
                    ["setVar:to:", "bin", ["readVariable", "result"]],
                    ["call", "FactLoop %n", ["getParam", "b", "r"]],
                    ["setVar:to:", "bin", ["\/", ["readVariable", "bin"], ["readVariable", "result"]]],
                    ["call", "FactLoop %n", ["-", ["getParam", "a", "r"], ["getParam", "b", "r"]]],
                    ["setVar:to:", "bin", ["\/", ["readVariable", "bin"], ["readVariable", "result"]]]]],
            [286.7,
                244,
                [["procDef", "FactLoop %n", ["n"], [1], false],
                    ["setVar:to:", "count", ["getParam", "n", "r"]],
                    ["setVar:to:", "result", "1"],
                    ["doUntil",
                        ["<", ["readVariable", "count"], "2"],
                        [["setVar:to:", "result", ["*", ["readVariable", "result"], ["readVariable", "count"]]],
                            ["changeVar:by:", "count", -1]]]]],
            [44,
                71,
                [["whenGreenFlag"],
                    ["doAsk", ""],
                    ["setVar:to:", "nseq", ["answer"]],
                    ["setVar:to:", "sum", 0],
                    ["setVar:to:", "i", 0],
                    ["doRepeat",
                        5,
                        [["call", "Power %n %n", -1, ["readVariable", "i"]],
                            ["setVar:to:", "term", ["readVariable", "presult"]],
                            ["call", "Power %n %n", ["-", 5, ["readVariable", "i"]], ["readVariable", "nseq"]],
                            ["setVar:to:", "term", ["*", ["readVariable", "term"], ["readVariable", "presult"]]],
                            ["call", "Binomial %n %n", 5, ["readVariable", "i"]],
                            ["setVar:to:", "term", ["*", ["readVariable", "term"], ["readVariable", "bin"]]],
                            ["changeVar:by:", "sum", ["readVariable", "term"]],
                            ["changeVar:by:", "i", 1]]],
                    ["say:", ["readVariable", "sum"]]]]],

Next Sequence: Inverse Moebius transformation of triangular numbers

\$\endgroup\$
2
  • \$\begingroup\$ +1 for using Scratch and for giving us an easy sequence. Solved in Swift 4 :) \$\endgroup\$
    – Mr. Xcoder
    Commented Dec 25, 2017 at 20:01
  • \$\begingroup\$ Scratch is verbose. (depends on how is the number of bytes counted) \$\endgroup\$
    – DELETE_ME
    Commented Dec 26, 2017 at 14:02
2
\$\begingroup\$

290. Hy, 337 bytes, A000149

(import decimal)
(setv ctx (.getcontext decimal))
(setv ctx.prec 500)
(setv iterations 2800)

(defn factorial [n]
  (reduce *
    (range 1 (inc n))
    1))

(defn exp [n series-terms]
  (sum
    (list-comp
      (/ (decimal.Decimal (** n k)) (factorial k))
      (k (range series-terms)))))

(defn A000149 [n]
  (int (exp n iterations)))

Next sequence--here's a nice easy one so you can break out the obscure esolangs. ;^)

We implement the exponential function by taking partial sums of its MacLaurin series: e^n = Sum[k=0..inf] n^k/k!. For values far away from 0, the series converges more slowly, so we need to calculate a lot of terms to get an accurate result. Trial and error showed that 2800 terms was sufficient for n=1000. The decimal module provides arbitrary-precision arithmetic; 500 significant digits gets us up to n=1000 easily.

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

292. Gaia, 132 bytes, A000130

ọ0D¦1C1=
┅f↑¦Σ2÷                                                                                                                    

Try it online!

Next sequence.

The next one should not be too hard (there is a näive approach to generate all the integer partitions, and for each partition P check if P is of length 5 and that each element in P is a square :P). I have solved this in Pyth first, then got a much more efficient technique, which I then ported to Gaia.

How it works?

ọ0D¦1C1= | Helper function.

ọ        | Compute the incremental differences (deltas).
 0D¦     | For each, calculate the absolute difference to 0 (absolute value).
    1C   | Count the 1's.
      1= | Return 1 if the result is equal to 1, 0 otherwise.

┅f↑¦Σ2÷  | Main function. Let N be the input.

┅        | The integers in the range 1 ... N.
 f       | Compute the permutations.
  ↑¦     | For each permutation, apply the above helper function called monadically.
    Σ    | Sum.
     2÷  | Halve and implicitly display the result.
\$\endgroup\$
1
  • \$\begingroup\$ This one has useful and easy to calculate g.f., but note that (1)² and (-1)² are different ways. You can implement FFT if you like. \$\endgroup\$
    – DELETE_ME
    Commented Dec 31, 2017 at 13:51
2
\$\begingroup\$

298. dc, 1008 bytes, A001460

# Define a factorial macro f; expects the accumulator in register a and the loop number
# (> 0) on the stack
[
 d        # Duplicate the loop number
 la * sa  # Load accumulator, multiply by loop number, store back in accumulator
 1 -      # Decrement loop number
 d 0<f    # Duplicate; if greater than 0, call the macro again
] sf

# Define a wrapper macro F; expects the argument on the stack, and can handle 0
[
 1 sa   # Store 1 in the accumulator register
 d 0<f  # Duplicate argument; if greater than 0, call macro f
 s_     # This leaves a 0 on the stack; store in register _ to get rid of it
 la     # Load accumulator onto stack
] sF

# Main program
? sn         # Read input and store in register n
ln 5 * lF x  # Load n, multiply by 5, take the factorial
ln 2 * lF x  # Load n, multiply by 2, take the factorial
ln lF x 3 ^  # Load n, take the factorial, raise to the 3rd power
*            # Multiply the last two results
/            # Divide the first result by the product
p            # Print

Try it online!

Next sequence.

\$\endgroup\$
2
  • \$\begingroup\$ The next one seems to be doable in Unefunge... \$\endgroup\$
    – Maya
    Commented Jan 3, 2018 at 15:51
  • \$\begingroup\$ The next one is a lot easier if you have a built-ins for finding lowest common multiple and simplifying fractions. The series is the numerator of the simplified fraction Sum(LCM(1...n)/n) / LCM(1...n). \$\endgroup\$ Commented Jan 3, 2018 at 16:18
2
\$\begingroup\$

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

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

Try it online!

Next sequence!

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

Explanation

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

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

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

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

This should be enough to understand the whole program.

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

303. APL (Dyalog), 203 bytes, A000135

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

Try it online!

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

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

Next sequence

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to the site, and nice first post! \$\endgroup\$ Commented Jan 7, 2018 at 19:17
2
\$\begingroup\$

304. Clojure, 143 bytes, A000203

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

Try it online!

Next sequence

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

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

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

Try it online!

Next sequence

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

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

Try it online!

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

310. Pyth, 148 bytes, A000699

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

Try it here!

Next Sequence.

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

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

316. Pascal (FPC), 1808 bytes, A000147

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



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

Try it online!

Next sequence! Easy, just implement generating function.

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

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

from itertools import zip_longest

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

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

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

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

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

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

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

Try it online!

Next sequence!

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

320. Java 7, 308 bytes, A000292

class Main{
  public static void main(String[] args){
    System.out.println(new Main().BinomialCoefficient(new Long(args[0])+2, 3));
  }
  
  static long BinomialCoefficient(long n, long k){
    return n==k || k<1?
        1
      :
        BinomialCoefficient(n-1, k) + BinomialCoefficient(n-1, k-1);
  }
}

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

Try it online.

Next sequence

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

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

#include <math.h>

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

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

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

Next sequence

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

321. Racket, 249 bytes, A000308

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

323. Common Lisp, 238 bytes, A000150

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

Try it online!

Next Sequence

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

325. Perl 6, 385 bytes, A000559

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

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

say $result;

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

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

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

Try it online!

Next Sequence

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

324. Pyon, 559 bytes, A000238

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

Try it online!

Next sequence!

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

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

327. tinylisp, 439 bytes, A000205

(load library)

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

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

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

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

Try it online!

Next sequence!

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

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

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

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

328. MY-BASIC, 222 bytes, A000439

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

329. Yacas, 155 bytes, A000222

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

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

Next sequence

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

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

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

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

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

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

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

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

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

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

331. Coconut, 766 bytes, A001854

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

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

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

333. Swift 3, 219 bytes, A000852

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

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

Try it online!

Next sequence.

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

338. Triangularity, 287 bytes, A000154

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

Try it online!

Next Sequence

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

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

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

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

Try it online!

Next Sequence

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

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

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

Test code:

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

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

    mov rdi, rax
    call f

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

348. Rust, 607 bytes, A000824

use num_bigint::BigUint;
use std::io::*;
fn main()->Result<()>{
    let mut stdin = stdin();
    let mut s = String::new();
    stdin.read_to_string(&mut s)?;
    let n=s.parse().unwrap()+1;
    println!("{}", a(n));
    Ok(())
}
fn a(n:u32)->BigUint{
    let part_a = helper(3,3,n);
    let part_b = helper(2,3,n) * 3u32;
    let part_c = helper(1,1,n) << 1;
    (part_a + part_b +part_c)/6u32
}
fn helper(r:u32,s:u32,n:u32)->BigUint{
    let one:BigUint = 1u32.into();
    let part_a = &one << (r << n); 
    let part_b = ((&one << n) - &one) * (&one << (s * (1 << (n - 1))));
    (part_a + part_b) >> n
}

Try it on the Rust Playground!

Next Sequence

I used the num_bigint crate to get arbitrary precision integers. Since the rust playground doesn't support stdin I created a drop-in replacement method- simply change the number in-between the 2 quotation marks to change the input. The code can make it up to a(18), which has 473,473 digits, before it times out if you do a release build. The sequence is calculated based on the formula found on the OEIS (after adjusting to a 1-index and using bitshifts for the \$2^n\$s):

$$\text{Let } b_n(r,s) = \frac{2^{r\cdot2^n} + (2^n-1)\cdot2^{s\cdot2^{n-1}}}{2^n} \\ \text{Then, } a(n) = \frac{b_n(3,3) + 3b_n(2,3) + 2b_n(1,1)}{6}$$

\$\endgroup\$
1
8 9
10
11 12
14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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