Hacker News Reader

Comment by scarmig | Hacker News Reader

Remotely related: I've been interested for awhile in how the same initial terms of a sequence could possibly be generated by multiple rules.

For example, you might have

2,3...

And the rest of the sequence might look like either

2,3,4,5,6...

2,3,5,8,13...

2,3,5,7,11...

or even

2,3,5,10,20...

Clearly, on some level those sequences are all much less complicated than one defined as "The first term is 2, the second term is 3, the third term is 919243, the fourth term is -1234..."

It's unclear to me how one might rank them in complexity, though. The maximum amount of memory necessary to get an arbitrary nth term? The number of operations necessary to get to the next term?

Another interesting question to me: if there is an ordering of ways to generate a sequence of numbers, given the first couple terms of a sequence of numbers, what are the simplest N ways to generate the full sequence?

View on HN

Fun fact: Mathemetica has a method FindSequenceFunction which does exactly what you describe. In my experience, however, it generally requires at least 4 terms.

I'm not totally sure how the math behind it works (maybe it's similar to Eureqa?) but the results speak for themselves and are rather incredible.

For example, if I run FindSequenceFunction on this input:

    {0, 1, 3, 8, 19, 43, 94, 201, 423, 880}

Which is the number of 0,1 sequences of length n that contain two adjacent 1s

Mathematica produces the result:

    1/10 (5 2^(1 + x) - 5 (1/2 - Sqrt[5]/2)^x + 
    3 Sqrt[5] (1/2 - Sqrt[5]/2)^x - 5 (1/2 + Sqrt[5]/2)^x - 
    3 Sqrt[5] (1/2 + Sqrt[5]/2)^x)

Which, astonishingly, is correct for all the values I've tried. So apparently Mathematica understands more about this sequence than I do, and I know its definition.

Another party trick is to use the input

    {-(1/6), 2/15, -(13/140), 23/315, -(83/1386), 305/6006, -(2269/
     51480), 4259/109395, -(16103/461890), 30616/969969}

Which is the integral x^n (1 - 2 x)^n for x from 0 to 1, for n = 0..<10. Here it seems 10 numbers are required. This yields the solution

    (2^(-2 - 3 x)
    x! (Sqrt[\[Pi]] (1 + x)! + 
    3 (-1)^x 2^(
    2 + 3 x) (1/2 (1 + 2 x))! Hypergeometric2F1[1, 3/2 + x, 
    2 + x, -8]))/((1/2 + x)! (1 + x)!)

Which as far as I can tell, is a closed-form solution (!) to the integral. A solution it worked out to an integral it has never seen, but only the first 10 elements in the sequence.

So it's safe to say Mathematica knows a lot more about math than I do.

For this purpose mathematicians use OEIS (oeis.org). Check it out.

Which is the number of 0,1 sequences of length n that contain two adjacent 1s

It sounds a lot simpler than that. There are n-1 places to put the adjacent 1s. For each of those, there are 2^(n-2) ways to complete the sequence with 0s and 1s. So the answer should be (n-1)*2^(n-2).

Edit: it isn't quite that simple, I'm counting sequences with multiple pairs of 1s multiple times.

By the way, Mathematica's formula looks a lot like the closed form for the Fibonacci sequence.

OK, got it.

Let a_n be the number of sequences of 0s and 1s of length n, that do not contain a pair of 1s, and end in 0. Let b_n be similar, except that the sequences end in 1. These satisfy the recurrences a_{n+1} = a_n + b_n, and b_{n+1} = a_n. It follows that a_n satisfies the Fibonacci recurrence a_{n+1} = a_n + a_{n-1}. Starting from a_1 = 1, and a_2 = 2, we have a_n = F_{n+1}.

The total number of sequences of length n is 2^n, so the number we want is 2^n - a_n - b_n = 2^n - F_{n+1} - F_n = 2^n - F_{n+2}.

And this time it works :-). There might be a point about confirmation bias here, in that the trick is to count sequences that _don't_ contain a pair of 1s.

One drawback of Mathematica is that it has a very poor idea of the formulae that human readers will regard as simple.

How about this?

Choose a programming language. Choose a sequence prefix (in your example: 2, 3). Then consider all the programs that accept n as input and output a sequence of n numbers, such that the first numbers are always 2, 3. Now take the shortest of those programs. The sequence it produces is the "simplest".

If this sounds tedious to code, you could easily outsource via Odesk or something.

You are asking for https://en.wikipedia.org/wiki/Kolmogorov_complexity

It's uncomputable in general.

I know. :-)

Take a look at Kolmogorov complexity. It's uncomputable.

I think you might enjoy the book Fluid Concepts and Creative Analogies, by Douglas Hofstadter [1]. The first chapter is on (what Hofstadter argues is) the fundamental nature of recognizing patterns in number sequences.

[1] http://www.amazon.com/Fluid-Concepts-And-Creative-Analogies/...

This might be helpful: https://en.wikipedia.org/wiki/Generating_function

Generating functions provide a general framework for describing sequences, solving recurrence relations, etc.

Reply on news.ycombinator.com