-3
\$\begingroup\$

Notice: This question originally had people write comments with a shorter program, rather than new answers. This has been changed so that people with shorter programs can get reputation too. Hopefully this doesn't become unmanageable...

There have been a couple of OEIS-related questions recently, so here's another:

Pick a sequence from the Online Encyclopedia of Integer Sequences, and write a full program or function which computes the sequence in one of the following ways:

  • It prints every term in the sequence in order
  • It takes an index in the sequence as input, and returns/outputs the term at that index.

You will be trying to pick the sequence with the longest possible shortest possible program/function to compute that sequence (see the example below if that's confusing). You must include which sequence you are using in your answer.

Try to make your program/function as short as possible. If anyone can find a shorter program which computes the same sequence, they should add a another answer with their shorter program. If you do find a shorter program than someone else, you should refer to their answer in yours. For all answers, a Try it Online link would be nice. If someone else has written a shorter program than yours, it would be nice if you put a link to it in your answer.

Of course, none of the programs should access the internet or the OEIS in any way, and they should all theoretically work on arbitrarily large inputs (you can ignore things like the maximum size of an integer type).

The sequence with the longest shortest program in bytes is the winner.

For example,

Let's say I pick the sequence A000027, the positive integers, and I submit this answer:

Python, 49 bytes, A000027

x = "o"
while True:
    print len(x)
    x += "o"

Obviously this is not a very short program for computing that sequence, so someone else (let's call them foo) might come along and add this answer:

Haskell, 2 bytes, A000027:

id

(id is the identity function, so it will just return whatever you pass into it, and because the nth positive integer is just n, it will compute that sequence).

Then, the person who posted the Python solution should edit their answer:

Python, 49 bytes, A000027

Superseded by foo's answer (link).

x = "o"
while True:
    print len(x)
    x += "o"

As long as no one else finds a shorter program, this sequence would get a score of 2 (because id is two bytes), and the sequence with the highest score wins.


Current best sequence: A014715, 252 bytes

\$\endgroup\$
13
  • \$\begingroup\$ Isn't this trivially just something like A060843? \$\endgroup\$ Jul 11, 2019 at 11:59
  • 1
    \$\begingroup\$ The answer with the longest sequence is the winner. don't you mean that the answer with the longest answer in bytes is the winner? \$\endgroup\$ Jul 11, 2019 at 12:04
  • 1
    \$\begingroup\$ Should one update their answer with the current shortest program? \$\endgroup\$
    – TFeld
    Jul 11, 2019 at 12:50
  • 6
    \$\begingroup\$ Honestly, the more I think about this question, the more it becomes obvious that the optimal strategy is finding challenges that are based on OEIS sequences and copying the shortest answer. \$\endgroup\$
    – Stephen
    Jul 11, 2019 at 12:54
  • 5
    \$\begingroup\$ This looks like a cops-and-robbers done wrong because there's no incentive for the robbers. It might be worth taking it to the sandbox and enlisting mod help to lock it until it can be reworked. \$\endgroup\$ Jul 11, 2019 at 21:31

4 Answers 4

4
\$\begingroup\$

Wolfram Language (Mathematica), 270 252 bytes A014715

252 bytes, by Expired Data

RealDigits[NSolve[3x-6==Plus@@({6,-12,4,-7,7,-1,0,-5,2,4,12,-2,-7,-12,7,10,4,-3,-9,7,0,8,-14,3,-9,-2,3,10,2,6,-1,-10,3,-1,-7,7,-7,12,5,-8,-6,-10,8,8,7,3,-9,-1,-6,-6,2,3,10,2,-3,-5,-2,1,1,1,1,1,-1,-2,-2,1,2,1,0,-1}x^2~Range~71),x,#][[-1,-1,-1]]][[1,#]]&

Try it online!

I've never golfed in mathematica before, but the sequence seemed like an obvious contender. The code is more or less a copy of the example on the OEIS page.

The sequence is the decimal expansion of Conway's constant, which itself is the root of this polynomial:

\$x^{71}-x^{69}-2x^{68}-x^{67}+2x^{66}+2x^{65}+x^{64}-x^{63}-x^{62}-x^{61}-x^{60}-x^{59}+2x^{58}+5x^{57}+3x^{56}-2x^{55}-10x^{54}-3x^{53}-2x^{52}+6x^{51}+6x^{50}+x^{49}+9x^{48}-3x^{47}-7x^{46}-8x^{45}-8x^{44}+10x^{43}+6x^{42}+8x^{41}-5x^{40}-12x^{39}+7x^{38}-7x^{37}+7x^{36}+x^{35}-3x^{34}+10x^{33}+x^{32}-6x^{31}-2x^{30}-10x^{29}-3x^{28}+2x^{27}+9x^{26}-3x^{25}+14x^{24}-8x^{23}-7x^{21}+9x^{20}+3x^{19}-4x^{18}-10x^{17}-7x^{16}+12x^{15}+7x^{14}+2x^{13}-12x^{12}-4x^{11}-2x^{10}+5x^{9}+x^{7}-7x^{6}+7x^{5}-4x^{4}+12x^{3}-6x^{2}+3x-6\$

\$\endgroup\$
7
  • 3
    \$\begingroup\$ Probably important to mention that the code is copied straight from the OEIS page for the sequence \$\endgroup\$
    – Stephen
    Jul 11, 2019 at 14:34
  • 1
    \$\begingroup\$ 261 bytes \$\endgroup\$ Jul 11, 2019 at 15:37
  • \$\begingroup\$ And a few bytes more by jiggling the equation around \$\endgroup\$ Jul 11, 2019 at 15:44
  • \$\begingroup\$ @Stephen Well, I did reverse the polynomial to save a few bytes :P \$\endgroup\$
    – TFeld
    Jul 11, 2019 at 16:03
  • \$\begingroup\$ @ExpiredData I've edited it into the answer. \$\endgroup\$
    – TFeld
    Jul 11, 2019 at 16:05
2
\$\begingroup\$

Python 3, 3 bytes, A055642

Finally, a ridiculously short answer that isn't just A000027 or some other stupidly simple sequence.

len

This is a function. Number should be inputted as a string of its digits. Undefined behavior for non-integers and other strings.

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

cQuents, 1 byte, A000027

$

Try it online!

Just to have a baseline answer in case every other answer is cracked.

\$\endgroup\$
3
  • 6
    \$\begingroup\$ Jelly, 0 bytes: Try it online! (sorry). Arguments are added to the stack in Jelly, and the top thing on the stack is printed when the program finishes, so the program takes an index as input, and outputs the corresponding term (which is just the same number). \$\endgroup\$
    – pommicket
    Jul 11, 2019 at 12:32
  • \$\begingroup\$ @LeoTenenbaum ah, I remembered having the shortest answer to this and forgot that you had two different input styles \$\endgroup\$
    – Stephen
    Jul 11, 2019 at 12:52
  • \$\begingroup\$ The 0 bytes version also works in GolfScript. Try it online! \$\endgroup\$
    – jimmy23013
    Jul 11, 2019 at 13:12
0
\$\begingroup\$

Wolfram Language (Mathematica), 490,453 bytes A002205

FromDigits[ToCharacterCode[StringReplace["$H\.06,\.1dVngsIno\.12RT",":3:"->FromCharacterCode[13]]]-1,127]

Where \.FF is a single byte of that value.

Try it online! - Limited to 2000 digits, I don't think the dev would appriciate ~1.5M of data coming through.

I took a while to search though the OEIS 'webcam', but I paused and looked at XKCD, where it mentioned the book "A Million Random Digits with 100,000 Normal Deviates". And what do you know, it's A002205. A pretty old entry too.

According to dieharder, a program for finding if a sequence of numbers is random, the sequence is pretty random, so I doubt there's going to be an algorithm to generate a given number. This makes it more of a Kolmogorov-complexity problem. Since every number is between 0 and 9 inclusive, then there are Log2[10] bits of information in a digit, or 1,000,000 * Log2[10]/Log2[256] bytes of information total, or just a tad under 415,242 bytes.

My final solution was to take the entire 1,000,000 digit number in as a number (big-int in other languages), convert it to base 127, and then put it in the range 1-127. 1,000,000 * Log2[10]/Log2[127] = 475,330 bytes. Character 13 is the Carriage Return, which is converted to a Line Feed on most systems, so it's replaced with the trigraph :3:, since all the digraphs are taken. Mathematica was surprisingly happy to convert a 1 million digit number to base 127. The answer can be optimized, since TIO allows the entire 127+ unicode space, but using this method the results would only reduce the score by 1%.

Here is the encoder I used, where str is a string containing all the digits:

StringReplace[FromCharacterCode[IntegerDigits[FromDigits[str],127]+1],{"\\"->"\\\\","\""->"\\\"",FromCharacterCode[13]->":3:"}]

BZIP2 can compress the data down to 431,122 bytes, which is pretty close, but I felt just BZipping the data and calling it an answer was a bit cheap since it's not a 'language', as much as those answers have been fun on other questions.

\$\endgroup\$

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.