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

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

#41

Post by wizard_2 » Thu, Nov 05, 2009, 7:43 PM UTC

markerdmann wrote: post #25

perone wrote: post #2

http://www.wolframalpha.com/input/?i=9%2C73%2C241%2C561%2C10...

Wolfram Alpha has been a bit of a disappointment in terms of natural language parsing, but it's hard not to be impressed by the way it handles mathematical inputs. Does anyone know if the natural language parsing is showing improvement, or does it still choke on most inputs?

I'm quite impressed with the differences table.

    9 |  | 73 |  | 241 |  | 561 |  | 1081 |  | 1849
      | 64 |  | 168 |  | 320 |  | 520 |  | 768 | 
      |  | 104 |  | 152 |  | 200 |  | 248 |  | 
      |  |  | 48 |  | 48 |  | 48 |  |  |

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

#42

Post by pfarrell » Thu, Nov 05, 2009, 7:44 PM UTC

I learned about difference tables in Conway and Guy's great book "The Book of Numbers". I wish the book had been available when I was an undergrad. It describes everything I loved in math that I wasn't able to pinpoint. There are so many little gems in it, I've spent months reading it halfway through and then starting over to pick up what I missed. Highly recommended. http://www.amazon.com/Book-Numbers-John-H-Conway/dp/03879799...

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

#43

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

wizard_2 wrote: post #41

markerdmann wrote: post #25

Earlier quoted context omitted.

Wolfram Alpha has been a bit of a disappointment in terms of natural language parsing, but it's hard not to be impressed by the way it handles mathematical inputs. Does anyone know if the natural language parsing is showing improvement, or does it still choke on most inputs?

I'm quite impressed with the differences table. 9 | | 73 | | 241 | | 561 | | 1081 | | 1849 | 64 | | 168 | | 320 | | 520 | | 768 | | | 104 | | 152 | | 200 | | 248 | | | | | 48 | | 48 | | 48 | | |

[deleted]

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

#44

Post by jcl » Thu, Nov 05, 2009, 8:10 PM UTC

bdr wrote: post #22

amichail wrote: post #15

Earlier quoted context omitted.

How will you prove that your answer is correct?

Well, that could be done by brute force. Realistically, though, it's more about whether anyone can beat your answer.

I don't know why you're being modded down.

To elaborate: You can define "simplest program", for instance, as "shortest string consisting of [0-9], plus, minus, times, parentheses, and the symbol 'n' that when evaluated as a mathematical expression yields the given sequence for n=1, 2, 3...". You can then find a suitable string, like "((8 * n + 4) * n - 4) * n + 1", and do an exhaustive search of shorter strings to show that no better string exists. That would be 16^16, or less than a year on a computer that can knock off a trillion strings per second -- less if you use logic to constrain the search space.

However, realistically, a person asking such a question is merely looking for a "good" solution, not necessarily a proven-optimal one, as there may be multiple reasonable explanations for a given sequence. Rather, the value of the "simplest program" criteria is that it allows you to compare proposed solutions. So, yes, for any given number, there is a formula to make it next in the sequence. But by applying the "simplest program" criteria, we see that some formulas -- and hence some values -- are better than others.

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

#45

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

wizard_2 wrote: post #41

markerdmann wrote: post #25

Earlier quoted context omitted.

Wolfram Alpha has been a bit of a disappointment in terms of natural language parsing, but it's hard not to be impressed by the way it handles mathematical inputs. Does anyone know if the natural language parsing is showing improvement, or does it still choke on most inputs?

I'm quite impressed with the differences table. 9 | | 73 | | 241 | | 561 | | 1081 | | 1849 | 64 | | 168 | | 320 | | 520 | | 768 | | | 104 | | 152 | | 200 | | 248 | | | | | 48 | | 48 | | 48 | | |

[deleted]

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

#46

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

amichail wrote: post #11

This question is not well-defined. Any number can be a solution.

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

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

#47

Post by l0nwlf » Thu, Nov 05, 2009, 8:23 PM UTC

Difference table only works in case of arithmetico-geometric series or polynomial series. It fails in other sequences like fibonacci,prime etc. However if given a sequence I always try difference table first as there are high chances that it'll be cracked.

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

#48

Post by amichail » Thu, Nov 05, 2009, 8:24 PM UTC

scott_s wrote: post #46

amichail wrote: post #11

This question is not well-defined. Any number can be a solution.

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)

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

#49

Post by roundsquare » Thu, Nov 05, 2009, 8:24 PM UTC

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

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 now you know you need at most a 5th degree polynomial.

So, you have y = a_0 + a_1 * x + a_2 * x^2 + ... + a_5 * x^5

Plug in each value of x and you get 6 equations with 6 unknowns. Solve for a_0, ..., a_5.

Bunch of the a's might well be 0, but thats ok.

Edit: This only works if your difference table eventually reduces to a set of differences which are all the same (e.g here 48, 48, 48). Otherwise, the answer is not a polynomial.

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

#50

Post by alain94040 » Thu, Nov 05, 2009, 8:25 PM UTC

bdr wrote: post #14

amichail wrote: post #11

This question is not well-defined. Any number can be a solution.

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?