58
\$\begingroup\$

In this challenge, the goal is to recreate the On-Line Encyclopedia of Integer Sequences one sequence at a time. Similar to the Evolution of Hello World, each answer depends on a previous answer.

Over time, this challenge will create a "family tree" of the OEIS sequences. It is simple to add on to this tree.

  1. Find a previous answer, which can be at any depth N of the tree.
  2. Determine the first N numbers generated by that answer's sequence.
  3. Find a sequence in OEIS which starts with those same numbers and which hasn't been used before.
  4. Write a program to generate this new sequence you just found.
  5. Submit your answer as depth N+1

Since the level of your answer influences scoring, you should always add your answer onto the tree at the deepest level possible. If you cannot fit your answer anywhere on the tree, you can start a new branch of the tree and put your answer as depth 1.

Answer Requirements

There are a few ways to output a sequence.

The first option is to write a program or function that inputs a number (from STDIN or as an argument) and returns the Nth number in your chosen sequence. You can assume that the sequence will be defined for N and that N and S_N are "reasonably sized" (so it won't cause overflows). You can also use any reasonable indexing, such as 0 indexing, 1 indexing, or the indexing listed under "offset" on the sequence's OEIS page, that doesn't matter. The term produced by the first index must match the first term of the OEIS entry.

The second option is to write a program or function that inputs a number and returns the first N terms of the sequence. The first terms of the output must be the first terms of the OEIS entry (you can't leave off the first few terms). Consecutive terms must be delimited by arbitrary strings of non-digit characters, so 0,1 1.2/3,5;8,11 works but 011235811 does not count.

The third option is to create a program that outputs a continuous stream of numbers. Similarly to the second option, there must be delimiters between consecutive terms.

Your answer should contain a header like this to aid Stack Snippet parsing:

 # [language], [number] bytes, depth [number], A[new sequence] from A[old sequence] 

Your answer should contain the code to generate the sequence, along with the first few terms that any descendants will need to contain. These few terms should be preceded by the exact word terms: so that the controller can use them as part of the tree diagram. It is also recommended to write a description of the sequence you chose.

If your post is a depth 1 answer and thus has no ancestor, you should simply omit the from A[number] in your header.

Here is an example answer:

# Perl, 26 bytes, depth 3, A026305 from A084912

    various code here
    and here

The next answer should match the following terms:

    1, 4, 20

This sequence is .... and does ....

Chaining Requirements

In order to make this challenge more fair, there are restrictions on which answers you can chain yours to. These rules are mostly to prevent a single person from creating a whole branch of the tree by themselves or owning a lot of "root" nodes.

  • You cannot chain to yourself.
  • You cannot directly chain two of your answers to the same ancestor.
  • You cannot make more than one "Level 1" answer.

Also, if the ancestor was of depth N, your post must have depth N+1, even if more than the required number of terms agree.

Scoring

Your score as a user is the sum of the scores of all of your answers. The score of a single answer is determined by the following formula:

Answer Score = Sqrt(Depth) * 1024 / (Length + 256)

This scoring system should encourage users to submit a large number of deeper answers. Shorter answers are preferred over longer answers, but depth has a much larger influence.

Below is a stack snippet that generates a leaderboard as well as a tree diagram of all of the answers. I would like to thank Martin Büttner and d3noob as the sources for a lot of this code. You should click "Full screen" to see the complete results.

function answersUrl(t){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+t+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(t){answers.push.apply(answers,t.items),t.has_more?getAnswers():process()}})}function shouldHaveHeading(t){var e=!1,r=t.body_markdown.split("\n");try{e|=/^#/.test(t.body_markdown),e|=["-","="].indexOf(r[1][0])>-1,e&=LANGUAGE_REG.test(t.body_markdown)}catch(a){}return e}function shouldHaveScore(t){var e=!1;try{e|=SIZE_REG.test(t.body_markdown.split("\n")[0])}catch(r){}return e}function getAuthorName(t){return t.owner.display_name}function decodeEntities(t){return $("<textarea>").html(t).text()}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.reverse();var t={},e=[],r=1,a=null,n=1,s=[];answers.forEach(function(t){var r=t.body_markdown.split("\n")[0],a=getAuthorName(t),n=r.match(SEQUENCE_REG)[0];n=n.trim();var o="from A000000";PARENT_REG.test(r)&&(o=r.match(PARENT_REG)[0]),o=o.substring(5).trim(),"A000000"==o&&(o="OEIS");var i="";SEQDATA_REG.test(t.body_markdown)&&(i=t.body_markdown.match(SEQDATA_REG)[1]);for(var u=!0,c=0;c<e.length;++c)u=u&&!(e[c]===n);for(var l=!0,c=0;c<e.length;++c)l=!(!l||e[c]===n||e[c]===n+a||e[c]===o+a);e.push(n),e.push(n+a),e.push(o+a),u&&data.push({name:n,parent:o,term:i+" : ",author:decodeEntities(a),URL:t.share_link}),l&&s.push(t)}),answers.sort(function(t,e){var r=t.body_markdown.split("\n")[0].match(SEQUENCE_REG),a=e.body_markdown.split("\n")[0].match(SEQUENCE_REG);return a>r?-1:r>a?1:void 0}),answers.forEach(function(e){var o=e.body_markdown.split("\n")[0],i=(o.match(NUMBER_REG)[0],(o.match(SIZE_REG)||[0])[0]),u=parseInt((o.match(DEPTH_REG)||[0])[0]).toString(),c=o.match(SEQUENCE_REG)[0],l="from A000000";PARENT_REG.test(o)&&(l=o.match(PARENT_REG)[0]),l=l.substring(5);var d=o.match(LANGUAGE_REG)[1];d.indexOf("]")>0&&(d=d.substring(1,d.indexOf("]")));for(var p=getAuthorName(e),E=!1,h=0;h<s.length;++h)E=E||s[h]===e;if(E){var f=jQuery("#answer-template").html();i!=a&&(n=r),a=i,++r;var m=1024*Math.pow(parseInt(u),.5)/(parseInt(i)+256);f=f.replace("{{SEQUENCE}}",c).replace("{{SEQUENCE}}",c).replace("{{NAME}}",p).replace("{{LANGUAGE}}",d).replace("{{SIZE}}",i).replace("{{DEPTH}}",u).replace("{{LINK}}",e.share_link),f=jQuery(f),jQuery("#answers").append(f),t[p]=t[p]||{lang:d,user:p,size:"0",numanswers:"0",link:e.share_link},t[p].size=(parseFloat(t[p].size)+m).toString(),t[p].numanswers=(parseInt(t[p].numanswers)+1).toString()}});var o=[];for(var i in t)t.hasOwnProperty(i)&&o.push(t[i]);o.sort(function(t,e){return parseFloat(t.size)>parseFloat(e.size)?-1:parseFloat(t.size)<parseFloat(e.size)?1:0});for(var u=0;u<o.length;++u){var c=jQuery("#language-template").html(),i=o[u];c=c.replace("{{RANK}}",u+1+".").replace("{{NAME}}",i.user).replace("{{NUMANSWERS}}",i.numanswers).replace("{{SIZE}}",i.size),c=jQuery(c),jQuery("#languages").append(c)}createTree()}function createTree(){function t(){var t=i.nodes(root).reverse(),e=i.links(t);t.forEach(function(t){t.y=180*t.depth});var r=c.selectAll("g.node").data(t,function(t){return t.id||(t.id=++o)}),a=r.enter().append("g").attr("class","node").attr("transform",function(t){return"translate("+t.y+","+t.x+")"});a.append("a").attr("xlink:href",function(t){return t.URL}).append("circle").attr("r",10).style("fill","#fff"),a.append("text").attr("x",function(){return 0}).attr("y",function(){return 20}).attr("dy",".35em").attr("text-anchor",function(){return"middle"}).text(function(t){return t.term+t.name}).style("fill-opacity",1),a.append("text").attr("x",function(){return 0}).attr("y",function(){return 35}).attr("dy",".35em").attr("text-anchor",function(){return"middle"}).text(function(t){return t.author}).style("fill-opacity",1);var n=c.selectAll("path.link").data(e,function(t){return t.target.id});n.enter().insert("path","g").attr("class","link").attr("d",u)}var e=data.reduce(function(t,e){return t[e.name]=e,t},{}),r=[];data.forEach(function(t){var a=e[t.parent];a?(a.children||(a.children=[])).push(t):r.push(t)});var a={top:20,right:120,bottom:20,left:120},n=3203-a.right-a.left,s=4003-a.top-a.bottom,o=0,i=d3.layout.tree().size([s,n]),u=d3.svg.diagonal().projection(function(t){return[t.y,t.x]}),c=d3.select("body").append("svg").attr("width",n+a.right+a.left).attr("height",s+a.top+a.bottom).append("g").attr("transform","translate("+a.left+","+a.top+")");root=r[0],t(root)}var QUESTION_ID=49223,ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",data=[{name:"OEIS",parent:"null",term:"",author:"",URL:"https://oeis.org/"}],answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*,)/,DEPTH_REG=/\d+, A/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/,SEQUENCE_REG=/A\d+/,PARENT_REG=/from\s*A\d+/,SEQDATA_REG=/terms:\s*(?:(?:-)?\d+,\s*)*((?:-)?\d+)/;
body{text-align: left !important}#answer-list{padding: 10px; width: 550px; float: left;}#language-list{padding: 10px; width: 290px; float: left;}table thead{font-weight: bold;}table td{padding: 5px;}.node circle{fill: #fff; stroke: steelblue; stroke-width: 3px;}.node text{font: 12px sans-serif;}.link{fill: none; stroke: #ccc; stroke-width: 2px;}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script src="http://d3js.org/d3.v3.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answer-list"> <h2>Sequence List</h2> <table class="answer-list"> <thead> <tr> <td>Sequence</td><td>Author</td><td>Language</td><td>Size</td><td>Depth</td></tr></thead> <tbody id="answers"></tbody> </table></div><div id="language-list"> <h2>Leaderboard</h2> <table class="language-list"> <thead> <tr> <td>Rank</td><td>User</td><td>Answers</td><td>Score</td></tr></thead> <tbody id="languages"></tbody> </table></div><table style="display: none"> <tbody id="answer-template"> <tr> <td><a href="https://oeis.org/{{SEQUENCE}}">{{SEQUENCE}}</a></td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td>{{DEPTH}}</td><td><a href="{{LINK}}">Link</a> </td></tr></tbody></table><table style="display: none"> <tbody id="language-template"> <tr> <td>{{RANK}}</td><td>{{NAME}}</td><td>{{NUMANSWERS}}</td><td>{{SIZE}}</td></tr></tbody></table>

\$\endgroup\$
14
  • 6
    \$\begingroup\$ You know, I think this is might just be the single coolest codegolf.sx question I've ever seen asked. It's not just cool, but actually useful as an archive. \$\endgroup\$ Apr 26, 2015 at 19:08
  • 3
    \$\begingroup\$ Given the OEIS is online, takes N terms of a sequence as a search term, and contains mathematica or maple code for many of the sequences, it would be possible to write a meta-entry which searched for the best scoring entry for which code exists in OEIS which is a descendent of any given entry here and posted it. \$\endgroup\$
    – abligh
    Apr 26, 2015 at 19:10
  • 2
    \$\begingroup\$ Can I recommend some way of marking on the graph the snippet generates that a node is terminal, ie there are no unused sequences of a greater depth available on the OEIS? \$\endgroup\$
    – Claudiu
    Apr 27, 2015 at 5:52
  • 1
    \$\begingroup\$ I think the only way to keep this challenge going would be to provide something where you give your username, and it lists the OEIS problems you could do, in order from highest depth to lowest. Otherwise it takes too long to find the next sequence to post. \$\endgroup\$
    – Claudiu
    May 4, 2015 at 22:38
  • 1
    \$\begingroup\$ The SVG is slightly too narrow. \$\endgroup\$ Apr 8, 2016 at 1:17

150 Answers 150

1
\$\begingroup\$

Mathematica, 15 bytes, depth 5, A018001 from A014137

Round[9^(#/3)]&

These are the powers of the cube root of 9 rounded to the nearest integer. The next answer should start with the terms:

1, 2, 4, 9, 19
\$\endgroup\$
0
1
\$\begingroup\$

J, 27 bytes, depth 4, A014137 from A000079

[:+/\[:(([:!2*])%!*[:!>:)i.

Interesting idea! These are the partial sums of the Catalan numbers:

   f=.[:+/\[:(([:!2*])%!*[:!>:)i.
   f 4
1 2 4 9

The next answer should start with the terms:

1, 2, 4, 9
\$\endgroup\$
0
1
\$\begingroup\$

Mathematica, 16 bytes, depth 3, A065134 from A000030

#~Mod~PrimePi@#&

The remainder of n over the number of primes <= n. The next answer should start with the terms:

0, 1, 0
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 46 bytes, depth 4, A001590 from A000035

Switch[#,0|2,0,1,1,_,#0[#-1]+#0[#-2]+#0[#-3]]&

"Tribonacci" numbers. The next answer should start with the terms:

0, 1, 0, 1
\$\endgroup\$
1
  • 6
    \$\begingroup\$ You know, you're on the best way to winning this challenge, but as it stands I don't think any of these answers are particularly interesting in either choice of sequence, programming language or solution. No offence, but maybe you'd want to spend some more time on answers that are also upvote-worthy rather than just mindlessly churning out answers to secure your top spot on the leaderboard? \$\endgroup\$ Apr 26, 2015 at 20:33
1
\$\begingroup\$

J, 13 bytes, depth 6, A018099 from A018001

Powers of the fourth root of 19 rounded down

[:<.(19^%4)^]

(OP: I'm not clear if we should provide the full series with our functions up to term N or just term N for any input N)

   f=.[:<.(19^%4)^]
   f i. 6
1 2 4 9 19 39

The next answer should start with the terms:

1, 2, 4, 9, 19, 39
\$\endgroup\$
1
  • \$\begingroup\$ You can choose between outputting term N, all terms up to N, or an infinite stream of the numbers of the sequence (without taking any input). That's the first half of the "Answer Requirements" section. \$\endgroup\$ Apr 26, 2015 at 20:24
1
\$\begingroup\$

J, 3 bytes, depth 3, A002378 from A005843

*>:

The next answer should start with the terms:

0, 2, 6
\$\endgroup\$
1
\$\begingroup\$

CJam, 4 bytes, depth 3, A000142 from A001333

rim!

The next answer should start with the terms:

1, 1, 2

Factorial.

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

CJam, 8 bytes, depth 6, A017980 from A070939

2rd3/#mo

The next answer should start with the terms:

1, 1, 2, 2, 3, 3

2^(n/3) rounded.

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

PARI/GP, 20 bytes, depth 7, A000006 from A017980

n->sqrtint(prime(n))

The integer part of the square root of the n-th prime.

The next answer should match the following terms:

1, 1, 2, 2, 3, 3, 4
\$\endgroup\$
1
\$\begingroup\$

Pyth, 16 bytes, depth 7, A056186 from A018099

thf>smc1^hd.9TQ0

Takes input via STDIN and outputs the Nth number.

Explanation

t                   decrement 1 from
 h                   the first item of
  f            0      filter integers T by
   >          Q        N is less than
    s                   sum of
     m       T           map d over 0..T-1
      c1^hd.9             1 / d^(9/10)

The next answer should start with the terms:

1, 2, 4, 9, 19, 39, 77
\$\endgroup\$
1
  • \$\begingroup\$ +1 for the explanation, which also has a depth of 7 ;) \$\endgroup\$
    – Ypnypn
    Apr 27, 2015 at 16:03
1
\$\begingroup\$

CJam, 17 bytes, depth 5, A136859 from A000292

qi_1&4\#10@2/(#*i

The next answer should match the following terms:

0, 1, 4, 10, 40

Integers n such that n and the square of n use only the digits 0, 1, 4 and 6, indexed from 1.

The final i is needed to avoid outputting 0.4 for input 1.

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

GolfScript, 11 bytes, depth 8, A103181 from A037888

{49&}%.1`?>

The next answer should match the following terms:

0, 1, 0, 1, 0, 1, 0, 1

"Replace all even digits by 0 and all odd digits by 1." Then the .1`?> removes leading zeroes.

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

PARI/GP, 25 bytes, depth 3, A027641 from A033999

n->numerator(bernfrac(n))

The next answer should start with the terms:

1, -1, 1

Numerator of Bernoulli number Bn.

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

CJam, 5 bytes, depth 3, A005408 from A000244

ri2*)

The odd numbers. The next answer should start with the terms:

1, 3, 5
\$\endgroup\$
1
\$\begingroup\$

Pyth, 18 bytes, depth 10, A083889 from A083912

lf&!%QTq\2eS`TtUhQ

The next sequence should match the following terms:

0, 1, 0, 1, 0, 1, 0, 1, 0, 1

Number of divisors of n with largest digit = 2 (base 10)

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

Mathematica, 92 bytes, depth 11, A116372 from A083889

Length@Select[IntegerPartitions@#,And@@(NestWhile[Plus@@IntegerDigits@#&,#,#<9&]==2&)/@#&]&

The number of partitions of n composed of numbers with a digital root of 2. The next answer should start with the terms:

0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1
\$\endgroup\$
1
\$\begingroup\$

CJam, 19 bytes, depth 12, A113217 from A116372

0p{"10"4*" "*p1p1}h

The next answer should start with the terms:

0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0

This is the parity of the decimal digital root of n. The sequence is periodic so I took the shortcut way of producing it. Output looks like:

0
"1 0 1 0 1 0 1 0"
1
"1 0 1 0 1 0 1 0"
1

etc... which from the rules I understand is ok.

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

Java, 41 bytes, depth 6, A028391 from A004523

int f(int n){return n-(int)Math.sqrt(n);}

This sequence is n minus the square root of n rounded to the lower integer for all n >= 0. This is a zero-index function. The next answer should start with the following terms:

0, 0, 1, 2, 2, 3
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 13 bytes, depth 4, A110654 from A000045

Ceiling[#/2]&

The OP said that it could be 0- or 1-indexed. The next answer should start with the terms:

0, 1, 1, 2
\$\endgroup\$
0
1
\$\begingroup\$

R, 34 bytes, depth 12, A125122 from A216188

n=scan();diff(nchar(3^(0:n+1)))[n]

The following sequence should start with the terms:

0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1

It is the sequence of first differences between the number of digits of 3n.
0:n+1 is equivalent to 1:(n+1) because : has precedence over +. The rest is relatively self-explanatory.

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

Mathematica, 22 bytes, depth 6, A090091 from A000110

FiniteGroupCount[3^#]&

The next answer should match the following terms:

1, 1, 2, 5, 15, 67

Number of groups of order 3^n.

I think this is the first answer with keyword "hard" on its OEIS page. It's not easy to calculate the number of finite groups of a given order. In fact, Mathematica can only calculate the first eight terms in this sequence.

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

Pyth, 12 bytes, depth 2, A001358 from A000211

#IqlPZ2Z)~Z1

The next answer should match the following terms:

4, 6

This is the sequence of semiprimes, i.e. product of two (not necessarily distinct) prime factors.

                     Z = 0
#                    while True:
 IqlPZ2                if len(prime_factorisation(Z)) == 2:
       Z)                print(Z)
 ~Z1                   Z += 1

Note that this prints an infinite stream of numbers, so it's best to try this locally.

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

R, 59 bytes, depth 3, A058199 from A001358

which(diff(rowSums(!outer(1:1e4,1:1e4,`%%`)))>=scan())[1]+1

The following sequence should start with the terms:

4, 6, 12

It is the sequence of integers whose number of divisors is larger than the number of divisors of the next integer by at least n.
The outer(1:1e4,1:1e4,`%%`) construct is such that the resulting matrix contains for i in 1 to 1e4 and j in 1 to 1e4 the results of i%%j. The sum of all zeroes in each row i thus gives the number of divisor for i. I limited to 1e4 so that it could be computed this way without overflow and fairly quickly and still work for all the values given on the A058199 page.

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

Java, 27 bytes, depth 8, A057359 from A049472

int f(int n){return 5*n/7;}

This sequence is 5 times n divided by 7, rounded to the lower integer. This is a zero-indexed function. The next answer should start with the following terms:

0, 0, 1, 2, 2, 3, 4, 5
\$\endgroup\$
1
\$\begingroup\$

CJam, 21 bytes, depth 11, A216188 from A083889

ri_2/),f{_`$@@-`$=}:+

The next answer should start with the following terms:

0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0

This is a cute one. They define an "anagrammatic pair of integers" as two integers which have the same number of each of the digits, e.g. 123 is anagrammatic to 132 and 321. A(n) is the number of unordered anagrammatic pairs that add up to n. Takes a bit to get more interesting. It's easily checked by sorted(repr(i))==sorted(repr(n-i)) in Python or

`$\`$=

in CJam. Got it down from 76 bytes in Python to 21 bytes in CJam. CJam version takes n as input.

\$\endgroup\$
0
1
\$\begingroup\$

CJam, 26 bytes, depth 10, A096972 from A083912

ri_,(;f{_`{i48-}%0-:*+=}:+

The next answer should start with the terms:

0, 1, 0, 1, 0, 1, 0, 1, 0, 1

This is a cute one. You have a hash function, h(i) = i + product of non-zero digits of i. The nth number is the number of inputs into h which result in n.

Python seemed especially ill-suited for this one: having to do lambda x,y:x*y instead of just x, and a very lengthy filter(None,map(int,``k``)) to get the non-zero digits as ints. I was right - changing the answer to CJam got it down to 26 bytes. I was a little sad I had to do '{i48-}% to convert a number to a list of its digits as integers, instead of just ':i.

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

Python, 241 bytes, depth 13, A249699 from A125122

from fractions import*
F=lambda n:n<2and 1or n*F(n-1)
R=range
def B(n):
 A={}
 for m in R(n):
  A[m]=Fraction(1,m+1)
  for j in R(m,0,-1):A[j-1]=j*(A[j-1]-A[j])
 return A[0]/((n-1)*F(n))
print 0,1,0
n=3
while n:print abs(B(n).numerator);n+=1

The next sequence should start with the terms:

0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0

Sadly this isn't on depth 14 because the next number in the sequence is 691! It quickly grows wild from there:

0
1
0
3617
0
43867
0
174611
0
77683
0
236364091

I could have gotten more points on a lower depth with fewer bytes, but this one was very weird and I wanted to try it out. The description is:

Numerators of coefficients in series expansion of Cl_2(x)+x*log(x), where Cl_2 is the Clausen function of order 2.

But I used the formula:

Numerators of BernoulliB(n - 1)/((n - 1)*n!), except the first 3 terms.

It actually ended up being the absolute value of the numerators.

I used the Akiyama–Tanigawa algorithm from the linked Wikipedia page to generate the Bernoulli numbers.

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

CJam, 30 bytes, depth 10, A226190 from A026233

ri_ml\,(;f{),(;{1.\/}%:+>!}1#)

The next sequence should start with the terms:

1, 1, 2, 2, 3, 3, 4, 4, 5, 6

A(n) is the least positive integer k such that 1 + 1/2 + ... + 1/k >= log(n). My answer uses the fact that n >= k. This is because:

Eq

So, k will never have to be greater than n.

I think this also sheds light on what the significance of this sequence is: it's a relation between the discrete sum of 1/m and the integral of 1/m.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think you can prove it by looking at the graph y=1/x, specifically the integral of 1/x from 1 to n (which is log(n)). Then look at the rectangles of width 1, height 1/k at each k from 1 to n, which will always go above the graph. \$\endgroup\$
    – Sp3000
    Apr 28, 2015 at 18:42
1
\$\begingroup\$

CJam, 3 bytes, depth 2, A000007 from A002522

ri!

The next answer should start with the terms:

1, 0

The sequence consists of 1 followed by only 0's.

There are a lot of interpretations (see the website's page), such as the decimal expansion of 1.

\$\endgroup\$
4
  • \$\begingroup\$ This gives 0 -> 0, 1 -> 1, 2 -> 0 ..., shouldn't it be 0 -> 1 and the rest 0? \$\endgroup\$
    – Claudiu
    Apr 28, 2015 at 22:56
  • \$\begingroup\$ @Claudiu The page says that a(1) = 1, a(n) = 0 for n > 1 \$\endgroup\$
    – Ypnypn
    Apr 29, 2015 at 0:22
  • \$\begingroup\$ I think that's "changing the offset to 1". But if you don't then you get this table (linked from the page): oeis.org/A000007/b000007.txt \$\endgroup\$
    – Claudiu
    Apr 29, 2015 at 1:50
  • 1
    \$\begingroup\$ @Claudiu Well in that case, I'll change the answer (and save a byte :) \$\endgroup\$
    – Ypnypn
    Apr 29, 2015 at 2:53
1
\$\begingroup\$

CJam, 61 bytes, depth 6, A182094 from A129953

{[_{_),(;{1$1$-P{\_@+@@}/;}/;}{;Q}?]:$_&}:P;riP{_,\0+:e>*}%:+

The next sequence must start with the following terms:

0, 1, 4, 10, 24, 47

This is the sum of the area of the "bounding boxes" for all integer partitions for n. For example, the partitions of 4 are:

[1,1,1,1] = 4 * 1
[1,1,2]   = 3 * 2
[2,2]     = 2 * 2
[1,3]     = 2 * 3
[4]       = 1 * 4

Eventually I figured out by "bounding box", the author meant the length of the list times the max of the list.

I'm quite proud of this Python -> CJam conversion, mostly because it works at all. It's my first fairly intricate recursive function implementation, either in CJam or Golfscript. These are the only languages where I actually have to think in terms of invariants, namely, what I expect the stack to look like at the start of each loop and function call.

Basically I define a recursive function P(N) which returns a list of all the unique partitions of N. I then sum the length times the max of each partition.

I saved 7 bytes by not appending to an array, instead setting an array marker and collecting the intermediate results all together. Here's the old version along with ungolfed explanation:

{_!{;[[]]}{_),(;[]\{2$1$-P{\_a@+a@+\}/;}/\;}?:$_&}:P;riP{_,\0+:e>*}%:+

Here is the ungolfed version with an explanation:

                     # pseudocode             |  stack view
                     # -----------------------+------------------------
{                    # def P(N):              |  N                   (at func start)
  _!                 #  if N==0:              |    N
  {;[[]]}            #   X = [[]]             |    X                 (return value)
  {                  #  else:                 |  N
    _),(;            #   G = range(1, N+1)    |    N (1..N)
    []\              #   X = []               |    N X (1..N)        (X is return value)
    {                #   for i in G:          |      N X i           (at loop start)
     2$1$-P          #    R = P(N-i)          |      N X i P(N-i)
     {               #    for r in R:         |        N X i r       (at loop start)
       \_a@+a        #     p = [[i]+r]        |        N X i [[i]+r]
       @+\           #     X += p             |        N X i         (X updated)
     }/;             #    endfor              |      N X
    }/\;             #   endfor               |    X
  }?                 #  endif                 |    X
  :$                 #  map(sort, X)          |    X
  _&                 #  X = X & X             |    X                 (remove duplicates)
}:P;                 # enddef                 |
                     #
riP                  # Y = P(input()) 
{                    # Y = [          
 _,\0+:e>*           #   len(r)*max(r)
}%                   #   for r in Y]  
:+                   # print sum(Y)   

Some questions: before I had ri<define P>;P. Is there any way to execute a block in CJam without having to pop it and push it back? I could do 1* but that's the same number of characters as ;P.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Bounding box makes more sense if you represent the partitions as Ferrers diagrams \$\endgroup\$
    – Sp3000
    Apr 27, 2015 at 0:59

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.