Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

9,73,241,561,1081,1849,_?_

algebra.com

Post reply on HN
Print view View original

81–90 of 91 posts

Re: 9,73,241,561,1081,1849,_?_

#81

Post by jacobolus »

req2 wrote: post #79
jacobolus wrote: post #74

Earlier quoted context omitted.

How does that work? Like this? That's not really following the "pattern" though, which is to keep adding 1 down the left edge of the triangle. Choosing to put a 0 in because we ran out of terms in our series is pretty arbitrary. 1 2 4 8 16 31 1 2 4 8 15 1 2 4 7 1 2 3 1 1 0

Difference tables don't operate on a "pattern"- they simply take the difference of the two terms above.

No, but the point is that using a difference table to find the "next term" in a sequence is rather stupid if the difference table doesn't terminate until you run out of terms.... the implication of that is that you have a sequence which cannot actually be fully described via that difference table.

Re: 9,73,241,561,1081,1849,_?_

#82

Post by jacobolus »

tkahn6 wrote: post #30

Can anyone explain why it takes so long to find the equation differentially? I understand that is subjective, but the 'constants' are only constant from y''' to y''. From y'' to y' the 'constant' is linear (meaning you have to solve for change in y' - y) and the 'constant' is quadratic from y' to y. Basically you can't just integrate each DE and solve for a constant C by finding the value of the lower order DE where…

This is just a sequence being modeled by a polynomial. The point of a "difference table" is that when you take enough levels of differences (if you like you can think of these as analogous in some way to derivatives, insofar as each step of grabbing differences reduces the order of a polynomial sequence by one power, but it's not really necessary), you eventually get down to a constant, from which you can work backwards to figure out what the patterns in higher-up differences are.

Re: 9,73,241,561,1081,1849,_?_

#85

Post by SandB0x »

jonsen wrote: post #37
JoeAltmaier wrote: post #5

I discovered difference tables as a kid, didn't know they were used much, I was modelling motion on a 2D display (an oscilloscope hooked to a P2P11!). Was a lifesaver for quick polynomial evolution - uses only addition, execution time scales linearly with the order of the polynomial. So, how do you go from the difference table "coefficients" to the polynomial?

Integrate the constant 48 back to the series level: 48 -> 48x -> 24x^2 -> 8x^3 Subtract 8x^3 from the series 9 - 8•1^3, 73 - 8•2^3, 241 - 8•3^3 and repeat the whole process on this series for the coefficient of x^2, etc...

Exactly. The other perspective: When you see 'difference', think 'derivative' .

Approximately, what the difference table is doing is differentiating until the leading term is constant. If we end up with a constant k levels down, we must have had a.x^k in the polynomial, as the derivative of a.x^k = ak.x^(k-1). Repeating this k times gives constant = a.k!

So the leading coefficient of the polynomial, a = constant/k!

I guess the next step is to subtract the values generated by this term from the sequence, then repeat to find the next term in the polynomial...

Re: 9,73,241,561,1081,1849,_?_

#86

Post by hurt »

fsniper wrote: post #4

I hit my head to wall after reading this. Difference table is a really cool way to solve this kind of questions. I thought "how come I have never learned this difference table before". I could make better points with IQ tests with difference tables :)

I've also never heard of difference tables before, what a cool little technique!

Re: 9,73,241,561,1081,1849,_?_

#87

Post by pvandehaar »

moron4hire wrote: post #24

Not to be too harsh here, but... I've been using "difference tables" (without calling it that) since I was 10 years old. I don't mean this to be bragging at all, because I didn't think (and still don't think) it was at all remarkable. It's just a basic method of analysis.

I home-schooled myself for a year and stumbled upon them, and decided to call them "differentials" because I had heard that term before. It's also possible I was had been sitting too close to my brother while he was studying them and had forgotten about it for a time.

Re: 9,73,241,561,1081,1849,_?_

#88

Post by tkahn6 »

jacobolus wrote: post #82
tkahn6 wrote: post #30

Can anyone explain why it takes so long to find the equation differentially? I understand that is subjective, but the 'constants' are only constant from y''' to y''. From y'' to y' the 'constant' is linear (meaning you have to solve for change in y' - y) and the 'constant' is quadratic from y' to y. Basically you can't just integrate each DE and solve for a constant C by finding the value of the lower order DE where…

This is just a sequence being modeled by a polynomial. The point of a "difference table" is that when you take enough levels of differences (if you like you can think of these as analogous in some way to derivatives, insofar as each step of grabbing differences reduces the order of a polynomial sequence by one power, but it's not really necessary), you eventually get down to a constant, from which you can work backwa…

I'm aware difference tables can be used to find the final term in the sequence - it's what I did to find the answer.

I was using differential equations to find the equation that describes the sequence and I was wondering why the constant that you get when you integrate a function isn't actually a constant after the second integration.

Re: 9,73,241,561,1081,1849,_?_

#89

Post by eru »

jey wrote: post #69
eru wrote: post #67

Earlier quoted context omitted.

It's only difficult in general. Nobody says there aren't any easy instances.

Sure, there's a bunch of trivial/easy ones for programs that do almost nothing, but I really wonder if are there any interesting programs for which tight bounds are known?

Look at primitive recursive functions.

E.g. see http://en.wikipedia.org/wiki/Primitive_recursive_function

Re: 9,73,241,561,1081,1849,_?_

#90

Post by jey »

eru wrote: post #89
jey wrote: post #69

Earlier quoted context omitted.

Sure, there's a bunch of trivial/easy ones for programs that do almost nothing, but I really wonder if are there any interesting programs for which tight bounds are known?

Look at primitive recursive functions. E.g. see http://en.wikipedia.org/wiki/Primitive_recursive_function

Even if we limit it to primitive recursive functions, how can we put a bound on the Kolmogorov complexity of one? We'd need some way of coming up with bounds on the smallest Turing machine to compute that function.
Post reply on HN