9,73,241,561,1081,1849,_?_ | Hacker News Reader

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

algebra.com

124 pointsseven84 comments

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 |  |  |

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).

This answer is also correct in another way :)

http://threesixty360.wordpress.com/2008/04/30/1-2-4-8-what-c...

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.

I read the title here which has no spaces between the numbers (a real pet peeve :P) then went on to read the explanation of "Edwin's" attempts to solve the blank. Except without the spaces, I thought he was trying to find the remaining digits of a single number (with commas for thousands separator).

(before clicking the link, I was expecting "find the remaining digits to make this number a prime" or something)

Nice link though!

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?

It's a bit non-trivial, but mechanically solvable. Polynomial coefficients are for normal powers. Difference table coefficients have more to do with falling powers (x * (x-1) * (x-2) * ...). Look up "Finite Calculus" or "Difference Equations" if you are interested.

I'm not sure if this is your question, but divided differences are a way to do polynomial interpolation, with efficient updating to account for new data points: http://en.wikipedia.org/wiki/Newton_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...

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

From which you can get

104 <-- Note: this needs to be given!

152

200

248

And work your way back to

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.

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!

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 never been particularly good (or confident?) at math, but this actually piqued my interest, it's a very cool trick/technique. Maybe I should enroll in a math class at the local community college just to try to improve myself a little bit. Besides, I have so many more ways to actually apply what I'd be learning now then I did when I took my last math class (which I think was back when I was 16 or 17).

You'll probably get farther with self-study. I suggest picking a field or two (discrete mathematics, number theory, graph theory, topology, and abstract algebra are probably the most useful and accessible ones to you right now) and then meeting with a professor a few times a month to go over homework problems.

Doing it that way will prepare you to teach yourself the material, giving you the confidence you claim you don't yet have.

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

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.

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...

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?

How will you prove that your answer is correct?

occam's razor

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.

You'd have to determine if a program halts. Unless you restrict to non-Turing-complete language, this is undecidable.

I can decide if some programs halt. (Just not for all.)

You can simply modify your definition of "simplest" to be "shortest that completes in a million steps" or some such. A program that takes so long to finish that you're not sure it will return your desired value is probably not the simplest.

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.

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

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.

That might be possible. Primitive recursion is much less powerful than Turing machines.

The simplest program that outputs these numbers is the program that outputs these numbers, so it doesn't output anything next.

  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 ;)

Define "simplest program"?

The shortest program in a low-level language. On the definition of a low-level language, see: http://www.paul-almond.com/WhatIsALowLevelLanguage.htm

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?

Sorry, the APL program is only 26 characters:

  +/1 ¯4 4 8×[2](⍳9)∘.*¯1+⍳4

And outputs:

  9 73 241 561 1081 1849 2913 4321 6121

This question is not well-defined.

It's defined just well enough to identify you as someone who'd rather debate the problem than attack it. In other words, it has done its job.

Is it defined well enough to allow you to draw that kind of conclusions without any context?

What if that question was meant to find people who think about what is the real goal and asking "are we thinking about the same thing, or should we agree on more details" instead of attacking the problem at hand. Otherwise "0" is a perfectly good answer (for any reason).

This discussion has as much sense as a typical IQ test... (~nil)

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."

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?

The explanation was clear what kind of functions are allowed: http://en.wikipedia.org/wiki/Elementary_function_%28differen...

Again, reasonable people. If we had to precisely define every question and interaction, we would never get anything done. Instead we rely on shared assumptions and clarify only when actual confusion occurs. (Yours is not an actual confusion.)

There's no reason to not allow arbitrary programs.

Moreover, even if we agree to use a certain form of closed expression, you will still need to define how we measure the size of such an expression and you will need to find a way to prove that an answer has the smallest possible expression size.

Sure there's a reason: someone said so.

I also said nothing about "smallest possible expression size."

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.

Same here. We learned of them in 4th grade, in Sweden.

Learned them in 5th grade "wings" class in Minnesota.

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.

http://www2.research.att.com/~njas/sequences/

This is a great resource for finding information on integer sequences significant in combinatorics and other formal math topics. It didn't have the solution to this particular sequence, because, afaik there is nothing particularly interesting about it.

Also of note is their Superseeker computer -- email it your sequence and it will perform a lot of additional analyses on the sequence beyond the normal web interface.

http://www2.research.att.com/~njas/sequences/ol.html

You can see a discussion about difference tables here: http://www.physicsforums.com/showthread.php?t=114995

Was surprised to see this happen:

http://www.wolframalpha.com/input/?i=0%2C1%2C2%2C4%2C8%2C16%...

Why start with 0?

1,2,4,8 works fine. http://www.wolframalpha.com/input/?i=1%2C2%2C4%2C8%2C16%2C32...

0, ...

Works properly if you take out the 0 term: http://www.wolframalpha.com/input/?i=1,2,4,8,16,32,64,128,25...

This works with 0: http://www.wolframalpha.com/input/?i=0,1,2,4,8,16,32,64,128,...

Yes but in the recurrence relation, it said "for all n >= 1". I guess the additional term was the tipping point that let mathematica infer that the meat of the sequence was for n >= 1.

Agreed, don't start with zero for that. There's no real number n such that 2^n = 0, so the the closed-form expression you were seeking won't be found that way.

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.

This method of computing successive terms of a polynomial actually has an interesting place in the history of computers; the basic principle is the same as that used by Charles Babbage's difference engine.

Wikipedia article on the difference engine: http://en.wikipedia.org/wiki/Difference_engine

Just for fun, a difference engine built with Legos: http://acarol.woz.org/

The series 9,73,241,561,..corresponds to:

2^3+1^2; 4^3+3^2; 6^3+5^2; 8^3+7^2; 10^3+9^2; 12^3+11^2; ?

Soln: 14^3+13^2 = 2913

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

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

Is there interest in people posting neat math puzzles on HN more frequently? There's a few I really like and I would love to see what puzzles others have.

oleis turns up nothing, sadly

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 x=1 and finding the difference. Why not?

I'm in Calc BC in high school so this could be a stupid question.

Huh? What DE?

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.

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.

why is this at the top?

because it is interesting.

Please don't post your homework to the list.

Reply on news.ycombinator.com