9,73,241,561,1081,1849,_?_ • Hacker News Board

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

#51

Post by JoeAltmaier » Thu, Nov 05, 2009, 8:45 PM UTC

roundsquare wrote: post #49

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?

Other people have given calculus answers... here is one that doesn't require calculus. Its very tedious, but fairly simple to understand. Give your DT "coefficients" work your way back to the solution. I.e. in this case: you start with 48 48 48 From which you can get 104 152 200 248 And work your way back to 9 73 241 561 1081 1849 So you know you want a polynomial P(x)such that P(1) = 9 p(2) = 73 ... p(3) = 1849 So n…

The order of the polynomial is equal to the number of difference steps until a constant is reached. It MAY be as long as the number of samples in the series. So difference tables are also a handy way to determine the order of a series!

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

#52

Post by scott_s » Thu, Nov 05, 2009, 8:55 PM UTC

amichail wrote: post #48

scott_s wrote: post #46

Earlier quoted context omitted.

Reasonable people understand that we're looking for a closed-form solution that can generate these numbers.

You would still need to define precisely what you mean by a closed-form solution and this definition needs to be part of the question. But even then you would be faced with the difficult task of proving that your answer is correct. This kind of ill-defined question might be a fun diversion but it should never be used for any serious purpose (e.g. in any test/assighnment that matters)

Luckily, mathematicians have already done this for me: http://en.wikipedia.org/wiki/Closed-form_solution

Note, that I said "reasonable people." Reasonable people know what is being asked. If, for example, I asked someone how much they weigh, they are not going to respond "I don't know. I weighed myself five minutes ago, but I must have a different weight right now."

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

#53

Post by [deleted] » Thu, Nov 05, 2009, 8:57 PM UTC

alain94040 wrote: post #50

bdr wrote: post #14

Earlier quoted context omitted.

Here's one interpretation: What will the simplest program that outputs these numbers output next?

print "9,73,241,561,1081,1849,0". So 0 is the answer. Actually, any digit, so I don't waste one extra character in my program. Did I win?

[deleted]

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

#54

Post by jey » Thu, Nov 05, 2009, 8:59 PM UTC

amichail wrote: post #31

duh wrote: post #28

Earlier quoted context omitted.

You can only prove that the answer is incorrect.

Why would you think that?

It only takes a counter-example (an example of a shorter program) to show that an answer is incorrect, but you could probably pick up a Turing Award or two if you find a way to put a tight bound on the Kolmogorov complexity of a bit string.

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

#55

Post by ivankirigin » Thu, Nov 05, 2009, 9:10 PM UTC

chaosprophet wrote: post #39

ivankirigin wrote: post #38

Earlier quoted context omitted.

python -c 'print 9,73,241,561,1081,1849 # or better yet echo 9,73,241,561,1081,1849

You forgot the 'output next', bit of the question ;)

You forgot to read the parent comment ;)

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

#56

Post by ajscherer » Thu, Nov 05, 2009, 9:14 PM UTC

redorb wrote: post #40

I loaded into excel, then copy and dragged down to see what excel would say is the next 2 answers ... I got the following ...1081,1849,[1890.067],[2248.467].... Now I just wonder how excel got these answers :/

Drag down a few more cells and use a difference table on the resulting sequence.

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

#57

Post by leif » Thu, Nov 05, 2009, 9:16 PM UTC

oleis turns up nothing, sadly

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

#58

Post by bd » Thu, Nov 05, 2009, 9:22 PM UTC

If somebody wants to try this method on different sequences, I made a simple solver in JavaScript:

http://alteredqualia.com/visualization/hn/sequence/

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

#59

Post by amichail » Thu, Nov 05, 2009, 9:27 PM UTC

scott_s wrote: post #52

amichail wrote: post #48

Earlier quoted context omitted.

You would still need to define precisely what you mean by a closed-form solution and this definition needs to be part of the question. But even then you would be faced with the difficult task of proving that your answer is correct. This kind of ill-defined question might be a fun diversion but it should never be used for any serious purpose (e.g. in any test/assighnment that matters)

Luckily, mathematicians have already done this for me: http://en.wikipedia.org/wiki/Closed-form_solution Note, that I said "reasonable people." Reasonable people know what is being asked. If, for example, I asked someone how much they weigh, they are not going to respond "I don't know. I weighed myself five minutes ago, but I must have a different weight right now."

Which functions do you allow in closed-form solutions?

Do you allow Turing-completeness? If not, why not?

What exactly is the measure used to determine the size of a solution?

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

#60

Post by osteele » Thu, Nov 05, 2009, 9:29 PM UTC

The wonderful (satirical, but mathematically sophisticated) book Mathematics Made Difficult introduces difference tables, and uses them to demonstrate how to compute the next number in the sequence [1,2,4,8,16,…] – that number being, of course, 31.

This answer is correct in that it is the next item in the lowest-order polynomial that generates the first five terms. This reveals both the strength and weakness of difference tables (and the flavor of Mathematics Made Difficult).