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

5
\$\begingroup\$

36. J, 124 bytes, A000067

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

Try it online!

Next sequence

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

37. 05AB1E, 6 bytes, A000124

The courtesy of Leaky Nun.

D>*2÷>

Try it online!

Next Sequence

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

38. Actually, 4 bytes, A000006

P√LA

Try it online!

Next sequence

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

41. PHP, 503 bytes, A003416

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

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

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

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

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

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

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

Try it online!

Next sequence

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

42. Cheddar, 28 bytes, A000503

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

Try it online!

Next sequence

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

44. Maxima, 94 bytes, A000651

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

Try it online!

Next sequence

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

59. Brachylog, 59 bytes, A000011

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

Try it online!

Next sequence

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

72. SML, 252 bytes, A000401

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

Online demo

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

Next sequence

Dissection

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

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

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

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

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

101. Fortress, 335 bytes, A000020

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

Next Sequence

Direct download of Fortress

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

\$\endgroup\$
  • \$\begingroup\$ Link to the language? \$\endgroup\$ – pppery Aug 11 '17 at 22:18
  • \$\begingroup\$ Dead. Very dead. There it is. \$\endgroup\$ – Zacharý Aug 11 '17 at 22:22
5
\$\begingroup\$

115. shortC, 273 bytes, A001560

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

Next sequence and Try it online!

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

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

149. dash, 1993 bytes, A000173

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

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

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

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

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

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

    j=$(( j + 1 ))
done

Online demo

Next sequence

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

231. Shakespeare Programming Language, 938 bytes, A000086

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

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

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

Try it online!

Next sequence!

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

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

244. UCBLogo, 1524 bytes, A000112

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

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

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

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

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

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

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

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

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

Next sequence.

There are 7 spaces in the last line.

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

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

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

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


Explanation:

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

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

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

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

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

254. Enlist, 98 bytes, A001516

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

Try it online!

haha enlist can do a thing :D

Next Sequence

Explanation

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

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

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

Try it online!

Next sequence

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

277. 2sable, 104 bytes, A000188

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

Try it online!

Next Sequence

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

Explanation

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

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

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

280. Axiom, 947 bytes, A002852

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

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

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

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

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

next sequence

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

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

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

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

43. Swift 4, 651 bytes, A000028

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

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

Try it online!

Next Sequence - A000651

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

297. Shakespeare Programming Language, 1460 bytes, A000161

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

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

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

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

       Scene III: Calculation.

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

       Scene IV: Add One.

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

       Scene V: Decision.

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

       Scene VI: Ending.

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

Try it online!

Next sequence: A001460 - just some trivial factorial things

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

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

Translated code (Python):

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

336. Pip, 159 bytes, A000620

b:[1]
c:[1]
Fi1,a+1{
 d:0
 e:2*(i%3%2)*c@(i/3)
 Fj,i{
  Fk,i-j{
   Ij=k{ d+:b@j * b@(i-j-k-1) }
   e+:c@j * c@k * c@(i-j-k-1)
  }
 }
 bAE:d
 cAE:e//3
}
c@v-b@v

Online demo

Next sequence


Basically this uses A000620 = A000625 - A000621 and the generating function relations for A000625 and A000621. I'm no chemist, but by the power of species theory I think I can reverse engineer the logic behind the g.f. relations, at least for one interpretation of the sequences. We're interested in monosubstituted alkanes, which correspond to graphs which are trees where every node has valence 4 (carbon atom) or 1 (either hydrogen atom or the substituted part, X).

In other words, modulo the trivial cases, we have a marked carbon atom which is attached to X:

   X
   |
a--C--b
   |
   d

The 3D geometry is relevant to the symmetries. The carbon atom is at the centre of a tetrahedron, and the other four elements are at the four vertices. Rotating around the axis CX doesn't change the molecule, so we'll need to avoid double-counting.

Note that if we consider the diagram from the perspective of e.g. a, the rest of the diagram (CXbd) can be considered as an X, and that's the heart of the recurrence logic.

If we ignore all restrictions and symmetry then by elementary species theory we have a generating function with recurrence \$F(x) = 1 + xF(x)^3\$. The \$1\$ corresponds to the special case that there's one molecule with 0 carbon atoms (X); the \$xF(x)^3\$ says that a molecule with \$n\$ carbon items can be identified with a molecule with one (\$x^1\$) identified carbon atom and then the remaining \$n-1\$ carbons are supplied by three smaller instances of the same type of object (a, b, d).

A000621 counts the non-stereoisomeric molecules. That means that they're symmetric: a = b, and all of a, b, d are non-stereoisomeric1. That gives generating function \$G(x) = 1 + xG(x)G(x^2)\$. The \$x\$ corresponds to the identified carbon atom C; the \$G(x)\$ corresponds to d; and the \$G(x^2)\$ corresponds to a and b being equal. (It uses \$x^2\$ to count each carbon atom in a twice).

A000625 counts all molecules under the rotational symmetry about the axis CX. If a, b, d are all different then there are three rotational positions, so we need to divide by 3; if two of them are the same then there are still three rotational positions; if all three are the same then there is only one rotational position, so we don't want to divide by three. We have g.f. \$H(x) = 1 + \frac13 xH(x)^3 + \frac23 xH(x^3)\$ where the final term is to bring the weight of the case where a=b=d back up from \$\frac13\$ to \$1\$.


1 Actually the choice that a = b is arbitrary, but works out nicely. We could alternatively consider the cases a = d and b = d as well, but then we have to divide by 3 to account for the symmetry.

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

16. Lua, 69 bytes, A000085

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

Try it online!

Next sequence

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

18. APL (Dyalog), 37 bytes, A000018

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

Try it online!

Next sequence

Warning: this is terribly inefficent

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

23. Ruby, 23 bytes, A000982

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

Try it online!

Next sequence

23rd entry uses 23 bytes!

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

27. C++, 584 bytes, A000274

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

Recursive solution with caching.

Next Sequence (shouldn't be a tricky one)

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

28. Positron, 9 bytes, A000584

->{$1**5}

Try it online!

Finally got Positron in here ^_^

Next sequence

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

32. C (gcc), 216 bytes, A000172

#include <stdio.h>

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

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

Try it online!

Next sequence

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

33. Octave, 73 bytes, A000216

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

Try it online!

Pretty basic recursive formula.

Next sequence

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

45. D, 190 bytes, A000094

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

Try it online!

Next sequence

\$\endgroup\$
  • \$\begingroup\$ Never thought I'd see a D answer, nice job making me use Fortress. Grr. \$\endgroup\$ – Zacharý Aug 11 '17 at 21:49
4
\$\begingroup\$

46. Jellyfish, 21 bytes, A000190

p
d^0
1|&*&*r
 E    i

Try it online!

Next sequence

\$\endgroup\$
  • \$\begingroup\$ Oh noes, it's "Number of positive integers <= 2^n of form x^2 + 12 y^2. " \$\endgroup\$ – Leaky Nun Jul 22 '17 at 13:18
  • \$\begingroup\$ This "Jellyfish" looks like a llama \$\endgroup\$ – HyperNeutrino Oct 31 '17 at 14:04
4
\$\begingroup\$

47. awk, 194 bytes, A000021

{
 n=0;
 for (i=1; i<=2**$1; i++) {
  stop = 0;
  for (x=0; x<=i && !stop; x++) {
   for (y=0; y<=i && !stop; y++) {
    if (x**2 + 12*y**2 == i){
     n++; stop=1;
    }
   }
  }
 }
 print n;
}

Try it online!

Next sequence

\$\endgroup\$

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.